林轩田机器学习基石课程个人笔记-第二讲

前一讲对于机器学习有了初步的认识,这一讲学习了一个很基本的模型:感知机模型。
林轩田机器学习基石课程个人笔记-第二讲

为了说明我们的感知机模型,这里我们首先举一个例子:当我们去银行申请信用卡的时候,我们需要填写一些相关的信息,然后银行审查后会决定是否发放。比如我们的信息有如下几种
林轩田机器学习基石课程个人笔记-第二讲
有了上面的信息后,我们怎么做呢?其中一种简单的做法就是对于每一个数据赋予一个权重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+12||相比||Wt2||的增量值不超过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来解决。
林轩田机器学习基石课程个人笔记-第二讲

上一篇:2021年R1快开门式压力容器操作找解析及R1快开门式压力容器操作模拟试题


下一篇:林轩田机器学习2