线性支持向量机

松弛变量和惩罚代价

线性不可分意味着某些样本点 <nobr> (xi,yi) </nobr>不能满足函数间隔大于等于1的约束条件。可以对每个样本点 <nobr> (xi,yi) </nobr>引入一个松弛变量 <nobr> ξi≥0 </nobr>，使函数间隔加上松弛变量大于等于1.这样，约束条件变为
<nobr> yi(wi⋅xi+b)≥1−ξi </nobr>
同时，对每个松弛变量 <nobr> ξi </nobr>，支付一个代价 <nobr> ξi </nobr>，目标函数变成
<nobr> 12||w||2+C∑i=1Nξi (7.31) </nobr>
这里C>0称为惩罚参数，C较大对误分类惩罚增大。最小化
目标函数(7.31)包含两层含义：使间隔尽量大，同时使得误分类点个数尽量少。

原始问题

线性不可分支持向量机的学习问题变成如下凸二次规划问题（原始问题）

<nobr> minw,b,ξ12||w||2+C∑i=1Nξi(7.32)s.t.yi(w⋅xi+b)≥1−ξi,i=1,...,N(7.33)ξi≥0,i=1,...N(7.33) </nobr>

原始问题(7.32)-(7.34)是一个凸二次规划问题。可以证明w的解是唯一的，但b的解可能不唯一，而是存在于一个区间。

学习的对偶算法

对偶问题

原始问题(7.32)-(7.34)的对偶问题是

<nobr> mina12∑i=1N∑j=1Naiajyiyj(xi⋅xj)−∑i=1Nai(7.37)s.t.∑i=1Naiyi=0(7.38)0≤ai≤C,i=1,...,N(7.39) </nobr>

拉格朗日函数

<nobr> L(w,b,a)=12||w||2+C∑i=1Nξi−∑Ni=1ai(yi(w⋅xi+b)−1+ξi)−∑Ni=1μiξi (7.40) </nobr>，其中 <nobr> ai≥0,μi≥0 </nobr>

拉格朗日对偶问题

根据拉格朗日对偶性，原始问题的对偶问题是极大极小问题：
<nobr> maxa,μminw,b,ξL(w,b,ξ,a,μ) </nobr>
为了得到对偶问题的解，先求L对 <nobr> w,b,ξ </nobr>的极小，再求对 <nobr> a,μ </nobr>的极大
1. 求 <nobr> minw,b,ξL(w,b,ξ,a,μ) </nobr>

<nobr> ∇wL(w,b,ξ,a,μ)∇bL(w,b,ξ,a,μ)∇ξiL(w,b,ξ,a,μ)得w∑i=1NC−=w−∑i=1Naiyixi=0=−∑i=1Naiyi=0=C−ai−μi=0=∑i=1Naiyixi (7.41)aiyi=0 (7.42)ai−μi=0 (7.43) </nobr>

将式(7.41)-(7.43)带入拉格朗日函数(7.40)，得
<nobr> minw,b,ξL(w,b,ξ,a,μ)=−12∑i=1N∑j=1Naiajyiyj(xi⋅xj)+∑i=1Nai </nobr>
2. 求 <nobr> minw,b,ξL(w,b,ξ,a,μ)对a的极大，即是对偶问题 </nobr>
<nobr> s.t.maxa−12∑i=1N∑j=1Naiajyiyj(xi⋅xj)+∑i=1Nai(7.44)∑i=1Naiyi=0(7.45)C−ai−μi=0(7.46)μi≥0,(7.47)ai≥0,i=1,2,..,N(7.48) </nobr>

将对偶最优化问题(7.44)-(7.48)进行变换；利用灯饰约束(7.46)消取 <nobr> μi </nobr> ，只留下变量 <nobr> ai </nobr> ，并将约束(7.46)-(7.48)写成
<nobr> 0≤ai≤C </nobr>
将上式目标函数由求极大转成求极小，得到对偶问题(7.37)-(7.39)。

由于原始问题(7.32)-(7.34)满足弱化的Slater条件，对偶问题(7.37)-(7.39)的最优值和原始问题最优值相同，设 <nobr> w∗,b∗,ξ∗ </nobr>是原始问题最优解， <nobr> a∗,μ∗ </nobr>是对偶问题最优解，根据KKT条件， <nobr> w∗,b∗,ξ∗,a∗,μ∗ </nobr>满足：

<nobr> ∇wL(w,b,ξ,a,μ)∇bL(w,b,ξ,a,μ)∇ξiL(w,b,ξ,a,μ)1−ξ∗−yi(w∗⋅xi+b∗)ξ∗a∗iμ∗ia∗i⋅[1−ξ∗−fyi(w∗⋅xi+μ∗iξ∗i=w−∑i=1Naiyixi=0(7.52)=−∑i=1Naiyi=0=C−ai−μi=0≤0≥0≥0≥0b∗)]=0(7.53)=0(7.54) </nobr>

由式(7.53)-(7.54)知，若存在
<nobr> 0<a∗j<C </nobr> ，则
<nobr> 0<C−μi<C⇒μi>0μiξi=0⇒ξi=0 </nobr>

<nobr> yj(w∗⋅xj+b∗)−1=0 </nobr>

由此，分离超平面可以写成
<nobr> ∑i=1Na∗iyi(x⋅xi)+b∗ </nobr>
决策函数
<nobr> f(x)=sign(∑i=1Na∗iyi(x⋅xi)+b∗) (7.56) </nobr>
由于对任一适合条件 <nobr> 0<a∗j<C </nobr>的 <nobr> a∗j </nobr>，都可求出 <nobr> b∗ </nobr>。从理论上，原始问题对b的解可能不唯一，然而在实际应用中，往往只会出现算法叙述的情况。

支持向量

在线性不可分的情况下，对偶问题中对应于 <nobr> a∗i>0 </nobr>的样本点 <nobr> (xi,yi) </nobr>的实例 <nobr> xi </nobr>称为支持向量（软间隔的支持向量）。
实例 <nobr> xi </nobr>到间隔边界的距离 <nobr> ξi||w|| </nobr>。
软间隔的支持向量 <nobr> xi </nobr>或者在间隔边界上，或者在间隔边界于分离超平面之间，或者在分离超平面误分一侧。
若 <nobr> a∗i<C </nobr>,则 <nobr> ξi=0 </nobr>，支持向量 <nobr> xi </nobr>恰好落在间隔边界上；
若 <nobr> a∗i=C,0<ξi<1, </nobr>则分类正确， <nobr> xi </nobr>在间隔边界与分离超平面之间；
若 <nobr> a∗i=C,ξi=1 </nobr>,则 <nobr> xi </nobr>在分离超平面上；
若 <nobr> a∗i=C，ξi>1， </nobr>则 <nobr> xi </nobr>位于分离超平面误分一侧。

合页损失函数

线性支持SVM还有另外一种解释，就是最小化以下目标函数
<nobr> ∑i=1N[1−yi(w⋅xi+b)]++λ||w||2 </nobr>
目标函数的第1项是经验损失或经验风险，函数
<nobr> L(y(w⋅x+b))=[1−y(w⋅x+b)]+ </nobr>
称为合页损失函数。
当样本点被正确分类且函数间隔（确信度） <nobr> yi(w⋅xi+b) </nobr>大于1时，损失是0，否则损失是 <nobr> 1−yi(w⋅xi+b) </nobr>。所以即使样本点被正确分类，损失也可能不是0。
下面证明线性支持向量机原始最优化问题：

<nobr> minw,b,ξ12||w||2+C∑i=1Nξis.t.yi(w⋅xi+b)≥1−ξi,i=1,...,N(7.61)ξi≥0,i=1,...,N(7.62) </nobr>

等价于最优化问题
<nobr> minw,b∑i=1N[1−yi(w⋅xi+b)]++λ||w||2 </nobr>
证明
令 <nobr> [1−yi(w⋅xi+b)]+=ξi(7.64) </nobr>
则 <nobr> ξi≥0 </nobr> ，式(7.62)成立。由式(7.64)，
当 <nobr> 1−yi(w⋅xi+b)>0 </nobr> 时，有 <nobr> yi(w⋅xi+b)=1−ξi </nobr> ；
当 <nobr> 1−yi(w⋅xi+b)≤0 </nobr> 时, <nobr> ξi=0 </nobr> ，有 <nobr> yi(w⋅xi+b)≥1−ξi </nobr> 。故式(7.61)成立。于是 <nobr> w,b,ξ </nobr> 满足约束条件(7.61)-(7.62)。
由式(7.64)有，
<nobr> [1−yi(w⋅xi+b)]+=[ξi]+=ξi </nobr> ,所以最优化问题(7.63)可写成
<nobr> minw,b∑i=1Nξi+λ||w||2若取λ=12C，则minw,b1C(12||w||2+C∑i=1Nξi) </nobr>

与式(7.60)等价。

参考文献

《统计学习方法》第7章