台湾大学林轩田《机器学习基石》学习笔记第2讲——Learning to Answer Yes/No
上节课主要简述了机器学习的定义及其重要性，并用流程图的形式介绍了机器学习的整个过程：
本节课将继续深入探讨机器学习问题，介绍感知机Perceptron模型，并推导课程的第一个机器学习算法：Perceptron Learning Algorithm（PLA）。
一、Perceptron Hypothesis Set
首先我们要解决一个问题：what hypothesis set can we use? 这里涉及到我们该如何选择一个模型，即Hypothesis Set，不同的模型将对机器学习的结果产生很大的影响。这里介绍一个简单常用的hypothesis set，即感知器（Perceptron）。
还是以上节课提到的一个案例：机器学习应该怎么通过以往的用户数据，来判断是否给新的申请用户发放信用卡。
首先第一步我们需要根据所拿到训练数据建立一个模型：
- 对用户不同维度的特征进行打分，组成一个向量X；
- 给每个维度的特征赋予一定的权重值wi；
- 计算加权和，并与threshold进行对比，得出 y{+1(good) or -1(bad)}；
- 这里h(x)是一个关于wi和threshold的函数，选取不同的wi和threshold就会有不同的结果，这些h我们统称为hypothesis set H；
h(x)的表达式可以通过以上进行简化，变成为一个权重w向量和向量x的内积。这样的数学形式很简洁，在以后的学习中可以有效地帮助我们理解和计算。
w和x都是一个d维的向量，那么h(x)究竟会长什么样？对于高维的抽象比较难以理解，这里使用一个二维的例子来进行说明 - X：把横轴理解为x1的值，纵轴理解为x2的值，这样每个点的位置就是一个用户的原始数据；
- Y：y在图中表示为o(+1)或者x(-1)，这些y也是已知的，在图中可以清楚知道；
- H：h(x)函数在图中有无线多可能的直线，均属于hypothesis set这个H集合中，但只有一部分是可以把图中的o和x切分开，这就是我们想要的g；
- Perceptron：实际上就是图中的一条一条线，我们又把它称为一种linear classifier 线性分类器。
二、Perceptron Learning Algorithm (PLA)
在上面我们已经找到了一个hypothesis set H，即Perceptron，我们也知道想要的g就在H集合中的无数条线中的一条，那么机器怎么去找出这样的一条线h (即g)出来呢？
这里要理解一个概念：学习是一个过程，不断修正的过程。
因此我们假定有一个初始的h，它所对应的一个w0向量，那么对于图中某一个点（x,y）它可能出现判断错误，那么我们就根据这样一个错误进行修正，得到另外一个h，它所对应的一个w1向量。
- 这里用到了线性代数的知识点了，上一小节我们知道了h是w向量与x向量内积的正负判定；
- 当w与x内积：w·x=|w|·|x|·cosθ，当θ>90°内积为负，当θ<90°内积为正；
- t代表是第几轮的修正，当t轮是遇到错误，那么可以针对以上两种情况对w进行修正：
- 当θ>90°时，这是wt+1=wt+xt (向量加)，这样新的wt+1与xt的夹角θ就小于90°，内积将大于1，针对xt便修正成功；
- 当θ<90°时，这是wt+1=wt+xt (向量加)，这样新的wt+1与xt的夹角θ就大于90°，内积将小于1，针对xt便修正成功；
- 这样的算法我们称之为Perceptron Learning Algorithm (PLA)
实际操作中，可以一个点一个点地遍历，发现分类错误的点就进行修正，直到所有点全部分类正确。这种被称为Cyclic PLA。
具体的学习过程可以自行参考ppt。
对PLA，我们需要考虑以下两个问题：
- PLA迭代一定会停下来吗？如果线性不可分怎么办？
- PLA停下来的时候，是否能保证g≈f？如果没有停下来，是否有g≈f？
三、Guarantee of PLA
PLA什么时候会停下来呢？根据PLA的定义，当找到一条直线，能将所有平面上的点都分类正确，那么PLA就停止了。要达到这个终止条件，就必须保证D是线性可分（linear separable）。如果是非线性可分的，那么，PLA就不会停止。
那么假如D是线性可分，那么PLA会停下来么？
- 既然D是线性可分的，那么存在一条线能够把正负正确分类，即存在一个理想的wf满足yn与xn的关系；
- PLA在遇到错误的点时，会进行修正，并得到一个新的wt+1，通过证明可以看到wf·wt+1内积是越来越大的，说明PLA的学习是有效的；
- wf·wt+1越来越大，说明二者的夹角越来越小？也就是说wt+1越来越接近理想的目标wf？
不一定，因为内积的增大，一方面有可能是长度变长了，也有可能是夹角变小了。
以上证明了|wt|^2的增长是有极限的，增量值不会超过max|xn|^2，也就是说wt长度的增量是被限制住的，即wt+1和wt的长度不会相差太大。
对以上的推导参照如下：
上述不等式左边其实是wT与wf夹角的余弦值，随着T增大，该余弦值越来越接近1，即wT与wf越来越接近。同时，需要注意的是，√T⋅constant≤1，也就是说，迭代次数T是有上界的。根据以上证明，我们最终得到的结论是：wt+1与wf的是随着迭代次数增加，逐渐接近的。而且，PLA最终会停下来（因为T有上界），实现对线性可分的数据集完全分类。
四、Non-Separable Data
虽然上一小节中，验证了PLA是一个很漂亮的算法，可以快速地帮我们找到一个理想的wf。但这是基于一个假设：D是线性可分的。
- wf是我们未知的，如果D线性可分，那么就存在一个理想的wf；
- 即使D线性可分，那么在找到wf时，PLA需要执行多长时间呢？不确定！因为ρ本身就是从wf推导来的，而wf未知。
- 因此在一个我们不知道是否线性可分的D中，简单地执行PLA，如果不停下来，我们仍然无法判断是否存在我们的目标wf；
- 简单来讲，D如果不是线性可分，那么我们该怎么办？
我们拿到的D中一般情况下都存在一些错误，这里称之为noise(类比通信系统中噪声)，相对于我们正确要学习的其他讯息，noise的信息应该是小的。 - 既然noise难免存在，不存在一个离线的wf，那么是否可以找到一个犯错误最少的wg呢？
- 理论上是可以的，但实际上工程上很难实现；
- 只能另辟蹊径，对PLA进行修正。
- 这里介绍了一个叫做Pocket Algorithm的算法；
- 每次得到一个wt时，发现它犯的错误比之前的都要少，就把它保存在pocket中；
- 直到执行了多次之后，pocket中的wt就会≈wg，我们希望获得的较为理想的g；
五、总结
- 本讲主要的问题在于如何去学习判断是非；
- 如果D是线性可分的，那么PLA总能找到一个理想的f，不管是多大的维度；
- 如果D不是线性可分的，那么通过Pocket Algorithm算法对PLA进行修正，也能有效地找到一个g，它趋近于我们的目标函数f。
Reference：
https://blog.****.net/red_stone1/article/details/70866527