PLA算法——Percetron Learning Algorithm

1、PLA用来干什么

        感知器学习算法PLA用于解决二维或者高维的线性可分问题的分类，最终分类结果是两类——是或不是。以二维数据为例，下图中第一张是线性可分的，其它两张都不是线性可分的：

2、PLA怎么实现的

        PLA算法用来求解向量W（用于预测的向量，可以看作是权重向量），使得在已知的数据（训练集）中机器做出的判断与现实完全相同。当X为二维向量时，相当于在平面上画出一条直线将所有的点分成两部分，一部分结果为是，另外一部分的结果为否。
        设$h(X)$h(X)为求出来的预测函数，$W^T$WT是权重向量和输入向量的内积，那么

        以二维为例，算法的过程：

• 先找一条初始的线（一般是$W_0$W0​）
• 依次去判断空间内的每一个点，如果这个点分对了则继续，如果分错了，修正这条线：
          $W_{t+1}=W_t+yx$Wt+1​=Wt​+yx，$y=±1$y=±1，x是分错的点，即：
  
  

        PLA也叫知错就改算法，可以证明如果数据集是线性可分的，通过这种不断的修改一定能找到一条线将数据集正确划分。

3、证明线性可分时一定能找到这条线

        $W_f^TW_{t+1}>W_f^TW_{t}$WfT​Wt+1​>WfT​Wt​，这里$W_f^T$WfT​是理论上的最优解，可以看到每一轮迭代后$W_{t+1}$Wt+1​与理论最优解的内积都在变大，即每一轮都在向最优解移动（暂时不考虑向量长度）。

        这张图表明$W_{t}$Wt​每一次的改变最多是最大的$X_{n}$Xn​

        有了上面两个推导，现在可以证明，运行次数T是存在上界的：

4、线性不可分怎么办——pocket PLA

        如果数据集是线性不可分的，那么对PLA进行改进，类似贪心算法：在pocket中保留一条当前最好的线，如果改进后的线更好（错分的样本数少），则更新最好的线，这样的缺点是需要遍历完空间内所有点的才能得到最好的结果。