【机器学习】支持向量机——软间隔（SVM中篇）

软间隔问题（soft-margin）

软间隔是相对于硬间隔定义的。上节中介绍的线性可分的SVM算法，属于硬间隔。硬间隔，就是存在所有样本必须划分正确的约束条件，即所有样本必须严格满足：
$y_i(w^Tx_i+b)\geq1\qquad i=1,2,\cdots,N$
所以从这个角度分析，上篇介绍的算法，是在硬间隔定义的基础之上推导的。而相对于软间隔，则是允许某些样本不满足约束条件
$y_i(w^Tx_i+b)\geq1\qquad i=1,2,\cdots,N$
之所以如此定义，是因为在样本集中总是存在一些噪音点或者离群点，如果强制要求所有的样本点都满足硬间隔，可能会导致出现过拟合的问题，甚至会使决策边界发生变化，为了避免这个问题的发生，所以在训练过程的模型中，允许部分样本（离群点或者噪音点）不必满足该约束。当然在最大化间隔的同时，不满足约束的样本应尽可能少

软间隔优化目标函数

针对软间隔问题，我们引入了以下的优化目标函数：
$\underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}l_{0/1}(y_i(w^Tx_i+b)-1)$
其中$C>0$是一个常数，$l_{0/1}$是"0/1损失函数"
$l_{0/1}(z) \begin{cases}1, \quad if \ z<0;\\ 0, \quad otherwise.\end{cases}$
从上式分析：
当C为无穷大时，为了保证目标函数取得最小值，需要要求$l_{0/1}=0$即，所有样本严格满足硬间隔约束条件；
当C取有限值时，允许部分样本不满足约束条件。
由于$l_{0/1}$非凸、非连续的数学特性，导致目标函数
$\underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{m}l_{0/1}(y_i(w^Tx_i+b)-1)$
不易求解，所以一般会采用以下的"替代损失"函数来进行替代：

• hinge损失：$l_{hinge}(z)=max(0,1-z)$
• 指数损失：$l_{exp}(z)=\exp(-z)$
• 对率损失：$l_{log}(z)=log(1+exp(-z))$

一般这些函数通常都是凸、连续且是$l_{0/1}$的上界的函数。例如：
采用hinge函数：
$\underset{w,b}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{N}max(0,1-y_i(w^Tx_i+b))$
忽略各种替代损失函数，引入“松弛因子”，故上式可重写为：
$\underset{w,b,\xi_i}{min}\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i$
其中约束条件为：
$\begin{cases}y_i(w^Tx_i+b)\geq1-\xi_i\\ \xi_i\geq0,\ i=1,2,\cdots,N\end{cases}$
该式就是常用的“软间隔支持向量机”
用拉格朗日乘子法进行求解：
$L(w,b,a,\xi,\mu)=\frac{1}{2}||w||^2+C\sum_{i=1}^{N}\xi_i+\sum_{i=1}^{N}a_i(1-\xi_i-y_i(w^Tx_i+b))-\sum_{i=1}^{N}\mu_i\xi_i$
其中$a_i\geq0,\mu_i\geq0$
令$L(w,b,a,\xi,\mu)$对$w,b,\xi$的偏导为0，可得：
$w=\sum_{i=1}^{N}a_iy_ix_i$
$\sum_{i=1}^{N}a_iy_i=0$
$C=a_i+\mu_i$
代入原式可得：
$\underset{a}{max}\sum_{i=1}^{N}a_i-\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}a_ia_jy_iy_jx_i^Tx_j$
或者
$\underset{a}{\max}\ \ -\frac{1}{2}\sum_{i=1}^N{\sum_{j=1}^N{a_ia_jy_iy_j \langle x_i \cdot x_j \rangle+\sum_{i=1}^N{a_i}}}$
其中约束条件为：
$\begin{cases} \sum_{i=1}^{N}a_iy_i=0 \\ 0 \leq a_i\leq C, \quad i=1,2,\cdots,N \end{cases}$

和之前的结果对比一下，可以看到唯一的区别就是现在拉格朗日乘子$a$多了一个上限$C$。而 Kernel 化的非线性形式也是一样的，只要把$\langle x_i,x_j\rangle$ 换成 $κ\langle x_i,x_j \rangle$ 即可(此部分内容在核函数部分介绍)。
最终的求解过程类似于上一篇，通过样本确定参数，求得：
$a^*=\left( a_{1}^{*},a_{2}^{*},\cdots,a_{N}^{*} \right) ^T$
然后计算
$w^*=\sum_{i=1}^N{a_{i}^{*}y_ix_i}$
选取$a^*$的一个满足$0 \leq a_i\leq C$的分量$a^*_i$计算：
$b^*=y_j-\sum_{i=1}^N{a_{i}^{*}y_i\langle x_i\cdot x_j \rangle}$
对任一适合条件都可求得一个$b^*$，但是由于原始问题对$b$的求解并不唯一，所以实际计算时可以取在所有符合条件的样本点上的平均值。

支持向量(此部分内容也可参考西瓜书)

再现性不可分的情况下，将对偶问题的解中对应于$a^*_i>0$的样本点$(x_i,y_i)$的实例$x_i$称为支持向量（软间隔的支持向量）。如图所示，这时的支持向量要比线性可分时的情况复杂一些。

图中，分离超平面由实线表示，间隔边界由虚线表示。正例点由“”表示，负例点由“×”表示。图中还标出了实例$x_i$到间隔边界的距离$\frac{\xi _i}{||w||}$
软间隔的支持向量$x_i$要么在间隔边界上，要么在间隔边界与分离超平面之间，要么在分离超平面误分类一侧。
若$a_i^*<C$,则$\xi _i=0$,支持向量恰好落在间隔边界上；
若$a_i^*=C,0< \xi _i<1$,则分类正确，$x_i$在间隔边界与分离超平面之间；
若$a_i^*=C,\xi _i=1$,则$x_i$在分隔超平面上；
若$a_i^*=C,\xi _i>1$，则$x_i$位于分离超平面误分一侧。
参考文献：
机器学习 周志华著
机器学习算法系列（12）：SVM（2）—线性支持向量机