本内容是《统计学习方法》(第2版)中的第二章,可以与第七章中的支持向量机(SVM)相结合进行学习。
一、感知机模型
感知机是一种二分类的线性模型,该方法对所分类的数据要求非常严格,数据必须是线性可分的,否则无法对其进行二分类,这对生活所遇到的数据来说是一项即为严格的条件,因此在使用感知机对数据进行二分类时,一定要确认数据是否是线性可分的。
感知机的数学定义为:
假设输入空间(特征空间)X⊆Rn,输出空间是Y={+1,−1}。输入x∈X表示实例的特征向量,对应于输入空间的(特征空间)的点;输出y∈Y表示实例的类别。由输入空间到输出空间的如下函数: f(x)=sign(w⋅x+b) 称为感知机。其中,w和b为感知机参数,w∈Rn叫做权值或者权值向量,b∈R叫作偏置。w⋅x表示w和x的內积。sign是符号函数。
感知机的几何表示如下
从这个几何表示中可以看出,对于线性可分的数据集,我们可以找到一个超平面S对数据集进行二分类;对于线性不可分的数据集是不能进行二分类的,例如对于异或运算,不能找到一个平面将这两类点进行分类。
二、感知机学习策略
2.1 感知机学习算法的原始形式
首先,我们根据感知机的几何表示,可以容易得到输入空间Rn中任一点x0到超平面的距离为
1||w|||w⋅x0+b|对于误分类的点(xi,yi)来说,其到超平面的距离就是
−1||w||yi(w⋅xi+b)因此在给定数据集{T={(x1,y1),(x2,y2),...,(xN,yN)}}, 其中xi∈Rn,yi∈{+1,−1},i=1,2,...,N,感知机学习的损失函数定义为
L(w,b)=−∑xi∈Myi(w⋅xi+b)其中M为误分类点的集合,与误分类点到超平面的距离不同的是,这里缺少了1‖w‖,由于这一项可以认为是一个常数项,因此可以忽略,同时为了方面计算,我们往往会选取一个单位向量作为这个超平面的法向量。
有了上面的损失函数,我们就可以将求感知机模型参数w,b的问题表示为如下的最优化问题
minw,bL(w,b)=−∑xi∈Myi(w⋅xi+b)针对上述的损失函数极小化问题,可以采用随机梯度下降法。首先,任意选择一个超平面w0,b0,然后用梯度下降法不断地极小化目标函数,极小化过程中不是一次对所有误分类的点的梯度下降,而是一次随机选取一个误分类点使其梯度下降。可以得到损失函数L对w与b的梯度分别为
∇wL(w,b)=−∑xi∈Myixi∇bL(w,b)=−∑xi∈Myi因此对于误分类点(xi,yi),对w,b进行更新:
w←w+ηyixib←b+ηyi其中η(0<η≤1)是步长,也称为学习率。这样通过多次迭代,就可以得到使损失函数不断减小,直到为0。因此也就可以得到感知机学习算法的原始形式
输入:训练数据集{T={(x1,y1),(x2,y2),...,(xN,yN)}}, 其中xi∈Rn,yi∈{+1,−1},i=1,2,...,N;学习率η(0<η≤1);
输出:w,b;感知机模型f(x)=sign(w⋅x+b)。
(1)选取初值w0,b0;
(2)在训练集中选取数据(xi,yi);
(3)如果yi(w⋅xi+b)≤0,
w←w+ηyixib←b+ηyi(4)转至(2),直至训练集中没有误分类点。
2.2 感知机算法的对偶形式
对偶形式的基本想法是,将w和b表示为实例xi和标记yi的线性组合的形式,通过求解其系数而求得w和b。当学习率η选定了之后,模型参数w,b每次的增量是固定的,分别为ηyixi与ηyi。因此对于误分类点(xi,yi),参数w,b修改了ni次,则参数关于该误分类点的增量就为αiyixi和αiyi,其中αi=niη。由于参数的初始值可以任意设定,因此为了便于计算和表示,设置w0,b0均为0,则最终学习到的参数w,b为
w=N∑i=1αiyixib=N∑i=1αiyi其中αi≥0,i=1,2,...,N。与感知机算法的原始形式相似,可以得到感知机算法的对偶形式:
输入:训练数据集训练数据集{T={(x1,y1),(x2,y2),...,(xN,yN)}}, 其中xi∈Rn,yi∈{+1,−1},i=1,2,...,N;学习率η(0<η≤1);
输出:α,b;感知机模型f(x)=sign(∑Nj=1αjyjxj⋅x+b),其中α=(α1,α2,...,αN)T。
(1)α←0,b←0;
(2)在训练集中选取数据(xi,yi);
(3)如果yi(∑Nj=1αjyjxj⋅xi+b)≤0,
αi←αi+ηb←b+ηyi(4)转至(2),直至训练集中没有误分类点。
对偶形式中训练实例仅以內积的形式出现。为了方便,可以预先将训练集中实例间的內积计算出来并以矩阵的形式存储,这个矩阵就是所谓的Gram矩阵:
GG=[xi⋅xj]N×N三、小结
从上述两种感知机学习算法中可以看出,对于线性可分的数据集,初值的选择与数据点选择的顺序都会影响最后参数的计算结果,同时也说明,感知机算法的结果不是唯一的,有无穷多解,这与初值的设定与数据点的选择顺序有关。对于线性不可分的数据集,在训练中会使得参数进行震荡,而不会收敛,所以感知机只能对线性可分的数据集进行二分类,若需要对非线性可分的数据集进行二分类,则需要用到支持向量机。