支持向量机的软间隔与正则化

看到西瓜书上有些东西写的不是特别清楚，结合李航的《统计学习方法》，把软间隔与正则化知识点重新整理了一下。
先给出支持向量机的基本形式：$\begin{aligned} &\min \limits_{w,b} \frac{1}{2} \left\|w\right\|^2\\s.t.\, &y_i(w^Tx_i+b)\ge 1,\:i=1,2,...,m \end{aligned}$s.t.​w,bmin​21​∥w∥2yi​(wTxi​+b)≥1,i=1,2,...,m​
之前支持向量机的普通形式都是假设样本点是线性可分的，也就是说存在一个超平面能将不同类的样本完全划分开，而现实世界中往往很难达到这种要求。我们的解决办法是允许支持向量机在一些样本上出错。由此引出了“软间隔”的概念。如下图：也就意味着某些样本点$(x_i,y_i)$(xi​,yi​)不能满足函数间隔大于等于1的约束条件,有些正样本的点会跑到负样本的区间，有些负样本的会跑到正样本的区间范围。

为了解决这个问题，可以对每个样本点$(x_i,y_i)$(xi​,yi​)引进一个松弛变量$\xi_i\ge0$ξi​≥0,使函数间隔加上松弛变量大于等于1.也就是$y_i(w^Tx_i+b)+\xi_i\ge 1$yi​(wTxi​+b)+ξi​≥1$y_i(w^Tx_i+b)\ge 1-\xi_i$yi​(wTxi​+b)≥1−ξi​同时，对每个松弛变量$\xi_i$ξi​,支付一个代价$\xi_i$ξi​.目标函数由原来的$\frac{1}{2} \left\|w\right\|^2$21​∥w∥2变成了:$\frac{1}{2} \left\|w\right\|^2+C\sum\limits_{i=1}^{N}\xi_i$21​∥w∥2+Ci=1∑N​ξi​,这里的$C>0$C>0称为惩罚参数，变大时对误分类的惩罚增大，减小时对误分类的惩罚减小。上面的最小化目标函数包含两层含义：使$\frac{1}{2} \left\|w\right\|^2$21​∥w∥2尽可能小也就是间隔尽量大，同时使误分类点的个数尽量小，$C$C是调和二者的系数，线性不可分的问题就可转化成下面的凸二次规划：$\begin{aligned}&\min\limits_{w,b,\xi}\qquad \frac{1}{2} \left\|w\right\|^2+C\sum\limits_{i=1}^{N}\xi_i\\&s.t.\qquad y_i(w^Tx_i+b)\ge 1-\xi_i,\:i=1,2,...,N\\&\qquad\qquad\xi_i\ge0,i=1,2,...,N\end{aligned}$​w,b,ξmin​21​∥w∥2+Ci=1∑N​ξi​s.t.yi​(wTxi​+b)≥1−ξi​,i=1,2,...,Nξi​≥0,i=1,2,...,N​上述问题可转化成朗格朗日函数：$L(w,b,\alpha,\xi,\mu)=\frac{1}{2} \left\|w\right\|^2+C\sum\limits_{i=1}^{N}\xi_i+\sum\limits_{i=1}^{m}\alpha_i(1-\xi_i-y_i(w^Tx_i+b))-\sum\limits_{i=1}^{m}\mu_i\xi_i\qquad①$L(w,b,α,ξ,μ)=21​∥w∥2+Ci=1∑N​ξi​+i=1∑m​αi​(1−ξi​−yi​(wTxi​+b))−i=1∑m​μi​ξi​①$\alpha_i\ge0$αi​≥0,$\mu_i\ge0$μi​≥0是朗格朗日乘子.令$L(w,b,\alpha,\xi,\mu)$L(w,b,α,ξ,μ)对$w,b,\xi_i$w,b,ξi​的偏导为0可得：$w=\sum\limits_{i=1}^{m}\alpha_iy_ix_i\\0=\sum\limits_{i=1}^{m}\alpha_iy_i\\C=\alpha_i+\mu_i$w=i=1∑m​αi​yi​xi​0=i=1∑m​αi​yi​C=αi​+μi​,将上面三个式子代入①式得到原问题的对偶问题：$\begin{aligned}&\max\limits_{\alpha}\sum\limits_{i=1}^{m}\alpha_i-\frac{1}{2}\sum\limits_{i=1}^{m}\sum\limits_{j=1}^{m}\alpha_i\alpha_jy_iy_jx_i^Tx_j\\&s.t.\sum\limits_{i=1}^{m}\alpha _iy_i=0\\&0\leq\alpha_i\leq C,i=1,2,...,m\end{aligned}$​αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​s.t.i=1∑m​αi​yi​=00≤αi​≤C,i=1,2,...,m​
还需满足KKT条件：
$\begin{cases}\alpha_i\ge0,\mu_i\ge0,\\y_if(x_i)-1+\xi_i\ge0,\\\alpha_i(y_if(x_i)-1+\xi_i)=0,\\\xi_i\ge0,\mu_i\xi_i=0\end{cases}$⎩⎪⎪⎪⎨⎪⎪⎪⎧​αi​≥0,μi​≥0,yi​f(xi​)−1+ξi​≥0,αi​(yi​f(xi​)−1+ξi​)=0,ξi​≥0,μi​ξi​=0​,之后的情况就和线性可分一样了，可用SMO或者其它方法进一步求解。