机器学习笔记之PLA算法

阅读本文需要线性代数基础，否则阅读体验很差。

这是我的第一篇原创，稍稍入门一下 Machine Learing 和 Deep Learning ，本篇参考视频 " 机器学习基石 " [ 中国台湾大学林轩田 ] ,以及其他机器学习书目。

PLA(Perceptron Learning Algorithm)感知器算法，是一个二元分类(Binary Classfication)的机器学习算法，对于二维或者高维的线性可分问题的分类，最终将问题分为两类——是或者不是。

1.Hypothesis Set

把测试集喂给算法，然后算法从他的Hypothesis Set 里经过一系列运算得到一个 方法G，使得这个G几乎接近目标F，使其能够得到正确的结果。

训练集包括数据和数据特征Xi，每个数据的数据特征包含很多种，把一系列数据特征集合看作一个向量(X1,X2,X3,...Xn)，把每一种不同的数据特征乘以一个权重，类似大学成绩里的加权平均分，像专业课科目权重大一点，体育课权重小一点，这里就把权重写作Wi,这里的权重亦可以是负的，把这个公式的值与阈值threshold作比较，大于阈值即为正，小于阈值即为负，来做一个二维分类。可以用一个sign函数来区分。

为了方便计算,引入一个X为+1，将threshold当作W*X，从而前面的累加公式即可以从i=0开始，然后可以看作一个列向量与行向量的积，最后结果仍为一个常数最后得出的就是我们的一个Hypothesis，这个h就由权重和设置的门槛值决定，我们的目的就是计算出所有权值w和阈值threshold。

为了更清晰地说明这个感知器模型，来看一下其中二维的简单的例子。

图中X是默认为1，所以二维的图中有一个W，有一个W1乘以X1的第一个维度，一个W2乘以X2的第二个维度，输出即为图中的蓝圈和红叉，蓝圈为+1,红叉为-1,h就是图中的直线，sign函数的作用是取正负号，当函数内的值等于0的时候切换正负号，在平面上显示的就是一条直线，直线的一边为+1，另一边为-1，h对应图中的线，训练集的每个x对应图中的点，最后输出y对应想要圈还是叉，每一条线有不一样的预测规则。在这个模型上就是一条直线，称之为linear(binary) classifiers。注意一下，感知器线性分类不限定在二维空间中，在3D中，线性分类用平面表示，在更高维度中，线性分类用超平面表示。

2.Perceptron Learning Algorithm(PLA)

到这里我们知道了可能的Hypothesis Set，然后要选一条最好的线，所谓最好的线，就是目标函数，但是并不知道目标函数是什么，所以先要求在所有的线里找到一个预测函数，要求它在训练集里与目标函数特别接近，在一个二维空间上，会有无数条线，从这里面找到一条相对较优的预测函数是不可能的，所以选择一个h修正，使这条线变得更好。一开始的线记为W，如果这条线存在错误，肯定能找到某一个点XnYn，这个点的Xn与Wt作内积与想要的结果yn不一样，所以就要修正他。

来看视觉化效果，喂给机器这样的训练集，一部分数据对应圆圈 一部分数据对应红叉。

一轮随机找一个点，这条线与原点的连线是预测函数的法向量，所以这条线就是这样的然后算法找到了有一个点是错的，然后要把红色的线往黑色的线方向修正，修正完算法一直找发现有一个叉错误了，继续更新修正，更新了很多很多轮之后所有的圆圈在一边，红叉在另一边，就是已经完成的一个函数了，至少在训练集的数据下。

照这种思想，遇到个错误点就进行修正，不断迭代。要注意一点：每次修正直线，可能使之前分类正确的点变成错误点，这是可能发生的。但是没关系，不断迭代，不断修正，最终会将所有点完全正确分类（PLA前提是线性可分的）。这种做法的思想是“知错能改”，有句话形容它：“A fault confessed is half redressed.”

那么还有两个问题需要考虑

1). 这个算法一定会停下来吗？如果线性不可分怎么办？

2). 假设这个算法停下来了，拿到的这个预测函数和目标函数是不是一样的？

3.Guarantee of PLA

PLA的终止条件是找到一条线，把训练集分的完全不犯错误。这个条件的前提就是需要训练集是线性可分的Linear Separable.

先考虑PLA算法是不是一定会停下来，把这个资料都分得完全没有错误，PLA就停下来了，那么这个算法就要有一个条件，训练集一定要有一条线可以切开，也就是Linear Separable线性可分，如果是线性不可分，PLA是不会停止的。对于线性可分的情况下，假设有一条直线Wf

必然满足

这个Xn(t)里的t代表第几次循环，最后就是看Wt与Wf之间的关系是什么，到底接不接近，数学上可以用内积来判断是否接近，内积越大，表示两条线的距离越近，那就来计算Wf的转置和Wt+1的内积：

然而，内积越大不完全代表两个向量越接近，也有可能是向量的长度发生变化，所以还需要证明两个向量长度的关系：

因为Wt只会在错误的情况下更新，蓝色项即错误的点为负值，所以Wt+1增长只会靠红色项增长，红色项即为随便选的一个犯错的点，最大值就是离原点距离最远的那个点，所以与Xn^2作比较。Wt的增长被限制，所以Wt与Wt+1差别不会太大。

如果令初始权值w0=0，那么经过T次错误修正后，有如下结论：

下面贴出来该结论的具体推导过程：

以上图片引用自网络，以及机器学习基石PPT。

总结：本节课主要介绍了线性感知机模型，以及解决这类感知机分类问题的简单算法：PLA。我们详细证明了对于线性可分问题，PLA可以停下来并实现完全正确分类。

----------------------------------------------------