笔记(总结)-SVM(支持向量机)的理解-2

上一篇我们讨论了SVM的建模由来与推导过程，最终得出了SVM的对偶问题和解的形式，不过这都基于一个重要前提，即样本集是线性可分的。为了解决线性不可分情况下的分类问题，我们引入soft margin SVM，即软间隔SVM。

---

为了处理上述情况，我们不再要求样本集全部位于“楚河汉界”外，放宽限制，允许数据点进入“楚河汉界”甚至错分，引入松弛变量ξ$\xi$，如下所示：

此时对应的约束条件为：

⎧⎩⎨⎪⎪wTx+b≥1−ξ, yi=1wTx+b≤−1+ξ, yi=−1ξi≥0$$\{\begin{array}{l}{w}^{T}x+b\ge 1-\xi ,y_i=1\\ w^{T}x+b\le -1+\xi ,y_i=-1\\ {\xi }_i\ge 0\end{array}$$

原问题转化为：

min12||w||2+C∑iξi$min\frac{1}{2}||w|{|}^2+C\sum _i{\xi }_i$

s.t. yi(wTxi+b)≥1−ξi, ξi≥0$s.t.y_i(w^T{x}_i+b)\ge 1-{\xi }_i,{\xi }_i\ge 0$

其中C$C$为惩罚因子，可以看到当C$C$取很大时，优化目标函数会导致xii$x{i}_i$很小，尽量减小甚至避免越界和错分情况出现。当C$C$很小时，会一定程度上对越界和错分情况有所容忍。

将约束写成gi≤0$g_i\le 0$的形式，构造拉格朗日函数：

f(w)=12||w||2$f(w)=\frac{1}{2}||w|{|}^2$

gi(w)=1−ξi−yi(wTxi+b),    hi(ξ)=−ξi$g_i(w)=1-{\xi }_i-y_i(w^T{x}_i+b),h_i(\xi )=-{\xi }_i$

L(w,α,β)=f(w)+∑iαigi(w)+∑iβihi(ξ)$L(w,\alpha ,\beta )=f(w)+\sum _i{\alpha }_i{g}_i(w)+\sum _i{\beta }_i{h}_i(\xi )$

推导对偶问题的过程同上一篇。极值在偏导为0处取到，令：

∂L∂w=0, ∂L∂b=0, ∂L∂ξi=0$\frac{\mathrm{\partial }L}{\mathrm{\partial }w}=0,\frac{\mathrm{\partial }L}{\mathrm{\partial }b}=0,\frac{\mathrm{\partial }L}{\mathrm{\partial }{\xi }_i}=0$

得到：

w=∑iαiyixi, ∑iαiyi=0, C=αi+βi$w=\sum _i{\alpha }_i{y}_i{x}_i,\sum _i{\alpha }_i{y}_i=0,C={\alpha }_i+{\beta }_i$

代回原函数，得到对偶问题：

maxW(α)=∑iαi−12∑i∑jαiαjyiyjxTixj$maxW(\alpha )=\sum _i{\alpha }_i-\frac{1}{2}\sum _i\sum _j{\alpha }_i{\alpha }_j{y}_i{y}_j{x}_i^T{x}_j$

s.t. ∑iαiyi=0, 0≤αi≤C$s.t.\sum _i{\alpha }_i{y}_i=0,0\le {\alpha }_i\le C$

此时对应的KKT条件为：

⎧⎩⎨⎪⎪⎪⎪⎪⎪αi≥0βi≥0yi(wTx+b)≥1−ξiξi≥0αi[1−ξi−yi(wTx+b)]=0 βi(−ξi)=0$$\{\begin{array}{l}{\alpha }_i\ge 0\\ {\beta }_i\ge 0\\ y_i(w^{T}x+b)\ge 1-{\xi }_i\\ {\xi }_i\ge 0\\ {\alpha }_i[1-{\xi }_i-y_i(w^{T}x+b)]=0\\ {\beta }_i(-{\xi }_i)=0\end{array}$$

可以看到，最终需要求解的W(α)$W(\alpha )$与之前形式是一致的，不同的只是约束条件的变化。根据KKT条件对αi${\alpha }_i$进行讨论：

• 当αi>0${\alpha }_i>0$，有yi(wTx+b)≥1−ξi$y_i(w^{T}x+b)\ge 1-{\xi }_i$，xi$x_i$为支持向量
• 当αi<C${\alpha }_i<C$，有βi>0${\beta }_i>0$，推得ξi=0${\xi }_i=0$，xi$x_i$在边界上
• 当αi=C${\alpha }_i=C$，有βi=0${\beta }_i=0$，此时ξi${\xi }_i$大小不确定。当ξi>1${\xi }_i>1$时，该样本被错误分类；当0≤ξi≤1$0\le {\xi }_i\le 1$，该样本在“楚河汉界内部”，被正确分类。

此时我们便可利用Soft Margin SVM来处理线性不可分的问题。