统计学习方法(一):感知机

感知机

模型

感知机是一种二类分类的线性分类模型,属于判别模型。感知机的数据集要求线性可分。 f(x)=sign(ωx+b) 其中 sign(x)={1,x01,x<0 ωx+b=0 决定了将数据分为正负两类的超平面。

学习策略

对于误分类的数据 (xi,yi)yi(ωxi+b)>0 则误分类点 xi 到超平面的距离为 1||w||yi(ωxi+b) ||ω||ωL2 范数,所有误分类点到超平面的总距离为 1||w||xiMyi(ωxi+b) 其中 M 为所有误分类点到集合。

忽略1||w||项,得感知机学习的经验风险函数 L(ω,b)=xiMyi(ωxi+b) 显然损失函数是非负的,若无误分类点,损失函数值为0,误分类点越少,损失函数值越小。

感知机学习算法

原始形式

由上文知感知机的学习目标为 minω,bL(ω,b)=xiMyi(ωxi+b) 算法学习是误分类驱动的,采用随机梯度下降法,有 ωL(ω,b)=xiMxiyibL(ω,b)=xiMyi 则更新方式为 ωω+ηxiyi

bb+ηyi

该学习方法的直观解释为:当一个实例点被误分类,则调整 ωb 的值,使超平面向误分类点到一侧移动,以减少误分类点与超平面间的距离,知道超平面越过该误分类点使其被正确分类。

感知机算法由于采用不同的初值或选取不同的误分类点,解可能会不同

算法的收敛性

为便于叙述,令 ω^=(ωT,b)Tx^=(xT,1)T,有 ω^x^=ωx+b

  1. 存在满足条件 ||ω^opt||=1 的超平面 ||ω^optx^||=ωoptx+bopt=0 将训练数据集完全正确分开,且存在 γ>0,对所有 i=1,2,,N

yi(ω^optx^i)=yi(ωoptxi+bopt)γ

  1. R=max1iN||x^i||,则该算法在训练数据集上误分类的次数 k 满足不等式

k(Rγ)2

证明如下:

  1. 由于训练数据集数线性可分的,则存在超平面可将训练数据集完全正确分开,任取符合条件的超平面 ||ω^optx^||=ωoptx+bopt=0,通过缩放调整 ω^opt=1。此时对于训练数据集,有 yi(ω^optx^i)=yi(ωoptxi+bopt)>0 所以存在 γ=mini{yi(ωoptxi+bopt)} 使 yi(ω^optx^i)=yi(ωoptxi+bopt)γ
  2. 首先参数 ω^ 对误分类点有如下更新方法 ω^k=ω^k1+ηx^iyi,其中 ω^k1 为第 k 个误分类实例 (这里应理解为第 k 次更新误分类而不是第 k 个误分类点) 更新前的权重向量。对更新方法的两侧同乘 ω^opt,有 ω^kω^opt=ω^k1ω^opt+ηyiω^optx^iω^k1ω^opt+ηγω^0=0,递推得 (1)ω^kω^optω^k1ω^opt+ηγω^k2ω^opt+2ηγkηγ 对更新方法的范数两边平方有 ||ω^k||2=||ω^k1||2+2ηx^iyiω^k1+η2||x^i||2 由于 yi{+1,1} ,上式右边第三项的 yi2=1 被省略,且对于误分类点有 yi(ω^k1x^i)0(这里为小于等于,不影响最后的结果),则上式满足 (2)||ω^k||2=||ω^k1||2+2ηx^iyiω^k1+η2||x^i||2||ω^k1||2+η2||x^i||2||ω^k1||2+η2R2||ω^k2||2+2η2R2kη2R2 结合公式 (1) 和 (2),有 kηγω^kω^opt||ω^k||||ω^opt||kηRk2γ2kR2k(Rγ)2 于是我们可以得到误分类的次数 k 是有上界的,算法可以经过有限次搜索将训练数据完全线性分开,即算法是收敛的。