前一讲对于机器学习有了初步的认识，这一讲学习了一个很基本的模型：感知机模型。

为了说明我们的感知机模型，这里我们首先举一个例子：当我们去银行申请信用卡的时候，我们需要填写一些相关的信息，然后银行审查后会决定是否发放。比如我们的信息有如下几种

有了上面的信息后，我们怎么做呢？其中一种简单的做法就是对于每一个数据赋予一个权重w，然后求积再取和，判断结果和我们设置的阈值的大小关系。如果大于阈值，发放，否则不予发放。

我们也可以使用符号函数sign（x）来将我们的结果二值化，+1表示可以，-1表示否决。

我们将上面的函数h(x)进行一个转化，将其写成W的转置和X相乘的形式

我们假设感知机模型在二维平面上，如下图所示，特征x表现在二维平面上就是一系列的点，标签就是o和×，表示前面提到的+1和-1，我们所作出的假设就是图中的线，目标就是找到一个可以正确对图中的点进行划分的线。

在这里的感知机模型，其实就是我们后面学习的二分类的线性模型。

既然我们的目标是找到一条最好的划分的线，换言之，我们做的很多的假设都可以取得想要的结果，但是如何在假设集中找到最好的一个呢？

那么应该怎么去做呢？梳理一下，我们希望从H中找到一个g，使其尽可能的接近真实的f，使得g(Xn) =f(Xn)=Yn成立，但是存在的一个问题就是我们的假设是无限的，这样看几乎是不太可能的了！我们怎么解决呢？既然我们无法一次性找到最好的，我们这里采用逐点修正的方法，随机的从一个开始，不断地调整来到达最好的那个。

PLA是怎么做的？首先随机选择一条直线进行分类。然后找到第一个分类错误的点，如果这个点表示正类，被误分为负类，即乘积<0，那表示w和x夹角大于90度，其中w是直线的法向量。所以，x被误分在直线的下侧（相对于法向量，法向量的方向即为正类所在的一侧），修正的方法就是使w和x夹角小于90度。通常做法是，W<-W+YX,Y=1,如图右上角所示，一次或多次更新后的W+YX与x夹角小于90度，能保证x位于直线的上侧，则对误分为负类的错误点完成了直线修正。

同理，如果是误分为正类的点，即乘积>0，那表示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.”实际操作中，可以一个点一个点地遍历，发现分类错误的点就进行修正，直到所有点全部分类正确。这种被称为Cyclic PLA。

具体的过程示例如下

那么在这个过程中就会有两个问题：
• 算法迭代一定会停下吗？
• 如果停下了是否一定有g接近于f?在其中的过程中是否有接近于f的g存在呢？

那么PLA什么时候会停下来呢？根据PLA的定义，当找到一条直线，能将所有平面上的点都分类正确，那么PLA就停止了。要达到这个终止条件，就必须保证D是线性可分（linear separable）。如果是非线性可分的，那么PLA就不会停止。

对于线性可分的情况，如果有这样一条直线，能够将正类和负类完全分开，令这时候的目标权重为Wf，则对每个点，必然满足Yn=sign(Wf^TXn)，即对任一点：

PLA会对每次错误的点进行修正，更新权重Wt+1的值，如果Wt+1与Wf越来越接近，数学运算上就是内积越大，那表示Wt+1是在接近目标权重Wf，证明PLA是有学习效果的。所以，我们来计算Wt+1与Wf的内积：

从推导可以看出， Wt+1与Wf的内积跟与的内积相比更大了。似乎说明了Wt+1更接近Wf，但是内积更大，可能是向量长度更大了，不一定是向量间角度更小。所以，下一步，我们还需要证明Wt+1与Wf向量长度的关系：

Wt只会在分类错误的情况下更新，最终得到的||Wt+1^{2||相比||Wt}2||的增量值不超过MAX||Xn^2||。也就是说， Wt的增长被限制了， Wt+1与Wt向量长度不会差别太大！如果令初始权值W0=0，那么经过T次错误修正后，有如下结论：

上一部分，我们证明了线性可分的情况下，PLA是可以停下来并正确分类的，但对于非线性可分的情况， 实际上并不存在，那么之前的推导并不成立，PLA不一定会停下来。所以，PLA虽然实现简单，但也有缺点：

对于非线性可分的情况，我们可以把它当成是数据集D中掺杂了一下noise，事实上，大多数情况下我们遇到的D，都或多或少地掺杂了noise。这时，机器学习流程是这样的：

在非线性情况下，我们可以把条件放松，即不苛求每个点都分类正确，而是容忍有错误点，取错误点的个数最少时的权重w：

事实证明，上面的解是Nphard问题，难以求解。然而，我们可以对在线性可分类型中表现很好的PLA做个修改，把它应用到非线性可分类型中，获得近似最好的g。修改后的PLA称为Packet Algorithm。它的算法流程与PLA基本类似，首先初始化权重，计算出在这条初始化的直线中，分类错误点的个数。然后对错误点进行修正，更新w，得到一条新的直线，在计算其对应的分类错误的点的个数，并与之前错误点个数比较，取个数较小的直线作为我们当前选择的分类直线。之后，再经过n次迭代，不断比较当前分类错误点个数与之前最少的错误点个数比较，选择最小的值保存。直到迭代次数完成后，选取个数最少的直线对应的w，即为我们最终想要得到的权重值。

如何判断数据集D是不是线性可分？对于二维数据来说，通常还是通过肉眼观察来判断的。一般情况下，Pocket Algorithm要比PLA速度慢一些。

最后总结一下，本节课主要介绍了线性感知机模型，以及解决这类感知机分类问题的简单算法：PLA。我们详细证明了对于线性可分问题，PLA可以停下来并实现完全正确分类。对于不是线性可分的问题，可以使用PLA的修正算法Pocket Algorithm来解决。