[ML Notes] SVM：软间隔
Contents
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$ 的分量尽量系数，即非零分量个数尽量少。