统计学习方法笔记（二）感知机

感知机于1957年由Rosenblatt提出，是一种线性分类模型，属于判别模型，直接学习判别函数，是神经网络和支持向量机的基础。

对于感知机的学习推导首先要知道他的模型是什么，然后是学习策略（损失函数），最后是学习算法。

1.    感知机的模型（假设空间）：

其中符号函数为：

2.     感知机的学习策略（损失函数）：

首先超平面为：

点到超平面的距离(几何间隔)为：

感知机的学习策略是误分类驱动的，当误分类的点的个数为零那么感知机的模型也就收敛了。

所以对于误分类的点有：

所以误分类的点到超平面的距离就可以表示为：

那么所有的被误分类的点到超平面的距离之和为：

其中M为被误分类点的集合。

由于感知机模型只是寻求一个超平面来将两类点分开，而不是像支持向量机那样需要找到一个最优的点，所以为了简单，去掉||w||来得到感知机的损失函数：

理论上，感知机的损失函数应该是误分类的点的个数的度量，但是由于它对于变量不是连续可导的，因此，实际中我们使用以上这个误分类点的距离之和来作为度量，此时L(w,x)对w和x是连续可导的。

3.     感知机的学习算法：

对于感知机的损失函数的优化，使用的是随机梯度下降的方法。对模型的求解变成了对目标函数的优化问题：

随机梯度下降法的梯度计算：

随机梯度下降算法每次从误分类的点中挑选一个点，所以权值和偏置的更新方式为：

其中是步长。这样通过不断的迭代最终能够实现损失函数为0.

学习算法流程为：

由于在计算的过程中选取不同的初值和不同的误分类点都会导致解的不同。但是由novikoff定理可以得到只要数据是线性可分的，最终，模型都是收敛的。且误分类的次数满足：

其中   

对偶形式的感知机学习算法：

为了更加的易于计算，提出了感知机学习算法的对偶形式。

因为  如果设置w和b的初始值都是0的话，那么最终的优化出来的w为： ,其中 ,如果步长为1，那么 则为第i个点被误分类的次数

因此，感知机对偶算法的模型为：

此时需要求出的变量变成了α和b

权值更新变成了:

对偶形式的训练样本都是以内积的形式出现的，因此可以预先计算出来并以矩阵的形式存储起来，这个矩阵被称为gram矩阵：