跳转到内容
← 返回算法
机器学习算法计算机科学 · 机器学习 · 统计学习约 25 分钟阅读

支持向量机

Support Vector Machines

1995 年，贝尔实验室的科琳娜·科尔特斯（Corinna Cortes）和弗拉基米尔·万普尼克（Vladimir Vapnik）发表论文《支持向量网络》，奠定了支持向量机（Support Vector Machine, SVM）的现代形态。其核心思想可追溯到更早：带核技巧的最大间隔分类器由 Boser、Guyon 与…

支持向量机SVM核方法分类凸优化

1995 年，贝尔实验室的科琳娜·科尔特斯（Corinna Cortes）和弗拉基米尔·万普尼克（Vladimir Vapnik）发表论文《支持向量网络》，奠定了支持向量机（Support Vector Machine, SVM）的现代形态。其核心思想可追溯到更早：带核技巧的最大间隔分类器由 Boser、Guyon 与 Vapnik 于 1992 年提出，而最大间隔与 VC 理论的源头则是 Vapnik 与 Chervonenkis 在 1960–70 年代的工作；1995 年这篇论文的关键贡献是引入"软间隔"，使方法能处理线性不可分的真实数据。在深度学习崛起之前的十余年里，SVM 是工业界和学术界最受信任的分类器——文本分类、人脸识别、生物信息学，几乎每个需要分类的领域都有 SVM 的身影。

SVM 的核心思想至今仍是机器学习理论的一块基石：用最大边距划分数据，并通过核技巧将低维不可分问题转化为高维可分问题。

破除误解：SVM 不是找任意分界线

给定两类线性可分的数据，能把它们分开的直线（或超平面）有无数条。直觉上，选哪条都行——但 SVM 指出，不同的分界线对未见数据的泛化能力差异极大。

SVM 的答案：选择最大化两类之间间距（Margin）的那条分界线。

这不只是直觉，背后有严格的统计学习理论支撑：更大的边距意味着更低的泛化误差上界（VC 理论）。

线性 SVM：最大边距分类器

设训练数据 {(xi,yi)}i=1n\{(x_i, y_i)\}_{i=1}^n，其中 yi∈{−1,+1}y_i \in \{-1, +1\}，寻找超平面 w⋅x+b=0w \cdot x + b = 0 使边距最大化。

边距（Margin）定义为两类数据中，距离分界超平面最近的点到超平面的距离之和：

margin=2∥w∥\text{margin} = \frac{2}{\|w\|}

最大化边距等价于最小化 ∥w∥2\|w\|^2，带约束：

min⁡w,b12∥w∥2s.t. yi(w⋅xi+b)≥1,∀i\min_{w, b} \frac{1}{2} \|w\|^2 \quad \text{s.t. } y_i(w \cdot x_i + b) \geq 1, \quad \forall i

这是一个二次规划（Quadratic Programming）问题，有唯一全局最优解。

支持向量：恰好满足 yi(w⋅xi+b)=1y_i(w \cdot x_i + b) = 1 的训练点，即距离分界面最近的点。这些点"支撑"着分界面——删去其他所有训练点，分界面不变。这也是 SVM 名称的来源。

手算最大边距超平面：三个点

"最大化边距"在小例子上可以完全用笔算完。取平面上三个点：

点坐标标签 $y$
x1x_1(3, 3)(3,\ 3)$+1$
x2x_2(4, 3)(4,\ 3)$+1$
x3x_3(1, 1)(1,\ 1)$-1$

直觉先行：正类里 x1x_1 离 x3x_3 更近（x2x_2 更远），所以分界线应当垂直于 x1−x3=(2, 2)x_1 - x_3 = (2,\ 2)，并从两点正中间穿过——即过点 (2, 2)(2,\ 2)、法向沿 $(1,1)$。那条直线是 x(1)+x(2)=4x^{(1)} + x^{(2)} = 4。

验证它确实是最优解。取 w=(0.5, 0.5)w = (0.5,\ 0.5)、$b = -2$（即 0.5x(1)+0.5x(2)−2=00.5x^{(1)} + 0.5x^{(2)} - 2 = 0，与上式同一条线），逐点检查约束 yi(w⋅xi+b)≥1y_i(w\cdot x_i + b) \geq 1：

点w⋅xi+bw\cdot x_i + byi(w⋅xi+b)y_i(w\cdot x_i + b)是否支持向量
x1=(3,3)x_1 = (3,3)$+1$1是（取等号）
x2=(4,3)x_2 = (4,3)$+1.5$1.5否（有余量）
x3=(1,1)x_3 = (1,1)$-1$1是（取等号）

三个约束全部满足，x1x_1 与 x3x_3 恰好取等号。于是 ∥w∥=0.52+0.52=0.5≈0.7071\|w\| = \sqrt{0.5^2 + 0.5^2} = \sqrt{0.5} \approx 0.7071，每个支持向量到超平面的距离是 1/∥w∥=2≈1.41421/\|w\| = \sqrt2 \approx 1.4142，边距宽度 =2/∥w∥=22≈2.8284= 2/\|w\| = 2\sqrt2 \approx 2.8284。

再从对偶问题算一遍，两条路径必须给出同一个答案。对偶问题是

max⁡α ∑iαi−12∑i,jαiαjyiyj (xi⋅xj),s.t. ∑iαiyi=0, αi≥0\max_{\alpha}\ \sum_i \alpha_i - \frac12\sum_{i,j}\alpha_i\alpha_j y_i y_j\,(x_i\cdot x_j), \qquad \text{s.t. } \sum_i \alpha_i y_i = 0,\ \alpha_i \geq 0

先算内积：x1⋅x1=18x_1\cdot x_1 = 18、x1⋅x2=21x_1\cdot x_2 = 21、x1⋅x3=6x_1\cdot x_3 = 6、x2⋅x2=25x_2\cdot x_2 = 25、x2⋅x3=7x_2\cdot x_3 = 7、x3⋅x3=2x_3\cdot x_3 = 2。

取 α2=0\alpha_2 = 0（x2x_2 不是支持向量），则约束 ∑iαiyi=0\sum_i\alpha_i y_i = 0 给出 α1=α3=α\alpha_1 = \alpha_3 = \alpha。代入目标：

2α−12[18α2+2α2−2×6α2]=2α−4α22\alpha - \frac12\left[18\alpha^2 + 2\alpha^2 - 2\times 6\alpha^2\right] = 2\alpha - 4\alpha^2

求导取零：2−8α=02 - 8\alpha = 0，得 α=0.25\alpha = 0.25，目标值 $0.25$。回代得

w=∑iαiyixi=0.25 (3,3)−0.25 (1,1)=(0.5, 0.5)w = \sum_i \alpha_i y_i x_i = 0.25\,(3,3) - 0.25\,(1,1) = (0.5,\ 0.5)

$b$ 由任一支持向量的等号条件确定：0.5×3+0.5×3+b=1⇒b=−20.5\times3 + 0.5\times3 + b = 1 \Rightarrow b = -2。与直觉解完全一致。

再核对一遍强对偶性：原问题最优值 12∥w∥2=0.25\frac12\|w\|^2 = 0.25，对偶最优值也是 $0.25$，对偶间隙为零——符合凸二次规划的理论保证。顺手还能验证一个漂亮的恒等式：∑iαi=0.5=∥w∥2\sum_i\alpha_i = 0.5 = \|w\|^2，于是边距宽度 =2/∑iαi= 2/\sqrt{\textstyle\sum_i\alpha_i}。α\alpha 之和越小，边距越宽。

这个例子最该注意的是 x2x_2：把它删掉，甚至把它挪到 (10, 10)(10,\ 10)，解一个字都不会变。SVM 的解只由贴着边界的那几个点决定，绝大多数数据在训练完成后对模型毫无贡献。 这既是它的优雅之处，也埋下了后面要讲的麻烦。

软边距：允许错误

真实数据往往不可线性分离。软边距 SVM（Soft-Margin SVM）引入松弛变量 ξi≥0\xi_i \geq 0，允许部分训练点违反约束，但对违反程度施加惩罚：

min⁡w,b,ξ12∥w∥2+C∑i=1nξi\min_{w, b, \xi} \frac{1}{2} \|w\|^2 + C \sum_{i=1}^n \xi_i s.t. yi(w⋅xi+b)≥1−ξi,ξi≥0\text{s.t. } y_i(w \cdot x_i + b) \geq 1 - \xi_i, \quad \xi_i \geq 0

超参数 $C > 0$ 控制边距与分类错误之间的权衡：$C$ 大则容错少，边距窄；$C$ 小则容错多，边距宽。

对偶与 KKT：为什么只有支持向量的 $\alpha_i > 0$

上一节"取 α2=0\alpha_2 = 0"不是运气，它由 KKT 条件强制。

软边距 SVM 的拉格朗日函数给每个样本配一个乘子 αi\alpha_i，最优解必须满足互补松弛条件（Complementary Slackness）：

αi[yi(w⋅xi+b)−1+ξi]=0\alpha_i\left[y_i(w\cdot x_i + b) - 1 + \xi_i\right] = 0

两个因子相乘为零，意味着二者必有一个为零。这就把所有样本干净地切成三类：

情形αi\alpha_iyi(w⋅xi+b)y_i(w\cdot x_i + b)几何位置
非支持向量αi=0\alpha_i = 0$> 1$在边距带之外，分类正确且有余量
边界支持向量0<αi<C0 < \alpha_i < C$= 1$恰好落在边距边界上
越界支持向量αi=C\alpha_i = C$< 1$侵入边距带内，或干脆被分错

第一行是关键：只要一个点离边界还有余量，它的 αi\alpha_i 必须为 0，于是它在 w=∑iαiyixiw = \sum_i \alpha_i y_i x_i 里的贡献是零，在预测函数里整项消失。这不是什么稀疏化技巧，是最优性条件的直接推论——SVM 的稀疏性是被证明出来的，不是被鼓励出来的。

第三行则揭示了 $C$ 的真实身份：它是单个样本影响力的上限。αi≤C\alpha_i \leq C 意味着任何一个点——包括一个标注错误的离群点——对 $w$ 的贡献都被 $C$ 卡住。$C$ 小则谁都推不动模型（欠拟合、边距过宽），$C$ 大则一个错误标注就能把超平面拽歪（过拟合）。把 $C$ 理解成"容错程度"是模糊的，理解成"每个样本的最大投票权重"就精确了，也就知道数据噪声大时该往哪个方向调。

预测函数的形状也在这里定下来：

f(x)=∑i∈SVαiyi K(xi,x)+bf(x) = \sum_{i \in SV} \alpha_i y_i\, K(x_i, x) + b

求和只跑支持向量，而原始向量 xix_i 只通过核函数出现。这两件事合起来才使核技巧可行——否则你必须显式写出那个可能是无穷维的 ϕ(x)\phi(x)。

核技巧：低维不可分 → 高维可分

线性 SVM 只能找线性分界面。对非线性可分数据，SVM 的解决方案是将数据映射到更高维特征空间，在高维空间中线性可分。

设映射 ϕ:X→H\phi: \mathcal{X} \to \mathcal{H}，在 H\mathcal{H} 中运行线性 SVM。

核技巧（Kernel Trick）：SVM 的对偶形式中，映射后的数据只以内积 ϕ(xi)⋅ϕ(xj)\phi(x_i) \cdot \phi(x_j) 的形式出现。定义核函数（Kernel Function）：

K(xi,xj)=ϕ(xi)⋅ϕ(xj)K(x_i, x_j) = \phi(x_i) \cdot \phi(x_j)

只要核函数满足 Mercer 条件（半正定性），就不需要显式计算 ϕ\phi，直接计算核函数值即可——即使对应的特征空间是无穷维的！

核函数公式适用场景
线性核K(x,z)=x⋅zK(x, z) = x \cdot z高维稀疏数据（文本）
多项式核K(x,z)=(x⋅z+c)dK(x, z) = (x \cdot z + c)^d有限阶多项式关系
RBF 高斯核$K(x, z) = e^{-\x-z\^2 / (2\sigma^2)}$通用，最常用
字符串核定义在序列上文本、生物序列

核矩阵长什么样：XOR 的四个点

"映射到高维就线性可分了"这句话讲了很多遍，但很少有人把核矩阵的数字摆出来看。用最小的非线性可分例子——XOR：

点坐标标签
x1x_1(1, 1)(1,\ 1)$+1$
x2x_2(−1, −1)(-1,\ -1)$+1$
x3x_3(1, −1)(1,\ -1)$-1$
x4x_4(−1, 1)(-1,\ 1)$-1$

这四个点在平面上没有任何直线能分开。取二次多项式核 K(x,z)=(x⋅z)2K(x,z) = (x\cdot z)^2，核矩阵是：

$K$x1x_1x2x_2x3x_3x4x_4
x1x_14400
x2x_24400
x3x_30044
x4x_40044

这个矩阵最该注意的是它的分块结构：同类点之间的核值全是 4，异类点之间全是 0。核矩阵已经把答案摊在桌面上了——它就是"谁跟谁像"的完整记录，而在这个相似度下，同类点完全相似、异类点完全正交。SVM 接下来做的事只是在这张表上解一个二次规划，从头到尾不需要知道点的坐标。

对应的显式特征映射是 ϕ(x)=(x12, 2 x1x2, x22)\phi(x) = \left(x_1^2,\ \sqrt2\,x_1x_2,\ x_2^2\right)，因为

ϕ(x)⋅ϕ(z)=x12z12+2x1x2z1z2+x22z22=(x1z1+x2z2)2\phi(x)\cdot\phi(z) = x_1^2z_1^2 + 2x_1x_2z_1z_2 + x_2^2z_2^2 = (x_1z_1 + x_2z_2)^2

代进四个点：ϕ(x1)=ϕ(x2)=(1, 2, 1)\phi(x_1) = \phi(x_2) = (1,\ \sqrt2,\ 1)，ϕ(x3)=ϕ(x4)=(1, −2, 1)\phi(x_3) = \phi(x_4) = (1,\ -\sqrt2,\ 1)。两类各自塌成了一个点，在第二个坐标上相隔 222\sqrt2。分界面是 x1x2=0x_1x_2 = 0——在原空间里是两条坐标轴组成的十字，在特征空间里是一张平面。这就是"高维线性可分"具体的样子。

RBF 核 K(x,z)=e−γ∥x−z∥2K(x,z) = e^{-\gamma\|x-z\|^2} 的两个极端也能直接从核矩阵读出来。γ→∞\gamma \to \infty 时只有对角项是 1，其余全趋于 0，核矩阵变成单位矩阵——每个训练点自成一类，模型退化成一张查找表，训练误差 0、泛化能力 0。γ→0\gamma \to 0 时所有元素都趋于 1，核矩阵近似全一矩阵，所有点被视为完全相同，模型退化成常数。γ\gamma 真正在调的是核矩阵离单位矩阵有多远。

这个视角比"控制高斯的宽度"更有操作性，也解释了 scikit-learn 的默认值为什么长成那样：gamma="scale" 取 1/(p⋅Var(X))1/(p \cdot \mathrm{Var}(X))，$p$ 为特征数。γ\gamma 的量纲是长度平方的倒数，所以它必须随数据的方差反向缩放——把 $X$ 整体放大 10 倍，γ\gamma 就得缩小 100 倍才等价。0.22 版之前的默认值 "auto" 只用了 $1/p$，忽略了方差这一项，在未标准化的数据上表现会明显变差。这也是"用 RBF 核前必须标准化特征"这条老规矩的由来。

与深度学习的对比

维度SVM深度神经网络
理论基础统计学习理论（VC 维）主要靠经验
全局最优保证（凸优化）不保证（非凸）
大数据扩展性困难（O(n2)O(n^2) 核矩阵）天然适合（SGD）
特征工程高度依赖核函数选择端到端自动特征学习
小数据性能通常较好容易过拟合
可解释性支持向量可追溯黑盒

深度学习崛起后，SVM 在图像分类等任务上的优势消失。但在小样本、高维稀疏数据（如基因表达分析、文本分类）领域，SVM 仍然有竞争力。

代价与争议

扩展性：核 SVM 训练时间复杂度约 O(n2)O(n^2) 到 O(n3)O(n^3)，n>105n > 10^5 时实际上不可行。线性 SVM（如 Liblinear）可通过 SGD 扩展到大数据。

核函数选择：核函数的选择直接决定 SVM 的性能，但没有系统的方法，依赖经验和交叉验证。

多类分类：SVM 本质是二分类器，多类问题需要"一对一"或"一对其余"策略，计算代价倍增。

概率输出：SVM 直接输出类别标签，不给出概率，需要额外的 Platt Scaling 来估计概率。

SVM 为什么退场：一笔存不下的核矩阵

"深度学习赢了"是个太笼统的解释。核 SVM 退出主流有一个非常具体、可以用数字说清的原因。

它的对偶问题需要核矩阵 $K$，而 $K$ 是 n×nn \times n 的：

训练样本数 $n$核矩阵元素个数float64 存储
10410^410810^80.7 GiB
10510^5101010^{10}74.5 GiB
10610^6101210^{12}7.3 TiB

这张表最该注意的是它跳得多快：样本数每涨 10 倍，内存涨 100 倍。n=105n = 10^5 时核矩阵已经放不进一台普通机器的内存，而 10510^5 在今天连"中等规模"都算不上。训练时间更糟——SMO 类分解算法的实测复杂度在 O(n2)O(n^2) 到 O(n3)O(n^3) 之间，样本数从 10410^4 涨到 10610^6，时间要乘 10410^4 到 10610^6 倍。

Platt 在 1998 年提出的序列最小优化（Sequential Minimal Optimization, SMO）是让 SVM 在当年真能跑起来的关键工程突破。它每次只挑两个乘子来优化——之所以是两个而不是一个，是因为等式约束 ∑iαiyi=0\sum_i\alpha_i y_i = 0 让单个乘子无法独立变动，必须两个一起调才能守住这个约束——而两变量的子问题有解析解，于是完全绕开了通用二次规划求解器和它对内存的要求。LIBSVM 用的是它的改进版，采用二阶信息来选工作集（Fan、Chen 与 Lin, JMLR 2005）。但要点在于：SMO 把常数因子压得很低，没有改变 O(n2)O(n^2) 这个量级——它让算法可用，不是让它可扩展。

还有一层更隐蔽的代价：支持向量的数量本身随 $n$ 线性增长。Steinwart 在 2003 年（JMLR）给出了渐近结果：对配高斯核的 L1-SVM，支持向量占样本的比例趋于贝叶斯风险的两倍。也就是说只要数据有内在噪声（贝叶斯风险 $> 0$），支持向量数就是 Θ(n)\Theta(n)。而预测时要对每个支持向量算一次核，于是推理时间也随训练集大小线性增长。这和神经网络形成刺眼的对照：网络训练完就是一堆固定的权重，见过 100 万还是 1 亿样本，推理成本一模一样；SVM 的模型体积与推理成本却会随着数据变多而一起变差。前面那句"绝大多数数据训练完就没用了"在这里翻了面——理论上没用，实践中却必须整套背着走。

对照线性 SVM 的命运会更清楚。丢掉核之后，$w$ 可以显式表示，不再需要核矩阵；LIBLINEAR（Fan 等人, JMLR 2008）与各种随机梯度方法能把线性 SVM 推到千万级样本。所以准确的说法不是"SVM 被淘汰了"——线性 SVM 至今活跃在高维稀疏文本分类里，被淘汰的是核 SVM。

最后一个值得记住的对照：核 SVM 曾经就是图像识别的最强方法。DeCoste 与 Schölkopf 用高斯核加虚拟支持向量（把已找到的支持向量做微小平移，生成新的训练样本，从而把平移不变性直接注入模型）在 MNIST 手写数字上取得 0.56% 的测试错误率，是当时公开报告的最好成绩。它输给深度学习不是因为精度上限低，而是因为这条路上每提升一点精度都要人手工注入一份先验——选核函数、造虚拟样本；而卷积网络把同一份先验（平移不变性）写进了架构里，剩下的交给数据。

统计学习理论：SVM 为何有泛化保证

SVM 之所以在理论上备受重视，是因为它有明确的泛化误差界。根据结构风险最小化（Structural Risk Minimization, SRM）原理，学习器的泛化误差可以被上界为：

GenError≤TrainError+O ⁣(hlog⁡(2n/h)−log⁡(δ/4)n)\text{GenError} \leq \text{TrainError} + O\!\left(\sqrt{\frac{h \log(2n/h) - \log(\delta/4)}{n}}\right)

其中 $h$ 是模型的 VC 维（Vapnik-Chervonenkis Dimension），$n$ 是训练样本数，δ\delta 是置信水平。

SVM 通过最大化边距来控制 VC 维（而不是直接控制参数数量），使得即使在高维甚至无穷维特征空间中，只要数据能被大边距分开，泛化误差上界也是有限的。这是核 SVM 理论上能在高维特征空间中工作的根本原因。

与深度学习的对比：深度网络的参数远多于训练样本，经典 VC 理论预测应该严重过拟合，但实践中表现良好。这个"双重下降"现象至今缺乏完整理论解释。SVM 的泛化理论更完善，但在大数据场景下的工程优势不如深度网络。

跨域连接

  • 最优化：这是凸优化在机器学习里最完整的一次落地：带线性约束的二次规划、拉格朗日对偶、KKT 条件、强对偶性四件事齐备。关键推论是稀疏性由互补松弛直接给出——离边界还有余量的样本，其乘子必须为零。稀疏不是被鼓励出来的技巧，是被证明出来的性质。
  • 泛函分析：核函数满足半正定条件，等价于说核矩阵是某个内积空间里的格拉姆矩阵。于是特征空间必然存在，哪怕你永远不把它写出来。整个核方法就建立在这个等价上：只要能给出"谁跟谁像"的一张表，高维映射就不必被显式构造。
  • 主成分分析：两者都在用少数方向表示数据，但方向的来源不同。一个由方差挑出，与标签无关；一个由间隔挑出，直接对着分类目标。这解释了降维为何可能损伤分类：判别信息若落在方差很小的方向上，无监督的选择会先把它丢掉。
  • 基因调控：表达谱这类数据的特征数远多于样本数，依赖参数计数的泛化论证在此失效。而基于间隔的界不含维数，只要数据能被大间隔分开就仍然有效——这是这类方法在高维小样本的组学数据上长期占优的形式理由，不只是经验观察。
  • 卷积神经网络：两条路线注入先验的方式截然不同。核方法靠人挑核函数、靠人造平移过的样本把不变性喂进去；卷积网把同一份不变性写进架构，剩下的交给数据。胜负的关键不是精度上限，而是先验由谁提供、能否随规模自动摊薄。

参考文献

  • Cortes, C. & Vapnik, V. Support-Vector Networks. Machine Learning 20(3), 273–297 (1995).
  • Boser, B. E., Guyon, I. M. & Vapnik, V. N. A Training Algorithm for Optimal Margin Classifiers. COLT 1992, 144–152.（核技巧与最大间隔分类器的结合）
  • Vapnik, V. The Nature of Statistical Learning Theory. Springer, 1995.
  • Platt, J. C. Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Microsoft Research Technical Report MSR-TR-98-14 (1998).
  • Fan, R.-E., Chen, P.-H. & Lin, C.-J. Working Set Selection Using Second Order Information for Training Support Vector Machines. JMLR 6, 1889–1918 (2005).
  • Chang, C.-C. & Lin, C.-J. LIBSVM: A Library for Support Vector Machines. ACM TIST 2(3), Article 27 (2011).
  • Fan, R.-E. et al. LIBLINEAR: A Library for Large Linear Classification. JMLR 9, 1871–1874 (2008).
  • Steinwart, I. Sparseness of Support Vector Machines. JMLR 4, 1071–1105 (2003).（支持向量比例趋于贝叶斯风险两倍）
  • DeCoste, D. & Schölkopf, B. Training Invariant Support Vector Machines. Machine Learning 46(1–3), 161–190 (2002).（虚拟支持向量与 MNIST 上 0.56% 的错误率）

延伸阅读

  • Schölkopf, B. & Smola, A. J. Learning with Kernels. MIT Press, 2002.
  • Burges, C. J. C. A Tutorial on Support Vector Machines for Pattern Recognition. Data Mining and Knowledge Discovery 2, 121–167 (1998).（对偶推导与 KKT 条件写得最清楚的一篇导读）
  • 李航《统计学习方法》第 2 版，清华大学出版社，2019.（第 7 章有与本文同类型的手算例题）

正文中引用本条 · 3 · 其中 2 条来自其他领域

宇宙学疏散星团
数学泛函分析