第2章支持向量机

如果说第 1 章的感知机回答了”机器如何学会分类”，那么本章的支持向量机（Support Vector Machine, SVM）则追问一个更深刻的问题：在无数条都能把两类数据分开的分界线里，哪一条最稳妥？SVM 诞生于 1990 年代统计学习理论的黄金期，由瓦普尼克（V. Vapnik）等人奠定，它以凸优化的严谨求解、间隔最大化的泛化保证和核技巧的升维魔法，成为深度学习时代之前应用最广、理论最完备的分类器；即便在深度网络大行其道的今天，它仍是小样本、高维场景下最可靠的基线之一。

2.1 支持向量机基本思想

二分类任务，本质就是”找一条线”。给定两类样本 - 本章统一用蓝色表示类别 $+1$、红色表示类别 $-1$ - 分类器的目标是从数据中找出一条分界线，把两类样本分开。第 1 章的感知机已经能做到这一点：它的学习规则保证，只要数据线性可分，就一定能找到一条把训练样本全部正确分类的直线。但请注意，感知机只承诺”找到一条”，从不承诺”找到最好的一条”。

对于同一份数据，能正确分类的分界线其实有无穷多条：稍微倾斜一点、平移一点，都能把两类分开。它们对训练样本的表现完全相同，对新样本的泛化能力却天差地别。直观的答案是：离两类数据都尽量远的那条线最稳妥 - 因为它对样本位置的微小扰动最不敏感。设想一条线贴着某个样本挤过去，新样本只要带一点噪声、位置稍稍偏移，就会被甩到线的另一侧，判错类别；而一条”居中”的线，两侧都留有充足的余地，噪声再大也不容易越界。

图 2-1　三个候选分界线的间隔带对比：A、B 虽然也能分开两类，但间隔带窄；C 的间隔带最宽，对新样本最稳妥，因而获胜

把这条直觉形式化，就得到 SVM 的两个核心概念。其一，间隔带（margin band）：把一条分界线向两侧平行平移，直到它刚好碰到各自一侧最近的样本，两条平移线之间夹出的带状区域就是间隔带，其宽度称为间隔（margin）。其二，支持向量（support vector）：恰好落在间隔带边缘上的样本。绝大多数样本离分界线很远，无论分界线怎么挪都碰不到它们，对间隔带的位置毫无影响；真正”撑住”间隔带、决定分界线走向的，只有边缘上那少数几个样本 - 它们就像撑起帐篷的支柱，故而得名”支持向量”。

提示

生活类比 · 中立地带
间隔带就像两国边境的”中立地带”。缓冲区越宽，哨兵和车辆误入对方领土的概率越低；缓冲区窄到只剩一条线，任何风吹草动都会引发冲突。SVM 要做的，就是替两类数据划出最宽的缓冲地带 - 这既是直觉，也被统计学习理论严格证明：间隔越大，模型的 VC 维越低，泛化误差的上界越小。“间隔最大”不是拍脑袋，而是有理论支撑的最优选择。

注记

与第1章的对比
感知机 = “只要能分开就行”，它给出的是可行解；SVM = “在所有可行解中挑最稳的”，它求解的是一个优化问题。从”找一条线”到”找最稳的一条线”，正是本章 2.2 节要解决的数学问题。

2.2 线性硬可分支持向量机

现在把”间隔最大”翻译成数学。设训练集为 {($x_{1}$, $y_{1}$), …, ($x_{N}$, $y_{N}$)}，其中 $x_{i}$ ∈ ℝⁿ，标签 $y_{i}$ ∈ {+1, −1}。分类面是一个 $n$ 维超平面：

\[ w^\top x+b=0 \]

其中 $w$ 是法向量，$b$ 是偏置；判定规则是 $w$·$x$ + $b$ > 0 判为 +1，反之判为 −1。接下来需要度量”样本离分界线有多远”，这有两种自然的度量：

\[ \hat\gamma_i=y_i(w^\top x_i+b)\qquad\gamma_i=\frac{y_i(w^\top x_i+b)}{\lVert w\rVert} \]

函数间隔的缺陷是”随刻度漂移”：把 $w$、$b$ 同时放大 10 倍，超平面本身纹丝不动，函数间隔却膨胀为 10 倍。几何间隔则把 $w$ 的模长除掉 - 它正是样本到超平面的带符号距离（乘 $y_{i}$ 后取正），不随等比例缩放改变，这才是我们要最大化的”真间隔”。

为什么可以把间隔固定为 1？既然几何间隔与刻度无关，我们总可以同时缩放 $w$、$b$，让距离超平面最近的样本的几何间隔恰好等于 1 - 缩放不改变超平面，只是换了一把”尺子”。于是”所有样本的间隔 ≥ $\gamma{}$“就等价于约束 $y_{i}$($w$·$x_{i}$ + $b$) ≥ 1，而间隔宽度 $\gamma{}$ = (2)/(‖w‖)（超平面两侧各贡献 1）。最大化 $\gamma{}$ 等价于最小化 ‖$w$‖，为求导方便写成二次形式，得到 SVM 的主优化问题：

\[ \min_{w,b}\ \frac12\lVert w\rVert^2\qquad\text{s.t.}\quad y_i(w^\top x_i+b)\ge1,\ i=1,\ldots,N \]

这是一个凸二次规划（convex QP）问题：目标函数是凸二次函数，约束全部线性。凸性的意义非同小可 - 局部最优解必然就是全局最优解，不存在”陷入局部极小”的困扰，用现成的二次规划求解器即可可靠求出全局最优。这与第 1 章神经网络依赖梯度下降、可能陷于局部极小的处境形成鲜明对照。

拉格朗日对偶与 KKT 条件。为引入对偶问题，构造拉格朗日函数：

\[ L(w,b,\alpha)=\frac12\lVert w\rVert^2-\sum_i\alpha_i\left[y_i(w^\top x_i+b)-1\right] \]

对 $w$、$b$ 求偏导并令其为零，可得 $w$ = $\sum_{i}\alpha{}_{i}y_{i}x_{i}$ 与 $\sum_{i}\alpha{}_{i}y_{i}$ = 0，代回即得只含 $\alpha{}$ 的对偶问题。KKT 条件中的互补松弛条件 $\alpha{}_{i}$[$y_{i}$($w$·$x_{i}$+$b$) − 1] = 0 揭示了支持向量的本质：只有当样本恰好落在间隔边缘上（约束取等号）时，对应的 $\alpha{}_{i}$ 才大于 0；其余样本的 $\alpha{}_{i}$ = 0，对模型毫无贡献。

图 2-2　最大间隔分离超平面：只有落在间隔边缘上的样本（红圈）是支持向量，它们唯一决定分类面；间隔宽度 γ = 2/‖w‖

决策函数。把 $w$ = $\sum_{i}\alpha{}_{i}y_{i}x_{i}$ 代回 $w$·$x$ + $b$，决策函数变成只含”样本内积”的形式：

\[ f(x)=\operatorname{sign}\!\left(\sum_i\alpha_i y_i\langle x_i,x\rangle+b\right) \]

训练完成后，绝大多数 $\alpha{}_{i}$ = 0，求和号下只剩支持向量。也就是说，SVM 的模型就是少数几个支持向量及其权重 - 预测一个新样本，只需计算它与每个支持向量的内积再求和。这种稀疏性既是”支持向量机”名称的由来，也是它在实际部署中内存占用小、推理速度快的原因。

注记

稀疏性的价值
支持向量通常只占训练样本的很小比例（例如 5%–20%）。这意味着训练完成后可以把其余样本全部丢弃，模型只保存支持向量；对每个新样本的预测只需少数几次内积运算。在样本海量、存储昂贵的时代，这种”以小博大”的优雅让 SVM 格外珍贵。

2.3 线性软可分支持向量机

硬间隔有一个致命的脆弱点：它要求所有样本都严格满足 $y_{i}$($w$·$x_{i}$+$b$) ≥ 1。真实数据几乎总有噪声：某个样本被标错了标签、某个离群点乱入数据。此时可行域可能直接为空 - 问题无解；即便有解，间隔也可能被一个异常点压得极窄，泛化能力大打折扣。解决办法是软间隔：允许少数样本”越界”，但为每次越界付出代价。

为此引入松弛变量（slack variable）$\xi{}_{i}$ ≥ 0，把约束放宽为：

\[ y_i(w^\top x_i+b)\ge1-\xi_i\qquad\xi_i\ge0 \]

$\xi{}_{i}$ = 0 表示样本乖乖待在间隔带外；0 < $\xi{}_{i}$ < 1 表示它落在间隔带内、但仍在正确一侧；$\xi{}_{i}$ > 1 表示它被彻底分错。目标函数在”间隔最大”之外追加一项”越界总惩罚”，由惩罚参数 $C$ 平衡两者：

\[ \min_{w,b,\xi}\ \frac12\lVert w\rVert^2+C\sum_i\xi_i\qquad\text{s.t.}\quad y_i(w^\top x_i+b)\ge1-\xi_i,\ \xi_i\ge0 \]

惩罚参数 $C$ 的直觉。$C$ 衡量对越界行为的容忍度。$C$ 越大，越不允许样本越界，间隔带被迫收紧，训练误差小，但决策面贴着样本走，容易过拟合；$C$ 越小，越容忍错误，间隔带变宽、决策面更平滑，泛化通常更好，但 $C$ 过小会放任大量样本被分错，导致欠拟合。$C$ 与 $\gamma{}$ 是 SVM 最重要的两个超参数，实践中一律用交叉验证选择。

图 2-3　软间隔支持向量机：引入松弛变量 ξᵢ，允许个别样本越过间隔带甚至分错（红圈），目标函数在最大间隔与越界惩罚 C·Σξᵢ 之间取得平衡

铰链损失视角。把约束改写成损失函数，每个样本的代价是合页损失（hinge loss）：

\[ \ell_{\mathrm{hinge}}=\max\!\left(0,1-y_i(w^\top x_i+b)\right) \]

样本离超平面足够远（函数间隔 ≥ 1）时损失为 0，越界越多损失线性增长。于是软间隔 SVM 等价于”正则化经验风险最小化”：min Σ_i max(0, 1−$y_{i}$($w$·$x_{i}$+$b$)) + $λ$‖$w$‖²。这也点出了 SVM 与第 1 章感知机的本质差异：感知机的损失 max(0, −$y_{i}$($w$·$x_{i}$+$b$)) 只惩罚”分错”，合页损失还惩罚”分对了但离分界线太近” - SVM 不仅要求分对，还要求分得足够远、留足余地。对偶问题的变化同样简洁：拉格朗日乘子的上界从 ∞ 收紧为 $C$，即 0 ≤ $\alpha{}_{i}$ ≤ $C$；支持向量也随之分为两类 - 0 < $\alpha{}_{i}$ < $C$（落在间隔边缘上）与 $\alpha{}_{i}$ = $C$（越界或被分错）。

对比项	硬间隔 SVM	软间隔 SVM
约束条件	$y_{i}$($w$·$x_{i}$+$b$) ≥ 1 $y_{i}$($w$·$x_{i}	$+$b$) ≥ 1−${i}$，${i}$ ≥ 0
目标函数	min ½‖$w$‖² min	½‖$w$‖² + $C$Σ$\xi{}_{i}$
对偶变量范围	$\alpha{}_{i}$ ≥ 0	0 ≤ $\alpha{}_{i}$ ≤ $C$
容错能力	不允许任何样本越界	允许少量越界，每次付出代价 $C$
适用场景	数据严格线性可分、无噪声	数据含噪声、离群点，或近似线性可分

注记

C 的生活类比 · 罚款额度
$C$ 就像交通规则里的罚款金额。罚得越重（$C$ 大），司机越不敢违章，但为了零违章要修建大量绕行道路（间隔被迫收紧、决策面复杂化）；罚得轻（$C$ 小），违章增多但道路畅通（间隔宽、决策面平滑）。好的 $C$ 是在”零违章的代价”和”违章的损失”之间取平衡 - 这正是交叉验证要搜索的。

2.4 非线性支持向量机

线性模型的天花板在”线性不可分”数据面前暴露无遗：第 1 章提到感知机无法解决 XOR 问题；再比如同心圆数据 - 内圈一类、外圈一类 - 任何一条直线都无法把它们分开。硬间隔、软间隔都在”直线/超平面”的框架内打转，要突破必须换思路。

升维的思想。把数据映射到更高维空间，原本”拧成一团”的数据可能在高维空间被”展开”成线性可分的。以同心圆为例：映射 $\phi{}$($x_{1}$, $x_{2}$) = ($x_{1}$, $x_{2}$, $x_{1}^{2}$+$x_{2}^{2}$) 把所有点”拎”到三维空间的一个抛物面上 - 内圈点离原点近，$z$ 值小；外圈点离原点远，$z$ 值大。此时一个水平的平面 $z$ = $c$ 就能把两类干净地切开（见图 2-4）。

图 2-4　核技巧示意图：左图为线性不可分的同心圆数据；经 φ 映射到三维空间后（右图，示意为锥面），内圈与外圈被一个平面 z = c 干净分开；核函数让我们无需显式写出 φ 即可完成这一切

核技巧。直接做高维映射的障碍在于：映射后的维度可能爆炸（甚至无穷维），显式计算 $\phi{}$($x$) 完全不可行。但请注意 2.2 节的对偶问题与决策函数 - 样本永远只以内积 ⟨$x_{i}$, $x_{j}$⟩ 的形式出现。因此只要定义一个核函数：

\[ K(x,z)=\langle\phi(x),\phi(z)\rangle \]

就能”绕过”$\phi{}$，直接在低维空间算出高维内积 - 既获得高维表示的能力，又只付出低维计算的开销。这就是核技巧（kernel trick）。相应地，非线性 SVM 的决策函数为 $f$($x$) = sign(Σ_i $\alpha{}_{i}y_{i}K$($x_{i}$, $x$) + $b$)。选用不同的核函数，就等于对”什么样的相似度是合理的”做了不同的先验假设。常用核函数如下：

核函数	公式	特点
线性核	$K$($x$, $z$) = $x$ · $z$ 就是普通内积，等价于	线性 SVM；数据本就可分时最省事
多项式核	$K$($x$, $z$) = ($x$ · $z$ + $c$)^d 次数 $d$ 控制复杂度，$c$	为常数项；可处理一定程度的非线性
RBF / 高斯核	$K$($x$, $z$) = exp(−$\gamma{}$‖$x$ − $z$‖²) 最常用；$	$ 控制高斯峰宽，理论上能逼近任意连续决策面
Sigmoid 核	$K$($x$, $z$) = tanh($κx$ · $z$ + $\theta{}$) 与两层神经网络在数学上有	联系（参数 $κ$、$\theta{}$）

什么样的函数才能当核函数？Mercer 条件给出了一句话的答案：一个对称函数 $K$($x$, $z$) 是合法核函数，当且仅当对任意有限样本集，其 Gram 矩阵（第 $i$ 行 $j$ 列为 $K$($x_{i}$, $x_{j}$)）总是半正定的 - 直观地说，就是它必须真的对应某个高维空间中的内积。上表中的四个核函数都满足该条件。

注记

RBF 中 γ 的直觉
$\gamma{}$ 控制高斯”山丘”的宽度。RBF 核可以理解为一种相似度度量：$K$($x$, $z$) 越大，说明 $x$、$z$ 在高维空间中离得越近。$\gamma{}$ 太大 → 山丘又尖又窄，每个样本只影响极近的邻居，决策面弯弯曲曲”记住”了每个训练点，极易过拟合；$\gamma{}$ 太小 → 山丘宽而平，所有样本彼此几乎一样相似，决策面过于平滑，容易欠拟合。$\gamma{}$ 与 $C$ 一样，必须靠交叉验证在”太尖”与”太平”之间寻找平衡点。

2.5 SMO算法

对偶问题是一个 $N$ 变量的二次规划。当样本数 $N$ 达到数万乃至百万，通用 QP 求解器需要存储 $N$×$N$ 的核矩阵并做矩阵分解 - 内存和时间都不可接受。SVM 从理论走向实用，必须解决大规模求解问题，答案就是 1998 年 Platt 提出的SMO 算法（Sequential Minimal Optimization，序列最小优化）。

坐标上升的思想。一种朴素的想法是：固定其他所有变量，每次只优化一个变量，循环往复。对 SVM 对偶问题，单变量子问题确实容易解，但两个约束 $\sum_{i}\alpha{}_{i}y_{i}$ = 0 与 0 ≤ $\alpha{}_{i}$ ≤ $C$ 挡了路：只动一个 $\alpha{}_{i}$，等式约束立刻被破坏。必须同时动两个变量 - 一个增、一个减（按 $y$ 的比例），等式约束才可能保持。

SMO 的核心：每次固定其余 $N$−2 个变量，只优化两个变量 ($\alpha{}_{1}$, $\alpha{}_{2}$)。此时目标函数退化为关于 $\alpha{}_{2}$ 的一元二次函数，求导并令其为零即可得到解析解（闭式解），完全不需要迭代：

\[ \alpha_2^{\mathrm{new}}\leftarrow\alpha_2+\frac{y_2(E_1-E_2)}{\eta}\qquad\eta=K_{11}+K_{22}-2K_{12} \]

其中 $E_{k}$ = $f$($x_{k}$) − $y_{k}$ 是第 $k$ 个样本的预测误差，$\eta{}$ 由核函数值组合给出。求得 $\alpha{}_{2}$ 后先按 0 ≤ $\alpha{}$ ≤ $C$ 与等式约束裁剪，再恢复 $\alpha{}_{1}$（由 $\alpha{}_{1}$ + $y_{1}y_{2}\alpha{}_{2}$ = 常数反解）。

启发式选择。两个变量怎么挑，直接决定收敛速度。SMO 采用两轮启发式：外层循环遍历样本，优先选择违反 KKT 条件最严重的样本作为 $\alpha{}_{1}$ - 多数样本 $\alpha{}_{i}$ = 0 早就满足 KKT，很快被跳过，省下大量计算；内层循环为 $\alpha{}_{1}$ 挑选使 |$E_{1}$ − $E_{2}$| 最大的 $\alpha{}_{2}$ - 直觉上两者误差差异最大，更新步长最大，收敛最快；若找不到合适的 $\alpha{}_{2}$，则退化为遍历全部样本挑选。每轮更新后还要同步刷新偏置 $b$ 与误差缓存 $E$。完整流程如下：

初始化：$\alpha{}$ = 0，$b$ = 0，计算各样本误差 $E$；
外层循环：选择一个违反 KKT 条件最严重的样本作为 $\alpha{}_{1}$；
内层循环：选择使 |$E_{1}$ − $E_{2}$| 最大的样本作为 $\alpha{}_{2}$（找不到则遍历所有样本挑选）；
解析求解：按公式更新 $\alpha{}_{2}$，裁剪到 [0, $C$]，再恢复 $\alpha{}_{1}$；
更新：刷新偏置 $b$ 与误差缓存 $E$；
迭代：重复第 2–5 步，直至所有样本满足 KKT 条件（或目标函数变化小于阈值）时停止。

SMO 的价值在于：无需存储整个核矩阵（每次只访问两列）、每次更新都是解析一步到位、配合误差缓存在大规模稀疏数据（如文本分类的亿级词特征）上表现优异。它把 SVM 的适用规模从”几千样本”推进到”百万级样本”，是 SVM 真正走向工业应用的临门一脚。

注记

SMO 与梯度下降的对比
神经网络靠梯度下降让所有参数”一起慢慢挪”，每一步都很小；SMO 则像”逐个拧螺丝” - 每次只精确调好两个变量，用解析解一步到位，不需要学习率，也不担心步长太大震荡。正因如此，SMO 在二次规划求解上远比通用迭代法高效、稳定。

重要

本章要点

SVM 的思想是”在无数条能正确分类的分界线中，找间隔带最宽的那条”；落在间隔边缘上的少数样本称为支持向量，它们唯一决定决策面。
硬间隔 SVM 归结为凸二次规划 min ½‖$w$‖²，s.t. $y_{i}$($w$·$x_{i}$+$b$) ≥ 1；对偶问题中支持向量对应 $\alpha{}_{i}$ > 0，决策函数只依赖支持向量的内积，模型天然稀疏。
软间隔引入松弛变量 $\xi{}_{i}$ 与惩罚参数 $C$，目标为 min ½‖$w$‖² + $C$Σ$\xi{}_{i}$，等价于合页损失加正则化；$C$ 平衡”容错”与”泛化”。
核技巧 $K$($x$,$z$) = ⟨$\phi{}$($x$), $\phi{}$($z$)⟩ 让 SVM 无需显式计算高维映射即可处理非线性问题；常用核有线性、多项式、RBF（高斯）与 sigmoid，RBF 的 $\gamma{}$ 与 $C$ 需交叉验证调参。
SMO 每次固定其余变量、只解析求解两个 $\alpha{}$，配合”违反 KKT 最严重 + 步长最大”的启发式选择，使 SVM 可以扩展到大规模样本。

警告

延伸阅读 · 与现代AI的联系

核方法的”幽灵”在现代 AI 中无处不在：Transformer 的自注意力可以看作一种核平滑（softmax 核），高斯过程回归（GPR）以 RBF 核定义函数先验与后验，Mercer 核的思想还渗透进谱聚类、流形学习等无监督方法。理解核技巧，等于拿到了解读这些方法的通用钥匙。

在深度学习主宰大样本视觉/语言任务的今天，SVM 依然在小样本、高维、强可解释的场景占据一席之地：文本分类（词袋特征维度极高而样本稀疏）、生物信息学（基因表达数据样本少）、故障诊断与医学影像辅助判读中，SVM 常常是可靠基线甚至最终方案 - 它训练快、不依赖海量数据、模型由少数支持向量构成，天然可解释。

想深入拓展，可继续学习：支持向量回归（SVR）把间隔思想推广到回归任务；One-Class SVM 用于异常检测；ν-SVM 用参数 ν 更直观地控制支持向量比例；核岭回归（KRR）则是核方法与正则化回归的结合，在中小数据集上常常比深度网络更划算。

核函数	公式	特点
线性核	\(K\)(\(x\), \(z\)) = \(x\) · \(z\) 就是普通内积，等价于	线性 SVM；数据本就可分时最省事
多项式核	\(K\)(\(x\), \(z\)) = (\(x\) · \(z\) + \(c\))^d 次数 \(d\) 控制复杂度，\(c\)	为常数项；可处理一定程度的非线性
RBF / 高斯核	\(K\)(\(x\), \(z\)) = exp(−\(\gamma{}\)‖\(x\) − \(z\)‖²) 最常用；$	$ 控制高斯峰宽，理论上能逼近任意连续决策面
Sigmoid 核	\(K\)(\(x\), \(z\)) = tanh(\(κx\) · \(z\) + \(\theta{}\)) 与两层神经网络在数学上有	联系（参数 \(κ\)、\(\theta{}\)）