上一篇讲到的是SVM和各种核函数，能够保证分类边界以更复杂的方式分类，但是很容易过拟合(overfit)。

下面两张图，分别是用线性SVM与4维多项式核做出来的分类边界，你觉得哪个更好？

相信你肯定不会选右边。

事实上，数据在收集的过程中，会出现各种意外，导致异常值(outliers)的产生，比如左下角的〇，和右上角的×，如果为了把这些异常值正确分类，而提高模型复杂度，会降低模型的泛化能力，并导致overfitting。

这种overfitting会导致在训练集上准确率为100%，而在测试集上的准确率却惨不忍睹。

所以为了让模型的泛化能力更高，应该容许一些错误发生。

基于容许错误的思想，软间隔支持向量机(soft-margin SVM)诞生了，原始的SVM的定义如下：

$$ \min\limits_{b,w}\frac{1}{2}||w||^2\\ s.t. y_i(w^Tx_i+b)\ge 1 \ \ \ \ \ ,i = 1,2...,n $$

我们称之为硬间隔SVM，硬间隔SVM不允许有任何错误发生。而我们在此基础上，为了能够容忍错误，我们增加了一个惩罚参数$C$，让分类器可以误判，但要受到惩罚：

$$ \min\limits_{b,w}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^{n}\bigg[y_i\ne sgn(w^Tx_i+b)\bigg]\\ \begin{aligned} s.t.\quad &y_i(w^Tx_i+b)\ge 1&,i = 1,2...,n\\ &y_i(w^Tx_i+b)\ge -\infty&,i = 1,2...,n \end{aligned} $$

这样，就允许了有错误点的发生，但是要把它们放在最小化函数中，尽量让他们变得更小。

使用$C$来控制容忍度，$C$越大，就禁止错误更多，容忍度就越低。而$C$越小，则可以犯更多的错误。

这个公式有两个问题

1.这个问题不是线性(linear)的，不是QP问题了，这他妈怎么解？？

2.函数不能不能识别分类错误的程度，例如：下图中有两个样本点，A:差一点就分对，B:离分类超平面很远。哪个惩罚应该更高？当然是B! 但是现在的函数对他们一视同仁，这并不科学。

因此，为了解决这两个问题，我们引入$\xi$作为错误程度，来让分类器能够分辨出错误的大小，修改后的分类器如下：

$$ \min\limits_{b,w}\frac{1}{2}||w||^2+C\sum\limits_{i=1}^{n}\xi_i\\ \begin{aligned} s.t. &y_i(w^Tx_i+b)\ge 1-\xi_i &,i = 1,2...,n\\ \end{aligned} $$

其中，$\xi_i\ge0​$

这样，约束条件是$\xi$的一次式，最小化函数的第二项也是$\xi$的一次式。这个是QP问题，可以解的！

$C$越小，分类边界越大，$C$越大，则分类边界越小。

对偶形式

根据之前文章的内容，我们可以很容易的写出这个问题的对偶形式：

$$ \begin{aligned} L(b,w,\xi,\alpha,\beta)=&\frac{1}{2}||w||^2+C\cdot\sum\limits_{i=1}^{N}\xi_i\\ &+\sum\limits_{i=1}^N \alpha_i\cdot(1-\xi_i-y_i(w^Tx_i+b))+\sum\limits_{i=1}^{N}\beta_i\cdot(-\xi_i) \end{aligned} $$

之后，满足KKT条件公式，再用对偶形式解决下面问题(具体的操作见我之前写的文章支持向量机SVM 系列(2)——对偶方法)

$$ \max\limits_{\alpha_i\ge 0,\beta_u\ge0}\bigg( \min\limits_{b,w,\xi}L(b,w,\alpha,\beta) \bigg) $$

展开写，就是下面这个公式

$$ \begin{aligned} \max\limits_{\alpha_i\ge 0,\beta_u\ge0}\bigg( \min\limits_{b,w,\xi} &\frac{1}{2}||w||^2+C\cdot\sum\limits_{i=1}^{N}\xi_i\\ &+\sum\limits_{i=1}^N \alpha_i\cdot(1-\xi_i-y_i(w^Tx_i+b))+\sum\limits_{i=1}^{N}\beta_i\cdot(-\xi_i) \bigg) \end{aligned} $$

对$\xi_i$求偏导，可以得出：

$$ \frac{\partial L}{\partial \xi_i}=C-\alpha_i-\beta_i $$

又因为$\beta_i\ge 0$可以推出$C-\alpha_i\ge 0 $，也就是$0\le\alpha\le C$，然后将$\beta_i$用$C-\alpha_i$代替，改变约束条件，也就得出：

$$ \begin{aligned} \max\limits_{0\le\alpha\le C,\beta=C-\alpha}\bigg( \min\limits_{b,w,\xi} =&\frac{1}{2}||w||^2+C\cdot\sum\limits_{i=1}^{N}\xi_i\\ &+\sum\limits_{i=1}^N \alpha_i\cdot(1-\xi_i-y_i(w^Tx_i+b))+\sum\limits_{i=1}^{N}(C-\alpha_i)\cdot(-\xi_i) \bigg) \end{aligned} $$

又发现刚好同时存在正的与负的$C\cdot\sum\limits_{i=1}^{N}\xi_i$和$\sum\limits_{i=1}^{N}\alpha_i\xi_i$，最后一项可以完全抵消，最后变成

$$ \begin{aligned} \max\limits_{0\le\alpha\le C,\beta=C-\alpha}\bigg( \min\limits_{b,w,\xi} \frac{1}{2}||w||^2+\sum\limits_{i=1}^N \alpha_i\cdot(1-y_i(w^Tx_i+b)) \bigg) \end{aligned} $$

这不就是硬间隔SVM的对偶形式，加上约束条件$0\le\alpha\le C,\beta=C-\alpha$吗？

那么就按照之前的方法，

$$ \begin{aligned} \nabla_W L(w,b,\alpha)&=w-\sum^N_{i=1}\alpha_i y^{(i)}x^{(i)} =0\\ \frac{\partial}{\partial b}L(w,b,\alpha)&=\sum^N_{i=1}\alpha_i y^{(i)}=0 \end{aligned} $$

最终的公式如下：

$$ \begin{aligned} \min_\alpha \quad & \frac12\sum^N_{i,j=1}y^{(i)}y^{(j)}\alpha_i\alpha_j\langle x^{(i)} x^{(j)} \rangle-\sum^N_{i=1}\alpha_i\\ s.t. \quad & \sum^m_{i=1}\alpha_i y^{(i)}=0\\ & 0\le\alpha_i\le C,\quad\quad i=1,...,N\\ \text{implicitly}\quad&w=\sum^N_{i=1}\alpha_i y^{(i)}x^{(i)}\\ &\beta_i=C-\alpha_n,\quad\quad i=1,...,N \end{aligned} $$

下面是使用高斯核的软间隔SVM在不同$C$值下的效果。可以看出，即使使用软间隔，如果不选好合适的$C$值，也会出问题的。