算法的收敛性证明

1. 感知机算法及收敛性证明

感知机算法其实已经很熟悉了，这次看《统计学习方法》权当复习一遍，然后有一橘念个point对我来说是新的—— 感知机算法实际上采用了随机梯度下降 。这其实是一个很显然的点，但我之前看到的资料都是直接说明了超平面参数的更新方式，并从几何直观上解释了这样做是为了让超平面向误分样本点的方向旋转，而未从梯度的角度来解释，这里补充一下这个角度。

感知机（perceptron）是二分类线性分类模型，其输入空间（特征空间）是 ，输出空间是 ，前伍简由输入空间到输出空间的如下函数：

称为感知机。 和 分别是感知机的权值和偏置。

感知机的损失函数定义为 所有误分类点到超平面的距离慧裤之和 ，即：

其中 表示误分类点的集合，若 固定，则损失函数梯度为：

采用随机梯度下降法，每次随机选取一个误分类点 ，对 进行更新：

其中 称为学习率。

感知机算法流程如下：

（1）选取初值 。
（2）在训练集中选取数据 。
（3）如果 ,则更新参数：

（4）转至（2）直至训练集中无误分点。

所谓感知机算法的收敛性，就是说只要给定而分类问题是线性可分的，那么按上述感知机算法进行操作，在有限次迭代后一定可以找到一个可将样本完全分类正确的超平面。

首先，为了方便推导，我们将偏置 并入权重向量 ,记作 ，同样将输入向量加以扩充，记作 ，显然， 。

既然样本是线性可分的，我们可以假设有一个满足条件 的超平面 将样本点完全正确分开，且存在 ，对所有 ，有：

令 ，则感知机算法在训练集上误分类次数 满足：

证明：

结合上述两个结论，可以得到：

从而感知机算法的收敛性得证。