1. SMO
- 设训练样本数目为N,原始观测空间的维数为m。支持向量机所对应的二次规划问题往往使用SMO(Sequential Minimal Optimization)算法求解。SMO算法不断地求解仅涉及两个优化变量的二次规划问题。设给定训练样本为{(xi,yi)}i=1N,对偶问题为:
D(α)=i=1∑Nαi−21i=1∑Nj=1∑NαiαjyiyjxiTxjs.t.i=1∑Nαiyi=0,αi>0,i=1,…,N。
具体地,在每次迭代时,选中两个优化变量αi∗和αj∗,同时保持其它变量固定,求解关于αi∗和αj∗的二次规划问题。请结合线性支持向量机(分为线性可分和线性不可分情况),给出在每次迭代过程中关于两个变量αi∗和αj∗的解。
SVM使用一种非线性映射,把原训练数据映射到较高的维。在新的维上,搜索最佳分离超平面,两个类的数据总可以被超平面分开。
2. 线性可分
要找到具有“最大间隔”的划分超平面,即
w,bmax∣∣w∣∣2s.t.yi(wTxi+b)≥1,i=1,2,…,N.
等价于
w,bmax21∣∣w∣∣2s.t.yi(wTxi+b)≥1,i=1,2,…,N.
3. 线性不可分
线性可分问题的支持向量机学习方法,对线性不可分训练数据是不适用的,为了满足函数间隔大于1的约束条件,可以对每个样本(xi,yi)引进一个松弛变量ξi≥0,使函数间隔加上松弛变量大于等于1:
yi(w⋅xi+b)≥1−ξi
目标函数为
21∣∣w∣∣2+Cj=1∑Nξi
其中C>0为惩罚参数。
因此,最小化目标函数也就是使21∣∣w∣∣2尽量小,同时使误分类点的个数尽量小。线性不可分的线性支持向量机问题变成下面的凸二次规划问题:
w,b,ξmin21∣∣w∣∣2+Ci=1∑Nξis.t.yi(w⋅xi+b)≥1−ξi,i=1,2,…,N,ξi≥0,i=1,2,…,N
4. 对偶问题
使用拉格朗日乘子法得到其“对偶问题”:
L(w,b,α)=21∣∣w∣∣2+i=1∑Nαi(1−yi(wTxi+b))
其中α=(α1;α2;…;αm)。令L(w,b,α)中的w和b的偏导为0可得
w=i=1∑Nαiyixi,0=i=1∑Nαiyi.
即可将L(w,b,α)中的w和b消去,得到对偶问题
D(α)=i=1∑Nαi−21i=1∑Nj=1∑NαiαjyiyjxiTxjs.t.i=1∑Nαiyi=0,αi>0,i=1,…,N
5. SMO算法
约束∑i=1Nαiyi=0重写为:
αi∗yi∗+αj∗yj∗=c,αi∗≥0,αj∗≥0c=−k=i∗,j∗∑αkyk
用上式中的c消去D(α)中的αj:
αj∗=(c−αi∗yi∗)yj∗
假设i∗=1,j∗=2:
α2=(c−α1y1)y2=γ−sα1
γ为常数,s=y1y2。
Kij=K(xi,xi),f(xi)=j=1∑NyjαjKij+b,vi=f(xi)−j=1∑2yjαjKij−b
固定α1、α2,得到:
D(α)=α1+α2−21K11α12−21K22α22−y1y2K12α1α2−y1α1v1−y2α2v2+constant
取α1为变量,则得到一个关于α1的单变量二次规划问题,仅有的约束是α1≥0:
D(α1)=α1+γ−sα1−21K11α12−21K22(γ−sα1)2−sK12α1(γ−sα1)−y1α1v1−y2(γ−sα1)v2+constant
对α1求偏导以求得最大值,有
∂α1∂W(α1)=1−s−K11α1+sK22γ−K22α1−sK12γ+2K12α1−y1v1+y1v2=0
由此可得:
α1new=K11+K22−2K12y1(y1−y2+y2γ(K22−K12)+v2−v1)
根据v的定义,展开v得到:
v2−v1=f(x2)−f(x1)−α1y1K12−y2α2K22+y1α1K11+α2y2K12
规定误差项Ei=f(xi)−yi,取γ=sα1old+α2old,并规定η=K11+K22−2K12,
上式可化简为:
α1new=α1old+ηy1(E2−E1)
再考虑限制条件0≤αi≤c,(α1,α2)的取值只能为直线α1y1+α2y2=γ落在[0,C]×[0,C]矩形中的部分。

因此需要检查α2new的值以确认这个值落在约束区间之内:
α1new,clipped=⎩⎪⎨⎪⎧H,α1new>Hα1new,L≤α1new≤HL,α1new<L
其中
{L=max(0,α1−α2),H=max(C,C+α1+α2)L=max(0,α1+α2−C),H=max(C,α1−α2)y1=y2y1=y2
假设s=y1y2,则新的α2new为
α2new=α2old+s(α1old−α1new,clipped)