机器学习笔记之PLA算法

阅读本文需要线性代数基础,否则阅读体验很差。

这是我的第一篇原创,稍稍入门一下 Machine Learing 和 Deep Learning ,本篇参考视频 " 机器学习基石 " [ 台湾大学林轩田 ] ,以及其他机器学习书目。

PLA(Perceptron Learning Algorithm)感知器算法,是一个二元分类(Binary Classfication)的机器学习算法,对于二维或者高维的线性可分问题的分类,最终将问题分为两类——是或者不是。

1.Hypothesis Set

把测试集喂给算法,然后算法从他的Hypothesis Set 里经过一系列运算得到一个 方法G,使得这个G几乎接近目标F,使其能够得到正确的结果。

训练集包括数据和数据特征Xi,每个数据的数据特征包含很多种,把一系列数据特征集合看作一个向量(X1,X2,X3,...Xn),把每一种不同的数据特征乘以一个权重,类似大学成绩里的加权平均分,像专业课科目权重大一点,体育课权重小一点,这里就把权重写作Wi,这里的权重亦可以是负的,把这个公式的值与阈值threshold作比较,大于阈值即为正,小于阈值即为负,来做一个二维分类。可以用一个sign函数来区分。

为了方便计算,引入一个X为+1,将threshold当作W*X,从而前面的累加公式即可以从i=0开始,然后可以看作一个列向量与行向量的积,最后结果仍为一个常数最后得出的就是我们的一个Hypothesis,这个h就由权重和设置的门槛值决定,我们的目的就是计算出所有权值w和阈值threshold。

为了更清晰地说明这个感知器模型,来看一下其中二维的简单的例子。

图中X是默认为1,所以二维的图中有一个W,有一个W1乘以X1的第一个维度,一个W2乘以X2的第二个维度,输出即为图中的蓝圈和红叉,蓝圈为+1,红叉为-1,h就是图中的直线,sign函数的作用是取正负号,当函数内的值等于0的时候切换正负号,在平面上显示的就是一条直线,直线的一边为+1,另一边为-1,h对应图中的线,训练集的每个x对应图中的点,最后输出y对应想要圈还是叉,每一条线有不一样的预测规则。在这个模型上就是一条直线,称之为linear(binary) classifiers。注意一下,感知器线性分类不限定在二维空间中,在3D中,线性分类用平面表示,在更高维度中,线性分类用超平面表示。

2.Perceptron Learning Algorithm(PLA)

到这里我们知道了可能的Hypothesis Set,然后要选一条最好的线,所谓最好的线,就是目标函数,但是并不知道目标函数是什么,所以先要求在所有的线里找到一个预测函数,要求它在训练集里与目标函数特别接近,在一个二维空间上,会有无数条线,从这里面找到一条相对较优的预测函数是不可能的,所以选择一个h修正,使这条线变得更好。一开始的线记为W,如果这条线存在错误,肯定能找到某一个点XnYn,这个点的Xn与Wt作内积与想要的结果yn不一样,所以就要修正他。

来看视觉化效果,喂给机器这样的训练集,一部分数据对应圆圈 一部分数据对应红叉。

一轮随机找一个点,这条线与原点的连线是预测函数的法向量,所以这条线就是这样的然后算法找到了有一个点是错的,然后要把红色的线往黑色的线方向修正,修正完算法一直找发现有一个叉错误了,继续更新修正,更新了很多很多轮之后所有的圆圈在一边,红叉在另一边,就是已经完成的一个函数了,至少在训练集的数据下。

照这种思想,遇到个错误点就进行修正,不断迭代。要注意一点:每次修正直线,可能使之前分类正确的点变成错误点,这是可能发生的。但是没关系,不断迭代,不断修正,最终会将所有点完全正确分类(PLA前提是线性可分的)。这种做法的思想是“知错能改”,有句话形容它:“A fault confessed is half redressed.”

那么还有两个问题需要考虑

1). 这个算法一定会停下来吗?如果线性不可分怎么办?

2). 假设这个算法停下来了,拿到的这个预测函数和目标函数是不是一样的?

3.Guarantee of PLA

PLA的终止条件是找到一条线,把训练集分的完全不犯错误。这个条件的前提就是需要训练集是线性可分的Linear Separable.

先考虑PLA算法是不是一定会停下来,把这个资料都分得完全没有错误,PLA就停下来了,那么这个算法就要有一个条件,训练集一定要有一条线可以切开,也就是Linear Separable线性可分,如果是线性不可分,PLA是不会停止的。对于线性可分的情况下,假设有一条直线Wf

必然满足

这个Xn(t)里的t代表第几次循环,最后就是看Wt与Wf之间的关系是什么,到底接不接近,数学上可以用内积来判断是否接近,内积越大,表示两条线的距离越近,那就来计算Wf的转置和Wt+1的内积:

然而,内积越大不完全代表两个向量越接近,也有可能是向量的长度发生变化,所以还需要证明两个向量长度的关系:

因为Wt只会在错误的情况下更新,蓝色项即错误的点为负值,所以Wt+1增长只会靠红色项增长,红色项即为随便选的一个犯错的点,最大值就是离原点距离最远的那个点,所以与Xn^2作比较。Wt的增长被限制,所以Wt与Wt+1差别不会太大。

如果令初始权值w0=0,那么经过T次错误修正后,有如下结论:

下面贴出来该结论的具体推导过程:

以上图片引用自网络,以及机器学习基石PPT。

总结:本节课主要介绍了线性感知机模型,以及解决这类感知机分类问题的简单算法:PLA。我们详细证明了对于线性可分问题,PLA可以停下来并实现完全正确分类。

----------------------------------------------------

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20180516G1Z29200?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券