文章原创,最近更新：2018-06-27
学习链接:
Leaming to Answer Yes No-Perceptron Leaming Algorithm
学习参考链接:台湾大学林轩田机器学习基石课程学习笔记2 -- Learning to Answer Yes/No
1.Select g from H
根据上一部分的介绍，我们已经知道了hypothesis set由许多条直线构成。接下来，我们的目的就是如何设计一个演算法A，来选择一个最好的直线，能将平面上所有的正类和负类完全分开，也就是找到最好的g，使g≈f。
如何找到这样一条最好的直线呢？即就是理想上的f，但是这个f我们是不知道的。我们可以使用逐点修正的思想，首先在平面上随意取一条直线，看看哪些点分类错误。然后开始对第一个错误点就行修正，即变换直线的位置，使这个错误点变成分类正确的点。接着，再对第二个、第三个等所有的错误分类点就行直线纠正，直到所有的点都完全分类正确了，就得到了最好的直线。这种“逐步修正”，就是PLA思想所在。
设第一条线为g0，如果这条线不够好，我们则让这条线变得更好。直到这条线好得不能再好了才结束。
用w0表示g0的权重
2.Perceptron Learning Algorithm感知器学习算法
1）一开始有w之后，那w长什么样的呢？不管的话全部都是0也可以。如果这个线还不完美，我们一定找出资料某个点在这条线犯的错误。这个点我们叫
备注：这个小写t，代表一轮又一轮，代表哪一轮的意思。
如果把现在的线叫做wt，在这个点犯的错误。什么是犯错误呢？就是
做内积的时候，得到的+-号跟我想要的结果不一样，因此就需要想办法去修正。
2）那么应该怎么修正呢？
修正有两种，具体如下：
- 一种是我要的符号是+，而实际是-
- 一种是我要的符号是-，而实际是+
具体表现如下：
a)一种是我要的符号是+，而实际是-
备注：内积＞0表示两个向量的夹角为锐角，＜0表示两个向量的夹角为钝角。
w与x的角度太大了，就用w+x把角度转回来。
具体解释如下:
下面介绍一下PLA是怎么做的。首先随机选择一条直线进行分类。然后找到第一个分类错误的点，如果这个点表示正类，被误分为负类，即:
那表示w和x夹角大于90度，其中w是直线的法向量。所以，x被误分在直线的下侧（相对于法向量，法向量的方向即为正类所在的一侧），修正的方法就是使w和x夹角小于90度。通常做法是w←w+yx, y=1,如图右上角所示，一次或多次更新后的w+yx与x夹角小于90度，能保证x位于直线的上侧，则对误分为负类的错误点完成了直线修正。
b)一种是我要的符号是-，而实际是+
w与x的角度太小了，就用w-x把角度转开来。
我们就做这样的修正，如果要+，把w靠近x多一点，如果-的，把把w远离x多一点。
具体解释如下:
同理，如果是误分为正类的点，即:
那表示w和x夹角小于90度，其中w是直线的法向量。所以，x被误分在直线的上侧，修正的方法就是使w和x夹角大于90度。通常做法是w←w+yx, y=−1，如图右下角所示，一次或多次更新后的w+yx与x夹角大于90度，能保证x位于直线的下侧，则对误分为正类的错误点也完成了直线修正。
按照这种思想，遇到个错误点就进行修正，不断迭代。要注意一点：每次修正直线，可能使之前分类正确的点变成错误点，这是可能发生的。但是没关系，不断迭代，不断修正，最终会将所有点完全正确分类（PLA前提是线性可分的）。这种做法的思想是“知错能改”，有句话形容它：“A fault confessed is half redressed.”
以上就是感知机演算法.
3.Practical Implementation of PLA
这个演算还有些细节,怎么简单判断,是完全没有犯错误,常见的方式是从1号点,2号点,一直到到n号点,轮流去看点。如果这个点没错，就看下一个点，如果这个点犯错，就进行修正。
实际操作中，可以一个点一个点地遍历，发现分类错误的点就进行修正，直到所有点全部分类正确。这种被称为Cyclic PLA。
4.Seeing is Believing
下面是个二维的资料，机器可以看到的资料就可以视觉化成这样的图，现在我们思考的方式是机器能不能通过这样的方法找到这条线。
下面用图解的形式来介绍PLA的修正过程：
机器刚开始找一个点点，因为开始没有线，就好像看到什么都是错的，所以找到第一个点是错的，就就先来进行修正。之前有说过w刚开始为（0,0），就把（0,0）加上这个点的向量，而这个点是正的，就会得到一条新的w（t+1）的线，w（t+1）是这个分界线法向量。
因为x9是在红色那边，这个是犯错的点。
上面的点转得有点多了，所以要转回去，就会得到一条新的线。
因为x3是在蓝色那边，所以要修正
因为x9是在红色那边，需要修正
因为上面的点转太多了，又要重新修正。
最终的线符合要求，圈圈在一边，x都在另外一边。
这个算法需要的程式不需要20行。如果需要写程式的话，需要将顾客的特征x0设置为1，这样的视觉效果比较好。
5.Some Remaining Issues of PLA
对PLA，我们需要考虑以下两个问题：
PLA迭代一定会停下来吗？如果线性不可分怎么办？
PLA停下来的时候，是否能保证f≈g？如果没有停下来，是否有f≈g？
6.Fun time
下面四条规则是一定对的？
答案是3
原因是如下：
上面这个更新的式子两边乘以ynxn，因为右边更新的公式是ynxn的平方是正的，所以左边的值比右边的值来得大。
来得大是什么意思呢？
xn是错误的点，经过一次修正之后，在t+1时应该会让xn点得到正确的答案，也就是wt+1会是xn得到正确的答案yn。
