感知机算法（Perceptron Learning Algori

作者: 格物致知Lee | 来源:发表于2019-02-14 11:47 被阅读0次

感知机（perceptron）是二类分类的线性分类模型，它的思想很简单，就是在一个二维空间中寻找一条直线将红点和蓝点分开（图1），类比到高维空间中，感知机模型尝试寻找一个超平面，将所有二元类别分开（图2）。

图1：二维空间

图2：三维空间

如果我们找不到这么一条直线的话怎么办？找不到的话那就意味着类别线性不可分（图3），也就意味着感知机模型不适合你的数据的分类。使用感知机一个最大的前提，就是数据是线性可分的。

图3：不可分数据

1.感知机模型

如果我们有n个样本，每个样本有m维特征和一个二元输出类别：

$((x_{1}^0，x_{2}^0...x_{m-1}^0,x_{m}^0,y_{0} ),(x_{1}^1，x_{2}^1...x_{m-1}^1,x_{m}^1,y_{1} ),....(x_{1}^n，x_{2}^n...x_{m-1}^n,x_{m}^n,y_{n} ))$

感知机的目标是找到一个超平面：

$\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b = 0$

让其中一个类别的样本满足 $\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b > 0$ ,而另一类样本满足

$\omega _{1} x_{1} +\omega _{2} x_{2} +...+\omega _{m} x_{m} + b < 0$ ，从而样本线性可分。但这样的超平面并不是唯一的，感知机模型采取不同的初始值（ $\vec{\omega }_{0} ，b_{0}$ ）解可能会不同。

我们用相量方式对上式进行表达： $\vec{\omega} \bullet \vec{x} + b = 0$ ，由此感知机的模型可以定义为：

$y = sign( \vec{\omega} \bullet \vec{x} +b)$ ,其中：

例如：将一个新的样本 $\vec{x1}$ 带入训练好的模型 $\vec{\omega} \bullet \vec{x} + b$ ，当 $\vec{\omega} \bullet \vec{x1} + b \geq 0$ ， $\vec{x1}$ 被分为 $+1$ 类。当 $\vec{\omega} \bullet \vec{x1} + b < 0$ ， $\vec{x1}$ 被分为 $-1$ 类。

2.感知机模型的损失函数（Loss Function）

我们将满足 $\vec{\omega} \bullet \vec{x} + b \geq 0$ 的样本类别输出值取 $+1$ ，满足 $\vec{\omega} \bullet \vec{x} + b < 0$ 的样本类别输出值取 $-1$ 。从而正确分类的样本满足 $y（ \vec{\omega} \bullet \vec{x} + b）> 0$ ，而错误分类的样本满足 $y（ \vec{\omega} \bullet \vec{x} + b）< 0$ 。损失函数的优化目标是使所有被错误分类的样本到超平面的距离之和最小。

一个被错误分类的样本 $i$ ， $y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）< 0$ ，到超平面的距离是 $-y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）/\vert \vert \vec{\omega } \vert \vert _{2}$ ，

其中 $\vert \vert \vec{\omega } \vert \vert _{2} = \sqrt{\sum_{i=1}^m\omega _{i}^2 }$ 。 $\vec{\omega }$ 为超平面的法向量， $\vec{\omega }$ 的大小变化并不会影响样本点到超平面的距离。我们令 $\vert \vert \vec{\omega } \vert \vert _{2} = 1$ ，并且假设所有错误分类的点的集合为M，则所有错误分类的样本到超平面的距离之和为：

$- \sum_{\vec{x_{i} } \in M}y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）$

最终构建的损失函数为：

$L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i} （ \vec{\omega} \bullet \vec{x_{i} } + b）$

3.感知机模型的优化方法

感知机模型选择的是采用随机梯度下降，这意味着我们每次仅仅需要使用一个误分类的点来更新梯度。损失函数 $L(\vec{\omega } ，b)$ 的梯度如下：

$∇_{\omega } L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i} \vec{x_{i}}$

$∇_{b} L(\vec{\omega } ，b) = - \sum_{\vec{x_{i}} \in M}y_{i}$

随机选取一个错误分类点 $(\vec{x_{i}} ,y_{i} )$ ，对 $\vec{\omega } ，b$ 进行更新：

$\vec{\omega } \leftarrow \vec{\omega _{0} } +\eta y_{i}\vec{x_{i}}$

$b \leftarrow b_{0} +\eta y_{i}$

式中 $\vec{\omega }_{0} ，b_{0}$ 为初始值， $\eta (0<\eta \leq 1)$ 是步长（learning rate）。通过这样迭代可以使损失函数 $L(\vec{\omega } ，b)$ 不断减小，直到为0。

感知机模型的优化方法可以通俗的解释为：当一个样本被错误分类，即位于分类超平面的错误一侧时，则调整 $\vec{\omega } ，b$ 的值，使分类超平面向该错误分类点的一侧移动，以减少该错误分类点与超平面间的距离，直至超平面越过该错误分类点，最终被正确分类。

4.感知机模型的优化方法的对偶形式

上一节的感知机模型的算法形式我们一般称为感知机模型的算法原始形式。对偶形式是对算法执行速度的优化。对偶形式的基本想法是将 $\vec{\omega } ，b$ 表示为样本 $\vec{x_{i} }$ 和标签 $y_{i}$ 的线性组合，通过求解其系数而求得 $\vec{\omega } ，b$ 。我们取初始值 $\vec{\omega }_{0} ，b_{0}$ 为 $0$ ，选取错误分类样本 $(\vec{x_{i}} ,y_{i} )$ 对 $\vec{\omega } ，b$ 进行更新有：

$\vec{\omega } \leftarrow\eta y_{i}\vec{x_{i}}$

$b \leftarrow \eta y_{i}$

假设为了将样本 $\vec{x_{i} }$ 正确分类而更新 $\vec{\omega } ，b$ 的次数为 $m_{i}$ ，每一个样本 $(\vec{x_{i}} ,y_{i} )$ 的 $m_{i}$ 的初始值为 $0$ ，每当次样本在某一次梯度下降迭代中因误分类而更新时， $m_{i}$ 的值 $+1$ ，则 $\vec{\omega } ，b$ 关于 $(\vec{x_{i}} ,y_{i} )$ 的增量分别为 $m_{i} \eta y_{i}\vec{x_{i}}$ 和 $m_{i} \eta y_{i}$ 。则用所有样本对 $\vec{\omega } ，b$ 进行更新，最后得到的 $\vec{\omega } ，b$ 可以表示为

$\vec{\omega } =\sum_{i=1}^nm_{i} \eta y_{i}\vec{x_{i}}$

$b =\sum_{i=1}^nm_{i} \eta y_{i}$

$m_{i}$ 的通俗解释：如果 $m_{i}$ 的值越大，那么意味着样本 $x_{i}$ 经常被误分。很明显离超平面很近的点，当超平面稍微移动一点点， $x_{i}$ 的类别就发生变化。

我们用 $y（ \vec{\omega} \bullet \vec{x} + b）< 0$ 的等价形式 $y(\sum_{i=1}^nm_{i} \eta y_{i}\vec{x_{i}} \bullet \vec{x} + \sum_{i=1}^nm_{i} \eta y_{i})< 0$ 来判断错误分类。上式中 $\vec{x_{i}} \bullet \vec{x}$ 表示的是两个样本的内积，而且这个内积的结果在更新 $\vec{\omega }$ 的过程中会多次使用。如果我们事先用矩阵运算计算出所有的样本之间的内积，那么在算法运行时，仅仅一次的矩阵内积运算比多次的循环计算省时。计算量最大的判断误分类这儿就省下了很多的时间，这也是对偶形式的感知机模型比原始形式优的原因。