[ML Notes] SVM：软间隔

Author: nex3z 2020-09-04

1. 软间隔支持向量机

  实际问题中，往往不能事先知道样本在特征空间中是否线性可分；即便线性可分，这也可能是发生了过拟合。

  软间隔（soft margin）的支持向量机允许在一些样本上出错，即不满足约束条件

$$y_i(\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \geq 1 \tag{1}$$

在原优化目标 $\min\limits_{\boldsymbol w, b} \frac{1}{2} ||\boldsymbol w||^2$ 的基础上，希望违反式 $(1)$ 的样本数量越少越好，此时的优化目标变为

$$\min_{\boldsymbol w, b} \frac{1}{2} ||\boldsymbol w||^2 + C \sum_{i=1}^m l_{0/1}\big(y_i(\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) – 1\big) \tag{2}$$

其中 $C > 0$ 是一个常数系数，用于平衡两个目标。当 $C \rightarrow +\infty$ 时，相当于不允许任何样本违反式 $(1)$。

  $l_{0/1}$ 是 $0/1$ 损失函数，即

$$l_{0/1}(z) = \begin{cases} 1 & \text{if } z < 0; \\ 0 & \text{otherwise}. \end{cases}$$

回到式 $(2)$ 中，如果某一样本 $(\boldsymbol{x}_i, y_i)$ 不满足式 $(1)$ 的约束条件，则 $y_i(\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) – 1 < 0$，于是 $l_{0/1}\big(y_i(\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) – 1\big) = 1$，进行了惩罚。$l_{0/1}$ 非凸、不连续，不便于优化。实际中通常使用具有较好数学性质的函数作为替代损失，这些函数通常是凸的、连续的，且是 $l_{0/1}$ 的上界，如

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

  使用 hinge 损失时，式 $(2)$ 变为

$$\min_{\boldsymbol w, b} \frac{1}{2} ||\boldsymbol w||^2 + C \sum_{i=1}^m \max \big( 0, 1 – y_i(\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \big) \tag{3}$$

为每个样本引入松弛变量（slack variable）$\xi_i \geq 0$ 来衡量样本不满足式 $(1)$ 约束的程度，可将上式写为

$$\begin{aligned} \min_{\boldsymbol w, b, \xi_i} \; & \frac{1}{2} ||\boldsymbol w||^2 + C \sum_{i=1}^m \xi_i \\ \text{s.t.} \; & y_i(\boldsymbol w^\mathrm{T} \boldsymbol x_i + b) \geq 1 – \xi_i \\ & \xi_i \geq 0, \;\; i = 1, 2, \dots, m \end{aligned} \tag{4}$$

即为软间隔支持向量机。

2. 求解方法

  式 $(4)$ 仍是一个二次规划问题，构造广义拉格朗日函数

$$\begin{aligned} L(\boldsymbol w, b, \boldsymbol \xi, \boldsymbol \alpha, \boldsymbol \mu) &= \frac{1}{2} ||\boldsymbol w||^2 + C \sum_{i=1}^m \xi_i \\ &+ \sum_{i=1}^m \alpha_i \big(1 – \xi_i – y_i(\boldsymbol w^\mathrm{T} \boldsymbol x_i + b)\big) – \sum_{i=1}^m \mu_i \xi_i \end{aligned} \tag{5}$$

其中 $\alpha_i \geq 0$，$\mu_i \geq 0$ 是拉格朗日乘子。

  计算相关偏导

$$\nabla L_{\boldsymbol w} = \boldsymbol w – \sum_{i=1}^m \alpha_i y_i \boldsymbol x_i$$

$$\frac{\mathrm{d}L}{\mathrm{d}b} = – \sum_{i=1}^m \alpha_i y_i$$

$$\frac{\mathrm{d}L}{\mathrm{d}\xi_i} = C – \alpha_i – \mu_i$$

令以上三个偏导为零，得到

$$\boldsymbol w = \sum_{i=1}^m \alpha_i y_i \boldsymbol x_i \tag{6}$$

$$0 = \sum_{i=1}^m \alpha_i y_i \tag{7}$$

$$C = \alpha_i + \mu_i \tag{8}$$

  将式 $(6)$、$(7)$、$(8)$ 带入式 $(5)$，得

$$\begin{aligned} L(\boldsymbol w, b, \boldsymbol \xi, \boldsymbol \alpha, \boldsymbol \mu) &= \frac{1}{2} \boldsymbol w^\mathrm{T} \sum_{i=1}^m \alpha_i y_i \boldsymbol x_i + C \sum_{i=1}^m \xi_i \\ &+ \sum_{i=1}^m \alpha_i – \sum_{i=1}^m \alpha_i \xi_i – \sum_{i=1}^m \alpha_i y_i \boldsymbol w^\mathrm{T} \boldsymbol x_i – b \sum_{i=1}^m \alpha_i y_i – \sum_{i=1}^m (C – \alpha_i) \xi_i \\ &= \sum_{i=1}^m \alpha_i – \frac{1}{2} \sum_{i=1}^m \alpha_i y_i \boldsymbol w^\mathrm{T} \boldsymbol x_i \\ &= \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 \boldsymbol x_i^\mathrm{T} \boldsymbol x_j \end{aligned}$$

上式中已经消去了 $\boldsymbol \mu$，于是得到式 $(4)$ 的对偶问题

$$\begin{aligned} \max_{\boldsymbol \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 \boldsymbol x_i^\mathrm{T} \boldsymbol x_j \\ \text{s.t.} \; & \sum_{i=1}^m \alpha_i y_i = 0 \\ & 0 \leq \alpha_i \leq C, \;\; i = 1, 2, \dots, m \end{aligned} \tag{9}$$

这个问题与线性 SVM 的对偶问题（前文式 $(12)$）具有相似的结构，区别只在于软间隔 SVM 对 $\alpha_i$ 的约束为 $0 \leq \alpha_i \leq C$。可以使用前文的方法求解。

  对软间隔 SVM，KKT 条件要求

$$\begin{aligned} \begin{cases} \alpha_i \geq 0, \; \mu_i \geq 0, \\ y_i f(\boldsymbol x_i) – 1 + \xi_i \geq 0, \\ \alpha_i (y_i f(\boldsymbol x_i) – 1 + \xi_i) = 0, \\ \xi_i \geq 0, \; \mu_i \xi_i = 0. \end{cases} \end{aligned} \tag{10}$$

其中 $\alpha_i \geq 0$、$y_i f(\boldsymbol x_i) – 1 + \xi_i \geq 0$ 和 $\alpha_i (y_i f(\boldsymbol x_i) – 1 + \xi_i) = 0$ 三个条件表示对任意样本 $(\boldsymbol x_i, y_i)$ 存在两种情况：

• 若 $\alpha_i = 0$，则该样本不会对模型 $f(\boldsymbol x)$ 产生影响；
• 若 $\alpha_i > 0$，则必有 $y_i f(\boldsymbol x_i) – 1 + \xi_i = 0$，即 $y_i f(\boldsymbol x_i) = 1 – \xi_i$，该样本为支持向量：
  • 若 $\alpha_i < C$，由式 $(8)$ 可知，此时 $\mu_i > 0$；又由 KTT 条件 $\mu_i \xi_i = 0$ 可知，此时 $\xi_i = 0$，该样本没有违反式 $(1)$，在最大间隔边界上；
  • 若 $\alpha_i = C$，由式 $(8)$ 可知，此时 $\mu_i = 0$：
  • 若 $\xi_i \geq 1$，则该样本在最大间隔内部；
  • 若 $\xi_i > 1$，则该样本被错误分类。

由以上分析可知，使用 hinge 损失函数的软间隔 SVM 最终模型仅与支持向量有关，hinge 损失函数保持了稀疏性。

3. 正则化

  通过将式 $(2)$ 中的 $l_{0/1}$ 损失函数更换为其他替代损失函数，可以得到具有不同性质的模型。这些模型的优化目标都可以写为

$$\min_{f} \; \Omega(f) + C \sum_{i=1}^m l \big(f(\boldsymbol x_i), y_i\big)$$

上式中的第一项 $\Omega(f)$ 用于描述划分超平面的间隔大小，称为结构风险（structural risk），描述了模型 $f$ 的性质；第二项 $\sum\limits_{i=1}^m l \big(f(\boldsymbol x_i), y_i\big)$ 称为经验风险（empirical risk），描述模型与训练数据的拟合程度。$C$ 用于对两个风险进行折中。

  通过 $\Omega(f)$ 可以控制模型的某些性质，如引入领域知识，从而缩小假设空间，降低过拟合风险。从这个角度，可以将 $\Omega(f)$ 看成是正则化项，$C$ 为正则化系数。

  常用的正则化项如 $\mathrm{L}_p$ 范数，$\mathrm{L}_2$ 范数 $||\boldsymbol w||_2$ 倾向于使 $\boldsymbol w$ 的分量取值尽量均衡，非零分量个数尽量稠密；$\mathrm{L}_1$ 范数 $||\boldsymbol w||_1$ 倾向于使 $\boldsymbol w$ 的分量尽量系数，即非零分量个数尽量少。