1、感知机算法简述

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

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

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

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

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

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

其中称为学习率。

感知机算法流程如下：

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

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

2、感知机算法收敛性证明

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

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

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

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

证明：

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

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