[转]PLA算法总结及其证明

PLA算法总结及其证明

http://m.blog.****.net/article/details?id=45232891

分类： 机器学习

PLA(Perception Learning Algorithm)适用于二维及高维的线性可划分问题。问题的答案只有同意或者不同意。例如银行可以根据顾客的个人信息来判断是否给顾客发放信用卡。将顾客抽象为一个向量X，包括姓名、年龄、年收入、负债数等。同时设定各个属性所占的比例向量w，对于正相关的属性设置相对较高的比例如年收入，对于负相关的属性设置较低的比例如负债数。y表示是否想该用户发放了信用卡。通过求x和w的内积减去一个阀值threshold，若为正则同意发放信用卡，否则不发放信用卡。我们假设存在着一个从X到Y的映射f，PLA算法就是用来模拟这个映射，使得求出的函数与f尽可能的相似，起码在已知的数据集(即样本上)上一致。

PLA算法即用来求向量W，使得在已知的数据中机器做出的判断与现实完全相同。当X为二维向量时，相当于在平面上画出一条直线将所有的点分成两部分，一部分同意发送，另一部分的不同意。内积可以表示成：

其中x₀=1，w₀=-threshold。

y_s的值域：{+1，-1 }(y_s 表示样本中y的值，用于输入到算法进行调整)

结合文中例子：y_s=1 表示在给定的样本数据中，给该用户发放了信用卡，y_s= -1表示未发放。

PLA先假定W₀为向量0，然后找到一个不满足条件的点，调整W的值，依次进行迭代使得最终可以将两部分完全分开。

W的调整方案

注：错误驱动调整

第一种，在给定的已知数据中向该用户发放了数据,即y_s(i)样本中第i个数据为+1，但算法给出的结果是不发放(即：h(x_i) 小于0)，说明两个向量的内积为负，需要调整w向量使得两条向量更接近，此时令调整系数为样本的y_s(i)。示意图为

则调整后的w_t+1= w_t + y_s(i)x_i。

第二种，在给定的已知数据中向该用户发放了数据,即y_s(i)样本中第i个数据为-1，但算法给出的结果是不发放(即：h(x_i) 大于0)，说明两个向量的内积为正，需要调整w向量使得两条向量更远离，此时令调整系数为样本的y_s(i)。示意图为

则调整后的w_t+1= w_t + y_s(i)x_i。

对于线性可分的数据集，PLA算法是可收敛的

两个向量的内积增大说明两个向量越来越相似或者向量的长度增大

图片上 ||w_t+1||²  <=  ||wt||² +
max{1 <=i<=  n | ||y_ix_i||²} 其中，y_i的值域为正负1

因此     ||w_t+1||²  <=  ||wt||² +
max{1 <=i<= n | ||x_i||²}

这说明每次调整后，向量的长度增加有限。不妨设

带入上一公式得到

因此，W(t)最终是收敛的。到此已经证明了PLA算法最终可以停止。

下面求该算法需要调整多少步才能停止

由上述过程可以得到以下两个不等式：

根据余弦值最大为1，可以得到

 等于     

因此  

 即纠正次数

该文主要是学习了*大学机器学习课程之后自己的一些总结，第一次写博客，有问题还请大家多多指正。算法的实现在接下来继续总结出来。

以上改自：http://blog.****.net/dreamermonkey/article/details/44065255

另一份证明同样很清楚：

以上证明来自：http://www.cnblogs.com/HappyAngel/p/3456762.html