[ML Notes] SVM：软间隔

Author: nex3z 2021-03-14

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)\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}

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 的分量尽量系数，即非零分量个数尽量少。