来自 丁磊_ml博客 网址为 blog.csdn.net/MosBest
我们有一堆数据，默认他们是线性可分的。 定义f为这个数据分割线的最优解，但是我们不知道他的值。 我们仅有一个函数集H，这个函数一般是无穷大的。我们的目的就是从H中找出一条线g来尽可能的接近f。但是，我刚刚说了，H内的函数一般是无穷多的，我们不可能把H中的函数一 一 比较，得到最好的分割线g吧！！！
不过伟大的科学家就说，我们的目的不就是找出一条线把这些数据都分开吗！！那我随机的初始化一条分割线 g0 ,让他一 一和数据点进行比较（数据总该是有限个的吧）, 如果 某一个数据点划分对了，那这条线就不动，继续比较下一个点。如果错了，那就调整 这条线，让他能把这个点分对。以此下去，直到我们发现所有的点都分隔对了为止。。。
那么问题就来了，我们怎么调整这条分隔线呢？？？ 首先要明确，只有当分类出错误的时候，才对分割线进行调整。 假设我们遇到的数据点 (xn,yn) 是我们第t次分类错误。那么就有
当 yn=+1 时，则我们的错误结果为 wTxn=wt−→∗xn−→=||w||∗||xn||∗cosΘ<0 ，即 cosΘ<0 则 Θ 太大,为了能过纠正错误，决定减小 Θ ，就让 w→t+1=w→t+x→ 即 紫色的就是更改后的 wt+1
同理 当 yn=−1 时，则我们的错误结果为 wTxn=wt−→∗xn−→=||w||∗||xn||∗cosΘ>0 ，即 cosΘ>0 则 Θ 太小,为了能过纠正错误，决定增大 Θ ，就让 w→t+1=w→t−x→ 即 紫色的就是更改后的 wt+1
综上所述，当分割线遇到点 (xn,yn) 时，如果分割正确，那么 wt 就不变，如果分割错误，那么就令
注意w是分割线 wTx=0 的法线，也就是说分割线的方向是与w的方向垂直的。。。
这个想法是挺好的，那么问题是，用这种方法到底行不行得通呢？？？现在，我们就来验证这个算法的正确性！！！ 这种方法到底行不行得通，其实就是说这个算法到底能不能找到正确区分所有点的线。即这个算法到底能不能收敛？（收敛就是能停下来，算法只有找到了满足要求的线才停下来，所以说法不同，但意思是一样的） 证明： 首先有两个前提： 前提1：数据本就是可以线性可分的。（如果数据不是线性可分的话，那不管我们怎么找都找不到那条线） 前提2：我们仅仅是遇到分错的点时，才改变 wt ，遇到分对的点 wt 不变。
根据前提1，说明最终的线一定存在。 假设 wf 是我们要的线，则有 当线 wTtx=0 遇到 (xn,yn) 发生错误时，则更新 wt+1 ,即 遂有 则
根据前提2，有 又有
则 判断w_t， wf 是否相近，只需他们的 Θ 尽可能为0
我们初始化 w0=0 ，则可以怎么得，在T次误差矫正后，有 所以，最终得到
即 cosΘ>=T−−√.Cconstant ,即随着T逐渐增大， cosΘ 也会逐渐增大，那么 Θ 会逐渐减小到0，所以 wt是越来越接近wf 又 cosΘ<=1 ，所以 wt 一定收敛。
这个算法最大的缺点就是假设数据点是线性可分的。问题是，我们并不知道数据到底是不是线性可分的！！如果不是，也就是说最终根本没有上面的 wf ，即没有一条不犯错误的线，那么以上的推论都是“白搭”！！！
那怎么办？？？有个想法是，我们能不能把找出一条犯错误最少的线呢？？？？即 其实，从实际意义上，是不能的。这是一个著名的NP hard 问题！！！因为线有无穷多个啊！！！
伟大的科学家又提出一条算法，来解决这个问题——-口袋算法 口袋算法基于贪心的思想。他总是让遇到的最好的线拿在自己的手上。。。 就是我首先手里有一条分割线 wt ，发现他在数据点 (xn,yn) 上面犯了错误，那我们就纠正这个分割线得到 wt+1 ,我们然后让 wt 与 wt+1 遍历所有的数据，看哪条线犯的错误少。如果 wt+1 犯的错误少，那么就让 wt+1 替代 wt ，否则 wt 不变。 那怎样让算法停下来呢？？——–我们就 自己规定迭代的次数 由于口袋算法得到的线越来越好（PLA就不一定了，PLA是最终结果最好，其他情况就说不准了），所以我们就 自己规定迭代的次数 。
最后一个问题，如果数据本就是线性可分，那么我们用 pocket algorithm 和用 PLA，那个更好？？？ 答案是PLA更好。先不说PLA可以找到最好的那条线。单从效率上来说，PLA也更好些。最主要的原因是，pocket algorithm 每次比较的时候，都要遍历所有的数据点，且两个算法都要遍历一遍，才会决定那个算法好，而这还是比较一次，如果我们让他迭代500次的，那就麻烦了！！！但是，所有前提是，数据是线性可分的。如果线性不可分，只能用pocket algorithm，因为PLA根本不会停下来（而且PLA的 wt 也不是每更改一次效果就会比之前的好）！！