机器学习数学推导（八）：支持向量机

引子。 两团点，能把它们分开的直线有无穷多条，“哪一条最好”？SVM 给出的答案出奇地几何：站在两个类之间最宽的"无人走廊"正中央的那一条。把这一个想法塞进拉格朗日对偶里，会自动跑出三件礼物——稀疏的模型（只有走廊壁上的点重要）、有全局最优解的二次规划、以及核技巧（同一套线性机器可以在无限维空间里画出弯曲的边界）。

你将学到什么

• “最宽走廊"如何变成一个带线性约束的凸二次规划
• 为什么对偶问题比原问题更好用，KKT 条件如何强制稀疏
• 软间隔、参数 $C$ 真正控制的是什么
• 核技巧：用 $K(x, z)$ 替换 $\phi(x)^\top \phi(z)$，永远不去构造 $\phi$
• Mercer 条件，以及标准核函数家族（线性 / 多项式 / RBF / sigmoid）
• SMO 算法：为什么一次两个变量、裁剪如何工作、为何收敛
• Hinge 损失——SVM 通向其它监督学习模型的桥梁

前置知识

• 线性代数：内积、超平面、投影
• 微积分：拉格朗日乘子、偏导数
• 凸对偶性的基本概念有帮助但非必需
• 对 第 7 篇：决策树 有印象

1. 硬间隔 SVM

1.1 函数间隔与几何间隔

考虑二分类，标签 $y_i \in \{-1, +1\}$，线性决策规则 $\hat{y} = \operatorname{sign}(w^\top x + b)$。“离边界多远"有两种说法：

函数间隔在分类正确时为正，但不是尺度无关的——把 $(w, b)$ 翻倍，函数间隔也翻倍。几何间隔才是 $x_i$ 到超平面的真实欧氏距离（带上标签的符号），它不随 $(w, b)$ 的缩放变化。这种尺度无关性是优化能良定的关键，否则"让间隔更大"是个开口子：缩小 $\lVert w \rVert$ 就行了。

这个公式怎么来的？ 任意点 $x_0$ 在超平面 $w^\top x + b = 0$ 上的最近点是它的正交投影，位移向量是 $-(w^\top x_0 + b)/\lVert w \rVert^2 \cdot w$，模长是 $\lvert w^\top x_0 + b\rvert / \lVert w \rVert$。乘 $y_i$ 让分类正确时为正。

1.2 最大间隔规划

我们要让最坏情况的几何间隔最大：

这里 $(w, b)$ 只在正比例下才唯一，所以钉一个尺度：要求最近点的函数间隔恰好为 $1$。等价地写成

这是带线性约束的凸二次规划。目标严格凸，最优 $w^\*$ 唯一；只要数据中两个类都出现，$b^\*$ 也唯一。

约束取等号的样本（$y_i(w^\top x_i + b) = 1$）就是支持向量。几何上它们落在边界两侧的两条平行间隔线上；代数上，它们是唯一决定 $w^\*$ 的点。

1.3 用拉格朗日导对偶

给每条约束附上乘子 $\alpha_i \ge 0$：

第一步——对 $w$ 与 $b$ 求极小。 令 $\partial_w L = 0$、$\partial_b L = 0$：

第二步——回代。 把 $w^\* = \sum_i \alpha_i y_i x_i$ 代回 $L$：

得到对偶规划：

两个性质在此处做了所有关键工作：

1. 数据只通过内积 $x_i^\top x_j$ 出现。把它换成 $K(x_i, x_j)$，整套推导原封不动——核技巧在还没正式登场时就已经被准备好了。
2. 对偶问题有 $N$ 个标量变量、一条等式约束。当特征维度 $d \gg N$ 时，对偶比原问题小得多。

1.4 KKT 条件与稀疏性

原问题凸、约束仿射，Slater 条件成立，强对偶成立。最优 $(w^\*, b^\*, \alpha^\*)$ 必然满足：

• 原始可行： $y_i(w^{\*\top} x_i + b^\*) \ge 1$。
• 对偶可行： $\alpha_i^\* \ge 0$。
• 稳定性： $w^\* = \sum_i \alpha_i^\* y_i x_i$，$\sum_i \alpha_i^\* y_i = 0$。
• 互补松弛： $\alpha_i^\* \cdot \bigl[\, y_i(w^{\*\top} x_i + b^\*) - 1 \,\bigr] = 0$。

最后一行是这一节的全部精华。对每个 $i$，下面两件事只能成立一个：

• $\alpha_i^\* = 0$——点严格在间隔带之外，对 $w^\*$ 没有任何贡献。
• $y_i(w^{\*\top} x_i + b^\*) = 1$——点恰好落在间隔线上，$\alpha_i^\* > 0$ 才允许。

最优分类器只由第二组支撑：

预测时可以把所有非 SV 训练点扔掉。这就是 SVM 的"内置稀疏”。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import numpy as np
from sklearn.svm import SVC

# 一个小的线性可分例子
X = np.array([[1, 2], [2, 3], [3, 3],
              [1, 0], [2, 1], [0, 1]], dtype=float)
y = np.array([1, 1, 1, -1, -1, -1])

clf = SVC(kernel="linear", C=1e6).fit(X, y)   # C 极大 ≈ 硬间隔
w, b = clf.coef_[0], clf.intercept_[0]

print(f"w = {w},  b = {b:.4f}")
print(f"#SV = {len(clf.support_)} / {len(X)}")
for i in clf.support_:
    print(f"  SV idx {i}: y(w·x+b) = {y[i] * (X[i] @ w + b):.4f}  "
          f"（应≈1）")

2. 软间隔 SVM

2.1 松弛变量与参数 $C$

真实数据通常有重叠。给每个点一个非负的"违规额度” $\xi_i$：

如何读 $\xi_i$：

• $\xi_i = 0$：在间隔带外，分类正确。
• $0 < \xi_i \le 1$：在间隔带内，但仍在正确一侧。
• $\xi_i > 1$：分类错误。

$C > 0$ 是在两件坏事之间做交易。$C$ 大——重罚松弛，间隔变窄，趋近硬间隔；$C$ 小——容许较多松弛，间隔变宽，对噪声更宽容。

2.2 对偶：盒约束登场

再走一遍拉格朗日。这次给间隔约束乘子 $\alpha_i \ge 0$，给 $\xi_i \ge 0$ 乘子 $\mu_i \ge 0$。令 $\partial_\xi L = 0$ 得 $\alpha_i + \mu_i = C$，故 $0 \le \alpha_i \le C$。对偶问题：

与硬间隔唯一的差别是上界 $\alpha_i \le C$。KKT 条件把样本切成三种状态：

偏置由任一边界 SV 给出：$b^\* = y_i - \sum_j \alpha_j^\* y_j x_j^\top x_i$。实际操作时对所有边界 SV 取平均，数值更稳。

2.3 Hinge 损失视角

注意到原问题中最优松弛恰好是 $\xi_i^\* = \max(0,\, 1 - y_i(w^\top x_i + b))$，把它代回去消掉 $\xi$：

右边那个求和正是 hinge 损失。也就是说——软间隔 SVM 不过是"L2 正则 + hinge 损失"的经验风险最小化。从这个角度看，SVM 跟你认识的所有线性分类器没有结构上的差别，唯一不同的就是损失函数。

Hinge 在 $m = 1$ 处有个尖点，且在那之后恒为 0——这正是 SV 稀疏性的源头：自信正确的点既无梯度也无 $\alpha$。

3. 核函数

3.1 核技巧

把输入映到某个特征空间 $\phi: \mathbb{R}^d \to \mathcal{H}$，在 $\mathcal{H}$ 里跑线性 SVM。对偶目标变成

整段推导里 $\phi$ 永远只在内积里出现。把这个内积命名为核函数：

凡是出现 $x_i^\top x_j$ 的地方（不管是对偶还是预测），都换成 $K(x_i, x_j)$。我们既不构造 $\phi$、也不存储特征、$\dim \mathcal{H}$ 是不是有限的根本无关紧要。

提升后的图直观解释了为什么这套招式有效。左图内外两类数据在二维里没有任何直线能分开。映射 $\phi(x) = (x_1, x_2, x_1^2 + x_2^2)$ 把外环在第三维抬起，水平面 $x_1^2 + x_2^2 = c$ 就成了分离面。要在 $\mathbb{R}^3$ 中算这个内积，用 $K(x, z) = (1 + x^\top z)^2$ 即可，整个过程不需要把 $\phi$ 显式写出来。

3.2 常用核函数

RBF 直觉。 每个训练点放下一个半径约 $1/\sqrt{\gamma}$ 的"鼓包"。$\gamma$ 大——鼓包窄，决策边界紧紧贴着每个点（过拟合风险）；$\gamma$ 小——鼓包宽，边界平滑（欠拟合风险）。

3.3 Mercer 定理

定理。 对称函数 $K(x, z)$ 能写成某个希尔伯特空间里的内积 $\phi(x)^\top \phi(z)$，当且仅当对任意有限点集 $\{x_i\}_{i=1}^N$，核矩阵 $\mathbf{K}_{ij} = K(x_i, x_j)$ 半正定，即

这条定理是核技巧的法律凭证：半正定的 $K$ 就是某个内积——其底层的再生核希尔伯特空间（RKHS）从构造上保证了这一点。

有用的封闭性。 若 $K_1, K_2$ 是核，则 $K_1 + K_2$、$\lambda K_1$（$\lambda \ge 0$）、$K_1 \cdot K_2$、$f(x) K_1(x, z) f(z)$、$K_1$ 的非负系数多项式、$\exp(K_1)$ 都是核。RBF 实际上就是把这些封闭性反复应用到线性核上得到的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import numpy as np
from sklearn.svm import SVC
from sklearn.metrics import accuracy_score

# XOR：不可线性分，RBF 一刀就过
X = np.array([[0, 0], [0, 1], [1, 0], [1, 1]], dtype=float)
y = np.array([0, 1, 1, 0])

print("linear:", accuracy_score(y, SVC(kernel="linear").fit(X, y).predict(X)))
print("rbf   :", accuracy_score(y, SVC(kernel="rbf", gamma=5).fit(X, y).predict(X)))

# 验证 Gram 矩阵半正定
gamma = 5.0
K = np.exp(-gamma * np.sum((X[:, None] - X[None, :]) ** 2, axis=-1))
eig = np.linalg.eigvalsh(K)
print(f"特征值: {eig.round(4)}  全部 ≥ 0: {np.all(eig >= -1e-10)}")

4. SMO 算法

4.1 为什么一次两个变量

对偶问题是 $N$ 个变量、一条等式约束 $\sum_i \alpha_i y_i = 0$ 的 QP。通用 QP 解法时间 $O(N^3)$、空间 $O(N^2)$——上万样本就吃不消了。

朴素的"坐标下降"——固定其它，只改一个 $\alpha_i$——是非法的：等式约束逼着任何合法移动至少改两个坐标。能在保持可行的前提下更新的最少变量数就是两个。这正是 Sequential Minimal Optimization（Platt, 1998）的全部前提：选一对、解析地解这两变量 QP、循环。

4.2 两变量子问题

选 $1, 2$，冻结其它。等式约束化简为

故 $\alpha_1$ 由 $\alpha_2$ 决定，对偶目标退化为关于 $\alpha_2$ 的一元二次函数。求导取零得无约束更新

其中

$\eta$ 就是特征空间中 $\lVert \phi(x_1) - \phi(x_2) \rVert^2$，自然非负。

4.3 裁剪到 $[L, H]$

更新后的对必须同时满足 $0 \le \alpha_1, \alpha_2 \le C$ 和等式约束。两者一合并就把 $\alpha_2$ 限制在区间 $[L, H]$ 上，区间端点取决于两个标签的符号关系：

裁剪并回代：

4.4 启发式与收敛

• 外层循环： 在(a) 扫所有样本与(b) 仅扫非边界 SV（$0 < \alpha_i < C$）之间切换——已经卡在边界的坐标几乎不动。
• 第一变量： 选违反 KKT 条件超过容差的任意 $\alpha_i$。
• 第二变量： 选使 $\lvert E_1 - E_2 \rvert$ 最大的样本（近似最大步长启发）。

只要选的对不在最优，每一步都严格改进对偶目标。配合"目标有界 + 步长有限"，SMO 收敛。实践中比通用 QP 快几个数量级。要让每步真正 $O(N)$ 而非 $O(N^2)$，关键工程细节是增量维护误差缓存 $E_i$。

5. 实践要点

• 永远先标准化特征。 SVM 用欧氏几何，量纲不齐时大尺度特征会主导间隔。
• $C$ 与 $\gamma$ 一起调。 它们的"乘积"粗略控制模型容量。在对数尺度上做网格搜索：$C \in \{10^{-2}, \dots, 10^3\}$，$\gamma \in \{10^{-3}, \dots, 10^1\}$，配合交叉验证。
• $N \gg 10^5$ 时优先线性 SVM（LIBLINEAR）或随机方法。 核 SVM 训练时间大致 $O(N^2)$。
• 多分类。 标准 SVM 是二分类。包成 One-vs-Rest（$K$ 个模型）或 One-vs-One（$K(K-1)/2$ 个模型 + 投票）。scikit-learn 的 SVC 默认 OvO。
• 概率输出。 SVM 给的是距离，不是校准概率。需要概率的话用 Platt scaling（对决策值再跑一个逻辑回归）或保序回归。

6. 练习

练习 1 — 几何间隔

题目。 超平面 $w = (3, 4)^\top$，$b = -1$。点 $x_0 = (1, 1)^\top$，标签 $y = +1$。求几何间隔。

解答。

1
2
3

import numpy as np
w, b, x, y = np.array([3, 4]), -1, np.array([1, 1]), 1
print(y * (w @ x + b) / np.linalg.norm(w))   # 1.2

练习 2 — 核函数对加法封闭

题目。 证明若 $K_1, K_2$ 是有效核，则 $K = K_1 + K_2$ 也是。

解答。 任取有限点集 $\{x_i\}$ 与 $c \in \mathbb{R}^N$：

两项都因 $K_1, K_2$ 半正定而 $\ge 0$，故 $K$ 半正定，是有效核。

练习 3 — 从 SV 个数读 $C$

题目。 100 个训练样本：$C = 0.1$ 得到 30 个 SV；$C = 100$ 得到 15 个 SV。解释。

解答。 $C$ 小时松弛代价低，最优解倾向于把间隔拉宽，更多点落进间隔带变成 $\alpha = C$ 的上界 SV。$C$ 大时松弛重罚，间隔被压窄，落在带内的样本变少，SV 也变少。一般规律：正则强（$C$ 小）→ 间隔宽 → SV 多。

练习 4 — 诊断 $\gamma$

题目。 RBF：$\gamma = 0.01$ 得到训练 95 % / 测试 60 %；$\gamma = 100$ 得到训练 100 % / 测试 70 %。哪个更好？应该试什么？

解答。 都不好。$\gamma = 0.01$ 鼓包太宽，模型欠拟合——训练勉强、测试很差。$\gamma = 100$ 鼓包像针尖，每个训练点自成一岛，严重过拟合。和 $C$ 一起在 $\gamma \in \{0.1, 0.3, 1, 3, 10, 30\}$ 上交叉验证，最优组合会让训练/测试差距收窄。

练习 5 — SVM vs 逻辑回归

题目。 何时该用哪个？

解答。

Q&A

为什么要最大化间隔？

几何上，间隔越宽对噪声越宽容——任何小于间隔的扰动都不会改变预测。统计上，基于间隔的泛化界（如通过 Rademacher 复杂度推出）显示泛化误差随间隔减小，所以最大化间隔等价于在隐式地正则化模型复杂度。

为什么用对偶？

三个理由。(1) 数据只以内积出现，可上核技巧；(2) $d \gg N$ 时对偶比原问题小得多；(3) KKT 条件保证大多数 $\alpha_i = 0$，预测高效。

SMO 中如果 $\eta = 0$ 怎么办？

$\eta = \lVert \phi(x_1) - \phi(x_2) \rVert^2$，$\eta = 0$ 意味着两个点在特征空间里重合。此时目标在可行段上是关于 $\alpha_2$ 的线性函数，最优点取 $L$ 或 $H$ 中目标值更大的端点。

SVM 能做回归吗？

能——支持向量回归（SVR） 用 $\varepsilon$-不敏感损失 $\max(0, |y - f(x)| - \varepsilon)$。误差小于 $\varepsilon$ 不计代价；超出 $\varepsilon$ 的样本成为支持向量。同一套对偶机器，每个点配两个乘子（$\alpha_i, \alpha_i^\*$，对应上下两侧）。

为什么必须标准化？

$\eta$ 与核矩阵都涉及 $\lVert x \rVert$。某个量纲很大的特征会压倒其它特征，把决策边界拉向坐标轴对齐。把每个特征调到零均值单位方差是一行代码就能做的事，往往同时改善速度与精度。

参考文献

• Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine Learning, 20(3), 273-297.
• Vapnik, V. N. (1998). Statistical Learning Theory. Wiley.
• Platt, J. C. (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Tech. Rep. MSR-TR-98-14, Microsoft Research.
• Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press.
• Cristianini, N., & Shawe-Taylor, J. (2000). An Introduction to Support Vector Machines. Cambridge University Press.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer. Chapter 12.

系列导航