直接跳过第一讲。从第二讲Perceptron开始,记录这一讲中几个印象深的点:
1. 之前自己的直觉一直对这种图理解的不好,老按照x、y去理解。
a) 这种图的每个坐标代表的是features;features的值是有物理意义的。
b) 而圈圈和叉叉是为了标注不同的样本(正样本 负样本),即label;为了后续的很多简便表示,这里正样本取+1,负样本取-1
2. Perceptron Learning策略的几何意义:表示临界线(面)的法向量旋转方向
由于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越接近?向量内积越大,则认为越接近(夹角越小)
基于上述思路可以得到
大意就是说,按照PLA的算法策略,可以保证每一轮Wf与W的内积总是越来越大的,这个就保证了算法朝着好的方向发展。
但是还有问题,每一轮W的长度也在变化啊,这样单纯比较Wf与W的内积大小就没意义了。
因此,更进一步,有了如下的推导:
至于这里为什么用2范数,我理解主要为了表述方便一些。
这么一大段的意思就每轮算法策略迭代后,我们要求的W的长度的增长速度是有上限的。(当然,也不一定是每轮都增长的,如果展开式子的中间项是比较大的负的,还可能减小)
上面两个PPT合在一起想说明一个直观的问题:算法策略每轮朝着好的方向发展的,而且W的增速是有上限的。
有了这样的一个直观的理解,我们就可以猜测,在一定迭代次数内,算法策略是可以收敛的。即,证明如下式子:
证明过程课件并没有给出,自己划一划也就出来了:
自己的字太难看,但是这样比较快捷,凑合看了。
这个证明过程,条件放松的都蛮宽的,但是可以证明PLA的算法策略是收敛的。
==================================================
第二次再过这个题目:
(1)PLA算法的迭代式子看成是对超平面法向量W的旋转
(2)证明PLA可以收敛的思路:
a. W的长度每轮增幅有限
b. W与Wf的内积越来越大(W越来越接近完全分类面)