感知机(Perceptron)

1 简介

感知机是一种简单的，用于二分类的模型。它的构建思想，就是使用一个超平面将数据分为正负两类，输出$+1$或者$-1$。感知机可以使用梯度下降的方法进行最优化，但是其优化算法只在数据线性可分的时候收敛。感知机是Rosenblatt在1957年提出的。

2 模型的构建

由上述构建思想可知，感知机要将一个特征空间为$X \subseteq R^n$的数据映射到输出空间$Y=\{+1,-1\}$。使用$x\in X$表示训练数据的特征向量，$y\in Y$表示输出的值。之前提到过，感知机使用超平面来区分正类和负类，那么就可以先把超平面的方程写出来。

$$w\cdot x +b=0$$

其中$w$称为权重向量。因为$w$和$x$点乘，实际上是和输入数据的特征进行加权求和。然后，我们需要把超平面计算的结果映射到0和1，感知机选择的是$sgn$函数。所以，感知机模型的数学表达式为

$$f(x) = sgn(w\cdot x+b)$$

它的参数是权重向量$w$和常量$b$。对应到超平面上，$w$就是超平面的法向量，$b$是超平面的截距。

3 感知机的学习策略

为了对感知机进行参数最优化，我们需要找到它的损失函数。很容易想到损失函数可以用分类错误的点数来衡量，但是错误的个数是离散的，这个函数不可微分，所以用不了梯度下降。所以考虑错误分类点到超平面S的总距离，一个点到超平面的计算方法是

$$\frac{1}{||w||}|w\cdot x_0+b|$$

其中$||w||$ 是$w$的$L_2$范数。

如果分析感知机错误分类的时候的两种情况，也就是正样本负判，负样本正判。对于第一种，$w\cdot x_i+b >0$的时候，感知机本应该输出1，但错误分类时输出-1，所以$-(w\cdot x_i+b)y_i>0$，对于第二种，$w\cdot x_i+b <0$的时候，感知机本应该输出-1，但错误分类时输出$1$，所以$-(w\cdot x_i+b)y_i>0$，所以，如果感知机错误分类一个数据，总有

$$-y_i(w\cdot x_i+b)>0$$

因此，拿掉距离计算公式里面的绝对值，可以得到新的距离计算公式

$$-\frac{1}{||w||}y_i(w\cdot x_i+b)$$

于是，我们对所有点到超平面的距离求和，得到总距离的计算公式

$$-\frac{1}{||w||}\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

现在不考虑权重的$L_2$范数，那么感知机的损失函数就是

$$L(w,b) = -\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

这个函数意味着，如果错误分类的越少，错误分类的点离超平面越近，那么损失函数就越小。

4 最优化

感知机的最优化问题就是求解损失函数最小时的参数$w$和$b$。

$$\min_{w,b}L(w,b) = -\sum_{x_i\in M}y_i(w\cdot x_i+b)$$

那么，采用随机梯度下降法进行优化。首先随机一个$w_0$和$b_0$，接下来求梯度。

对于法向量$w$。

$$\nabla_w L(w,b) = -\sum_{x_i\in M}y_ix_i$$

对于截距$b$

$$\nabla_b L(w,b) = -\sum_{x_i\in M}y_i$$

于是，如果随机选取一个错误分类的数据，更新的方法就是

$$\begin{cases} w^* = w-(-\eta y_ix_i)=w+\eta y_ix_i \\ b^* = b-(-\eta y_i) = b+\eta y_i \end{cases}$$

其中$\eta$就是学习率。

所以，适用于编程实现的算法应该是

1. 随机一个$w_0$, $b_0$
2. 在训练集中选取一个数据$(x_i, y_i)$
3. 如果$y_i(w\cdot x_i+b)\leq 0$
4. 使用更新方法更新参数
5. 循环到第二部，直到感知机不会产生错误分类的数据。

至此，感知机的构建，学习策略和最优化算法阐述完毕。