SVM支持向量机(二)：Soft Margin SVM

上一节我们介绍了SVM在处理二分类问题时的经典概念，但是现实场景中的数据往往有很多噪音，这个时候如何处理才能让模型更鲁棒呢？

松弛变量（Slack variables）

引入松弛变量的想法是，让基础SVM中关于margin的约束不再那么严格。（必须保证边界之外的样本预测值要么是+1要么是-1，且边界上的样本预测值为0）
同时还要对约束的松弛度进行一定的惩罚。

我们为每一个训练样本 $\mathbf{x}_i$ 都定义一个松弛变量 $\xi_i \geq 0$ ，来表示该样本违反margin的程度。

Slack variable

于是我们的分类表达式变成了：
$\mathbf{w}^T \mathbf{x}_i + b \geq +1 - \xi_i$ for $y_i = +1$
$\mathbf{w}^T \mathbf{x}_i + b \leq -1 + \xi_i$ for $y_i = -1$

它们可以合并成：
$y_i (\mathbf{w}^T \mathbf{x}_i + b) \geq 1 - \xi_i$ for all $i$

引入松弛变量之后，原来的cost function就从 $\frac{1}{2} \mathbf{w}^T\mathbf{w}$ 变成了
$\frac{1}{2} \mathbf{w}^T\mathbf{w} + C \sum_{i=1}^N \xi_i$

$C > 0$ 表示对于违反margin边界的惩罚力度。当 $C \rightarrow \infty$ 时，整个函数又变回了hard-margin SVM

求最优解

minimize: $f_0(\mathbf{w}, b, \mathbf{\xi}) = \frac{1}{2} \mathbf{w}^T\mathbf{w} + C \sum_{i=1}^N \xi_i$
subject to: $y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 + \xi_i \geq 0$
and $\xi_i \geq 0$ for $i = 1, ..., N$

_{备注：这里的惩罚项我们使用了L1-norm $\sum_i \xi_i$ ，也可以用L2-norm的形式 $\sum_i \xi_i^2$ ，取决于数据本身的特性以及噪音的类型，这里不做过多讨论。}

拉格朗日Primal problem

$L(\mathbf{w}, b, \mathbf{\xi}_i, \mathbf{\alpha}, \mathbf{\mu}) = \frac{1}{2} \mathbf{w}^T\mathbf{w} + C \sum_{i=1}^N \xi_i - \sum_{i=1}^N \alpha_i [y_i(\mathbf{w}_i^T \mathbf{x_i} + b) - 1 + \xi_i] - \sum_{i=1}^N \mu_i \xi_i$

$\nabla_w L = \mathbf{w} - \sum_{i=1}^N \alpha_i y_i \mathbf{x}_i \overset{!}{=} 0$ $\space \space \space \space$ (1)
$\frac{\partial L}{\partial b} = \sum_{i=1}^N \alpha_i y_i \overset{!}{=}0$ $\space \space \space \space$ (2)
$\frac{\partial L}{\partial b} = C - \alpha_i - \mu_i \overset{!}{=} 0$ $\space \space \space \space$ (3)

(3)式中，由于拉格朗日中 $\mu_i \geq 0$ , $\alpha_i \geq 0$ ，于是我们有: $0 \leq \alpha_i \leq C$

拉格朗日Dual problem

maximize: $g(\mathbf{\alpha}) = \sum_{i=1}^N \alpha_i - \frac{1}{2}\sum_{i=1}^N \sum_{j=1}^N y_iy_j \alpha_i \alpha_j \mathbf{x}_i^T \mathbf{x}_j$
subject to $\sum_{i=1}^N \alpha_i y_i = 0, \space \space \space 0 \leq \alpha_i \leq C, \space \space \space i = 1,..., N$

这和普通的SVM的dual problem几乎完全一致，只是多了 $\alpha_i \leq C$ 这个约束。它保证了 $\alpha_i$ 的最大值是有界限的，而不会变得无限大。

惩罚项C带来的影响

可以看到当C比较小的时候，margin里是允许有训练样本越界的。当C的值越来越大，margin的范围也在缩小，直到不允许任何样本出现在margin内部。

加入Hinge Loss到SVM中

让我们再回头看看soft margin SVM的优化问题：
minimize: $f_0(\mathbf{w}, b, \mathbf{\xi}) = \frac{1}{2} \mathbf{w}^T\mathbf{w} + C \sum_{i=1}^N \xi_i$
subject to: $y_i(\mathbf{w}^T \mathbf{x}_i + b) - 1 + \xi_i \geq 0$
and $\xi_i \geq 0$ for $i = 1, ..., N$

很明显可以看出松弛变量的最优解为：
$\xi_i=\left\{ \begin{array}{rcl} 1 - y_i(\mathbf{w}^T \mathbf{x}_i + b) & & {if \space \space y_i(\mathbf{w}^T \mathbf{x}_i + b) < 1}\\ 0 & & {else} \end{array} \right.$

因此，我们可以把objective function改写成hinge loss的形式：
$\underset{\mathbf{w}, b}{min} \space \frac{1}{2} \mathbf{w}^T \mathbf{w} + C \sum_{i=1}^N max \{ 0, 1 - y_i(\mathbf{w}^T \mathbf{x}_i + b) \}$

有了这个表达式，我们直接利用基于梯度的方式对其进行优化。

Reference

本文的内容总结自慕尼黑工业大学由Prof. Stephan Günnemann教授的Machine Learning课程。未经允许请勿转载。