【Perceptron Learning Algorithm】林轩田机器学习基石

直接跳过第一讲。从第二讲Perceptron开始,记录这一讲中几个印象深的点:

1. 之前自己的直觉一直对这种图理解的不好,老按照x、y去理解。

【Perceptron Learning Algorithm】林轩田机器学习基石

a) 这种图的每个坐标代表的是features;features的值是有物理意义的。

b) 而圈圈和叉叉是为了标注不同的样本(正样本 负样本),即label;为了后续的很多简便表示,这里正样本取+1,负样本取-1

2. Perceptron Learning策略的几何意义:表示临界线(面)的法向量旋转方向

【Perceptron Learning Algorithm】林轩田机器学习基石

由于label设为了+1和-1,可以直接用w+yx来表示遇上错分样本时临界线的旋转策略,很巧妙和简洁。

这里是有一个疑问的,如果每次根据一个点调整,能保证调整后这个点一定就对了么?

我想这个答案是否定的:当轮调整后,这个点不一定就对了。

比如y=+1的例子,如果W向量特别长,x特别短,而且W与x的夹角特别大,那么就可能出现W+yx之后还是不能保证W(t+1)x是正的(即夹角转不过来);

但是这并不影响最后总体的收敛趋势(如果是Linear seperable的)

3. 为什么在Linear Seperable的条件下,Perceptron Learning Algorithm的算法策略是收敛的?

林的思路是这样的:

a) 首先假设数据是linear seperable的,在这个条件下,我们认为存在一个理想的分界线法向量Wf

b) 如果我们要求的W与Wf越接近,则认为越好

c) 如何衡量W与Wf越接近?向量内积越大,则认为越接近(夹角越小)

基于上述思路可以得到

【Perceptron Learning Algorithm】林轩田机器学习基石

大意就是说,按照PLA的算法策略,可以保证每一轮Wf与W的内积总是越来越大的,这个就保证了算法朝着好的方向发展。

但是还有问题,每一轮W的长度也在变化啊,这样单纯比较Wf与W的内积大小就没意义了。

因此,更进一步,有了如下的推导:

【Perceptron Learning Algorithm】林轩田机器学习基石

至于这里为什么用2范数,我理解主要为了表述方便一些。

这么一大段的意思就每轮算法策略迭代后,我们要求的W的长度的增长速度是有上限的。(当然,也不一定是每轮都增长的,如果展开式子的中间项是比较大的负的,还可能减小)

上面两个PPT合在一起想说明一个直观的问题:算法策略每轮朝着好的方向发展的,而且W的增速是有上限的。

有了这样的一个直观的理解,我们就可以猜测,在一定迭代次数内,算法策略是可以收敛的。即,证明如下式子:

【Perceptron Learning Algorithm】林轩田机器学习基石证明过程课件并没有给出,自己划一划也就出来了:

【Perceptron Learning Algorithm】林轩田机器学习基石

自己的字太难看,但是这样比较快捷,凑合看了。

这个证明过程,条件放松的都蛮宽的,但是可以证明PLA的算法策略是收敛的。

==================================================

第二次再过这个题目:

(1)PLA算法的迭代式子看成是对超平面法向量W的旋转

(2)证明PLA可以收敛的思路:

  a. W的长度每轮增幅有限

  b. W与Wf的内积越来越大(W越来越接近完全分类面)

上一篇:Deep Learning 17:DBN的学习_读论文“A fast learning algorithm for deep belief nets”的总结


下一篇:【Base64&UrlEncode】