2.2Leaming to Answer Yes No-Perc

文章原创,最近更新：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。