机器学习总结(lecture 2)算法:感知机学习算法 (PLA)
lecture 2:感知机学习算法
Perceptron Learning Algorithm(PLA)
目录
1Perceptron Hypothesis Set(感知器假设集)
感知机是最简单的机器学习算法,一般作为机器学习的入门级算法,也很好理解,但是麻雀虽小,五脏俱全,机器学习大致的思想和过程都涉及到了。
感知机可以认为是线性二元分类器,我们有一些特征数据,根据这些特征数据我们线性回归出一个值,如果超过了某个阈值,我们就说YES,否则NO。
一个简单的现实例子就是信用卡的发放问题,银行得到用户的一些个人信息,比如年龄,收入,信用记录等。
针对这些信息我们赋予一些权重,这样我们就能够得到一个具体的数值,以此来判断是否发信用卡
感知机模型,就是当特征加权和与阈值的差大于或等于0,则输出h(x)=1;当特征加权和与阈值的差小于0,则输出h(x)=-1
- 而我们的目的就是计算出所有权值w和阈值threshold。
为了计算方便,通常我们将阈值threshold当做w0,引入一个x0=1的量与w0相乘,这样就把threshold也转变成了权值w0,简化了计算。h(x)的表达式做如下变换:
为了更清晰地说明感知机模型,我们假设Perceptrons在二维平面上,即。其中是平面上一条分类直线,直线一侧是正类(+1),直线另一侧是负类(-1)。权重w不同,对应于平面上不同的直线。
- 那么,我们所说的Perceptron,在这个模型上就是一条直线,称之为linear(binary) classifier。
注意一下,感知器线性分类不限定在二维空间中,在3D中,线性分类用平面表示,在更高维度中,线性分类用超平面表示,即只要是形如的线性模型就都属于linear(binary) classifier。
同时,需要注意的是,这里所说的linear(binary) classifier是用简单的感知器模型建立的,线性分类问题还可以使用logistic regression来解决,后面将会介绍。
2Perceptron Learning Algorithm (PLA)
我们的目的就是如何设计一个算法A,来选择一个最好的直线,能将平面上所有的正类和负类完全分开。
(1)我们可以使用逐点修正的思想,首先在平面上随意取一条直线,看看哪些点分类错误。
(2)然后开始对第一个错误点进行修正,即变换直线的位置,使这个错误点变成分类正确的点。
(3)接着,再对第二个、第三个等所有的错误分类点进行直线纠正,直到所有的点都完全分类正确了,就得到了最好的直线
- 这种“逐步修正”,就是PLA思想所在。
PLA是怎么运行的:W是直线的法向量,,W和X的夹角大于90度
按照这种思想,遇到个错误点就进行修正,不断迭代。
要注意一点:每次修正直线,可能使之前分类正确的点变成错误点,这是可能发生的。
但是没关系,不断迭代,不断修正,最终会将所有点完全正确分类。
(PLA前提是线性可分的)。这种做法的思想是“知错能改”。
3PLA停下的保证
PLA什么时候会停下来呢?根据PLA的定义,当找到一条直线,能将所有平面上的点都分类正确,那么PLA就停止了。要达到这个终止条件,就必须保证D是线性可分(linear separable)。如果是非线性可分的,那么,PLA就不会停止。
4不可分的数据与Packet Algorithm
对于非线性可分的情况,我们可以把它当成是数据集D中掺杂了一下noise,事实上,大多数情况下我们遇到的D,都或多或少地掺杂了noise。
- 在非线性情况下,我们可以把条件放松,即不苛求每个点都分类正确,而是容忍有错误点,取错误点的个数最少时的权重w
事实证明,上面的解是NP-hard问题,难以求解。
然而,我们可以对在线性可分类型中表现很好的PLA做个修改,把它应用到非线性可分类型中
修改后的PLA称为Packet Algorithm
- (1)它的算法流程与PLA基本类似,首先初始化权重w0,计算出在这条初始化的直线中,分类错误点的个数。
- (2)然后对错误点进行修正,更新w,得到一条新的直线,再计算其对应的分类错误的点的个数,并与之前错误点个数比较,取个数较小的直线作为我们当前选择的分类直线。
- (3)之后,再经过n次迭代,不断比较当前分类错误点个数与之前最少的错误点个数比较,选择最小的值保存。
- (4)直到迭代次数完成后,选取个数最少的直线对应的w,即为我们最终想要得到的权重值。
如何判断数据集D是不是线性可分?
对于二维数据来说,通常还是通过肉眼观察来判断的。
一般情况下,Pocket Algorithm要比PLA速度慢一些。
5总结
对于线性可分问题,PLA可以停下来并实现完全正确分类。
对于不是线性可分的问题,可以使用PLA的修正算法Pocket Algorithm来解决。