感知机模型原理（二）

３. 感知机算法的原始形式

在之前我们提到过感知机模型的损失函数为 $L(w,b)=-\sum_{x_i\in M}y_i(wx_i+b)$ , 感知机的算法本质上就是求解损失函数最优的过程, 可以采用梯度下降法和拟牛顿法进行求解, 其中最常用的是梯度下降法．

首先, 任选一个超平面, 然后通过梯度下降法不断地极小化损失函数．需要注意的是，在极小化过程中不是一次性选择所有误分类点进行梯度下降，而是随机地选取一个误分类点进行梯度下降，也就是说，这里采用的是梯度下降法中的随机梯度下降．

根据梯度的定义，我们可以得到损失函数的梯度:
$\begin{cases} ▽_wL(w,b)=-\sum_{x_i\in M}y_ix_i \\ ▽_bL(w,b)=-\sum_{x_i\in M}y_i \end{cases}$
假设随机选择一个误分类点 $(x_i,y_i)$ , 对ｗ,b进行更新:
$\begin{cases}w←w+\eta y_ix_i \\ b←b+\eta y_i\end{cases}$
其中， $\eta$ 为学习效率，有时也称为步长．通过反复的迭代使得损失函数的数值不断的减小，直到０为止．

上述的算法是感知机模型的基本算法，也称为原始形式，其具体的过程可以解释为：当一个实例点被误分类(即位于分类错误的一侧)时，调整ｗ,ｂ的值，使得分类超平面向该误分类点的一侧移动，目的是减少该误分类点到超平面间的距离，直至超平面越过该误分类点使其能够被正确分类．

不同的初始值以及选取不同的误分类点，可能会导致不同的感知机模型．也就是说感知机模型的结果不唯一．

４.感知机算法的收敛性

当训练数据集线性可分时，那么感知机算法的原始形式迭代是收敛的．也就是说，经过有限次迭代可以得到一个将训练数据集完全正确划分的超平面及感知机模型．反之，当训练数据集线性不可分时，感知机学习算法不收敛．

5.感知机算法的对偶形式

对偶形式的基本思想是：将ｗ和ｂ表示维实例 $x_i$ 和分类标记 $y_i$ 的线性组合的形式，然后通过求解其系数而求得ｗ和ｂ．

假设第i个实例点 $(x_i,y_i)$ 由于误分类而进行更新的次数为 $n_i$ , 从学习过程中不难得到ｗ,b的表示：
$\begin{cases} w=\sum_{i=1}^N n_i\eta y_ix_i \\ b=\sum_{i=1}^N n_i\eta y_i \end{cases}$
将上式中的ｗ,b分别代入感知机模型后，可以发现结果与ｗ,ｂ无关, 而与 $n_i$ 有关．另外, 实例点更新的次数越多(即 $n_i$ 值越大)，意味着它距离超平面越近，也就经常被误分类．

通过以上，也可以看出对偶形式是基于原始形式推导得到的，而且对偶形式中的训练实例仅以内积的形式出现，通常会预先将训练集中实例间的内积计算出来并以矩阵(即Gram矩阵)的形式存储，这样可以优化计算速度．

参考：
李航博士著《统计学习方法》

最后编辑于：2019.02.17 19:23:49