【机器学习基础】从感知机模型说起

感知机（perceptron）

感知器（perceptron）1957年由Rosenblatt提出，是神经网络与支持向量机的基础。感知器是二类分类的线性分类模型，其输入为实例的特征向量，输出为实例的类别，取+1和-1二值。感知机对应于输入空间（特征空间）中将实例划分为正负两类的分离超平面，属于判别模型。感知机学习旨在求出将训练数据进行线性划分的分离超平面。

分离超平面分类法

分离超平面进行分类的过程是构造线性判定边界，试图显示地、尽可能好地将数据分到不同的类。

超平面分离定理

超平面分离定理是应用凸集到最优化理论中的重要结果，这个结果在最优化理论中有重要的位置。所谓两个凸集分离，直观地看是指两个凸集合没有交叉和重合的部分，因此可以用一张超平面将两者隔在两边。

感知机定义

感知机几何解释

感知机学习算法（perception learning algorithm）

下面的图片给出了感知机的原始学习过程：

pla_process

从图中可以看出，如果2D平面中向量w与向量x呈钝角，而x为正例，这说明w·x的角度太大了，这样，将w调整成w+y·x，即将w向x转动一下，接近x向量；同理，如果分离超平面错将正例数据分成负例数据时（2D平面中，向量w与向量x呈锐角），那么将w调整成w+y·x，实际上是向量w-x，则w要远离x一点。

2D感知机学习算法演示

初始情况下，分类器认为所有数据都是错误的，所以任意找一个数据进行修正。

step_initial

这里，w为分离平面的法向量，分离平面垂直于法向量。

step1
xg是被错分的数据，所以将原来的法向量和数据的向量相加，得到一个旋转之后的法向量。
step2

如此，进行下去，不断地修正，直到所有的数据都被正确的分类。

step3
step4
step5
step6
step7
step8
step9
step_final

最后，找到了“完美”分类的线。

PLA会不会停下来

在线性可分的条件下，我们如何保证PLA算法能停下来呢？我们可以用wf和wt的内积来表示它们是不是越来越接近。
我们可以看出wf和wt的内积随着更新不断变大，这在一定程度上说明wf和wt越来越相似了，但由于没有考虑到向量的长度，所以还不完备。

接下来的说明，wt每次最多增长xn的长度。

最后我们对wf和wt进行正规化，得到一个乘积，其实就是wf和wt的夹角的cosine值。这代表，每次更新，wf和wt的角度就靠近一点点，并且不可能无限的增长，因为这个值不可能大于1。所以这就证明了，PLA算法会停下来。

转载请注明作者Jason Ding及其出处
Github主页(http://jasonding1354.github.io/)
CSDN博客(http://blog.csdn.net/jasonding1354)
简书主页(http://www.jianshu.com/users/2bd9b48f6ea8/latest_articles)