统计学习方法笔记 -- 感知机

感知机（perceptron），听着很牛比，其实就是二类分类的线性分类模型
属于判别模型，1957年由Rosenblatt提出，是神经网络和支持向量机的基础
任何统计机器学习都是三要素，只需要说清楚模型，策略和算法

感知机模型

感知机是一种线性分类模型。
假设空间是定义在特征空间中的线性分类模型或线性分类器，即函数集合

几何解释为，
线性方程，wx+b=0，对应于特征空间中的一个分离超平面（separating hyperplane），其中w为超平面的法向量，b是超平面的截距。该平面将数据点分为正，负两类

策略
策略就是要定义损失函数，并让损失函数极小化
如何选取损失函数很关键？
这里一个自然的选择是，用误分点的总数作为损失函数，但问题是这个损失函数和w，b没关系，不易优化
所以这里选择误分点到超平面的总距离作为损失函数，这样损失函数对于w，b是连续可导的，这样就可以使用梯度下降来找到最优解
任一点到平面S的距离，参考点到平面的距离公式


所以可以用来替换
假设误分点集合为M，那么所有误分点到超平面S的总距离为，

损失函数不需要考虑常量部分，所以感知机的损失函数为，

损失函数是非负，如果没有误分点，为0，误分点越少，离超平面越近，损失函数值越小

算法

原始形式

要解决的问题如上，由于损失函数是对于w和b连续可导的，所以这里使用梯度下降法（gradient descent）来找到最优解，
Andrew Ng的公开课，理解梯度下降比较好的例子是，想象一下你在山上如果要以最快的速度下山，你会选择如何走一步（注意只是一步，下一步取决于新的位置）
应该选择梯度的反方向，首先要定义梯度，

可以看出梯度就是对于损失函数求偏导数，对于w的梯度就是对于L(w,b)求w的偏导，同样对于b的梯度也是对L(w,b)求b的偏导数

导数和微分（参考wiki）
导数描述了这个函数在这一点附近的变化率。导数的本质是通过极限的概念对函数进行局部的线性逼近。

微分是对函数的局部变化率的一种线性描述。微分可以近似地描述当函数自变量的取值作足够小的改变时，函数的值是怎样改变的。
可微的函数，其微分等于导数乘以自变量的微分，因此，导数也叫做微商。

一个多变量的函数的偏导数是它关于其中一个变量的导数，而保持其他变量恒定

几何意义是，在求偏导那维上的切线斜率

上面可以看到对于梯度的计算需要使用所有的误分样本点，如果M非常大的话，效率很低，所以这里使用的是随机梯度下降

随机梯度下降（stochastic gradient descent）

可见这里只是用一个样本点的损失函数的偏导值来修正w和b，效率会高
但问题是，这次修正只是减小对该样本点的损失值，而非所有样本点的整体的损失值，也就是所这次修正是对于该样本点的局部最优，而非对整个样本集的全局最优
所以随机梯度下降，会导致下降过程的震荡，但往往可以逼近全局最优
当然这个方法的优点，不需要遍历所有的样本点，可以针对每个样本点对w和b进行迭代更新，这样通过部分样本点就可以使损失函数达到最小或收敛

所以给出完整的算法如下，

感知机学习算法，给不同的初值或选取不同的误分类点，得到的解可能是不同的，比如对于下图的例子，明显解不是唯一的，会有很多解，为了得到唯一的超平面，需要增加约束条件，这就是支持向量机的思路
并且可以证明（参考原书），当训练集线性可分时，感知机学习算法一定会收敛
但是如果非线性可分，那么会导致不收敛，迭代结果会反复发生震荡