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。