---
tags: [AI, 经典机器学习, svm, 凸优化]
阶段: 03-经典机器学习
难度: ★★★
created: 2026-10-18
related: "[[逻辑回归]], [[优化算法-梯度下降与Adam]], [[模型评估与交叉验证]], [[树模型与集成学习]]"
---

# 支持向量机SVM

## 定义

**支持向量机**（Support Vector Machine, SVM）指以最大化几何间隔为准则求解线性判别函数 $f(\mathbf{x})=\mathbf{w}^\top\mathbf{x}+b$ 的一类分类方法；样本线性不可分时引入松弛变量 $\xi_i$ 得到软间隔形式，并用核函数 $K(\mathbf{x},\mathbf{z})=\phi(\mathbf{x})^\top\phi(\mathbf{z})$ 替换内积，使判别函数在映射后的特征空间中线性、在原输入空间中非线性。

- $\mathcal{D}=\{(\mathbf{x}_i,y_i)\}_{i=1}^{n}$：训练集，$n$ 为样本数。
- $\mathbf{x}_i\in\mathbb{R}^{d}$：第 $i$ 个样本的特征向量，$d$ 为特征维数。
- $y_i\in\{-1,+1\}$：类别标记，二分类采用该编码。
- $\mathbf{w}\in\mathbb{R}^{d}$：分离超平面的法向量，决定超平面方向。
- $b\in\mathbb{R}$：偏置，决定超平面相对原点的位置。
- $\hat\gamma_i=y_i(\mathbf{w}^\top\mathbf{x}_i+b)$：样本 $i$ 的**函数间隔**（functional margin）。
- $\gamma_i=\hat\gamma_i/\lVert\mathbf{w}\rVert$：样本 $i$ 的**几何间隔**（geometric margin），等于样本到超平面的欧氏距离，分类正确时取正值。
- $\xi_i\ge 0$：松弛变量，度量样本违反间隔约束的程度。
- $C>0$：正则化常数，控制间隔宽度与间隔违反总量之间的权衡。
- $\alpha_i\ge 0$：间隔约束对应的拉格朗日乘子，软间隔下同时受上界 $C$ 约束。
- $K(\mathbf{x},\mathbf{z})$：核函数，$K(\mathbf{x},\mathbf{z})=\phi(\mathbf{x})^\top\phi(\mathbf{z})$，$\phi:\mathbb{R}^{d}\to\mathcal{H}$ 为特征映射，$\mathcal{H}$ 为内积空间。
- **支持向量**（support vector）：满足 $\alpha_i>0$ 的训练样本，其间隔约束在最优解处起作用。

## 为什么重要

- 解决的问题：逻辑回归只要求把样本分对，分离超平面在可分数据上有无穷多个；SVM 在全部可行超平面中选出到最近样本距离最大的一个，使解唯一且对样本扰动不敏感。
- 没有它会怎样：缺少一个把「间隔最大化」写成凸二次规划、再用对偶与 KKT 求解的完整范例；也缺少核方法的入口，非线性判别将只能依靠显式构造高维特征。
- 对偶形式的意义：原始问题在 $\mathbb{R}^{d}$ 中求解，对偶问题在 $\mathbb{R}^{n}$ 中求解，且目标函数只通过样本两两内积依赖数据。当 $d\gg n$ 时对偶更经济，同时为核替换提供了结构上的可能。
- 在全书中的位置：前置为 [[逻辑回归]] 的线性判别与 [[优化算法-梯度下降与Adam]] 的凸优化、拉格朗日乘子；本篇的对偶与 KKT 是理解 [[树模型与集成学习]] 中正则化目标、以及后续对偶方法的基础；$C$ 与 $\gamma$ 的选取直接进入 [[模型评估与交叉验证]] 的流程。
- 对应能力目标：懂原理要求能完成从原始问题到对偶问题的推导并解释 KKT 的每一组条件；能复现要求能写出核化决策函数与两变量解析更新；会评估要求能判断 $C$、$\gamma$、核类型对支持向量数量与泛化误差的影响。

## 原理与推导

```mermaid
flowchart TD
    A["原始问题：最小化 0.5·||w||²，约束 y_i(w·x_i+b)>=1"] --> B["拉格朗日函数 L(w,b,alpha)"]
    B --> C["对偶问题：关于 alpha 的二次规划"]
    C --> D["KKT 条件：互补松弛 alpha_i·(y_i f_i-1)=0"]
    D --> E["支持向量与偏置 b"]
    C --> F["核替换：内积 x_i·x_j 换为 K(x_i,x_j)"]
    F --> G["核化决策函数 f(x)=sum alpha_i y_i K(x_i,x)+b"]
    C --> H["SMO：固定其余变量，解析求解两个 alpha"]
```

### 1. 最大间隔分类的几何设定

分离超平面定义为点集 $\{\mathbf{x}:\mathbf{w}^\top\mathbf{x}+b=0\}$，法向量 $\mathbf{w}$ 与其正交。点 $\mathbf{x}$ 到该超平面的带符号距离为

$$
\frac{\mathbf{w}^\top\mathbf{x}+b}{\lVert\mathbf{w}\rVert}.
$$

符号由 $\mathbf{w}^\top\mathbf{x}+b$ 决定，绝对值除以 $\lVert\mathbf{w}\rVert$ 后与 $\mathbf{w}$ 的尺度无关。判别规则取 $f(\mathbf{x})=\operatorname{sign}(\mathbf{w}^\top\mathbf{x}+b)$。

设两类样本分别位于超平面两侧。记最近的正类样本到超平面的距离为 $d_+$，最近的负类样本距离为 $d_-$，则**间隔**（margin）定义为 $d_++d_-$。对固定方向 $\mathbf{w}$，平移 $b$ 可使两侧最近距离相等，即最优解处 $d_+=d_-=\gamma$，间隔宽度为 $2\gamma$。若把两侧的约束统一写成 $y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1$，则由点到平面距离公式，$\gamma=1/\lVert\mathbf{w}\rVert$，间隔宽度为

$$
\frac{2}{\lVert\mathbf{w}\rVert}.
$$

因此最大化间隔等价于最小化 $\lVert\mathbf{w}\rVert$，这是后续优化问题的几何来源。

### 2. 函数间隔与几何间隔

函数间隔 $\hat\gamma_i=y_i(\mathbf{w}^\top\mathbf{x}_i+b)$ 只要求约束值不小于某个正数，本身带有尺度不确定性：把 $(\mathbf{w},b)$ 同时乘以 $c>0$，超平面不变，但 $\hat\gamma_i$ 变为 $c\hat\gamma_i$。数据集上的函数间隔取 $\hat\gamma=\min_i\hat\gamma_i$，几何间隔取 $\gamma=\hat\gamma/\lVert\mathbf{w}\rVert$。

尺度不确定性带来两种归一化方式：

1. 固定 $\lVert\mathbf{w}\rVert=1$，此时函数间隔等于几何间隔，优化变量落在单位球面上，约束为非线性。
2. 固定 $\hat\gamma=1$，即要求 $\min_i y_i(\mathbf{w}^\top\mathbf{x}_i+b)=1$，约束为线性，代价是 $\lVert\mathbf{w}\rVert$ 可以自由缩放。

第 2 种方式把问题化为凸二次规划，是标准做法。其合法性在于：对任意可行解 $(\mathbf{w},b)$，设其函数间隔为 $\hat\gamma$，令 $\mathbf{w}'=\mathbf{w}/\hat\gamma$、$b'=b/\hat\gamma$，则新解的函数间隔为 $1$，几何间隔保持不变，而 $\lVert\mathbf{w}'\rVert=\lVert\mathbf{w}\rVert/\hat\gamma$。因此「在 $\hat\gamma=1$ 的约束下最小化 $\lVert\mathbf{w}\rVert$」与「在所有可行超平面中最大化 $\hat\gamma/\lVert\mathbf{w}\rVert$」等价。

### 3. 硬间隔优化问题

在数据线性可分的假设下，原始问题为

$$
\begin{aligned}
\min_{\mathbf{w},b}\quad & \frac{1}{2}\lVert\mathbf{w}\rVert^{2}\\
\text{s.t.}\quad & y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1,\quad i=1,\dots,n.
\end{aligned}
$$

目标函数是 $\mathbf{w}$ 的严格凸二次函数，约束是仿射函数，可行域为凸集，因此局部最优即全局最优，且最优 $\mathbf{w}$ 唯一（$b$ 的唯一性需另行判断）。$\frac{1}{2}$ 是为了求导后消去系数 $2$。$b$ 由 KKT 条件确定：若存在满足 $0<\alpha_i<C$ 的自由支持向量，则 $b$ 唯一；若不存在，$b$ 只能确定在一个由两类边界样本共同界定的区间内。

### 4. 拉格朗日函数与对偶问题

对每个不等式约束引入乘子 $\alpha_i\ge 0$，拉格朗日函数为

$$
L(\mathbf{w},b,\boldsymbol{\alpha})=\frac{1}{2}\lVert\mathbf{w}\rVert^{2}-\sum_{i=1}^{n}\alpha_i\left[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1\right].
$$

原始问题等价于 $\min_{\mathbf{w},b}\max_{\boldsymbol{\alpha}\ge\mathbf{0}}L$：当约束被违反时，括号内为负，乘子取无穷大使 $L\to+\infty$；约束满足时，$\max$ 在 $\alpha_i=0$ 处取到，$L$ 退化为原目标。交换 $\min$ 与 $\max$ 得到对偶问题 $\max_{\boldsymbol{\alpha}\ge\mathbf{0}}\min_{\mathbf{w},b}L$，由弱对偶，对偶值不超过原始值。

先对内层求极小。令偏导为零：

$$
\frac{\partial L}{\partial\mathbf{w}}=\mathbf{w}-\sum_{i=1}^{n}\alpha_i y_i\mathbf{x}_i=\mathbf{0}
\;\Longrightarrow\;
\mathbf{w}=\sum_{i=1}^{n}\alpha_i y_i\mathbf{x}_i,
$$

$$
\frac{\partial L}{\partial b}=-\sum_{i=1}^{n}\alpha_i y_i=0
\;\Longrightarrow\;
\sum_{i=1}^{n}\alpha_i y_i=0.
$$

将两式代回 $L$。第一项：

$$
\frac{1}{2}\lVert\mathbf{w}\rVert^{2}
=\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j\,\mathbf{x}_i^\top\mathbf{x}_j .
$$

第二项：

$$
\sum_{i=1}^{n}\alpha_i y_i\mathbf{w}^\top\mathbf{x}_i
=\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j\,\mathbf{x}_i^\top\mathbf{x}_j .
$$

第三项 $-\sum_i\alpha_i y_i b=0$。合并得

$$
L=\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j\,\mathbf{x}_i^\top\mathbf{x}_j .
$$

于是对偶问题为

$$
\begin{aligned}
\max_{\boldsymbol{\alpha}}\quad & \sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n}\alpha_i\alpha_j y_i y_j\,\mathbf{x}_i^\top\mathbf{x}_j\\
\text{s.t.}\quad & \alpha_i\ge 0,\quad \sum_{i=1}^{n}\alpha_i y_i=0 .
\end{aligned}
$$

对偶目标关于 $\boldsymbol{\alpha}$ 是凹二次函数，约束为线性，可行域非空，因此对偶可解。线性可分时存在严格可行点，Slater 条件成立，强对偶成立，原始最优值等于对偶最优值。数据不可分时原始问题无可行解，此时必须引入松弛变量。

### 5. KKT 条件与支持向量

凸问题且强对偶成立时，原始最优解与对偶最优解满足 KKT 条件：

1. 平稳性：$\nabla_{\mathbf{w}}L=\mathbf{0}$，$\nabla_b L=0$，即 $\mathbf{w}=\sum_i\alpha_i y_i\mathbf{x}_i$ 且 $\sum_i\alpha_i y_i=0$。
2. 原始可行性：$y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1$。
3. 对偶可行性：$\alpha_i\ge 0$。
4. 互补松弛：$\alpha_i\left[y_i(\mathbf{w}^\top\mathbf{x}_i+b)-1\right]=0$。

由第 4 条，若 $\alpha_i>0$，则 $y_i(\mathbf{w}^\top\mathbf{x}_i+b)=1$，样本恰好落在间隔边界上；若 $y_i(\mathbf{w}^\top\mathbf{x}_i+b)>1$，则 $\alpha_i=0$。因此只有位于间隔边界上的样本对 $\mathbf{w}$ 有非零贡献，这些样本就是支持向量。决策函数可写成

$$
f(\mathbf{x})=\sum_{i\in \mathrm{SV}}\alpha_i y_i\,\mathbf{x}_i^\top\mathbf{x}+b,
$$

预测代价只与支持向量数量成正比，与 $n$ 无必然关系。

偏置由自由支持向量给出：若存在 $k$ 使 $0<\alpha_k<C$，则

$$
b=y_k-\sum_{i=1}^{n}\alpha_i y_i\,\mathbf{x}_i^\top\mathbf{x}_k .
$$

数值实现中通常对所有满足 $0<\alpha_k<C$ 的样本求平均以降低误差。若不存在自由支持向量，$b$ 只能确定在一个区间内，该区间由 $\alpha_i=0$ 与 $\alpha_i=C$ 两侧的约束共同界定。

### 6. 软间隔、松弛变量与 C 的作用

数据不可分时，约束 $y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1$ 无解。引入松弛变量 $\xi_i\ge 0$ 允许违反：

$$
\begin{aligned}
\min_{\mathbf{w},b,\boldsymbol{\xi}}\quad & \frac{1}{2}\lVert\mathbf{w}\rVert^{2}+C\sum_{i=1}^{n}\xi_i\\
\text{s.t.}\quad & y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge 1-\xi_i,\quad \xi_i\ge 0 .
\end{aligned}
$$

$C$ 是间隔宽度与违反总量之间的交换率。$C\to\infty$ 时任何 $\xi_i>0$ 都不可接受，退化为硬间隔；$C$ 减小时允许更多样本进入间隔内部甚至被错分，间隔变宽。对应的对偶问题只多出上界约束：

$$
\begin{aligned}
\max_{\boldsymbol{\alpha}}\quad & \sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j\,\mathbf{x}_i^\top\mathbf{x}_j\\
\text{s.t.}\quad & 0\le\alpha_i\le C,\quad \sum_{i=1}^{n}\alpha_i y_i=0 .
\end{aligned}
$$

三类 $\alpha_i$ 的几何含义：

| $\alpha_i$ 取值 | 位置 | 对 $\mathbf{w}$ 的贡献 |
|---|---|---|
| $\alpha_i=0$ | 间隔外且分类正确 | 无 |
| $0<\alpha_i<C$ | 恰在间隔边界上 | 有，且 $b$ 由这些样本确定 |
| $\alpha_i=C$ | 间隔内或被错分 | 有，其违反量为 $\xi_i=\max\left(0,1-y_i f(\mathbf{x}_i)\right)$ |

从偏差-方差角度看，$C$ 小对应强正则化、宽间隔、偏差大方差小；$C$ 大对应弱正则化、窄间隔、偏差小方差大。$C$ 需要通过交叉验证选择，不能由训练误差单调判断。

### 7. 合页损失视角

软间隔问题可消去 $\xi$。对固定的 $\mathbf{w},b$，每个 $\xi_i$ 的可行下界是 $\max\left(0,1-y_i f(\mathbf{x}_i)\right)$，目标中 $\xi_i$ 的系数 $C$ 为正，故最优取该下界：

$$
\xi_i=\max\left(0,1-y_i f(\mathbf{x}_i)\right).
$$

代回目标得无约束形式

$$
\min_{\mathbf{w},b}\;\frac{1}{2}\lVert\mathbf{w}\rVert^{2}+C\sum_{i=1}^{n}\max\left(0,1-y_i f(\mathbf{x}_i)\right).
$$

右侧求和项即**合页损失**（hinge loss）$\ell_{\mathrm{hinge}}(y,\hat y)=\max(0,1-y\hat y)$。它在 $y\hat y\ge 1$ 时为零，在 $y\hat y<1$ 时线性增长，在 $y\hat y=1$ 处不可导。其 subgradient 为

$$
\frac{\partial \ell}{\partial \mathbf{w}}=
\begin{cases}
0, & y_i f(\mathbf{x}_i)>1,\\
-y_i\mathbf{x}_i, & y_i f(\mathbf{x}_i)<1,
\end{cases}
$$

因此目标的次梯度下降更新为 $\mathbf{w}\leftarrow\mathbf{w}-\eta\left(\mathbf{w}-C\sum_{i:\,y_if_i<1}y_i\mathbf{x}_i\right)$。合页损失在间隔外梯度为零，这解释了支持向量的稀疏性：只有违反间隔的样本持续影响参数。

与 [[逻辑回归]] 的对数损失对比：对数损失在 $y\hat y<0$ 时仍给出非零梯度，模型会继续把已正确分类但置信度低的样本推远；合页损失在 $y\hat y\ge 1$ 后停止惩罚，因而解更稀疏。二者都是 $0$-$1$ 损失的凸上界，训练目标不同导致解的性质不同。

### 8. 核技巧与 Mercer 条件

对偶目标与决策函数只通过内积 $\mathbf{x}_i^\top\mathbf{x}_j$ 依赖数据。若把每个样本映射为 $\phi(\mathbf{x})$，只需把内积替换为 $K(\mathbf{x}_i,\mathbf{x}_j)=\phi(\mathbf{x}_i)^\top\phi(\mathbf{x}_j)$，无需显式计算 $\phi$。这一替换称为**核技巧**（kernel trick）。

一个对称函数 $K$ 能写成某个内积空间中的内积，当且仅当它对任意有限样本集的 Gram 矩阵半正定：

$$
\mathbf{K}_{ij}=K(\mathbf{x}_i,\mathbf{x}_j),\qquad
\mathbf{c}^\top\mathbf{K}\mathbf{c}=\Big\lVert\sum_i c_i\phi(\mathbf{x}_i)\Big\rVert^{2}\ge 0
\quad\text{对任意 }\mathbf{c}\in\mathbb{R}^{n}.
$$

连续形式即 **Mercer 条件**：对平方可积函数 $g$，

$$
\iint g(\mathbf{x})K(\mathbf{x},\mathbf{z})g(\mathbf{z})\,\mathrm{d}\mathbf{x}\,\mathrm{d}\mathbf{z}\ge 0 .
$$

满足该条件的核对应对称半正定核矩阵，此时存在特征映射与再生核希尔伯特空间。实践中可行性检查即为：对训练集计算核矩阵，检查最小特征值是否显著为负。

常用核：

| 核 | 表达式 | 超参数 | 性质 |
|---|---|---|---|
| 线性核 | $\mathbf{x}^\top\mathbf{z}$ | 无 | 等价于原始空间线性 SVM，$d$ 大时首选 |
| 多项式核 | $(\gamma\mathbf{x}^\top\mathbf{z}+r)^{d}$ | $\gamma,r,d$ | 显式建模特征交叉，$d$ 大时数值不稳定 |
| RBF 核 | $\exp\left(-\gamma\lVert\mathbf{x}-\mathbf{z}\rVert^{2}\right)$ | $\gamma>0$ | 对应无穷维特征空间，局部性由 $\gamma$ 控制 |
| Sigmoid 核 | $\tanh(\gamma\mathbf{x}^\top\mathbf{z}+r)$ | $\gamma,r$ | 仅部分参数下半正定，不保证满足 Mercer 条件 |

RBF 核的无穷维展开说明其表达能力：由 $\lVert\mathbf{x}-\mathbf{z}\rVert^2=\lVert\mathbf{x}\rVert^2+\lVert\mathbf{z}\rVert^2-2\mathbf{x}^\top\mathbf{z}$ 与指数函数的幂级数，

$$
\exp\left(-\gamma\lVert\mathbf{x}-\mathbf{z}\rVert^{2}\right)
=e^{-\gamma\lVert\mathbf{x}\rVert^{2}}e^{-\gamma\lVert\mathbf{z}\rVert^{2}}
\sum_{k=0}^{\infty}\frac{(2\gamma)^{k}}{k!}\left(\mathbf{x}^\top\mathbf{z}\right)^{k},
$$

即特征映射包含所有阶数的多项式项。$\gamma$ 越大，核随距离衰减越快，单个支持向量的影响范围越小，模型越容易过拟合；$\gamma$ 越小，核接近常数，模型趋向欠拟合。

### 9. 核化后的决策函数

把内积替换为核后，对偶问题与决策函数为

$$
\max_{\boldsymbol{\alpha}}\;\sum_{i=1}^{n}\alpha_i-\frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j K(\mathbf{x}_i,\mathbf{x}_j)
\quad\text{s.t.}\quad 0\le\alpha_i\le C,\;\sum_i\alpha_i y_i=0,
$$

$$
f(\mathbf{x})=\sum_{i=1}^{n}\alpha_i y_i K(\mathbf{x}_i,\mathbf{x})+b .
$$

在特征空间中 $\lVert\mathbf{w}\rVert_{\mathcal{H}}^{2}=\sum_{i,j}\alpha_i\alpha_j y_i y_j K(\mathbf{x}_i,\mathbf{x}_j)$，因此核化后的间隔宽度仍是 $2/\lVert\mathbf{w}\rVert_{\mathcal{H}}$，只是该范数无法在原始空间中直接观测。预测时需计算 $\mathbf{x}$ 与全部支持向量的核值，代价为 $O(n_{\mathrm{SV}}d)$。

由于核矩阵只依赖样本间的相似度，SVM 的预测可视为「以支持向量为参照、按核相似度加权投票」，其权重由 $\alpha_i y_i$ 给出。这一结构与 [[Embedding与向量检索]] 中以内积衡量相似度的做法同源，区别在于 SVM 的权重由间隔约束解出，检索的权重由模型训练得到。

### 10. SMO 算法

对偶问题是 $n$ 个变量的二次规划，通用求解器需要 $O(n^{3})$ 量级。**序列最小最优化**（Sequential Minimal Optimization, SMO）利用等式约束 $\sum_i\alpha_i y_i=0$：若只保留两个变量，其余固定，则等式约束把两个变量压成一维，子问题有解析解。

设选中 $i,j$，其余 $\alpha_k$ 固定。由约束得

$$
y_i\alpha_i+y_j\alpha_j=y_i\alpha_i^{\mathrm{old}}+y_j\alpha_j^{\mathrm{old}}
\;\Longrightarrow\;
\alpha_i=\alpha_i^{\mathrm{old}}+y_i y_j\left(\alpha_j^{\mathrm{old}}-\alpha_j\right).
$$

代入对偶目标，得到关于 $\alpha_j$ 的一元二次函数，二次项系数为 $-\eta/2$，其中

$$
\eta=K(\mathbf{x}_i,\mathbf{x}_i)+K(\mathbf{x}_j,\mathbf{x}_j)-2K(\mathbf{x}_i,\mathbf{x}_j)
=\left\lVert\phi(\mathbf{x}_i)-\phi(\mathbf{x}_j)\right\rVert^{2}\ge 0 .
$$

由 $\eta\ge 0$ 知目标关于 $\alpha_j$ 凹，无约束极大值点为

$$
\alpha_j^{\mathrm{new}}=\alpha_j^{\mathrm{old}}-\frac{\nabla_j-y_i y_j\nabla_i}{\eta},
\qquad
\nabla_t=\sum_{k}\alpha_k y_k K(\mathbf{x}_k,\mathbf{x}_t)-1 .
$$

再把 $\alpha_j^{\mathrm{new}}$ 裁剪到可行区间 $[L,H]$，并由等式约束回代 $\alpha_i^{\mathrm{new}}$。

区间端点由 $0\le\alpha_i\le C$ 与等式约束共同决定：

| 情形 | $L$ | $H$ |
|---|---|---|
| $y_i\ne y_j$ | $\max\left(0,\alpha_j-\alpha_i\right)$ | $\min\left(C,C+\alpha_j-\alpha_i\right)$ |
| $y_i=y_j$ | $\max\left(0,\alpha_i+\alpha_j-C\right)$ | $\min\left(C,\alpha_i+\alpha_j\right)$ |

推导 $y_i\ne y_j$ 一行：此时 $\alpha_i=\alpha_i^{\mathrm{old}}+\alpha_j^{\mathrm{old}}-\alpha_j$，条件 $0\le\alpha_i\le C$ 给出 $\alpha_j\le\alpha_i^{\mathrm{old}}+\alpha_j^{\mathrm{old}}$ 与 $\alpha_j\ge\alpha_i^{\mathrm{old}}+\alpha_j^{\mathrm{old}}-C$，与 $0\le\alpha_j\le C$ 取交集即得上表。

工作集选择常用**最大违反对**：以 $g_t=-y_t\nabla_t$ 为违反度量，在

$$
I_{\mathrm{up}}=\{t:(y_t=+1,\alpha_t<C)\ \text{或}\ (y_t=-1,\alpha_t>0)\},
$$
$$
I_{\mathrm{low}}=\{t:(y_t=+1,\alpha_t>0)\ \text{或}\ (y_t=-1,\alpha_t<C)\}
$$

中取 $i=\arg\max_{I_{\mathrm{up}}}g_t$、$j=\arg\min_{I_{\mathrm{low}}}g_t$，当 $g_i-g_j$ 小于容差时停止。每次更新只修改两个乘子，其余乘子保持不变，因而每步代价为 $O(n)$ 量级，整体在中等规模数据上明显快于通用二次规划求解器。

### 11. 复杂度

| 环节 | 代价 | 说明 |
|---|---|---|
| 核矩阵构造 | $O(n^{2}d)$ 时间、$O(n^{2})$ 内存 | 线性核可省去显式矩阵，按需计算 |
| 通用二次规划求解 | 最坏 $O(n^{3})$ | 稠密矩阵分解 |
| SMO | 每步 $O(n)$，总步数与问题难度相关 | 实践中常为 $O(n^{2})$ 量级 |
| 线性核专用求解器 | 每轮 $O(nd)$ | 坐标下降或对偶坐标下降 |
| 预测 | $O(n_{\mathrm{SV}}d)$ | 只与支持向量数量有关 |

$n$ 达到 $10^{4}$ 以上时，$O(n^{2})$ 的核矩阵内存成为主要瓶颈；此时可选线性核并改用线性求解器，或使用随机特征近似 RBF 核，把核化问题转回 $O(ndm)$ 的线性问题。

## 关键直觉

> [!tip] 机制性直觉
> 对偶形式说明：SVM 的判别函数只通过核函数与支持向量的内积依赖训练数据，$\alpha_i$ 是每个间隔约束的对偶变量，只有约束在最优解处取等号的样本才有 $\alpha_i>0$，软间隔下还包括被截断在 $C$ 的违反样本。最大化间隔等价于在「所有样本距超平面至少 $1/\lVert\mathbf{w}\rVert$」的约束下最小化 $\lVert\mathbf{w}\rVert$，因此预测代价由支持向量数量 $n_{\mathrm{SV}}$ 决定，而非由样本总数 $n$ 决定。这与定义中「支持向量是 $\alpha_i>0$ 的样本」一条严格对应：$\alpha_i$ 的稀疏性直接给出预测时的计算量。

## 例子与代码

### 手算：4 个样本的硬间隔解

取 $\mathbf{x}_1=(3,3)$、$\mathbf{x}_2=(4,3)$ 为正类，$\mathbf{x}_3=(1,1)$、$\mathbf{x}_4=(1,0)$ 为负类，$y=(+1,+1,-1,-1)$。

第 1 步：确定起作用约束。跨类最近的点对是 $\mathbf{x}_1$ 与 $\mathbf{x}_3$，距离 $\sqrt{(3-1)^2+(3-1)^2}=2\sqrt{2}$。若最大间隔超平面的最近点正是这一对，则法向量平行于 $\mathbf{x}_1-\mathbf{x}_3=(2,2)$，可设 $\mathbf{w}=(s,s)$。

第 2 步：令两个约束取等号。

$$
\mathbf{w}^\top\mathbf{x}_1+b=6s+b=1,\qquad
\mathbf{w}^\top\mathbf{x}_3+b=2s+b=-1 .
$$

两式相减得 $4s=2$，即 $s=0.5$，代回得 $b=-2$。于是 $\mathbf{w}=(0.5,0.5)$，$f(\mathbf{x})=0.5x_1+0.5x_2-2$，分界直线为 $x_1+x_2=4$。

第 3 步：验证其余约束。$\mathbf{w}^\top\mathbf{x}_2+b=3.5-2=1.5\ge 1$，$\mathbf{w}^\top\mathbf{x}_4+b=0.5-2=-1.5\le -1$，均满足。

第 4 步：由 KKT 求乘子。由 $\mathbf{w}=\sum_i\alpha_i y_i\mathbf{x}_i$ 得

$$
(0.5,0.5)=\alpha_1(3,3)-\alpha_3(1,1),
$$

两个分量给出同一方程 $3\alpha_1-\alpha_3=0.5$；由 $\sum_i\alpha_i y_i=0$ 得 $\alpha_1=\alpha_3$。联立得 $\alpha_1=\alpha_3=0.25$，$\alpha_2=\alpha_4=0$。

第 5 步：验证最优性。对偶目标

$$
\sum_i\alpha_i-\frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j\mathbf{x}_i^\top\mathbf{x}_j
=0.5-\frac{1}{2}\left(8\times0.25^{2}\right)=0.5-0.25=0.25,
$$

而原始目标 $\frac{1}{2}\lVert\mathbf{w}\rVert^{2}=\frac{1}{2}(0.25+0.25)=0.25$，两者相等，强对偶成立，故该解最优。

第 6 步：几何量。$\lVert\mathbf{w}\rVert=\sqrt{0.5}\approx0.7071$，几何间隔 $1/\lVert\mathbf{w}\rVert=\sqrt{2}\approx1.414$，间隔宽度 $2\sqrt{2}\approx2.828$。各样本的函数间隔为 $(1,1.5,1,1.5)$，只有 $\mathbf{x}_1,\mathbf{x}_3$ 落在边界上。

尺度检查。若取 $(2\mathbf{w},2b)=(1,1,-4)$，超平面不变，函数间隔变为 $(2,3,2,3)$，几何间隔不变。这说明约束 $\min_i y_i f(\mathbf{x}_i)=1$ 是归一化约定，不是几何不变量。

### 代码一：不同核的对比与 C 的作用

以下代码在二维双月数据上训练三种核的 SVM，输出支持向量数量与准确率。标准化是必要的：RBF 核按欧氏距离衰减，特征尺度不同会让距离由方差大的特征主导。

```python
# 依赖：Python 3.12、NumPy 2.3.5、scikit-learn 1.9.1
import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
from sklearn.svm import SVC

X, y = make_moons(n_samples=200, noise=0.25, random_state=0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
scaler = StandardScaler().fit(X_tr)
X_tr, X_te = scaler.transform(X_tr), scaler.transform(X_te)

grid = {
    "linear": dict(kernel="linear"),
    "poly3": dict(kernel="poly", degree=3, coef0=1.0, gamma="scale"),
    "rbf": dict(kernel="rbf", gamma="scale"),
}
for name, kw in grid.items():
    clf = SVC(C=1.0, **kw).fit(X_tr, y_tr)
    print(f"{name:6s} 支持向量 {clf.n_support_.sum():3d}（每类 {clf.n_support_}）"
          f" 训练 {clf.score(X_tr, y_tr):.4f} 测试 {clf.score(X_te, y_te):.4f}")

for C in [0.01, 0.1, 1.0, 100.0]:
    clf = SVC(C=C, kernel="rbf", gamma="scale").fit(X_tr, y_tr)
    at_bound = int(np.sum(np.abs(clf.dual_coef_) >= C - 1e-9))
    print(f"C={C:<6} 支持向量 {clf.n_support_.sum():3d} 位于上界 {at_bound:3d}"
          f" 测试 {clf.score(X_te, y_te):.4f}")
```

预期输出：

```text
linear 支持向量  54（每类 [27 27]） 训练 0.8143 测试 0.8667
poly3  支持向量  46（每类 [23 23]） 训练 0.9286 测试 0.9333
rbf    支持向量  54（每类 [26 28]） 训练 0.9357 测试 0.9333
C=0.01   支持向量 140 位于上界 140 测试 0.8833
C=0.1    支持向量  96 位于上界  92 测试 0.8833
C=1.0    支持向量  54 位于上界  44 测试 0.9333
C=100.0  支持向量  26 位于上界  14 测试 0.9000
```

解读：

- 线性核在二维双月数据上训练准确率 0.8143，明显低于 RBF 核的 0.9357。数据本身非线性可分，线性核的假设空间不足，增加 $C$ 也不能改变这一点。
- 支持向量占比高（54/140）说明间隔边界附近样本密集，这也是非线性数据上 SVM 预测代价偏高的原因。
- $C=0.01$ 时 140 个训练样本全部成为支持向量且全部位于上界 $C$，每轮更新都被箱约束截断，模型容量被 $C$ 强限制，测试准确率 0.8833；$C=100$ 时支持向量降至 26，模型更贴合训练集，测试准确率反而下降到 0.9000。这组数据上 $C=1$ 的测试表现最好，说明 $C$ 必须由验证集选择。
- `dual_coef_` 返回的是 $\alpha_i y_i$ 组成的带符号数组，两类的符号相反，因此用绝对值与 $C$ 比较。

### 代码二：手写 SMO

以下实现只依赖 NumPy，用最大违反对选择工作集，用核矩阵统一处理线性与 RBF 两种情形。收敛判据取对偶目标的增量，避免退化情形下 KKT 间隙判据的振荡。

```python
import numpy as np
from sklearn.datasets import make_moons
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler

def rbf_kernel(A, B, gamma):
    d2 = (A ** 2).sum(1)[:, None] + (B ** 2).sum(1)[None, :] - 2.0 * A @ B.T
    return np.exp(-gamma * np.maximum(d2, 0.0))

def smo(K, y, C=1.0, tol=1e-9, max_iter=5000):
    n = len(y)
    a = np.zeros(n)
    Q = np.outer(y, y) * K
    W_old = -np.inf
    for it in range(max_iter):
        W = a.sum() - 0.5 * a @ Q @ a          # 对偶目标，用于判断是否继续
        if W - W_old < tol:
            break
        W_old = W
        grad = Q @ a - 1.0                     # 对偶目标的梯度
        up = ((y > 0) & (a < C)) | ((y < 0) & (a > 0))
        low = ((y > 0) & (a > 0)) | ((y < 0) & (a < C))
        gu = np.where(up, -y * grad, -np.inf)
        gl = np.where(low, -y * grad, np.inf)
        i = int(np.argmax(gu))                 # 最大违反对中的 i
        for j in np.argsort(gl):               # 依次尝试违反最大的 j
            if j == i:
                continue
            ai, aj = a[i], a[j]
            if y[i] != y[j]:
                L, H = max(0.0, aj - ai), min(C, C + aj - ai)
            else:
                L, H = max(0.0, ai + aj - C), min(C, ai + aj)
            if L >= H:
                continue
            eta = K[i, i] + K[j, j] - 2.0 * K[i, j]
            if eta <= 1e-12:
                continue
            aj_new = np.clip(aj - (grad[j] - y[i] * y[j] * grad[i]) / eta, L, H)
            a[i], a[j] = ai - y[i] * y[j] * (aj_new - aj), aj_new
            break
    return a, it

def fit_b(K, y, a, C):
    sv = (a > 1e-9) & (a < C - 1e-9)           # 自由支持向量确定 b
    f0 = K @ (a * y)
    return float(np.mean(y[sv] - f0[sv])) if sv.any() else 0.0

Xs = np.array([[3., 3.], [4., 3.], [1., 1.], [1., 0.]])
ys = np.array([1., 1., -1., -1.])
K4 = Xs @ Xs.T
a, it = smo(K4, ys, C=1e6, tol=1e-12)
b = fit_b(K4, ys, a, 1e6)
print("手算例：alpha =", np.round(a, 4), " b =", round(b, 4))
print("w =", np.round((a * ys) @ Xs, 4), " 间隔 =", np.round(ys * (K4 @ (a * ys) + b), 4))
print("迭代次数 =", it, " ||w|| =", round(float(np.linalg.norm((a * ys) @ Xs)), 4))

X, y = make_moons(n_samples=200, noise=0.25, random_state=0)
y = np.where(y == 0, -1.0, 1.0)
X_tr, X_te, y_tr, y_te = train_test_split(X, y, test_size=0.3, random_state=0, stratify=y)
sc = StandardScaler().fit(X_tr)
X_tr, X_te = sc.transform(X_tr), sc.transform(X_te)
gamma = 1.0 / X_tr.shape[1]
K_tr, K_te = rbf_kernel(X_tr, X_tr, gamma), rbf_kernel(X_te, X_tr, gamma)
a, it = smo(K_tr, y_tr, C=1.0)
b = fit_b(K_tr, y_tr, a, 1.0)
print("双月：迭代", it, " 支持向量", int((a > 1e-9).sum()), " 上界", int((a > 1 - 1e-9).sum()))
print("训练准确率", round(float(np.mean(np.sign(K_tr @ (a * y_tr) + b) == y_tr)), 4),
      " 测试准确率", round(float(np.mean(np.sign(K_te @ (a * y_tr) + b) == y_te)), 4))
print("对偶目标", round(float(a.sum() - 0.5 * (a * y_tr) @ K_tr @ (a * y_tr)), 4))
```

预期输出：

```text
手算例：alpha = [0.25 0.   0.25 0.  ]  b = -2.0
w = [0.5 0.5]  间隔 = [1.  1.5 1.  1.5]
迭代次数 = 7  ||w|| = 0.7071
双月：迭代 38  支持向量 52  上界 46
训练准确率 0.9357  测试准确率 0.9333
对偶目标 39.5929
```

说明：

- 手算例得到 $\alpha=(0.25,0,0.25,0)$、$b=-2$、$\mathbf{w}=(0.5,0.5)$，与手算完全一致，说明解析更新与裁剪逻辑正确。$C=10^{6}$ 用于近似硬间隔；若取 $C=0.1$，$\alpha$ 会被压到上界，$\mathbf{w}$ 的模长随之改变。
- 双月数据上 38 次迭代收敛，训练准确率 0.9357、测试 0.9333，与 scikit-learn 的 LIBSVM 结果一致（其支持向量数为 54，差异来自对偶解在边界样本上的不唯一性与数值容差）。
- 若删去 `np.clip`，$\alpha_j$ 可能越出 $[0,C]$，等式约束仍成立但违反箱约束，迭代会发散或得到负的乘子。
- 若删去 `fit_b` 中「自由支持向量」的筛选而直接用全部样本平均，$b$ 的估计会被位于间隔内或被错分的样本影响而产生偏移，因为只有 $0<\alpha_k<C$ 的样本满足 $y_k f(\mathbf{x}_k)=1$。

## 易错点

> [!warning] 常见错误
> - 把函数间隔当作几何间隔。约束 $y_i(\mathbf{w}^\top\mathbf{x}_i+b)\ge1$ 只是归一化约定，间隔宽度是 $2/\lVert\mathbf{w}\rVert$；报告中若写「间隔为 1」，必须说明是函数间隔。
> - 认为 $\alpha_i>0$ 等价于样本「在间隔边界上」。$0<\alpha_i<C$ 才对应边界；$\alpha_i=C$ 对应间隔内部或错分样本，其函数间隔小于 1。
> - 用 $\alpha$ 的唯一性做结论。当支持向量线性相关或恰在边界上时，对偶最优解可能不唯一，而原始最优 $\mathbf{w}$ 仍唯一；例如四个位于正方形顶点的样本，$\alpha_i=1/4$ 与其他组合给出同一个 $\mathbf{w}$。
> - 混淆 $C$ 与 $\gamma$ 的作用。$C$ 控制间隔违反的惩罚，$\gamma$ 控制 RBF 核的局部性；固定 $C$ 调 $\gamma$ 会同时改变模型复杂度与支持向量数量，二维网格搜索必须联合进行。
> - 在未标准化的特征上直接使用 RBF 核。尺度大的特征主导欧氏距离，核矩阵接近单位阵，模型退化为最近邻分类。
> - 把 `SVC(probability=False)` 的 `decision_function` 输出当作概率。原始 SVM 输出的是到超平面的带符号距离，概率需要额外的校准（如 Platt 缩放）并会改变训练过程。

## 关联笔记

- 前置：[[逻辑回归]] —— 同为线性判别模型，对照对数损失与合页损失的差异可解释稀疏性与概率输出的取舍。
- 前置：[[优化算法-梯度下降与Adam]] —— 拉格朗日乘子、对偶与 KKT 是凸优化的直接应用，本篇第 4、5 节依赖该篇的约束优化结论。
- 后续：[[模型评估与交叉验证]] —— $C$、$\gamma$ 与核类型的联合选择需要在验证集上完成，本篇只给出目标函数与求解方法。
- 对照：[[树模型与集成学习]] —— 轴对齐划分不需要特征缩放、可处理非线性，但其决策边界不连续；SVM 的边界由少数支持向量连续决定，对特征尺度敏感。
- 应用：[[Embedding与向量检索]] —— 核矩阵与嵌入相似度矩阵同为样本两两内积，SVM 的核化决策函数与基于内积的检索评分结构相同。

## 达标检测

- [ ] 写出函数间隔与几何间隔的定义，并说明为什么可以令 $\min_i y_i(\mathbf{w}^\top\mathbf{x}_i+b)=1$ 而不失一般性。
- [ ] 从硬间隔原始问题出发，写出拉格朗日函数，完成对 $\mathbf{w}$、$b$ 的求导、回代与对偶问题的全部步骤。
- [ ] 写出 KKT 的四组条件，并由互补松弛条件推出「只有支持向量影响决策函数」。
- [ ] 由软间隔原始问题消去 $\xi_i$ 得到合页损失形式，并说明 $C$ 增大时偏差与方差如何变化。
- [ ] 手算本篇 4 点例子：给出 $\alpha$、$\mathbf{w}$、$b$、间隔宽度，并验证对偶目标等于原始目标。
- [ ] 运行代码二，把 `gamma` 改为 $0.01$ 与 $10$，记录支持向量数量与测试准确率的变化并解释原因。
- [ ] 构造一个对称函数并检查其 Gram 矩阵的最小特征值，判断它能否作为核使用。

## 参考来源

- Hastie, Tibshirani, Friedman, *The Elements of Statistical Learning*, 2009, 第 12 章 —— 对应本篇最大间隔几何设定、对偶推导、核技巧与正则化视角。
- Stanford CS229 课程讲义（Andrew Ng），支持向量机与拉格朗日对偶部分 —— 对应本篇原始问题到对偶问题的推导、KKT 条件与 SMO 的两变量解析更新。
- d2l.ai《动手学深度学习》，第 12.2 节 凸性（含约束优化与 KKT 条件的讨论）—— 对应本篇对偶问题与 KKT 条件的凸优化背景。
- Goodfellow, Bengio, Courville, *Deep Learning*, 2016, 第 5 章 机器学习基础 —— 对应本篇合页损失作为线性分类器训练目标的定位，以及与逻辑回归损失的对照。
