03. 硬间隔与软间隔

来源：原始 Jupyter Notebook。内容已转换为网页阅读格式；下载原文件。

在前面的例子中，我们假定样本空间是线性可分的，即存在一个超平面将不同类别完全划分开来。然而在现实的分类任务中，样本空间往往是线性不可分的，譬如下面这样：

可见，数据中混入了一些异常点，导致没办法通过一个超平面将其分成两个部分。解决这个问题的一个办法是，允许支持向量机在一些样本上出错。在前面介绍支持向量机的基本形式时，我们要求所有的样本都满足下面的约束条件：

\left\{ \begin{align} w^Tx_i + b \ge +1, y_i = +1 \\ w^Tx_i + b \le -1, y_i = -1 \end{align} \right.

也可以简写成：

y_i(w^Tx_i + b) \geq 1

这个约束条件确保所有样本都被正确划分，这被称为 硬间隔（hard margin），我们把这个约束条件稍微放宽，允许某些样本不满足该条件，得到的就是 软间隔（soft margin），当然，我们希望不满足约束条件的样本越少越好。

为此，我们对每个样本引入一个松弛变量 $\xi_i \geq 0$ ，约束条件变成：

y_i(w^Tx_i + b) \geq 1 - \xi_i

同时，对每一个松弛变量 $\xi$ ，支付一个代价 C，所以优化目标就变成了：

\begin{align} &\mathop \min_{w,b} \frac{1}{2}\|w\|^2 + C\sum_{i=1}^n\xi_i \\ &s.t. y_i(w^Tx_i + b) \geq 1 - \xi_i, \xi_i \geq 0, i = 1,2,\dots,n \end{align}

这就是软间隔支持向量机的基本形式。

这里的 C 是一个超参数，决定了你有多重视异常点带来的损失。显然，当 C 为无穷大时，为了求优化目标的最小值，这里加上的松弛变量类似于惩罚项，要非常小甚至等于 0 才行，也就是 $\xi_i = 0$ ，会迫使所有的样本都满足约束 $y_i(w^Tx_i + b) \geq 1$ ，这就和硬间隔一样；当 C 为某一常数时，允许某些样本不满足约束，得到的就是软间隔。

损失函数的其他形式

上面通过在硬间隔的优化目标中引入松弛变量 $\xi_i$ 得到了软间隔支持向量机的基本形式。实际上，我们还有很多其他的方式来推导软间隔的优化目标，最简单的想法是在优化目标中加入 0/1损失函数，硬间隔的优化目标为：

\mathop \min_{w,b} \frac{1}{2}\|w\|^2

加入 0/1损失函数后，优化目标变成了：

\mathop \min_{w,b} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^m \ell_{0/1}(y_i(w^Tx_i + b) - 1)

其中， $\ell_{0/1}$ 就是 0/1损失函数，当样本满足硬间隔的约束条件时，也就是 $y_i(w^Tx_i + b) \geq 1$ 时，损失为 0，不满足时损失为 1：

\ell_{0/1}(z) = \left\{ \begin{align} 0, z \geq 0 \\ 1, z < 0 \\ \end{align} \right.

但是 0/1损失函数不连续，也不是凸函数，导致优化目标不易求解，通常用一些其他函数来替代 0/1损失函数，这被称为 替代损失（surrogate loss），替代损失一般具有良好的数学性质，通常是凸的连续函数并且是 0/1损失函数的上界。比如 Hinge损失：

\ell_{hinge}(z) = max(0, 1-z)

Hinge损失，又叫 合页损失 或 铰链损失，它就像一个打开的合页形状：

加入 Hinge损失函数后，优化目标变成了：

\mathop \min_{w,b} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^m \max(0, 1 - y_i(w^Tx_i + b))

其中，当样本满足硬间隔的约束条件时，也就是 $y_i(w^Tx_i + b) \geq 1$ 时，这时 $1 - y_i(w^Tx_i + b) \leq 0$ ，Hinge损失为 0；当样本不满足约束条件时损失为 $1 - y_i(w^Tx_i + b)$ 。

令：

\xi_i = \max(0, 1 - y_i(w^Tx_i + b))

于是得到和上面一样的优化目标：

\mathop \min_{w,b} \frac{1}{2}\|w\|^2 + C \sum_{i=1}^m \xi_i

很显然：

\left\{ \begin{align} & \xi_i = \max(0, 1 - y_i(w^Tx_i + b)) \geq 1 - y_i(w^Tx_i + b) \\ & \xi_i = \max(0, 1 - y_i(w^Tx_i + b)) \geq 0 \end{align} \right .

所以有约束条件：

y_i(w^Tx_i + b) \geq 1 - \xi_i, \xi_i \geq 0

除 Hinge损失之外，还有很多其他的替代损失，比如 指数损失（exponential loss）：

\ell_{exp}(z) = exp(-z)

或者 对率损失（logistic loss）：

\ell_{log}(z) = log(1+exp(-z))

他们的图像如下所示：

损失函数的其他形式#

损失函数的其他形式