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

引子： 假设有两团点，能将它们分开的直线有无数条，哪一条才是“最佳选择”？SVM 给出了一个极具几何美感的答案：位于两类点之间“最宽空白走廊”正中央的那条直线。将这一朴素思想通过拉格朗日对偶推演下去，竟能同时收获三大成果——稀疏模型（只有走廊边界上的点才起作用）、具有全局最优解的凸二次规划问题，以及几乎算是附赠的核技巧：它让同一套线性机制能在无限维空间中刻画出弯曲的决策边界。

你将学到什么#

• “最宽走廊”如何转化为带线性约束的凸二次规划问题
• 对偶问题为何比原问题更实用，KKT 条件又是如何催生稀疏性的
• 软间隔变体及其正则化参数 $C$ 的真实作用
• 核技巧：用 $K(x, z)$ 替代 $\phi(x)^\top \phi(z)$ ，完全无需显式构造映射 $\phi$
• Mercer 条件与常用核函数家族（线性 / 多项式 / RBF / Sigmoid）
• SMO 算法：为何每次只优化两个变量、裁剪机制如何运作、算法为何能收敛
• Hinge 损失——连接 SVM 与其他监督学习方法的桥梁

前置知识#

• 线性代数：内积、超平面、投影
• 微积分：拉格朗日乘子、偏导数
• 对凸对偶性有所了解会有帮助，但非必需
• 熟悉 第 7 篇：决策树

硬间隔 SVM#

函数间隔与几何间隔#

函数间隔在分类正确时为正，但它不具备尺度不变性：若将 $(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$ 后，只要预测正确，结果就为正。

最大间隔规划#

这是一个带线性约束的凸二次规划问题。目标函数严格凸，因此最优解 $w^\*$ 唯一；只要数据中两类样本均存在，偏置 $b^\*$ 也唯一。

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

拉格朗日对偶推导#

这里有两个关键观察：

1. 数据仅通过内积 $x_i^\top x_j$ 出现。若将其替换为核函数 $K(x_i, x_j)$ ，整个推导过程依然成立——这正是核技巧的雏形。
2. 对偶问题仅有 $N$ 个标量变量和一个等式约束，当特征维度 $d \gg N$ 时，求解对偶问题远比原问题高效。

KKT 条件与稀疏性#

原问题是凸优化问题，约束为仿射函数，Slater 条件成立，因此强对偶性成立。最优解 $(w^\*, b^\*, \alpha^\*)$ 必须满足以下 KKT 条件：

• 原始可行性： $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$ 。

预测时，所有非支持向量的训练样本均可丢弃。这便是 SVM 模型的稀疏性本质。

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

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）")

软间隔 SVM#

松弛变量与参数 $C$ #

$\xi_i$ 的含义如下：

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

参数 $C > 0$ 用于权衡两个目标：$C$ 越大，对松弛变量的惩罚越重，间隔越窄，模型越接近硬间隔；$C$ 越小，对松弛越宽容，间隔越宽，更能容忍噪声。

对偶问题：盒约束#

与硬间隔相比，唯一区别是增加了上界 $\alpha_i \le C$ 。此时 KKT 条件将样本划分为三类：

偏置 $b^\*$ 可通过任一边界支持向量计算：$b^\* = y_i - \sum_j \alpha_j^\* y_j x_j^\top x_i$ 。为提升数值稳定性，通常对所有边界支持向量的结果取平均。

Hinge 损失视角#

右侧求和项即为 hinge 损失。因此，软间隔 SVM 本质上就是 L2 正则化的经验风险最小化，损失函数为 hinge 损失。从这一视角看，SVM 与其他线性分类器并无本质区别，差异仅在于损失函数的选择。

Hinge 损失在 $m = 1$ 处存在一个“尖角”，且在 $m > 1$ 时恒为零。正是这一特性造就了支持向量的稀疏性：那些被自信正确分类的样本既不贡献梯度，也不影响对应的 $\alpha_i$ 。

核函数#

核技巧#

凡是在对偶问题或预测公式中出现 $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$ 。

常用核函数#

RBF 直觉：每个训练点生成一个半径约为 $1/\sqrt{\gamma}$ 的“鼓包”。$\gamma$ 越大，鼓包越窄，决策边界越紧贴单个点（易过拟合）；$\gamma$ 越小，鼓包越宽，边界越平滑（可能欠拟合）。

Mercer 定理#

这正是核技巧的理论基石：半正定核 本质上就是某个内积——再生核希尔伯特空间（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

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

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

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

SMO 算法#

为什么一次更新两个变量#

对偶问题是一个含 $N$ 个变量的 QP 问题，带有一个等式约束 $\sum_i \alpha_i y_i = 0$ 。通用 QP 求解器的时间复杂度为 $O(N^3)$ ，空间复杂度为 $O(N^2)$ ——对数万样本的数据集而言，这显然不可行。

若尝试朴素的坐标下降法（固定其余变量，仅优化一个 $\alpha_i$ ），会发现这是非法的：等式约束要求任何可行更新必须至少改变两个变量。因此，在保持可行性的前提下，最少需同时更新两个变量。这正是 Sequential Minimal Optimization（Platt, 1998）的核心思想：每次选取一对变量，解析求解该两变量子问题，然后迭代。

两变量子问题#

$\eta$ 即为特征空间中 $\lVert \phi(x_1) - \phi(x_2) \rVert^2$ ，故非负。

裁剪到 $[L, H]$ #

启发式策略与收敛性#

• 外层循环：交替执行 (a) 遍历所有样本 和 (b) 仅遍历非边界支持向量（$0 < \alpha_i < C$ ），因为边界变量极少移动。
• 第一变量：任选一个违反 KKT 条件超过容差的 $\alpha_i$ 。
• 第二变量：选择使 $\lvert E_1 - E_2 \rvert$ 最大的变量，这近似于最大步长启发式。

只要所选变量对未达最优，每步都会严格提升对偶目标值。结合目标函数有界及有限步长集合，SMO 必然收敛。实践中，SMO 比通用 QP 求解器快几个数量级；而通过增量维护误差缓存 $E_i$ ，可将每步复杂度控制在 $O(N)$ 而非 $O(N^2)$ 。

实践要点#

• 务必标准化特征：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（对决策值拟合逻辑回归）或保序回归。

练习题#

练习 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$ 也是有效核。

因 $K_1$ 和 $K_2$ 均满足 Mercer 条件，两项均非负。故 $K$ 半正定，是有效核。

练习 3 — 从支持向量数量看 $C$ #

问题： 100 个训练样本：$C = 0.1$ 时有 30 个支持向量；$C = 100$ 时有 15 个支持向量。解释原因。

解答： $C$ 较小时，松弛代价低，优化器倾向于扩大间隔带，更多点落入带内成为 $\alpha = C$ 的上界支持向量；$C$ 较大时，松弛惩罚重，间隔带收缩，落入带内的点减少，支持向量数量也随之减少。一般规律是：正则化越强（$C$ 越小），间隔越宽，支持向量越多。

练习 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 和逻辑回归的对比#

问题： 何时该用哪个？

解答。

常见问题#

为什么要最大化间隔？#

几何上，宽间隔能容忍更大噪声：只要扰动幅度小于间隔，预测结果就不会改变。统计上，基于间隔的泛化界（如通过 Rademacher 复杂度推导）表明，泛化误差随间隔增大而减小。因此，SVM 实质上是在隐式地控制模型复杂度。

为什么用对偶形式？#

主要有三点：(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$ 的样本不计损失，超出者成为支持向量。对偶框架同样适用，但每个样本对应两个乘子（$\alpha_i, \alpha_i^\*$ ，分别对应上下边界）。

为什么要标准化输入？#

$\eta$ 和核矩阵均涉及 $\lVert x \rVert$ 。若某特征量纲过大，会主导其他特征，导致决策边界偏向坐标轴对齐。将各特征标准化为零均值、单位方差（通常一行代码即可），常能显著提升训练速度与模型精度。

下一步#

到这里，监督学习的两条主流路线我都走了一遍：判别式（线性回归、逻辑回归、SVM、决策树）。它们都直接建模 $P(y\mid x)$ 或决策函数 $f(x)$ 。下一章我换到对偶面——生成式模型，从最简单的朴素贝叶斯开始。

生成式模型先建模 $P(x\mid y)$ 和 $P(y)$ ，再用贝叶斯公式反推 $P(y\mid x)$ 。朴素贝叶斯做了一个看似很离谱的假设：给定类别后，特征之间条件独立。这个假设在文本分类里几乎不成立，朴素贝叶斯却经常打得过逻辑回归——这是 ML 里最反直觉的结果之一。Ng 和 Jordan 在 2001 年那篇 paper 给出了答案：渐近误差更高的模型在小样本下反而更稳。理解这一现象，是后面所有"判别 vs 生成"权衡的起点。

参考文献#

• 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.
• Scholkopf, B., & Smola, A. J. (2002). Learning with Kernels. MIT Press.
• Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed.). Springer. Chapter 12.