第十讲 · 支持向量机

线性可分的数据通常不只存在一条分界线。支持向量机（Support Vector Machine，SVM）不满足于“把训练样本分对”，而是要在两类之间留下尽可能宽的安全带。分界线离最近的样本越远，小扰动就越不容易改变预测。

本讲的主线是：线性分类器 → 最大间隔 → 约束优化 → 对偶与 KKT → 软间隔 → 核方法。最后再看实际训练为什么常用 SMO。

先看历史：SVM 解决了什么旧问题

1957 年提出的感知机已经能用监督学习寻找线性边界，但无法解决异或等线性不可分问题。后来多层网络与反向传播可以表达非线性边界，却一度缺少成熟的泛化理论，而且训练效果高度依赖模型规模、数据和优化。

Vapnik 在 1960 年代提出支持向量思想，Kimeldorf 等人在 1970 年代发展了与核空间有关的方法；1992 年最优间隔分类器工作推动 SVM 形成，1995 年前后软间隔 SVM 与统计学习理论得到系统阐述。SVM 的里程碑意义在于：它把泛化、模型容量和可解的凸优化连接起来，并用核技巧优雅处理非线性。

一、从经验风险到结构风险

模型在真实数据分布上的期望风险为

$$R(f)=\mathbb E_{(x,y)\sim P}\bigl[L(y,f(x))\bigr],$$

但真实分布 $P$ 不可知，只能在 $n$ 个训练样本上计算经验风险

$$R_{\mathrm{emp}}(f)=\frac1n\sum_{i=1}^n L(y_i,f(x_i)).$$

只把训练误差压到最低并不保证泛化最好：模型越复杂，越可能连训练集里的偶然噪声也记住。统计学习理论用 VC 维刻画假设类的容量，并给出“真实风险不超过经验风险加复杂度项”的概率界。这里不必死记课件中的常数，真正要记住的是关系：

$$\text{真实风险上界} =\text{经验风险}+\text{随模型复杂度增大的置信项}.$$

结构风险最小化（Structural Risk Minimization）的思想，就是在“训练集分得准”和“模型不要太复杂”之间找平衡。SVM 用最大间隔把这个思想变成一个可计算的凸优化问题。

二、线性分类器的几何意义

二分类标签记作 $y_i\in\{-1,+1\}$，线性判别函数为

$$g(x)=w^{\mathsf T}x+b.$$

• $g(x)=0$ 是分类超平面；
• $w$ 是超平面的法向量，决定朝向；
• $b$ 决定超平面的平移；
• $\operatorname{sign}(g(x))$ 给出类别。

点 $x$ 到超平面的有符号距离是

$$\frac{w^{\mathsf T}x+b}{\lVert w\rVert_2}.$$

因此线性分类器也可以理解为：先把样本投影到法向量 $w$ 上，再用阈值 $-b$ 做一维分类。

三、硬间隔：把安全带做到最宽

对线性可分数据，可以缩放 $(w,b)$，让离超平面最近的正负样本满足

$$w^{\mathsf T}x+b=+1, \qquad w^{\mathsf T}x+b=-1.$$

两条间隔边界之间的距离为 $2/\lVert w\rVert_2$。最大化间隔等价于最小化 $\lVert w\rVert_2^2$，于是硬间隔 SVM 的原问题是

$$\begin{aligned} \min_{w,b}\quad &\frac12\lVert w\rVert_2^2\\ \text{s.t.}\quad &y_i(w^{\mathsf T}x_i+b)\ge 1, \quad i=1,\ldots,n. \end{aligned}$$

约束中的 $y_i$ 把正负两类统一到一个式子里：标签与判别值同号且离边界至少一个单位。

拉格朗日对偶

给每条约束引入乘子 $\alpha_i\ge0$：

$$\mathcal L(w,b,\alpha) =\frac12\lVert w\rVert_2^2 -\sum_{i=1}^n\alpha_i\bigl[y_i(w^{\mathsf T}x_i+b)-1\bigr].$$

分别对 $w$ 与 $b$ 求偏导并令其为零：

$$w=\sum_{i=1}^n\alpha_i y_i x_i, \qquad \sum_{i=1}^n\alpha_i y_i=0.$$

代回拉格朗日函数，得到只含 $\alpha$ 的对偶问题：

$$\begin{aligned} \max_{\alpha}\quad &\sum_i\alpha_i- \frac12\sum_i\sum_j \alpha_i\alpha_jy_iy_jx_i^{\mathsf T}x_j\\ \text{s.t.}\quad &\alpha_i\ge0, \qquad \sum_i\alpha_i y_i=0. \end{aligned}$$

这个变形带来两个关键结果：样本只通过内积 $x_i^{\mathsf T}x_j$ 出现；最终通常只有少数 $\alpha_i$ 非零。

KKT 条件与支持向量

最优解还满足互补松弛条件

$$\alpha_i\bigl[y_i(w^{\mathsf T}x_i+b)-1\bigr]=0.$$

它表示每个样本二选一：

• 若样本严格位于间隔外，括号大于 $0$，则必须有 $\alpha_i=0$；
• 若 $\alpha_i>0$，样本必在间隔边界上，即 $y_i(w^{\mathsf T}x_i+b)=1$。

后一类样本就是支持向量。由 $w=\sum_i\alpha_i y_i x_i$ 可见，最终分类面只由支持向量决定；远离边界的样本即使删掉，解通常也不变。

四、课件四点例子的完整计算

训练样本为

$$\begin{array}{c|c} x_i & y_i\\ \hline (0,0)^{\mathsf T} & +1\\ (1,0)^{\mathsf T} & +1\\ (2,0)^{\mathsf T} & -1\\ (0,2)^{\mathsf T} & -1 \end{array}$$

二次规划给出的乘子为

$$\alpha_1=0,\quad \alpha_2=1,\quad \alpha_3=\frac34,\quad \alpha_4=\frac14.$$

于是

$$\begin{aligned} w &=\sum_i\alpha_i y_i x_i\\ &=(1,0)^{\mathsf T} -\frac34(2,0)^{\mathsf T} -\frac14(0,2)^{\mathsf T}\\ &=\left(-\frac12,-\frac12\right)^{\mathsf T}. \end{aligned}$$

课件继续给出 $b=3/4$，因此分类面为

$$-\frac12x_1-\frac12x_2+\frac34=0,$$

也就是 $x_1+x_2=3/2$。课件这组系数使用了非单位的函数间隔：三个支持向量的 $y_i g(x_i)$ 都是 $1/4$，不是前文规范化约定的 $1$。决策只看符号，整体缩放不改变分类面；若要与标准硬间隔原问题严格一致，把 $w,b,\alpha$ 同乘 $4$：

$$w=(-2,-2)^{\mathsf T},\qquad b=3,$$ $$(\alpha_1,\alpha_2,\alpha_3,\alpha_4)=(0,4,3,1).$$

此时支持向量 $(1,0)$、$(2,0)$、$(0,2)$ 都满足 $y_i g(x_i)=1$；而 $(0,0)$ 满足 $y_1g(x_1)=3>1$，所以它不是支持向量，恰好对应 $\alpha_1=0$。

五、软间隔：现实数据不可能永远可分

离群点或重叠类别会让硬间隔无解。给每个样本加入松弛变量 $\xi_i\ge0$：

$$\begin{aligned} \min_{w,b,\xi}\quad &\frac12\lVert w\rVert_2^2+C\sum_i\xi_i\\ \text{s.t.}\quad &y_i(w^{\mathsf T}x_i+b)\ge1-\xi_i. \end{aligned}$$

$C$ 控制“宽间隔”和“少违规”的取舍：

• $C$ 很大：重罚训练错误，边界努力迁就每个点，可能更容易过拟合；
• $C$ 较小：允许少量样本越界，换取更宽、更平滑的间隔。

其对偶形式与硬间隔几乎相同，只把约束改成

$$0\le\alpha_i\le C.$$

也可以把软间隔写成无约束的合页损失：

$$\min_{w,b}\quad \frac12\lVert w\rVert_2^2 +C\sum_i\max\bigl(0,1-y_i g(x_i)\bigr).$$

这更直观地说明：离间隔足够远的点损失为零，进入间隔或分错的点才受罚。

六、核技巧：不显式进入高维空间

异或问题在二维空间线性不可分，但加入 $z=x_1x_2$ 后，在三维空间可以被平面分开。更一般地，用非线性映射 $\phi(x)$ 把样本送入高维特征空间，再做线性 SVM。

直接计算 $\phi(x)$ 可能非常昂贵。对偶问题只需要内积，因此可用核函数

$$K(x_i,x_j)=\phi(x_i)^{\mathsf T}\phi(x_j)$$

直接得到高维内积，这就是核技巧。预测函数变为

$$f(x)=\operatorname{sign}\left( \sum_{i\in\mathrm{SV}}\alpha_i y_i K(x_i,x)+b \right).$$

常用核函数包括：

$$K_{\mathrm{poly}}(x,z)=(x^{\mathsf T}z+c)^q,$$ $$K_{\mathrm{RBF}}(x,z)= \exp\left(-\frac{\lVert x-z\rVert_2^2}{2\sigma^2}\right),$$

以及满足相应条件时可用的 Sigmoid 核。不是任意“相似度”都能当核；合法核的 Gram 矩阵应为半正定，这与课件提到的 Mercer 条件相对应。

七、大数据怎样训练：Chunking 与 SMO

SVM 的对偶是带约束二次规划。样本很多时，完整核矩阵会消耗 $O(n^2)$ 内存。课件介绍了两种分解思路：

1. Chunking：每次只优化一小批样本，保留支持向量，再加入违反约束的样本继续训练；
2. SMO：每次只更新两个拉格朗日乘子，因为约束 $\sum_i\alpha_i y_i=0$ 使它们必须成对变化。

设误差 $E_i=f(x_i)-y_i$，两点的核值满足

$$\eta=K(x_1,x_1)+K(x_2,x_2)-2K(x_1,x_2),$$

则未裁剪的更新可写成

$$\alpha_2^{\mathrm{new}} =\alpha_2^{\mathrm{old}} +\frac{y_2(E_1-E_2)}{\eta},$$

再按标签是否相同把它裁剪到允许区间 $[L,H]$，并由线性约束更新 $\alpha_1$。SMO 的价值不在背完整推导，而在理解：把大二次规划拆成许多个有解析解的两变量小问题，并优先选择最违反 KKT 的点。

八、应用与多类扩展

课件给出手写数字识别和滑窗人脸检测。手写数字有十类，二分类 SVM 通常用 one-vs-rest 或 one-vs-one 组合成多类分类器。历史课件引用的美国邮政数字实验使用 7291 个训练样本、2007 个测试样本，每张图为 $16\times16$ 维；其中记录的错误率为：

分类者	历史实验错误率
人工表现	$2.5\%$
C4.5 决策树	$16.2\%$
当时最好的两层神经网络	$5.9\%$
SVM	$4.0\%$

这些数字只属于特定年代、数据划分和实现，不能拿来判断今天模型的相对强弱。

人脸检测流程是：把输入图缩放到多个尺度，截取 $19\times19$ 窗口，对窗口做遮罩、光照校正和直方图均衡，再交给 SVM；若判为人脸，就在原图画出对应框。

课件还列出 LibSVM、SVMlight、BSVM、mySVM 与 MATLAB SVM toolbox 等工具，其中 LibSVM 以接口简单和实现成熟而广泛使用。工具会替我们解优化问题，但特征缩放、核函数、$C$ 与核参数仍需正确设置。

这些例子也提示 SVM 的边界：它在中小规模、特征较清晰的数据上很强，但核 SVM 随样本量增长较慢；现代大规模视觉任务更常用可端到端学习特征的深度网络。

九、常见误区与 sanity check

• 间隔是 $2/\lVert w\rVert$，不是 $2\lVert w\rVert$。 放大 $w,b$ 不会改变分类面，所以必须先做规范化。
• 支持向量不是“离原点最近”的点。 它们是离分类超平面最近、对应 $\alpha_i>0$ 的点。
• 核方法没有让问题凭空变线性。 它是在隐式特征空间中做线性分类，原空间边界仍可高度非线性。
• $C$ 越大不等于模型一定越好。 它只是更重视训练误差，需要用验证集选择。
• 手算完成后应检查 $\sum_i\alpha_i y_i=0$、$\alpha_i$ 的取值范围，以及支持向量是否满足 KKT 等式。