第四讲 · 支持向量机 SVM

SVM 是判别式方法的代表，也是本课公式推导最长的一部分。推导顺序是：±1 标签 → 最大间隔 → 规范化 → 基本型 → 对偶 → KKT → 软间隔。

一、动机：最大间隔

线性可分时，能分开两类的超平面有无数个。SVM 要的是分类间隔（Margin）最大的那个——离两类最近的点都尽量远。直觉：留白越宽，对噪声扰动的容忍越好，泛化越强（“两堵墙之间走正中央”）。

图：两条边界都能分对训练样本，但右侧留下了更宽的安全带。SVM 优先选择这种大间隔边界。

两个要点：定义一个所有分类面都能比较的距离指标；在该指标上取最优。

二、建模与记号

• 样本 $\{\mathbf{x}_n, t_n\}$，标签 $t_n \in \{+1, -1\}$（用 ±1 而非 0/1，是关键设计）；
• 线性模型 $y(\mathbf{x}) = \mathbf{w}^{\mathsf{T}}\mathbf{x} + b$，决策 $f(\mathbf{x}) = \mathrm{sgn}(y(\mathbf{x}))$；
• $\mathbf{w}$ 垂直于超平面（法向量），决定方向；$b$ 决定平移。

±1 标签的第一个作用——正确分类可统一写成一个式子：

$t_n\, y(\mathbf{x}_n) > 0 \iff \text{第 } n \text{ 个样本分类正确}$

因为正类（$t=+1$）落在 $y>0$ 一侧、负类（$t=-1$）落在 $y<0$ 一侧，乘积恒正。

三、点到超平面的距离

点 $\mathbf{x}_n$ 到超平面 $y(\mathbf{x}) = 0$ 的几何距离为 $\dfrac{|y(\mathbf{x}_n)|}{\|\mathbf{w}\|}$。对分对的点，$t_n y(\mathbf{x}_n) > 0$ 正好等于绝对值，于是去掉绝对值：

$\text{距离} = \frac{t_n\, y(\mathbf{x}_n)}{\|\mathbf{w}\|} = \frac{t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b)}{\|\mathbf{w}\|}$

这是 ±1 标签的第二个作用。原始的最大间隔目标（最大化”最近点距离”）为：

$\max_{\mathbf{w}, b}\ \frac{1}{\|\mathbf{w}\|} \min_n \left[ t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) \right]$

形式复杂（max 套 min），需化简。

四、规范化（Canonical Form）

关键观察：$(\mathbf{w}, b)$ 同乘常数 $k$ 表示同一超平面，尺度自由。于是规定离超平面最近的点满足：

$t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) = 1$

则所有点满足 $t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) \ge 1$，且最近点距离 $= \dfrac{1}{\|\mathbf{w}\|}$。

最大化 $\dfrac{1}{\|\mathbf{w}\|}$ 等价于最小化 $\dfrac{1}{2}\|\mathbf{w}\|^2$。

五、基本型（原问题）

$\min_{\mathbf{w}, b}\ \frac{1}{2}\|\mathbf{w}\|^2 \quad \text{s.t.} \quad t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) \ge 1,\ n = 1, \dots, N$

这是凸二次规划：线性可分时最优解是全局最优；线性不可分时，硬间隔约束没有可行解。 目标函数对 $\mathbf w$ 严格凸，因此最优法向量唯一；在退化情形下，偏置 $b$ 不一定唯一。

六、拉格朗日与对偶问题

什么是对偶问题

对带约束的最小化，用拉格朗日乘子法给每条约束配乘子 $a_n \ge 0$，把约束揉进目标，再消去原变量，得到的只含乘子的等价问题就叫对偶问题；原来的叫原问题。

博弈视角：拉格朗日函数里你控制 $\mathbf{w}, b$ 想让它小、对手控制 $\mathbf{a}$ 想让它大。原问题是 $\min_{\mathbf{w},b}\max_{\mathbf{a}} L$（你先动），对偶是 $\max_{\mathbf{a}}\min_{\mathbf{w},b} L$（对手先动）。凸问题下两者最优值相等（强对偶），故可解更好算的对偶。

推导

$L(\mathbf{w}, b, \mathbf{a}) = \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{n=1}^{N} a_n \left[ t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) - 1 \right]$

对 $\mathbf{w}$、$b$ 求偏导置零：

$\mathbf{w} = \sum_{n=1}^{N} a_n t_n \mathbf{x}_n$

$\sum_{n=1}^{N} a_n t_n = 0$

代回消去 $\mathbf{w}, b$，得对偶问题：

$\max_{\mathbf{a}}\ \tilde{L}(\mathbf{a}) = \sum_{n=1}^{N} a_n - \frac{1}{2}\sum_{n=1}^{N}\sum_{m=1}^{N} a_n a_m t_n t_m \mathbf{x}_n^{\mathsf{T}}\mathbf{x}_m$

约束 $a_n \ge 0$，$\sum_n a_n t_n = 0$。

对偶的两个好处：样本只以内积 $\mathbf{x}_n^{\mathsf{T}}\mathbf{x}_m$ 出现（为核技巧留接口）；解出来大部分 $a_n = 0$（稀疏，引出支持向量）。

七、KKT 条件与支持向量

KKT 互补条件（核心三条）：

$a_n \ge 0$

$t_n\, y(\mathbf{x}_n) - 1 \ge 0$

$a_n \left( t_n\, y(\mathbf{x}_n) - 1 \right) = 0$

互补松弛条件直接解释了支持向量：对每个点，要么 $a_n = 0$（对 $\mathbf{w}$ 无贡献），要么 $t_n y(\mathbf{x}_n) = 1$（点恰在间隔边界上）。

因此：

• 严格分对、在间隔外（$t_n y > 1$）的点：$a_n = 0$，无关紧要；
• 恰在间隔边界（$t_n y = 1$）的点：$a_n > 0$，称为支持向量。

由 $\mathbf{w} = \sum_n a_n t_n \mathbf{x}_n$，只有支持向量贡献，故超平面完全由少数支持向量决定，删掉其余点不影响结果——这就是 SVM 名字由来。

偏置 $b$ 由任一支持向量（$t_n y(\mathbf{x}_n) = 1$）反解，通常对所有支持向量取平均。

八、手算例子

两点：正类 $\mathbf{x}_1 = (1,1)$、$t_1 = +1$；负类 $\mathbf{x}_2 = (0,0)$、$t_2 = -1$。两点都是支持向量。

由 $\sum_n a_n t_n = 0$ 得 $a_1 = a_2 = a$。则 $\mathbf{w} = a(1,1) - a(0,0) = (a, a)$。

代入 $t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) = 1$：

• 对 $\mathbf{x}_1$：$2a + b = 1$；
• 对 $\mathbf{x}_2$：$-b = 1$，即 $b = -1$。

解得 $a = 1$，$\mathbf{w} = (1, 1)$，$b = -1$。分界线 $x_1 + x_2 - 1 = 0$，过中点 $(0.5, 0.5)$，垂直平分两点连线，间隔 $= 1/\sqrt{2}$。

手算步骤：用 $\sum_n a_n t_n = 0$ 减少未知数 → 写 $\mathbf{w} = \sum_n a_n t_n \mathbf{x}_n$ → 对每个支持向量列 $t_n(\mathbf{w}^{\mathsf{T}}\mathbf{x}_n + b) = 1$ → 解方程组。

九、软间隔（处理噪声与线性不可分）

硬间隔的问题：线性不可分时无解；对离群点敏感。引入松弛变量 $\xi_n \ge 0$，把约束松绑：

$t_n\, y(\mathbf{x}_n) \ge 1 - \xi_n$

$\xi_n$ 的含义：$\xi_n = 0$ 时满足间隔要求；$0 < \xi_n < 1$ 时进入间隔但仍在正确一侧；$\xi_n = 1$ 时落在分类超平面上；$\xi_n > 1$ 时被分错。

目标加惩罚项：

$\min_{\mathbf{w}, b, \xi}\ \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{n=1}^{N} \xi_n \quad \text{s.t.}\quad t_n\, y(\mathbf{x}_n) \ge 1 - \xi_n,\ \xi_n \ge 0$

$C$ 控制违规惩罚的强度：$C$ 较大时更强调减少训练集违规，正则化较弱；$C$ 较小时允许更多违规，正则化较强。它不直接保证泛化性，具体值仍需用验证集选择。

软间隔对偶与硬间隔几乎相同，仅 $a_n$ 多了上界：

$0 \le a_n \le C, \qquad \sum_{n=1}^{N} a_n t_n = 0$

软间隔里，$0 < a_n < C$ 的点满足 $\xi_n = 0$，恰在间隔边界；凡是 $\xi_n > 0$ 的点都满足 $a_n = C$，它们进入了间隔或被错分。反过来不一定成立：退化情形下， $a_n = C$ 的点也可能仍在边界上，因此不能把 $a_n=C$ 与“必然越界”画等号。

复习要点

• ±1 标签的两个作用（统一正确判别式 + 去绝对值的距离）。
• 规范化如何把 max-min 化成 $\min \frac{1}{2}\|\mathbf{w}\|^2$，写出基本型（凸二次规划）。
• 对偶推导：$\mathbf{w} = \sum_n a_n t_n \mathbf{x}_n$、$\sum_n a_n t_n = 0$、对偶目标，以及”只剩内积 + 稀疏”两个好处。
• KKT 互补松弛怎么推出支持向量；超平面只由支持向量决定。
• 两点手算例子全流程。
• 软间隔：松弛变量、惩罚 $C$ 的权衡、$0 \le a_n \le C$，以及 $\xi_n>0\Rightarrow a_n=C$。