文章原创,最近更新：2018-07-16
学习链接:
Learning to Answer Yes No-Guarantee of PLA
学习参考链接:
1、台湾大学林轩田机器学习基石课程学习笔记2 -- Learning to Answer Yes/No
2、林轩田机器学习基石——Guarantee of PLA
1.Linear Separability线性可分
PLA迭代什么时候会停下来吗？
PLA什么时候会停下来呢？根据PLA的定义，当找到一条直线，能将所有平面上的点都分类正确，那么PLA就停止了。要达到这个终止条件，就必须保证D是线性可分（linear separable）。如果是非线性可分的，那么，PLA就不会停止。
具体线性可分,可见如下截图:
如果资料线性不可分,比如以下截图这条,不管你怎么转,总是有犯错的点,无法用一条线将资料一分两段.
以下的截图也不是线性可分,因为是个圆分开,如果坚持用线进行线性可分的话,怎么切都是
不可能把资料切开的.
以下这两种情形都不是线性可分,以后的课程有讲到.
那么PLA的保证是什么时候?我们假设是简单的情形,有一条线,PLA到底会不会停下来呢?是否能找到这样的线呢?
2.PLA Fact: Wt Gets More Aligned with Wf
对于线性可分的情况，如果有这样一条直线，能够将正类和负类完全分开，令这时候的目标权重为wf，则对每个点，必然满足
即对任一点：
备注:
此外截图的公式是代表分类的点与线之间的距离有多远,这个距离是有带正负号的,乘以yn,这个yn代表是想点在哪一边?
以下截图的公式的结果要＞0,因为这个线是完美的,能够很好的将点分为正、负类的点。
而选择所犯错误的点满足这个性质，结果也会>0,如下截图：
PLA会对每次错误的点进行修正，更新权重 的值，如果 与 越来越接近，数学运算上就是内积越大，那表示 是在接近目标权重 ，证明PLA是有学习效
果的。所以，我们来计算 与 的内积：
从推导可以看出， 与 的内积跟 与 的内积相比更大了。似乎说明了更接近 ，但是内积更大，可能是向量长度更大了，不一定是向量间角度更小。所
以，下一步，我们还需要证明 与 向量长度的关系：
备注:
这里的yn标注是灰色,是因为yn的取值只有-1,+1.
-
如下图,xn表示最长的向量
根据以上的推理结果可以得到,如下结果:
以上的公式具体的推理结果如下:
备注：这里的constant指的是某个常数。
练习的题目如下：
备注：
计算wf和wt的夹角余弦，具体如下：
cos的最大值是1，也就是说上式的最大值为1，那么最大迭代次数T就是这么多啦：
