写在前面
本系列文章是对《统计学习方法》（李航著）的深度研读笔记。每篇不是简单的知识罗列，而是从第一性原理出发，把每个公式的来龙去脉推演清楚。我会补充原书中省略的推导步骤、给出具体的数值计算案例，并在文末附上面试常考的高频问答。
支持向量机（Support Vector Machine, SVM）是统计学习中理论最优美的算法之一。它源于 Vapnik 等人的统计学习理论，核心思想极其简洁：在特征空间中寻找一个分类超平面，使得两类样本点到这个超平面的最小距离（margin）最大化。
本文将从线性可分 SVM 的硬间隔推导出发，逐步深入到软间隔、核技巧、SMO 算法、SVR 以及多分类策略。建议读者在手边备好纸笔，跟着推导一起推一遍——死磕系列的精髓就在于亲手算。
1. 线性可分支持向量机（硬间隔最大化）
1.1 问题设定
给定训练数据集：
$$D = \{(x_1, y_1), (x_2, y_2), \ldots, (x_N, y_N)\}$$
其中 $x_i \in \mathbb{R}^n$，$y_i \in {+1, -1}$。假设数据集线性可分，即存在一个超平面：
$$w \cdot x + b = 0$$
能够将两类样本完全分开。
1.2 函数间隔与几何间隔
定义 1（函数间隔, Functional Margin）：对于给定的训练数据集 $D$ 和超平面 $(w, b)$，样本点 $(x_i, y_i)$ 的函数间隔为：
$$\hat{\gamma}_i = y_i (w \cdot x_i + b)$$
整个数据集的函数间隔为所有样本点函数间隔的最小值：
$$\hat{\gamma} = \min_{i=1,\ldots,N} \hat{\gamma}_i$$
函数间隔的问题：如果我们等比例缩放 $w$ 和 $b$（例如乘以 2），超平面没有改变，但函数间隔会变成原来的两倍。这说明函数间隔并不能真实反映样本点到超平面的几何距离。
定义 2（几何间隔, Geometric Margin）：样本点 $(x_i, y_i)$ 到超平面 $(w, b)$ 的几何间隔为：
$$\gamma_i = y_i \left(\frac{w}{\|w\|} \cdot x_i + \frac{b}{\|w\|}\right)$$
数据集的几何间隔为：
$$\gamma = \min_{i=1,\ldots,N} \gamma_i$$
几何间隔是样本点到超平面的带符号的 Euclid 距离。当样本被正确分类时，它就是点到超平面的垂直距离。
函数间隔与几何间隔的关系：
$$\gamma_i = \frac{\hat{\gamma}_i}{\|w\|}, \quad \gamma = \frac{\hat{\gamma}}{\|w\|}$$
1.3 最大间隔优化问题
SVM 的核心思想：寻找一个超平面，使得离超平面最近的点（支持向量）到超平面的距离最大化。
直观理解：如果我们把分类超平面想象成一条”最宽的路”的中间线，那么我们希望路的两边尽可能宽，这样才能给新样本留出足够的容错空间。
原始优化问题：
$$\begin{aligned} \max_{w,b} &\quad \gamma \\ \text{s.t.} &\quad y_i\left(\frac{w}{\|w\|} \cdot x_i + \frac{b}{\|w\|}\right) \geq \gamma, \quad i = 1, 2, \ldots, N \end{aligned}$$
利用函数间隔与几何间隔的关系 $\gamma = \frac{\hat{\gamma}}{|w|}$，上述问题等价于：
$$\begin{aligned} \max_{w,b} &\quad \frac{\hat{\gamma}}{\|w\|} \\ \text{s.t.} &\quad y_i(w \cdot x_i + b) \geq \hat{\gamma}, \quad i = 1, 2, \ldots, N \end{aligned}$$
取 $\hat{\gamma} = 1$（这是合法的，因为函数间隔的缩放不影响优化结果），得到 SVM 的标准形式：
$$\begin{aligned} \min_{w,b} &\quad \frac{1}{2}\|w\|^2 \\ \text{s.t.} &\quad y_i(w \cdot x_i + b) \geq 1, \quad i = 1, 2, \ldots, N \end{aligned}$$
这里用 $\frac{1}{2}|w|^2$ 替代 $|w|$ 是为了求导方便（消去根号），且 $\min \frac{1}{2}|w|^2$ 与 $\max \frac{1}{|w|}$ 等价。
为什么取 $\hat{\gamma} = 1$？ 这本质上是利用函数间隔可以任意缩放的性质做归一化。具体来说，令 $\hat{\gamma} = 1$ 等价于要求所有点到超平面的函数间隔至少为 1。如果我们得到了一个解 $(w, b)$ 使得 $y_i(w \cdot x_i + b) \geq 1$，那么对于任意正的 $c$，$(cw, cb)$ 也会满足同样的约束，但 $|cw| = c|w|$ 会更大，所以优化问题会自动选择使 $|w|$ 最小的那个规范化。
1.4 支持向量
满足 $y_i(w \cdot x_i + b) = 1$ 的样本点称为支持向量（Support Vector）。它们是距离分类超平面最近的点，决定了超平面的位置——这就是”支持向量机”名字的由来。
对于正类支持向量，有 $w \cdot x_i + b = 1$；
对于负类支持向量，有 $w \cdot x_i + b = -1$。
两个异类支持向量到超平面的距离之和为：
$$\gamma = \frac{2}{\|w\|}$$
这就是 margin 的几何含义：分类间隔的宽度等于 $\frac{2}{|w|}$。
SVM 的稀疏性：最终模型只依赖于支持向量，其他样本点（满足 $y_i(w \cdot x_i + b) > 1$）的 Lagrange 乘子 $\alpha_i = 0$，对模型没有贡献。这一性质使得 SVM 在预测时具有很高的效率。
2. 对偶问题与 KKT 条件
2.1 拉格朗日对偶性
对于原始问题：
$$\begin{aligned} \min_{w,b} &\quad \frac{1}{2}\|w\|^2 \\ \text{s.t.} &\quad y_i(w \cdot x_i + b) - 1 \geq 0, \quad i = 1, 2, \ldots, N \end{aligned}$$
引入 Lagrange 乘子 $\alpha_i \geq 0$（共 $N$ 个，每个约束一个），构造拉格朗日函数：
$$L(w, b, \alpha) = \frac{1}{2}\|w\|^2 - \sum_{i=1}^{N} \alpha_i [y_i(w \cdot x_i + b) - 1]$$
注意这里的不等式约束是 $g_i(w, b) = y_i(w \cdot x_i + b) - 1 \geq 0$ 的形式，所以 Lagrange 函数中减号前面对应 $\alpha_i g_i$。
原始问题可以写成拉格朗日函数的 min-max 形式：
$$\min_{w,b} \max_{\alpha \geq 0} L(w, b, \alpha)$$
这是因为：如果存在 $i$ 使得 $y_i(w \cdot x_i + b) - 1 < 0$，则 $\max_{\alpha \geq 0}$ 会通过让 $\alpha_i \to \infty$ 使得整个值趋向 $+\infty$；只有在所有约束都满足时，$\max_{\alpha \geq 0}$ 才收敛到 $\frac{1}{2}|w|^2$（因为此时 $\alpha_i [y_i(w \cdot x_i + b) - 1] \geq 0$，取 $\alpha_i = 0$ 使第二项为 0）。
2.2 对偶问题
交换 min 和 max 的顺序，得到对偶问题：
$$\max_{\alpha \geq 0} \min_{w,b} L(w, b, \alpha)$$
为什么可以交换？ SVM 的原始问题是凸二次规划问题，且满足 Slater 条件（对于线性可分数据，存在严格可行点），因此强对偶性成立，对偶间隙为零。
Step 1：求解 $\min_{w,b} L(w, b, \alpha)$
对 $w$ 和 $b$ 求偏导并令其为 0：
$$\nabla_w L = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0 \quad \Rightarrow \quad w = \sum_{i=1}^{N} \alpha_i y_i x_i$$
$$\frac{\partial L}{\partial b} = -\sum_{i=1}^{N} \alpha_i y_i = 0 \quad \Rightarrow \quad \sum_{i=1}^{N} \alpha_i y_i = 0$$
Step 2：将结果代回 $L(w, b, \alpha)$
$$\begin{aligned} L(w, b, \alpha) &= \frac{1}{2}\|w\|^2 - \sum_{i=1}^{N} \alpha_i [y_i(w \cdot x_i + b) - 1] \\ &= \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i y_i (w \cdot x_i) - b\sum_{i=1}^{N} \alpha_i y_i + \sum_{i=1}^{N} \alpha_i \end{aligned}$$
由于 $\sum_{i=1}^{N} \alpha_i y_i = 0$，第三项为 0。又因为 $w = \sum_{j=1}^{N} \alpha_j y_j x_j$，所以：
$$\begin{aligned} \sum_{i=1}^{N} \alpha_i y_i (w \cdot x_i) &= \sum_{i=1}^{N} \alpha_i y_i \left(\sum_{j=1}^{N} \alpha_j y_j x_j \cdot x_i\right) \\ &= \sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) \end{aligned}$$
代入后：
$$\begin{aligned} L(w, b, \alpha) &= \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \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 (x_i \cdot x_j) + \sum_{i=1}^{N} \alpha_i \end{aligned}$$
对偶问题：
$$\begin{aligned} \max_{\alpha} &\quad -\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) + \sum_{i=1}^{N} \alpha_i \\ \text{s.t.} &\quad \sum_{i=1}^{N} \alpha_i y_i = 0 \\ &\quad \alpha_i \geq 0, \quad i = 1, 2, \ldots, N \end{aligned}$$
通常我们把它写为等价的极小化问题：
$$\begin{aligned} \min_{\alpha} &\quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i \\ \text{s.t.} &\quad \sum_{i=1}^{N} \alpha_i y_i = 0 \\ &\quad \alpha_i \geq 0, \quad i = 1, 2, \ldots, N \end{aligned}$$
2.3 KKT 条件
KKT（Karush-Kuhn-Tucker）条件是原始问题与对偶问题最优解的必要条件。对于强对偶成立的凸优化问题，KKT 条件也是充分条件。
SVM 的 KKT 条件：
原始可行性（Primal Feasibility）：
$$y_i(w \cdot x_i + b) - 1 \geq 0, \quad i = 1, \ldots, N$$对偶可行性（Dual Feasibility）：
$$\alpha_i \geq 0, \quad i = 1, \ldots, N$$互补松弛条件（Complementary Slackness）：
$$\alpha_i [y_i(w \cdot x_i + b) - 1] = 0, \quad i = 1, \ldots, N$$驻点条件（Stationarity）：
$$\nabla_w L = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0$$
$$\frac{\partial L}{\partial b} = -\sum_{i=1}^{N} \alpha_i y_i = 0$$
2.4 从 KKT 条件理解支持向量
由互补松弛条件 $\alpha_i [y_i(w \cdot x_i + b) - 1] = 0$：
- 若 $\alpha_i > 0$，则必有 $y_i(w \cdot x_i + b) = 1$，即样本 $x_i$ 落在间隔边界上，是支持向量。
- 若 $\alpha_i = 0$，则 $y_i(w \cdot x_i + b) \geq 1$，即样本 $x_i$ 在间隔边界之外或刚好在边界上（一般在我们关心的范围内是 $> 1$），它不是支持向量。
超平面的参数完全由支持向量决定：
$$w = \sum_{i=1}^{N} \alpha_i y_i x_i = \sum_{i \in SV} \alpha_i y_i x_i$$
对于 $b$，选择任意一个满足 $\alpha_j > 0$ 的支持向量 $(x_j, y_j)$：
$$b = y_j - \sum_{i \in SV} \alpha_i y_i (x_i \cdot x_j)$$
实践中为了数值稳定性，通常对所有支持向量求平均：
$$b = \frac{1}{|SV|} \sum_{j \in SV} \left[y_j - \sum_{i \in SV} \alpha_i y_i (x_i \cdot x_j)\right]$$
2.5 数值计算案例
假设我们有如下三个样本点：
| $i$ | $x_i$ | $y_i$ |
|---|---|---|
| 1 | $(0, 0)$ | $-1$ |
| 2 | $(1, 0)$ | $+1$ |
| 3 | $(2, 0)$ | $+1$ |
这是一维数据，很容易看出分类超平面应该在 $x = 0$ 和 $x = 1$ 之间。
对偶问题为：
$$\min_{\alpha} \quad \frac{1}{2}\sum_{i=1}^{3}\sum_{j=1}^{3} \alpha_i \alpha_j y_i y_j x_i x_j - \sum_{i=1}^{3} \alpha_i$$
约束：$\sum_{i=1}^{3} \alpha_i y_i = -\alpha_1 + \alpha_2 + \alpha_3 = 0$，$\alpha_i \geq 0$。
令核矩阵 $K_{ij} = y_i y_j x_i x_j$：
$$ K = \begin{bmatrix} 0 & 0 & 0 \\ 0 & 1 & 2 \\ 0 & 2 & 4 \end{bmatrix} $$
目标函数：
$$\begin{aligned} J(\alpha) &= \frac{1}{2}(\alpha_2^2 + 4\alpha_2\alpha_3 + 4\alpha_3^2) - (\alpha_1 + \alpha_2 + \alpha_3) \\ &= \frac{1}{2}(\alpha_2 + 2\alpha_3)^2 - (\alpha_1 + \alpha_2 + \alpha_3) \end{aligned}$$
由等式约束 $\alpha_1 = \alpha_2 + \alpha_3$，代入：
$$J(\alpha) = \frac{1}{2}(\alpha_2 + 2\alpha_3)^2 - (2\alpha_2 + 2\alpha_3)$$
对 $\alpha_2$ 和 $\alpha_3$ 求偏导并令其为 0：
$$\frac{\partial J}{\partial \alpha_2} = (\alpha_2 + 2\alpha_3) - 2 = 0$$
$$\frac{\partial J}{\partial \alpha_3} = 2(\alpha_2 + 2\alpha_3) - 2 = 0$$
从第二式得 $\alpha_2 + 2\alpha_3 = 1$，代入第一式验证一致。
考虑约束 $\alpha_i \geq 0$，取 $\alpha_2 = 1, \alpha_3 = 0$，则 $\alpha_1 = 1$。
计算 $w$：
$$w = \sum_{i=1}^{3} \alpha_i y_i x_i = 1 \cdot (-1) \cdot 0 + 1 \cdot (+1) \cdot 1 + 0 \cdot (+1) \cdot 2 = 1$$
计算 $b$（取支持向量 $x_1 = 0, y_1 = -1$）：
$$b = y_1 - w \cdot x_1 = -1 - 1 \cdot 0 = -1$$
决策函数：$f(x) = \text{sign}(x - 1)$
也就是说，分类超平面在 $x = 1$ 处（注意：这里 $w=1, b=-1$，超平面是 $x-1=0$，即 $x=1$）。
解读：支持向量是点 1 $(0, -1)$ 和点 2 $(1, +1)$。点 3 $(2, +1)$ 不是支持向量（$\alpha_3 = 0$）。margin 为 $\frac{2}{|w|} = 2$，两条间隔边界分别是 $x = 0$（负类支持向量处）和 $x = 1$（正类支持向量处）。
3. 软间隔最大化（Soft Margin）
3.1 线性不可分情形
现实中的数据很少是完全线性可分的。即使数据线性可分，追求完美的硬间隔也可能导致过拟合（对噪声敏感）。
软间隔的核心思想：允许一些样本点不满足 $y_i(w \cdot x_i + b) \geq 1$ 的约束，但要对这些”犯规”进行惩罚。
3.2 松弛变量
引入松弛变量（slack variables）$\xi_i \geq 0, i = 1, \ldots, N$，约束条件变为：
$$y_i(w \cdot x_i + b) \geq 1 - \xi_i$$
此时，每个样本点的函数间隔允许小于 1。当 $\xi_i$ 足够大时，约束条件是平凡的，但我们在目标函数中惩罚 $\xi_i$ 的值。
软间隔的原始问题：
$$\begin{aligned} \min_{w,b,\xi} &\quad \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{N} \xi_i \\ \text{s.t.} &\quad y_i(w \cdot x_i + b) \geq 1 - \xi_i, \quad i = 1, 2, \ldots, N \\ &\quad \xi_i \geq 0, \quad i = 1, 2, \ldots, N \end{aligned}$$
其中 $C > 0$ 是惩罚参数（regularization parameter）：
- $C$ 越大，对误分类的惩罚越重 → 更接近硬间隔 → 可能过拟合
- $C$ 越小，对误分类的容忍度越高 → margin 更宽 → 可能欠拟合
3.3 软间隔的几何解释
$\xi_i$ 的值反映了样本点 $x_i$ 的位置：
- $\xi_i = 0$：$x_i$ 在间隔边界外侧或被正确分类（$y_i(w \cdot x_i + b) \geq 1$）
- $0 < \xi_i \leq 1$：$x_i$ 落在间隔内部，但仍被正确分类（$0 \leq y_i(w \cdot x_i + b) < 1$）
- $\xi_i > 1$：$x_i$ 被误分类（$y_i(w \cdot x_i + b) < 0$）
所以 $\sum_{i=1}^{N} \xi_i$ 是训练数据中不满足 $y_i(w \cdot x_i + b) \geq 1$ 的总”偏移量”的上界。
3.4 软间隔的对偶问题
构造拉格朗日函数：
$$L(w, b, \xi, \alpha, \mu) = \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{N} \xi_i - \sum_{i=1}^{N} \alpha_i [y_i(w \cdot x_i + b) - 1 + \xi_i] - \sum_{i=1}^{N} \mu_i \xi_i$$
其中 $\alpha_i \geq 0, \mu_i \geq 0$。
求偏导：
$$\nabla_w L = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0 \quad \Rightarrow \quad w = \sum_{i=1}^{N} \alpha_i y_i x_i$$
$$\frac{\partial L}{\partial b} = -\sum_{i=1}^{N} \alpha_i y_i = 0 \quad \Rightarrow \quad \sum_{i=1}^{N} \alpha_i y_i = 0$$
$$\frac{\partial L}{\partial \xi_i} = C - \alpha_i - \mu_i = 0 \quad \Rightarrow \quad C = \alpha_i + \mu_i$$
将 $w = \sum \alpha_i y_i x_i$ 和 $\sum \alpha_i y_i = 0$ 代入，并利用 $\mu_i = C - \alpha_i$，得到对偶问题：
$$\begin{aligned} \min_{\alpha} &\quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j (x_i \cdot x_j) - \sum_{i=1}^{N} \alpha_i \\ \text{s.t.} &\quad \sum_{i=1}^{N} \alpha_i y_i = 0 \\ &\quad 0 \leq \alpha_i \leq C, \quad i = 1, 2, \ldots, N \end{aligned}$$
与硬间隔对偶问题的唯一区别：约束条件从 $\alpha_i \geq 0$ 变成了 $0 \leq \alpha_i \leq C$。
$\alpha_i$ 的上界 $C$ 源于 $\mu_i = C - \alpha_i \geq 0$ 的要求。
3.5 软间隔的 KKT 条件
- 原始可行性：$y_i(w \cdot x_i + b) \geq 1 - \xi_i$, $\xi_i \geq 0$
- 对偶可行性：$\alpha_i \geq 0$, $\mu_i \geq 0$
- 互补松弛：
$$\alpha_i [y_i(w \cdot x_i + b) - 1 + \xi_i] = 0$$
$$\mu_i \xi_i = 0$$ - 驻点：$w = \sum \alpha_i y_i x_i$, $\sum \alpha_i y_i = 0$, $C = \alpha_i + \mu_i$
由 KKT 条件可以分析 $\alpha_i$ 取值的含义：
| $\alpha_i$ | 条件 | 样本位置 |
|---|---|---|
| $\alpha_i = 0$ | $\mu_i = C$, $\xi_i = 0$ | 在间隔边界外，正确分类 |
| $0 < \alpha_i < C$ | $\mu_i > 0$, $\xi_i = 0$ | 在间隔边界上，支持向量 |
| $\alpha_i = C$ | $\mu_i = 0$, $\xi_i \geq 0$ | 在间隔内或被错分 |
支持向量扩展到包含所有 $\alpha_i > 0$ 的样本，包括在间隔内和错分的点。
3.6 Hinge Loss 视角
软间隔 SVM 可以等价地表示为无约束优化问题：
$$\min_{w,b} \quad \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{N} \max(0, 1 - y_i(w \cdot x_i + b))$$
其中 $\ell_{\text{hinge}}(z) = \max(0, 1-z)$ 称为 Hinge Loss（合页损失函数）。
证明：令 $\xi_i = \max(0, 1 - y_i(w \cdot x_i + b))$，则约束 $y_i(w \cdot x_i + b) \geq 1 - \xi_i$ 自动满足，且 $\xi_i \geq 0$。无约束形式的最优解与原始约束问题一致。
Hinge Loss 的性质：
- 当 $y_i(w \cdot x_i + b) \geq 1$（正确分类且置信度足够高）时，loss 为 0
- 当 $y_i(w \cdot x_i + b) < 1$ 时，loss 线性增长
- 0-1 loss 的上界是 hinge loss：$\mathbf{1}{y(w \cdot x + b) < 0} \leq \max(0, 1 - y(w \cdot x + b))$
与 Logistic Loss 的对比：
| 损失函数 | 公式 | 特点 |
|---|---|---|
| 0-1 Loss | $\mathbf{1}{y f(x) < 0}$ | 非凸，难以优化 |
| Hinge Loss | $\max(0, 1 - y f(x))$ | 稀疏解（支持向量少） |
| Logistic Loss | $\log(1 + e^{-y f(x)})$ | 概率输出，处处可导 |
| Exponential Loss | $e^{-y f(x)}$ | 对异常值极敏感（AdaBoost 所用） |
Hinge loss 的一个关键性质是产生稀疏解：对于 $y f(x) > 1$ 的样本，loss 严格为 0，其梯度也为 0——这对应于 $\alpha_i = 0$。
4. 核技巧（Kernel Trick）
4.1 从线性到非线性
前面讨论的都是线性 SVM，但现实中很多问题是线性不可分的。一个自然的想法是：将数据映射到高维空间，在高维空间中线性可分。
设 $\phi: \mathcal{X} \to \mathcal{H}$ 为从输入空间 $\mathcal{X}$ 到特征空间 $\mathcal{H}$ 的映射。我们希望在 $\mathcal{H}$ 中学习线性 SVM。
对偶问题中，样本点的内积 $x_i \cdot x_j$ 被替换为 $\phi(x_i) \cdot \phi(x_j)$。如果我们能够**不显式计算 $\phi$ 而直接计算 $\phi(x_i) \cdot \phi(x_j)$**，就可以避免高维特征空间带来的计算负担。这就是核技巧的核心思想。
4.2 核函数定义
定义 3（核函数）：设 $\mathcal{X}$ 是输入空间，$K(\cdot, \cdot)$ 是定义在 $\mathcal{X} \times \mathcal{X}$ 上的对称函数。如果存在一个从 $\mathcal{X}$ 到 Hilbert 空间 $\mathcal{H}$ 的映射 $\phi$，使得：
$$K(x, z) = \phi(x) \cdot \phi(z)$$
对任意 $x, z \in \mathcal{X}$ 成立，则称 $K$ 为核函数，$\phi$ 为映射函数。
核技巧的作用：在 SVM 对偶问题中，所有涉及 $x_i \cdot x_j$ 的地方替换为 $K(x_i, x_j)$。这样我们隐式地在高维空间中做线性分类，而计算量仍保持在原始维度的水平。
$$\begin{aligned} \min_{\alpha} &\quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j K(x_i, x_j) - \sum_{i=1}^{N} \alpha_i \\ \text{s.t.} &\quad \sum_{i=1}^{N} \alpha_i y_i = 0 \\ &\quad 0 \leq \alpha_i \leq C, \quad i = 1, 2, \ldots, N \end{aligned}$$
决策函数：
$$f(x) = \text{sign}\left(\sum_{i=1}^{N} \alpha_i y_i K(x_i, x) + b\right)$$
4.3 Mercer 定理
不是任意一个二元函数都可以作为核函数。Mercer 定理给出了判断标准。
定理 1（Mercer 定理）：对称函数 $K(x, z)$ 是某个特征空间中的内积运算的充要条件是：对任意满足 $\int f(x)^2 dx < \infty$ 的函数 $f(x)$，有：
$$\iint K(x, z) f(x) f(z) dx dz \geq 0$$
这等价于：对于任意有限个输入点 ${x_1, \ldots, x_N}$，Gram 矩阵 $K = [K(x_i, x_j)]_{N \times N}$ 是半正定矩阵。
验证方法：对于给定的函数 $K(x, z)$，任取一组点 ${x_1, \ldots, x_m}$，构造 Gram 矩阵并验证其半正定性。
- 如果存在一组点使得 Gram 矩阵不是半正定的，则 $K$ 不是正定核。
4.4 常见核函数
4.4.1 线性核（Linear Kernel）
$$K(x, z) = x \cdot z$$
就是原始空间中的内积，不进行任何映射。适用于线性可分数据。
4.4.2 多项式核（Polynomial Kernel）
$$K(x, z) = (x \cdot z + c)^d$$
其中 $d$ 为正整数（多项式次数），$c \geq 0$ 为常数项。
特征映射示例（$d = 2, c = 1, x \in \mathbb{R}^2$）：
$$K(x, z) = (x_1 z_1 + x_2 z_2 + 1)^2 = 1 + 2x_1 z_1 + 2x_2 z_2 + x_1^2 z_1^2 + x_2^2 z_2^2 + 2x_1 x_2 z_1 z_2$$
对应的特征映射为：
$$\phi(x) = (1, \sqrt{2}x_1, \sqrt{2}x_2, x_1^2, x_2^2, \sqrt{2}x_1 x_2)^T$$
原始 2 维 → 特征空间 6 维。如果我们不借助核技巧直接在 6 维空间中计算内积，每次需要 6 次乘法和 5 次加法；而核函数只需要原空间中的 2 次乘法、1 次加法和 1 次平方，计算量与维度无关。
参数影响：
- $d$：控制映射空间的复杂度。$d$ 越大，决策边界越复杂，越容易过拟合。
- $c$：控制低阶项和高阶项的相对权重。$c$ 越大，低阶项的影响越大。
4.4.3 高斯核 / RBF 核
$$K(x, z) = \exp\left(-\frac{\|x - z\|^2}{2\sigma^2}\right) = \exp(-\gamma \|x - z\|^2)$$
其中 $\gamma = \frac{1}{2\sigma^2}$ 是带宽参数（bandwidth），这是实践中使用最广泛的核函数。
RBF 核的特征空间是无限维的。我们可以通过 Taylor 展开来验证：
$$\begin{aligned} K(x, z) &= \exp(-\gamma\|x\|^2) \exp(-\gamma\|z\|^2) \exp(2\gamma x \cdot z) \\ &= \exp(-\gamma\|x\|^2) \exp(-\gamma\|z\|^2) \sum_{n=0}^{\infty} \frac{(2\gamma x \cdot z)^n}{n!} \end{aligned}$$
特征映射 $\phi(x)$ 的每个分量对应 Taylor 展开中的每一项，无限多项 → 无限维。
参数 $\gamma$ 的影响：
- $\gamma$ 大（$\sigma$ 小）→ 高斯分布窄 → 每个样本只影响其非常邻近的区域 → 决策边界曲折 → 容易过拟合
- $\gamma$ 小（$\sigma$ 大）→ 高斯分布宽 → 每个样本的影响范围大 → 决策边界平滑 → 可能欠拟合
可以通过观察 $|x - z|^2$ 与 $K(x, z)$ 的关系来直观理解：
| $|x - z|$ | $K(x, z)$（$\gamma = 0.1$） | $K(x, z)$（$\gamma = 1$） | $K(x, z)$（$\gamma = 10$） |
|---|---|---|---|
| 0 | 1.000 | 1.000 | 1.000 |
| 1 | 0.905 | 0.368 | 0.00005 |
| 2 | 0.670 | 0.018 | $\approx 0$ |
| 5 | 0.082 | $\approx 0$ | $\approx 0$ |
可以看到，$\gamma$ 越大，核函数的值下降越快，相似度判断越”苛刻”。
4.4.4 Sigmoid 核
$$K(x, z) = \tanh(\kappa x \cdot z + \theta)$$
其中 $\kappa > 0$（scale 参数），$\theta < 0$（shift 参数）。
注意：Sigmoid 核对应的 Gram 矩阵不总是半正定的（对某些参数可能不满足 Mercer 条件），但在实践中有时仍能工作。它的形式相当于一个两层的神经网络（没有隐层），这揭示了 SVM 与神经网络的深层联系。
4.5 核函数的选择策略
| 场景 | 推荐核函数 | 原因 |
|---|---|---|
| 特征维数高（如文本分类） | 线性核 | 数据在原始空间已经接近线性可分 |
| 特征维数低，样本量中等 | RBF 核 | 最通用，几乎没有失败的先例 |
| 特征维数低，样本量大 | 线性核 或 自定义核 | 加快训练速度 |
| 需要显式的特征表示 | 多项式核 | 特征空间维数可计算 |
经验法则：先用线性核测试，如果效果不好再用 RBF 核。RBF 核通常是”默认首选”。
4.6 核函数运算
给定两个核函数 $K_1$ 和 $K_2$，以下运算仍产生有效核函数（封闭性）：
- $K(x, z) = K_1(x, z) + K_2(x, z)$
- $K(x, z) = c \cdot K_1(x, z)$（$c > 0$）
- $K(x, z) = K_1(x, z) \cdot K_2(x, z)$
- $K(x, z) = f(x) \cdot K_1(x, z) \cdot f(z)$（$f$ 为任意实值函数）
- $K(x, z) = \exp(K_1(x, z))$
- $K(x, z) = x^T A z$（$A$ 为半正定矩阵）
这些性质允许我们从基本核函数出发构造复杂的核函数，类似于用 LEGO 积木搭出所需的特征空间。
5. SMO 算法
5.1 为什么需要 SMO
SVM 的对偶问题是一个凸二次规划（QP）问题，变量个数等于样本数 $N$。当 $N$ 很大时，通用的 QP 求解器（如内点法）计算量巨大（$O(N^3)$）。
SMO（Sequential Minimal Optimization，序列最小最优化）由 John Platt 于 1998 年提出，它将大 QP 问题分解为一系列最小的 QP 子问题——每次只优化两个变量。
5.2 SMO 的核心思想
**每次选择两个变量 $\alpha_i$ 和 $\alpha_j$ 进行优化，固定其他所有 $\alpha$**。
之所以至少要选两个变量，是因为等式约束 $\sum_{k=1}^{N} \alpha_k y_k = 0$ 的存在——如果只改变一个 $\alpha_i$，约束就无法维持。
设在第 $t$ 次迭代中，选择 $\alpha_1$ 和 $\alpha_2$ 进行优化，固定 $\alpha_3, \ldots, \alpha_N$。
由于 $\sum_{k=1}^{N} \alpha_k y_k = 0$ 且 $\alpha_3, \ldots, \alpha_N$ 固定，则有：
$$\alpha_1 y_1 + \alpha_2 y_2 = -\sum_{k=3}^{N} \alpha_k y_k = \text{常数} \triangleq \zeta$$
5.3 双变量优化子问题
以优化 $\alpha_1, \alpha_2$ 为例。记 $\alpha_1^{\text{old}}, \alpha_2^{\text{old}}$ 为优化前的值，$\alpha_1^{\text{new}}, \alpha_2^{\text{new}}$ 为优化后的值。
约束条件：
- $0 \leq \alpha_1 \leq C$
- $0 \leq \alpha_2 \leq C$
- $\alpha_1 y_1 + \alpha_2 y_2 = \zeta$
从第三个约束可以解出 $\alpha_1 = y_1(\zeta - \alpha_2 y_2)$，带入目标函数得到一个关于 $\alpha_2$ 的一元二次函数。由于约束是线性的，目标函数在闭区间上的最小值可以直接求得。
5.4 未剪辑解与剪辑
Step 1：计算 $\alpha_2^{\text{new, unc}}$（未剪辑解）
令 $E_i = f(x_i) - y_i$ 为第 $i$ 个样本的误差（其中 $f(x_i) = \sum_{k=1}^{N} \alpha_k y_k K(x_k, x_i) + b$）。
经验证，$\alpha_2$ 的未剪辑更新公式为：
$$\alpha_2^{\text{new, unc}} = \alpha_2^{\text{old}} + \frac{y_2(E_1 - E_2)}{\eta}$$
其中 $\eta = K(x_1, x_1) + K(x_2, x_2) - 2K(x_1, x_2) = |\phi(x_1) - \phi(x_2)|^2$。
推导：将目标函数写为 $\alpha_2$ 的函数（把 $\alpha_1$ 表示为 $\alpha_2$ 的线性函数后代入），求导令为 0 即可。这里 $\eta$ 是目标函数对 $\alpha_2$ 的二阶导数。目标的二次项系数为 $\frac{1}{2}\eta$。
Step 2：对 $\alpha_2^{\text{new}}$ 进行剪辑（Clipping）
$\alpha_2$ 必须满足 $0 \leq \alpha_2 \leq C$ 且与 $\alpha_1$ 的约束相容。
设 $L \leq \alpha_2 \leq H$：
若 $y_1 \neq y_2$（异号）：
$$L = \max(0, \alpha_2^{\text{old}} - \alpha_1^{\text{old}}), \quad H = \min(C, C + \alpha_2^{\text{old}} - \alpha_1^{\text{old}})$$若 $y_1 = y_2$（同号）：
$$L = \max(0, \alpha_1^{\text{old}} + \alpha_2^{\text{old}} - C), \quad H = \min(C, \alpha_1^{\text{old}} + \alpha_2^{\text{old}})$$
推导：由 $\alpha_1 y_1 + \alpha_2 y_2 = \alpha_1^{\text{old}} y_1 + \alpha_2^{\text{old}} y_2$：
- 当 $y_1 = y_2$ 时：$\alpha_1 + \alpha_2 = \alpha_1^{\text{old}} + \alpha_2^{\text{old}}$，结合 $0 \leq \alpha_1, \alpha_2 \leq C$ 即可得到范围。
- 当 $y_1 \neq y_2$ 时：$\alpha_1 - \alpha_2 = \alpha_1^{\text{old}} - \alpha_2^{\text{old}}$，类似推导。
剪辑后的解：
$$\alpha_2^{\text{new}} = \begin{cases} H & \text{if } \alpha_2^{\text{new, unc}} > H \\ \alpha_2^{\text{new, unc}} & \text{if } L \leq \alpha_2^{\text{new, unc}} \leq H \\ L & \text{if } \alpha_2^{\text{new, unc}} < L \end{cases}$$
Step 3：计算 $\alpha_1^{\text{new}}$
由 $\alpha_1^{\text{new}} y_1 + \alpha_2^{\text{new}} y_2 = \alpha_1^{\text{old}} y_1 + \alpha_2^{\text{old}} y_2$：
$$\alpha_1^{\text{new}} = \alpha_1^{\text{old}} + y_1 y_2 (\alpha_2^{\text{old}} - \alpha_2^{\text{new}})$$
5.5 阈值 $b$ 的更新
每轮优化两个 $\alpha$ 后，需要更新 $b$ 使得两个样本的 KKT 条件被满足。
若 $0 < \alpha_1^{\text{new}} < C$，则：
$$b_1^{\text{new}} = -E_1 - y_1 K(x_1, x_1)(\alpha_1^{\text{new}} - \alpha_1^{\text{old}}) - y_2 K(x_2, x_1)(\alpha_2^{\text{new}} - \alpha_2^{\text{old}}) + b^{\text{old}}$$
若 $0 < \alpha_2^{\text{new}} < C$，则：
$$b_2^{\text{new}} = -E_2 - y_1 K(x_1, x_2)(\alpha_1^{\text{new}} - \alpha_1^{\text{old}}) - y_2 K(x_2, x_2)(\alpha_2^{\text{new}} - \alpha_2^{\text{old}}) + b^{\text{old}}$$
最终取法：
$$b^{\text{new}} = \begin{cases} b_1^{\text{new}} & \text{if } 0 < \alpha_1^{\text{new}} < C \\ b_2^{\text{new}} & \text{if } 0 < \alpha_2^{\text{new}} < C \\ \frac{b_1^{\text{new}} + b_2^{\text{new}}}{2} & \text{otherwise} \end{cases}$$
直觉：只有当 $\alpha_i$ 在 $(0, C)$ 之间时，对应的样本恰好在间隔边界上，此时互补松弛条件强制 $y_i(w \cdot x_i + b) = 1$，从而可以精确反解 $b$。
5.6 变量选择启发式
SMO 的性能关键依赖于选择合适的 $\alpha_1, \alpha_2$。
第一个变量的选择（外层循环）：
选择违反 KKT 条件最严重的 $\alpha_i$。KKT 条件的违反程度可以用以下方式判断：
| $\alpha_i$ 范围 | KKT 条件 | 违反条件 |
|---|---|---|
| $\alpha_i = 0$ | $y_i f(x_i) \geq 1$ | $y_i f(x_i) < 1$ |
| $0 < \alpha_i < C$ | $y_i f(x_i) = 1$ | $y_i f(x_i) \neq 1$（在容差 $\epsilon$ 外） |
| $\alpha_i = C$ | $y_i f(x_i) \leq 1$ | $y_i f(x_i) > 1$ |
第二个变量的选择（内层循环）：
选择使 $|E_1 - E_2|$ 最大的 $\alpha_2$。因为更新步长 $\frac{y_2(E_1 - E_2)}{\eta}$ 与误差差成正比，差异越大，更新幅度越大，收敛越快。
如果上述策略选出的 $\alpha_2$ 不能使目标函数有足够下降，则遍历所有非边界 $\alpha$；如果仍然不行，则遍历整个数据集。
5.7 SMO 算法流程（伪代码）
Algorithm: SMO (Sequential Minimal Optimization) |
复杂度分析：
- 每次选择两个变量并更新的计算量为 $O(N)$（因为需要计算 $E_i$ 和 $E_j$）
- 最差情况下每轮遍历需要 $O(N^2)$，但实践中收敛速度远快于这个上界
- Platt 的原论文报告 SMO 在小到中等规模数据集上的训练时间比标准 QP 求解器快几个数量级
5.8 SMO 数值计算实例
沿用第 2.5 节的例子，设 $C = 1$。
初始化：$\alpha = (0, 0, 0)^T$, $b = 0$。
第一轮迭代：
- $f(x_1) = 0$, $E_1 = 0 - (-1) = 1$
- $f(x_2) = 0$, $E_2 = 0 - 1 = -1$
- $f(x_3) = 0$, $E_3 = 0 - 1 = -1$
检查 KKT：$\alpha_1 = 0$，需要 $y_1 f(x_1) \geq 1$，即 $(-1) \times 0 = 0 \geq 1$ → 违反。
选择 $i=1$ 更新。选 $j=2$（使 $|E_1 - E_2| = 2$ 最大）。
- $y_1 \neq y_2$：$L = \max(0, 0-0) = 0$, $H = \min(1, 1+0-0) = 1$
- $\eta = K_{11} + K_{22} - 2K_{12} = 0 + 1 - 0 = 1$
- $\alpha_2^{\text{new, unc}} = 0 + 1 \cdot (1 - (-1)) / 1 = 2$
- 剪辑到 $[0, 1]$：$\alpha_2^{\text{new}} = 1$
- $\alpha_1^{\text{new}} = 0 + (-1) \cdot 1 \cdot (0 - 1) = 1$
更新 $b$（$\alpha_2^{\text{new}} = 1 = C$，边界上，取平均值）：
$b_1 = -1 - (-1) \cdot 0 \cdot 0 - 1 \cdot 0 \cdot 0 + 0 = -1$，
$b_2 = -(-1) - (-1) \cdot 0 \cdot (-1) - 1 \cdot 0 \cdot 0 + 0 = 1$，
$b = (-1 + 1) / 2 = 0$。
此时 $w = (-1) \cdot 1 \cdot 0 + 1 \cdot 1 \cdot 1 + 0 \cdot 1 \cdot 2 = 1$。
这里 $b^{\text{old}} = 0$，而正确的 $b$ 应该是 $-1$。这是因为 SMO 中 $b$ 的更新是基于互补松弛条件推导的，初值设为 0 后需要逐步收敛。在多个迭代后，$b$ 会收敛到 $-1 + 1 = 0$…实际上和之前闭式解得到的 $b = -1$ 有出入，这提示我们在计算 $b$ 时需要注意使用正确的支持向量（$0 < \alpha < C$ 的样本）。在实际实现中（如 LIBSVM），$b$ 会逐步收敛到正确值。
6. $\nu$-SVM
6.1 问题引入
$C$-SVM 中的惩罚参数 $C$ 缺乏直观的统计解释。$\nu$-SVM（由 Scholkopf 等人于 2000 年提出）引入了一个更直观的参数 $\nu$ 来替代 $C$。
6.2 $\nu$-SVM 的原始问题（$\nu$-SVC）
$$\begin{aligned} \min_{w,b,\xi,\rho} &\quad \frac{1}{2}\|w\|^2 - \nu\rho + \frac{1}{N}\sum_{i=1}^{N} \xi_i \\ \text{s.t.} &\quad y_i(w \cdot \phi(x_i) + b) \geq \rho - \xi_i, \quad i = 1, \ldots, N \\ &\quad \xi_i \geq 0, \quad \rho \geq 0 \end{aligned}$$
这里 $\rho$ 也是优化变量，它代表 margin 的大小（在 $C$-SVM 中 margin 固定为 $2/|w|$，而这里 $\rho$ 是最小化的），通过 $-\nu\rho$ 这一项被拉大。
6.3 $\nu$ 的统计含义
可以证明，$\nu$ 具有以下性质：
- $\nu$ 是支持向量个数占训练样本总数的比例的上界。
- $\nu$ 是 margin error（满足 $\xi_i > 0$ 的样本）占训练样本总数的比例的下界。
- 因此，$\nu \in (0, 1]$ 同时控制了支持向量的数量和训练误差。
这个含义使得 $\nu$-SVM 的参数选择比 $C$-SVM 更加直观：
- $\nu = 0.1$：期望至多 10% 的样本是支持向量
- $\nu = 0.5$：期望至多 50% 的样本是支持向量
6.4 $\nu$-SVM 的对偶问题
$$\begin{aligned} \min_{\alpha} &\quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} \alpha_i \alpha_j y_i y_j K(x_i, x_j) \\ \text{s.t.} &\quad \sum_{i=1}^{N} \alpha_i y_i = 0 \\ &\quad 0 \leq \alpha_i \leq \frac{1}{N} \\ &\quad \sum_{i=1}^{N} \alpha_i \geq \nu \end{aligned}$$
与 $C$-SVM 的区别：
- 上界从 $C$ 变为 $1/N$
- 新增了 $\sum \alpha_i \geq \nu$ 的约束
7. 支持向量回归（SVR）
7.1 回归问题的设定
SVM 不仅可以做分类，还可以做回归。SVR（Support Vector Regression）的目标是找到一个函数 $f(x) = w \cdot \phi(x) + b$，使得大多数训练样本的预测误差在 $\varepsilon$ 范围内，同时 $f$ 尽可能”平坦”（$|w|$ 尽可能小）。
7.2 $\varepsilon$-不敏感损失函数
$$\ell_\varepsilon(y, f(x)) = \max(0, |y - f(x)| - \varepsilon)$$
也就是说，当预测误差不超过 $\varepsilon$ 时，损失为 0；超过 $\varepsilon$ 时，损失线性增长。$\varepsilon$ 就像一条管道，落在管道内的点不计损失。
7.3 $\varepsilon$-SVR 的原始问题
引入两个松弛变量 $\xi_i, \hat{\xi}_i \geq 0$（分别对应上方和下方超出管道的情况）：
$$\begin{aligned} \min_{w,b,\xi,\hat{\xi}} &\quad \frac{1}{2}\|w\|^2 + C\sum_{i=1}^{N} (\xi_i + \hat{\xi}_i) \\ \text{s.t.} &\quad y_i - (w \cdot \phi(x_i) + b) \leq \varepsilon + \xi_i \quad &\text{(上界)} \\ &\quad (w \cdot \phi(x_i) + b) - y_i \leq \varepsilon + \hat{\xi}_i \quad &\text{(下界)} \\ &\quad \xi_i \geq 0, \hat{\xi}_i \geq 0, \quad i = 1, \ldots, N \end{aligned}$$
7.4 $\varepsilon$-SVR 的对偶问题
$$\begin{aligned} \min_{\alpha,\hat{\alpha}} &\quad \frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N} (\alpha_i - \hat{\alpha}_i)(\alpha_j - \hat{\alpha}_j) K(x_i, x_j) \\ &\quad + \varepsilon\sum_{i=1}^{N} (\alpha_i + \hat{\alpha}_i) - \sum_{i=1}^{N} y_i (\alpha_i - \hat{\alpha}_i) \\ \text{s.t.} &\quad \sum_{i=1}^{N} (\alpha_i - \hat{\alpha}_i) = 0 \\ &\quad 0 \leq \alpha_i, \hat{\alpha}_i \leq C \end{aligned}$$
其中 $\alpha_i$ 对应上界约束的 Lagrange 乘子，$\hat{\alpha}_i$ 对应下界约束。
回归函数：
$$f(x) = \sum_{i=1}^{N} (\alpha_i - \hat{\alpha}_i) K(x_i, x) + b$$
只有 $|\alpha_i - \hat{\alpha}_i| > 0$ 的样本才是支持向量（落在管道外或管道壁上）。
7.5 $\nu$-SVR
类似分类中的 $\nu$-SVM，$\nu$-SVR 用参数 $\nu$ 控制支持向量比例和 $\varepsilon$：
$$\begin{aligned} \min_{w,b,\xi,\hat{\xi},\varepsilon} &\quad \frac{1}{2}\|w\|^2 + C\left(\nu\varepsilon + \frac{1}{N}\sum_{i=1}^{N} (\xi_i + \hat{\xi}_i)\right) \\ \text{s.t.} &\quad y_i - (w \cdot \phi(x_i) + b) \leq \varepsilon + \xi_i \\ &\quad (w \cdot \phi(x_i) + b) - y_i \leq \varepsilon + \hat{\xi}_i \\ &\quad \xi_i, \hat{\xi}_i \geq 0, \varepsilon \geq 0 \end{aligned}$$
$\nu$ 的含义：$\nu$ 是支持向量占训练样本比例的上界（同时也是落在 $\varepsilon$ 管道外的样本比例的下界）。$\nu \in (0, 1]$。
8. 多分类 SVM
SVM 本质上是二分类器。处理多分类问题主要有三种策略：
8.1 One-vs-Rest（一对多, OvR）
对于 $K$ 类问题，训练 $K$ 个二分类 SVM。第 $k$ 个 SVM 将第 $k$ 类作为正类，其余所有类作为负类。
预测：选择得分最高的类别（即 $w_k \cdot x + b_k$ 值最大的类）。
$$\hat{y} = \arg\max_{k \in \{1,\ldots,K\}} (w_k \cdot x + b_k)$$
优点：
- 只需训练 $K$ 个分类器
- 训练每个分类器时使用全部数据
缺点：
- 每个二分类器面对严重的类别不平衡（正负样本比约为 $1:K-1$）
- 当 $K$ 较大时，每个分类器的负类过于庞杂，决策边界可能不精确
8.2 One-vs-One（一对一, OvO）
对于 $K$ 类问题，训练 $\binom{K}{2} = \frac{K(K-1)}{2}$ 个二分类 SVM，每个分类器比较两类中的一对。
预测：投票法（每个分类器给其判定的类别投一票，得票最多的类别获胜）。
$$\hat{y} = \arg\max_{k} \sum_{j \neq k} \mathbf{1}\{f_{kj}(x) > 0\}$$
其中 $f_{kj}$ 是比较第 $k$ 类和第 $j$ 类的分类器。
优点：
- 每个子问题数据量小，训练更快
- 不存在类别不平衡问题
缺点：
- 需要训练 $O(K^2)$ 个分类器
- 存在平票的可能（尤其当 $K$ 大时）
8.3 DAG SVM（有向无环图 SVM）
训练阶段与 OvO 相同（$\binom{K}{2}$ 个分类器），预测阶段构建一个有向无环图来减少测试时间。
预测时从根节点开始，每次用一个分类器排除一个类，经过 $K-1$ 步后到达叶节点（仅剩一个类），该叶节点的标签即为预测结果。
优点：预测只需 $K-1$ 个分类器（vs. OvO 的 $K(K-1)/2$ 个）
缺点：结果依赖于分类器的排列顺序，且误差会累积传播。
8.4 多分类策略对比
| 策略 | 训练分类器数 | 预测分类器数 | 训练数据量 | 不平衡问题 | 实现复杂度 |
|---|---|---|---|---|---|
| OvR | $K$ | $K$ | 全部 | 严重 | 低 |
| OvO | $K(K-1)/2$ | $K(K-1)/2$ | 两类 | 无 | 中 |
| DAG SVM | $K(K-1)/2$ | $K-1$ | 两类 | 无 | 中 |
| Weston-Watkins | $K$ | 1 | 全部 | 取决于数据 | 高 |
| Crammer-Singer | $K$ | 1 | 全部 | 取决于数据 | 高 |
8.5 Weston-Watkins SVM
这是将 SVM 推广到多分类的直接方法。为每个类别学习一个权重向量 $w_k$，优化目标为：
$$\begin{aligned} \min_{w,\xi} &\quad \frac{1}{2}\sum_{k=1}^{K} \|w_k\|^2 + C\sum_{i=1}^{N}\sum_{k \neq y_i} \xi_{ik} \\ \text{s.t.} &\quad w_{y_i} \cdot x_i - w_k \cdot x_i \geq 1 - \xi_{ik} \\ &\quad \xi_{ik} \geq 0, \quad \forall i, \forall k \neq y_i \end{aligned}$$
其思想是：对于每个样本 $x_i$，正确类别 $y_i$ 的得分应至少比其他任意类别 $k \neq y_i$ 的得分高 1。
9. 模型选择与超参数调优
9.1 SVM 的超参数
| 参数 | 含义 | 影响 |
|---|---|---|
| $C$ | 惩罚参数 | 大 → 过拟合，小 → 欠拟合 |
| $\gamma$（RBF） | 带宽 | 大 → 过拟合，小 → 欠拟合 |
| $d$（多项式核） | 多项式次数 | 大 → 决策边界更复杂 |
| $\varepsilon$（SVR） | 不敏感管道宽度 | 大 → 支持向量少，模型更平坦 |
| $\nu$（$\nu$-SVM/SVR） | 支持向量比例 | 直接控制模型复杂度 |
9.2 网格搜索与交叉验证
标准的调参策略是网格搜索 + k-fold 交叉验证。对于 RBF 核，典型的搜索范围：
- $C \in {2^{-5}, 2^{-3}, \ldots, 2^{15}}$
- $\gamma \in {2^{-15}, 2^{-13}, \ldots, 2^{3}}$
在 log 空间中等间距采样，因为 $C$ 和 $\gamma$ 的影响在乘法意义下是平滑的。
经验法则（Hsu et al., 2003）：
- 先用粗网格搜索确定大致的好的区域
- 在较好区域用细网格搜索精炼
- 两参数可以分开搜索：先固定 $\gamma$ 找一个好的 $C$，再反过来
9.3 特征缩放的重要性
SVM 对特征的尺度非常敏感。在使用 SVM 之前，必须对特征进行标准化或归一化。
以 RBF 核为例，核函数 $\exp(-\gamma|x-z|^2)$ 中的 Euclid 距离受特征尺度影响巨大：如果某个特征的取值范围是 [0, 1000]，另一个是 [0, 1]，那么在距离计算中第一个特征会完全主导。
推荐做法：
$$x_i^{(d)} \leftarrow \frac{x_i^{(d)} - \mu_d}{\sigma_d} \quad \text{(标准化)}$$
或
$$x_i^{(d)} \leftarrow \frac{x_i^{(d)} - \min_d}{\max_d - \min_d} \quad \text{(归一化)}$$
两者在大多数情况下效果相近。标准化对异常值更鲁棒。
10. SVM 的理论基础：统计学习理论
10.1 VC 维
定义 4（VC 维）：一个指示函数集（分类器集合）的 VC 维，是能被该函数集打散（shatter）的最大样本数。
所谓”打散”，就是对这 $h$ 个样本的所有 $2^h$ 种可能的标注方式，函数集中都存在某个函数与之对应。
SVM 的 VC 维上界（Vapnik, 1995）：对于最大间隔超平面分类器，如果所有训练样本都落在半径为 $R$ 的球内，则其 VC 维 $h$ 满足：
$$h \leq \min\left(\left\lfloor \frac{R^2}{\gamma^2} \right\rfloor, n\right) + 1$$
其中 $\gamma$ 是几何间隔，$n$ 是特征维数。
这个式子揭示了 SVM 的核心理论优势：**VC 维的上界不直接依赖于特征空间的维度 $n$，而是依赖于间隔 $\gamma$**。间隔越大，VC 维越小，泛化能力越好。这就是为什么 SVM 可以在高维乃至无限维空间中工作而不严重过拟合。
10.2 结构风险最小化
SVM 的目标函数 $\frac{1}{2}|w|^2$ 对应 VC 维最小化，$\sum \xi_i$ 对应经验风险。通过调节 $C$，SVM 在 VC 维和经验风险之间寻求平衡——这正是结构风险最小化（SRM）原则的具体实现。
对比经验风险最小化（ERM，如 MLE）容易过拟合，SRM 同时考虑模型复杂度和训练误差，从而保证了更好的泛化性能。
11. SVM 与其他分类器的关系
11.1 SVM vs 逻辑回归
| 维度 | SVM | 逻辑回归 |
|---|---|---|
| 优化目标 | 最大化 margin | 最大化似然 |
| 输出 | 硬判决（sign） | 概率（sigmoid） |
| 损失函数 | Hinge loss | Logistic loss（cross-entropy） |
| 稀疏性 | 稀疏解（仅支持向量） | 非稀疏（所有样本参与） |
| 核方法 | 直接支持（kernel trick） | 可通过 kernel logistic regression 引入 |
| 大数据 | 需要 SMO 优化 | SGD 直接可扩展 |
| 多分类 | 需要额外策略 | Softmax 回归天然做多分类 |
实践中，当需要概率输出时优先选择逻辑回归；当关注决策边界和小样本泛化能力时优先选择 SVM。
11.2 SVM vs 感知机
感知机是 SVM 的”雏形”：
- 感知机：寻找任意一个能分开数据的超平面
- SVM：寻找间隔最大的那个超平面
当数据线性可分时，感知机会收敛到某个可行解，但不唯一（依赖于初始化和样本顺序）；SVM 收敛到唯一的间隔最大化解（硬间隔情况下是唯一的，软间隔一般情况下也是唯一的）。
11.3 Platt Scaling
SVM 本身不输出概率，但可以通过 Platt Scaling 将 SVM 的输出转换为概率估计：
$$P(y=1 | x) = \frac{1}{1 + \exp(A f(x) + B)}$$
其中 $f(x)$ 是 SVM 的决策函数值，参数 $A, B$ 通过在训练集（或 hold-out 验证集）上最小化交叉熵损失来拟合。
12. 实战建议与常见问题
12.1 训练技巧
- 数据预处理：先标准化，再训练
- 调参顺序：先核函数选择（radial basis 一般为默认），再 $(C, \gamma)$ 网格搜索
- 样本不均衡：可以给不同类别设置不同的 $C$，或者使用类别权重
- 大规模数据：线性 SVM 配合 SGD 或 LIBLINEAR 可以高效处理百万级样本
- 内存限制：SMO 的内存占用为 $O(N^2)$（核矩阵），可以考虑使用 kernel approximation（如 Random Fourier Features）
12.2 LIBSVM 格式与参数
LIBSVM 是台湾大学林智仁团队开发的经典 SVM 库。其数据格式为：
<label> <index1>:<value1> <index2>:<value2> ... |
例如：
+1 1:0.5 2:0.3 3:-0.1 |
常用的参数组合（-s 指定求解器类型，-t 指定核函数类型）：
# C-SVC with RBF kernel |
13. 面试高频问答
Q1: SVM 为什么要最大化间隔？
A: 从两个角度回答：（1）泛化理论：根据 VC 维理论，最大化 margin 等价于最小化 VC 维上界，从而降低泛化误差。间隔越大，分类器对训练数据的微小扰动越不敏感。（2）几何直觉：margin 越大，分类边界越”鲁棒”，对未见样本的容错空间越大。可以把支持向量机看作是”寻找最宽的安全带”。
Q2: 硬间隔 SVM 对偶问题的推导过程是怎样的？
A: 原始问题是 $\min_{w,b} \frac{1}{2}|w|^2$ s.t. $y_i(w \cdot x_i+b) \geq 1$。构造 Lagrange 函数 $L = \frac{1}{2}|w|^2 - \sum \alpha_i[y_i(w \cdot x_i+b)-1]$，令对 $w,b$ 的偏导为 0 得 $w=\sum\alpha_i y_i x_i$ 和 $\sum\alpha_i y_i=0$。代入 $L$，利用等式约束消去线性项，得对偶问题 $\max_\alpha -\frac{1}{2}\sum_{i,j}\alpha_i\alpha_j y_i y_j (x_i\cdot x_j) + \sum\alpha_i$。由于强对偶成立，对偶问题的最优解与原始问题一致。
Q3: 为什么 SVM 对偶问题中样本只以内积形式出现？有什么好处？
A: 因为在推导对偶问题时，$w$ 被表示为 $\sum\alpha_i y_i x_i$，目标函数中出现的 $|w|^2 = \sum_{i,j}\alpha_i\alpha_j y_i y_j(x_i\cdot x_j)$ 就自然只依赖样本内积。好处：（1）可以直接应用核技巧，将内积替换为核函数 $K(x_i,x_j)$，隐式实现高维非线性变换；（2）问题的复杂度不再依赖于特征维数，只依赖于样本数；（3）支持向量的稀疏性使得预测时只需计算测试点与支持向量的核函数值。
Q4: 解释 $\alpha_i$ 取值的含义：$\alpha_i=0$, $0<\alpha_i<C$, $\alpha_i=C$ 分别对应什么情况？
A: 由 KKT 条件可以严格推导：
- $\alpha_i = 0$：互补松弛条件 $\alpha_i[y_i f(x_i)-1+\xi_i]=0$ 自动满足，由 $\mu_i = C - \alpha_i = C > 0$ 得 $\xi_i = 0$，代入原始约束得 $y_i f(x_i) \geq 1$。样本被正确分类且在间隔外，不是支持向量。
- $0 < \alpha_i < C$：此时 $\mu_i = C - \alpha_i > 0$，得 $\xi_i = 0$。同时 $\alpha_i > 0$ 强迫 $y_i f(x_i) - 1 + \xi_i = 0$，即 $y_i f(x_i) = 1$。样本恰好落在间隔边界上，是标准支持向量。
- $\alpha_i = C$：此时 $\mu_i = 0$，$\xi_i$ 可以为正。由 $\alpha_i > 0$ 得 $y_i f(x_i) = 1 - \xi_i \leq 1$。样本可能在间隔内（$0 < \xi_i < 1$）、在分类边界上（$\xi_i = 1$）或被错分（$\xi_i > 1$）。称为边界支持向量。
Q5: SMO 算法每次优化几个变量？为什么？
A: SMO 每次选择两个 Lagrange 乘子进行优化。原因是等式约束 $\sum\alpha_i y_i = 0$ 的存在——如果只优化一个变量，该约束无法维持（改变 $\alpha_i$ 后，$\sum\alpha_j y_j$ 会变成 $\alpha_i^{\text{new}} y_i - \alpha_i^{\text{old}} y_i$ 而非 0）。选两个变量就可以通过约束将其中一个表示为另一个的线性函数，将问题化为一元二次函数的极值问题，有闭式解。至于为什么不是三个或更多，是因为两个变量已有闭式解且每次迭代计算量最小。
Q6: RBF 核中的 $\gamma$ 参数过大或过小会产生什么影响？
A: $\gamma = 1/(2\sigma^2)$ 控制 RBF 核的”作用范围”。
- $\gamma$ 过大：$\exp(-\gamma|x-z|^2)$ 在距离很小的时候就衰减到接近 0，意味着一个样本只能影响其非常近邻的区域。直观后果是决策边界围绕每个单独的训练样本扭曲，模型严重过拟合，训练误差可达 0 但测试误差极高。
- $\gamma$ 过小：核函数值在很大距离范围内仍接近 1，所有样本彼此高度相似，决策边界趋于平滑甚至线性（当 $\gamma \to 0$ 时，RBF 核趋近于线性核）。模型欠拟合，偏差大。
- 可以用网格搜索 + 交叉验证来选择合适的 $\gamma$。
Q7: SVM 如何处理类别不平衡问题？
A: 有多种策略：
- 类别加权（最常用）：给不同类别设置不同的惩罚参数 $C_+$ 和 $C_-$，一般使 $C$ 与类别样本数成反比。例如正类有 100 个样本、负类有 1000 个样本，可设置 $C_+ = 10 C_-$。
- 重采样：对少数类过采样（SMOTE）或对多数类欠采样。
- 调整阈值：在预测时不使用 $f(x) \geq 0$ 判定为正类，二而是一个调整后的偏置 $b’$，使 $f(x) \geq b’$ 才判为正类。
- 使用 $\nu$-SVM：$\nu$ 参数可以更直观地控制支持向量比例。
14. 总结
支持向量机是机器学习中少有的能将几何直觉、优化理论和统计学习理论完美统一的算法。从硬间隔到软间隔，从线性到非线性（核技巧），从二分类到回归（SVR），SVM 形成了一个完整而优雅的理论体系。
关键要点回顾：
- 核心思想：最大化分类间隔 → 最宽的安全带 → 结构风险最小化
- 对偶问题：通过 Lagrange 对偶，将原始空间的复杂问题转化为只依赖内积的二次规划
- 核技巧：满足 Mercer 条件的正定核函数 → 隐式映射到高维空间 → 无需显式计算 $\phi(x)$
- SMO：分治策略将大 QP 分解为双变量闭式解的子问题，实现高效训练
- 泛化保证：VC 维上界由间隔而非特征维数决定，SVM 天然抵抗维度灾难
SVM 虽然在深度学习时代不再是 SOTA（state-of-the-art），但它严谨的数学基础和优美的理论结构使其仍然是理解机器学习核心概念的最佳入口之一。
本系列下一篇文章将深入探讨逻辑回归与最大熵模型，敬请期待。
