Perceptron Learning Algorithm
Perceptron Learning Algorithm
Perceptron Learning
0.说在前面
1.PLA
2.实例
3.Guarantee of PLA
4.作者的话
0.说在前面
上一节我们主要通过一个简单的银行发卡例子，引出一个简单的Perceptron Hypothesis Set-感知器，并且这个Hypothesis Set由许多条直线构成的。
接下来，我们的目的是去设计一个演进算法A，来选择一条最好的直线，能将平面上所有的正类和负类完全分开，从而找到最好的g，使得g与f基本一致。
1.PLA
【PLA思想】
那么现在问题来了，如何找到一条最好的直线?
我们可以使用逐点修正思想，在平面上随意取一条直线，看看哪些点分类错误。然后开始对第一个错误进行修正，即变换直线的位置，使这个错误点变成分类正确的点，紧接着，再对后续的所有错误分类点进行上述纠正，知道所有的点都完全分类正确，就得到了最好的直线。
那么第一条直线如何选取呢？
这个问题可以转化为初始化这个g，定义g0为该g的初始化形式，那么g0则为向量W0和向量X0的内积。
由于这是一个初始化的情况，因此可以将向量W0和向量X0均设为0向量（向量的各个分量均为0）。
然后，我们利用g0对data set中的数据进行验证，如果得出的结果与f验证的结果一致，则视为g0正确。如果在对所有的data set进行走查且g0正确，则g0视为最接近f的假设。若在某一个data上g0出现错误，则对g0进行修正，直到修正的结果g对于data set中所有的数据都正确为止。
为了方便，我们用w向量代表g0
那么如何修正错误呢？
修正错误图
从w0向量开始，不断纠正D中的错误。
首先随机选择一条直线进行分类。然后找到第一个分类错误的点，如果期望该点是正类，结果变成了负类，此时t轮的w向量转置与x向量点乘结果为负，表现为上图右上角结果，x向量与w向量的夹角大于90度(此时的w向量转置与x向量点乘最后的结果不满足分类点)，此时就得纠正，让t轮的w向量变为(t+1)轮的w，(t+1)轮的w向量是通过w与x向量求和得到的(w(t)+y(t)*x(t))；
如果被误分为正类的点，此时t轮的w向量转置与x向量点乘结果为正，x向量与w向量的夹角小于90度(此时的w向量转置与x向量点乘最后的结果也不满足分类点)，此时也得纠正，让t轮的w向量变为(t+1)轮的w，(t+1)轮的w向量是通过w向量减去x向量求得(w(t)+y(t)*x(t))。
这种思想，就是不断迭代纠正错误点，这种思想用一句英文"A falut confessed is half redressed."中文表示，知错能改。
实际实践中，可以将每个点进行遍历，直到将所有分类错误点全部修正，分类正确，这种称为Cyclic PLA。
2.实例
图解PLA思想：
一开始原始情况如下图：
初始情况图
第一轮，没有线，w与x均为0向量，第一点一定表现错误，需要做一次修正，修正之后的结果为以原点和X1连接的直线所在的向量为法向量的直线。(0加上方向上的线)
第一轮图
第二轮：x0与w(t)夹角大于90度，且此时的黑色圈圈点，被误划分为负类点，所以得纠正，按照上述pla思想进行两向量相加，得到了w(t+1)向量，进入下一轮，w(t)变为w(t+1)，继续进行修正。
第二轮图
第三轮
第三轮图
第四轮
第四轮图
第五轮
第五轮图
第六轮
第六轮图
第七轮
第七轮图
第八轮
第八轮图
第九轮
第九轮图
第十轮
第十轮图
自此分类完成，无修正的点！
3.Guarantee of PLA
对于PLA我们需要考虑两个问题：
第一点：PLA迭代一定会停下来吗？如果线性不可分怎么办？
第二点：PLA停下来的时候，是否保证f近似等于g？如果没停下来，是否有f近似等于g?
PLA何时能停，这个问题直接从PLA定义出发，当找到一条直线，能将所有平面上的点全部分类正确，那么PLA自然就停止了。要达到这个终止条件，必须得保证集合D满足线性可分(line separable)。如果线性不可分，PLA自然停止不了。
如下图所示为推导w(t+1)与w(f)的内积过程，其中w(f)表示目标权重。
第一个式子表示当无犯错情况下所满足的公式，yn与w(f)的转置乘以x(n)同号。
第二个式子表示推导w(t+1)与w(f)的内积，PLA会对每次错误的点进行修正，更新w(t+1)的值，如果w(t+1)与w(f)越接近，那么内积就越大。表示w(t+1)越接近权重w(f)，说明PLA是有学习效果的。
内积图
上图可以看出，w(t+1)与w(f)的内积跟w(t)与w(f)的内积相比更大。这说明w(t+1)更接近w(f)。以上提到内积大，就越接近，也就是夹角小，但是长度也有可能产生影响，接下来分析w(t+1)与w(t)的向量长度关系：
我们知道PLA的一个核心思想是纠正错误，也就是此时的yn与w(f)的转置乘以x(n)异号。也就引出了下图第一个式子。
下图第二个式子推导出w(t+1)与w(t)相比，增量值不超过max(x(n)^2)。也就是说，w(t)增长受限，w(t+1)与w(t)长度差别不大，那么与上述夹角的影响因素混合起来，则表示内积的大小着重在于夹角，而夹角则影响接近程度。
向量模长图
如果令初始权重w0=0，那么经过T次错误修正，有上图中的第三个式子。而这个式子的左边小于等于1，也就是说右边根号T的式子不会比1大，也就是说迭代次数T是有上界的。
根据以上证明，我们得到如下结论：
w(t+1)与w(f)是随着迭代次数增加而逐步接近，PLA最终停下来，是因为T有上界，可以实现对线性可分的数据集完全分类。
4.作者的话
以上正文图片来源于林老师课程！ 最后，您如果觉得本公众号对您有帮助，欢迎您多多支持，转发，谢谢！ 更多内容，请关注本公众号机器学习系列！