【自学笔记】支持向量机（3）——软间隔

引入

  上一回解决了SVM在曲线边界的上的使用，使得非线性数据集也能得到正确的分类。然而，对于一个大数据集来说，极有可能大体呈线性分类趋势，但是边界处混杂，若仍采用原来的方式，会得到极其复杂的超平面边界，浪费了算力。
  上述要求所有训练样本满足约束的分类方式称为硬分类。而允许部分样本不满足约束的分类方式则被称为软分类。

实现逻辑

  在实现软间隔的同时，我们既要保证模型的性能（违反约束的样本点尽量少），同时保证模型复杂度不要过高，我们需要设置一个损失函数来控制模型的样本点是否需要满足约束。
  最简单的，定义0/1损失函数${\ell }_{0/1}(z)$：

${\ell }_{0/1}(z)=\{\begin{array}{l}1,ifz<0\\ 0,otherwise\end{array}$

  并修改优化目标为：

$mi{n}_{\vec{w},b}\frac{1}{2}||\vec{w}|{|}^2+C{\sum }_{i=1}^m{\ell }_{0/1}(y_i({\vec{w}}^T{\vec{x}}_i+b)-1)$

  其中常数$C>0$，称为正则化参数，控制了对误分类样本的惩罚程度。而损失函数则决定这个样本点误分类是否需要产生惩罚。

  然而，0/1损失函数非凸，非连续，使得后续求解不方便。人们通常用其他一些函数来替代${\ell }_{0/1}(z)$，称为替代损失：

  以$hinge$损失为例，目标变成：

$mi{n}_{\vec{w},b}\frac{1}{2}||\vec{w}|{|}^2+C{\sum }_{i=1}^{m}max(0,1-y_i({\vec{w}}^T{\vec{x}}_i+b))$

  将求和符号后的部分记作松弛变量${\xi }_i\ge 0$，可重写为：

$mi{n}_{\vec{w},b}\frac{1}{2}||\vec{w}|{|}^2+C{\sum }_{i=1}^m{\xi }_i$
 
$s.t.y_i({\vec{w}}^T{\vec{x}}_i+b)\ge 1-{\xi }_i$
${\xi }_i\ge 0,i=1,2,...,m$

  松弛变量的值反映了样本点离群的程度。值越大，样本点离正确的分类区域越远。

  使用软间隔方法的SVM被称为软间隔支持向量机

求解

  问题被转化后，依然是一个二次规划问题，我们仍用拉格朗日乘子法得到拉格朗日函数：

$L(\vec{w},b,\vec{\alpha },\vec{\xi },\vec{\mu })=\frac{1}{2}||\vec{w}|{|}^2$
$+C{\sum }_{i=1}^m{\xi }_i$
$+{\sum }_{i=1}^m{\alpha }_i[1-{\xi }_i-y_i({\vec{w}}^T{\vec{x}}_i+b)]$
$-{\sum }_{i=1}^m{\mu }_i{\xi }_i$
其中${\alpha }_i\ge 0$, ${\mu }_i\ge 0$是拉格朗日乘子

  令$L(\vec{w},b,\vec{\alpha },\vec{\xi },\vec{\mu })$对$\vec{w},b,{\xi }_i$求导为$0$，得：

$\vec{w}={\sum }_{i=1}^m{\alpha }_i{y}_i{\vec{x}}_i$
$0={\sum }_{i=1}^m{\alpha }_i{y}_i$
$C={\alpha }_i+{\mu }_i$

  代回得：

$ma{x}_{\vec{\alpha }}{\sum }_{i=1}^m{\alpha }_i-\frac{1}{2}{\sum }_{i=1}^m{\sum }_{j=1}^m{\alpha }_i{\alpha }_j{y}_i{y}_j{\vec{x}}_i^T{\vec{x}}_j$
 
$s.t.{\sum }_{i=1}^m{\alpha }_i{y}_i=0$
$0\ge {\alpha }_i\ge C,i=1,2,...,m$

  不难发现，与硬间隔的对偶问题相比，只是把$0\le {\alpha }_i$改成了$0\le {\alpha }_i\le C$。

  更改后的KKT要求为：

1.互补松弛条件
  ${\alpha }_i[y_i(\vec{w}{\vec{x}}_i+b)-(1-{\xi }_i)]=0$
  ${\mu }_i{\xi }_i=0$
 
2.原始约束
  $y_i(\vec{w}{\vec{x}}_i+b)-(1-{\xi }_i)\ge 0$
  ${\xi }_i\ge 0$
3.对偶约束
  $0\le {\alpha }_i\le C$
  ${\sum }_{i=1}^m{\alpha }_i{y}_i=0$

  分析一下上面的式子，发现对任意样本$({\vec{x}}_i,y_i)$，总有${\alpha }_i=0$或$y_i(\vec{w}{\vec{x}}_i+b)-(1-{\xi }_i)=0$。（由第一个式子推得）

  当${\alpha }_i=0$，则说明该样本不会对$f(\vec{x})$有任何影响
  否则，有$y_i(\vec{w}{\vec{x}}_i+b)=1-{\xi }_i$，则该样本是支持向量

  注意，由于软间隔对边界附近的数据点进行了处理，支持向量的定义不再限制于完全在分类边界上的样本，而是规定为满足$y_{i}f({\vec{x}}_i)=1-{\xi }_i$这个式子的样本。

  而对于所有的支持向量，也有一些分类：

  在《机器学习》中，紧跟了一句话：

  由此可以看出，软间隔支持向量机的最终模型仅与支持向量有关，即通过采用$hinge$损失函数仍保持了稀疏性。

  这里作个解释：

一般化

  以上其实是以$hinge$损失函数替代$0/1$损失函数的例子，我们当然可以通过其他的损失函数来得到其他的学习模型，最终都会变成以下的一般形式：

$mi{n}_f\Omega (f)+C{\sum }_{i=1}m\ell (f({\vec{x}}_i),y_i)$

  前半部分的$\Omega (f)$称为结构风险（structural risk），是由模型的结构所产生的惩罚，如各种正则化，描述了模型$f$的各种性质。

  后半部分的$C{\sum }_{i=1}m\ell (f({\vec{x}}_i,y_i)$被称为经验风险，是模型在训练数据集上的平均损失，它衡量了模型在已知训练数据上的拟合程度。