Chapter 8 支持向量机
一、最大间隔分类器
疾旋鼬在草地上看到红色和蓝色两种花混杂在一起，想用一条直线把它们分开。能分开的直线有很多条——哪条最好？
想象在两种花之间修一条路。路越宽，两边的花离路越远，新花就越不容易被分错。
SVM 的核心思想：找到使得间隔 (margin) 最大的分界线。
问题设定
给定训练集 \(\{(x^{(i)}, y^{(i)})\}_{i=1}^m\)，\(x \in \mathbb{R}^d\)，\(y \in \{-1, +1\}\)。
寻找超平面 \(w^T x + b = 0\) 将两类分开。对每个样本，要求：
这只是可行性问题——满足条件的超平面一般有无穷多个。
几何间隔
样本 \((x^{(i)}, y^{(i)})\) 到超平面的距离可以用函数间隔来度量：
但函数间隔可以被 \(w, b\) 成倍缩放而改变（例如 \(w \to 2w, b \to 2b\)，函数间隔翻倍但超平面不变）。规范化后得到几何间隔：
间隔 (margin)：所有样本中几何间隔的最小值：
最大间隔的优化问题
等价于（取倒数，平方，最小化）：
这是一个凸二次规划 (QP) 问题——目标函数是凸函数（\(\|w\|^2\) 是凸的），可行域是凸集（线性不等式的交集）。
约束中的 "1" 是一个任意的尺度选择。由于函数间隔可以缩放，我们总可以找到合适的 \(w, b\) 使得最近的样本满足 \(y^{(i)}(w^T x^{(i)} + b) = 1\)。
支持向量
使 \(y^{(i)}(w^T x^{(i)} + b) = 1\) 成立的样本称为支持向量 (support vector)——它们是距超平面最近的点。
最终模型仅与支持向量有关——其他样本对决策边界没有影响。SVM 因此而得名。
二、约束优化与对偶理论
拉格朗日函数
对一般约束优化问题：
拉格朗日函数：
其中 \(\lambda_i \geq 0\) 是不等式约束的乘子，\(\nu_i\) 是等式约束的乘子。
对偶函数与对偶问题
对偶函数：\(g(\lambda, \nu) = \inf_x \mathcal{L}(x, \lambda, \nu)\)
对偶函数是原始问题最优值的下界：\(g(\lambda, \nu) \leq p^*\)（弱对偶性）。
对偶问题：\(\max_{\lambda \geq 0, \nu} g(\lambda, \nu)\)
强对偶性：若原始问题是凸的且满足 Slater 条件（存在严格可行点），则 \(d^* = p^*\)。
KKT 条件
定理：若 \(x^*\) 是正则局部最小点，则存在乘子 \(\lambda^*, \nu^*\) 使得：
- 平稳性 (Stationarity)：\(\nabla_x \mathcal{L}(x^*, \lambda^*, \nu^*) = 0\)
- 原始可行性 (Primal Feasibility)：\(c_i(x^*) \leq 0\)（\(i \in \mathcal{I}\)），\(c_i(x^*) = 0\)（\(i \in \mathcal{E}\)）
- 对偶可行性 (Dual Feasibility)：\(\lambda_i^* \geq 0\)（\(i \in \mathcal{I}\)）
- 互补松弛 (Complementary Slackness)：\(\lambda_i^* c_i(x^*) = 0\)（\(i \in \mathcal{I}\)）
直觉理解：在最优点 \(x^*\)，\(-\nabla f(x^*)\) 与 \(\nabla c_i(x^*)\) 平行且同方向。若约束不紧（\(c_i(x^*) < 0\)），则乘子为零。
为什么 \(\lambda^* \geq 0\)？ 考虑不等式约束 \(c_i(x) \leq 0\)。在最优点，\(-\nabla f(x^*)\) 指向可行域内部，而 \(\nabla c_i(x^*)\) 指向可行域外部。两者平行且同方向，故 \(\lambda_i^* \geq 0\)。
凸问题中，KKT 条件是充分必要条件。
KKT 条件证明（简化版）
必要性：设 \(x^*\) 是最优解。由约束优化的一阶必要条件（Fritz John 条件），存在不全为零的 \(\mu_0^*, \lambda_i^*\) 使得：
若 \(\mu_0^* = 0\)，则约束的梯度线性相关（不满足正则性条件），矛盾。故 \(\mu_0^* > 0\)，两边除以 \(\mu_0^*\) 得平稳性。\(\square\)
三、SVM 对偶问题推导
第一步：构造拉格朗日函数
引入乘子 \(\alpha_i \geq 0\)（每个样本对应一个约束）：
注意约束是 \(y^{(i)}(w^T x^{(i)} + b) - 1 \geq 0\)，即 \(-[y^{(i)}(w^T x^{(i)} + b) - 1] \leq 0\)。
第二步：令偏导为零
对 \(w\) 求导：
对 \(b\) 求导：
第三步：代入消去 \(w, b\)
将 \(w = \sum_i \alpha_i y^{(i)} x^{(i)}\) 代入 \(\mathcal{L}\)：
对偶问题
关键观察：对偶问题中，数据只以内积 \(x^{(i)T} x^{(j)}\) 的形式出现——这为核技巧埋下伏笔。
KKT 互补松弛的应用
- \(\alpha_i = 0\)：非支持向量，对模型无贡献
- \(\alpha_i > 0\)：支持向量，\(y^{(i)}(w^T x^{(i)} + b) = 1\)
支持向量是训练集中"最难"的样本——它们距决策边界最近。
求解 \(b\)
对任意支持向量 \((x^{(s)}, y^{(s)})\)（\(\alpha_s > 0\)）：
为提高鲁棒性，通常使用所有支持向量求解的平均值：
四、SMO 算法
SMO (Sequential Minimum Optimization) 是求解 SVM 对偶问题的高效算法 [Platt, 1998]。
基本思路
每次选择两个变量 \(\alpha_i, \alpha_j\)，固定其他参数，求解对偶问题更新 \(\alpha_i, \alpha_j\)。
为什么选两个？
由约束 \(\sum_k \alpha_k y^{(k)} = 0\)，若只选一个变量，它被其他变量完全确定，没有优化空间。选两个变量时，可以用一个表示另一个。
求解过程
固定 \(\alpha_i, \alpha_j\) 以外的参数，令 \(\alpha_i y^{(i)} + \alpha_j y^{(j)} = -\sum_{k \neq i,j} \alpha_k y^{(k)} = \zeta\)（常数）。
则 \(\alpha_j = \frac{\zeta - \alpha_i y^{(i)}}{y^{(j)}}\)。代入对偶问题（关于 \(\alpha_i\) 的二次函数），求导令其为零，得闭式解。
再根据约束 \(0 \leq \alpha_i \leq C\)（软间隔时）进行裁剪。
偏差项 \(b\) 的更新
每步更新 \(\alpha_i, \alpha_j\) 后，根据 KKT 条件更新 \(b\)。
五、核函数
特征空间映射
若原始空间线性不可分，将样本映射到更高维的特征空间：
在特征空间中，数据可能线性可分。
定理：如果原始空间是有限维（属性数有限），那么一定存在一个高维特征空间使样本可分。
核技巧
对偶问题中数据只以内积形式出现。定义核函数：
绕过显式映射——直接计算内积，无需知道 \(\phi\) 的具体形式。
例子：设 \(x = (x_1, x_2)\)，\(\phi(x) = (x_1^2, x_2^2, \sqrt{2}x_1 x_2)\)。
即 \(\kappa(x, z) = (x^T z)^2\) 对应一个 3 维特征空间的内积，但直接计算只需要 2 维的运算。
Mercer 定理
定理：对称函数 \(\kappa(x, z)\) 可作为核函数，当且仅当对任意有限样本集，其对应的核矩阵 \(K_{ij} = \kappa(x^{(i)}, x^{(j)})\) 是半正定的。
常用核函数
| 核函数 | 公式 | 特点 |
|---|---|---|
| 线性核 | \(\kappa(x, z) = x^T z\) | 最简单，文本数据常用 |
| 多项式核 | \(\kappa(x, z) = (x^T z + c)^d\) | 有限维特征空间 |
| 高斯核 (RBF) | \(\kappa(x, z) = \exp(-\frac{\|x-z\|^2}{2\sigma^2})\) | 无穷维特征空间 |
| Sigmoid 核 | \(\kappa(x, z) = \tanh(\beta x^T z + \theta)\) | 类似神经网络 |
核函数的组合：若 \(\kappa_1\) 和 \(\kappa_2\) 是核函数，则对任意正数 \(a_1, a_2\) 和任意函数 \(g(x)\)： - \(a_1 \kappa_1 + a_2 \kappa_2\) 是核函数 - \(g(x) \kappa_1(x, z) g(z)\) 是核函数 - \(\kappa_1(x, z) \cdot \kappa_2(x, z)\) 是核函数
"核函数选择"是决定 SVM 性能的关键。基本经验：文本数据常用线性核，情况不明时先尝试高斯核。
核函数的直觉
高斯核 \(\kappa(x, z) = \exp(-\frac{\|x-z\|^2}{2\sigma^2})\) 的直觉： - 当 \(x = z\) 时，\(\kappa = 1\)（最大相似度） - 当 \(\|x - z\| \to \infty\) 时，\(\kappa \to 0\)（无相似度） - \(\sigma\) 控制"邻域大小"：\(\sigma\) 越大，越远的点也被认为"相似"
任何核函数隐式定义了一个再生核希尔伯特空间 (RKHS)。
六、软间隔
动机
现实中数据很难完美线性可分。即使在特征空间中，也可能存在噪声或异常值。
即便貌似线性可分，也很难断定是否是因过拟合造成的。
优化目标
引入松弛变量 \(\xi_i \geq 0\)：
\(C > 0\) 是惩罚参数：\(C\) 越大，对误分类的惩罚越重。
- \(\xi_i = 0\)：样本被正确分类且在间隔带外
- \(0 < \xi_i < 1\)：样本被正确分类但在间隔带内
- \(\xi_i \geq 1\)：样本被误分类
替代损失
原始的 \(0/1\) 损失函数 \(\ell_{0/1}(z) = \mathbb{I}(z < 0)\) 非凸、非连续，不易优化。用替代损失 (surrogate loss) 函数：
| 损失函数 | 公式 | 特点 |
|---|---|---|
| hinge 损失 | \(\max(0, 1-z)\) | SVM 使用，保持稀疏性 |
| 指数损失 | \(e^{-z}\) | AdaBoost 使用 |
| 对率损失 | \(\log(1+e^{-z})\) | 对率回归使用 |
替代损失是 \(0/1\) 损失的上界。采用替代损失后，SVM 仍保持解的稀疏性。
软间隔的对偶问题
与硬间隔的区别：多了上界约束 \(\alpha_i \leq C\)。
正则化视角
SVM 可以写为正则化框架：
- 第一项是经验风险（hinge 损失）
- 第二项是结构风险（正则化项）
- \(\lambda\) 控制两者权衡
七、支持向量回归 (SVR)
基本思路：允许模型输出与实际值间存在 \(2\epsilon\) 的偏差。
\(\epsilon\)-不敏感损失：落入 \(2\epsilon\) 间隔带的样本不计算损失。
八、核方法与表示定理
表示定理
定理：对任意单调递增函数 \(\Omega\) 和任意非负损失函数 \(\ell\)，优化问题
的解总可写为核函数的线性组合：
核化方法
基于表示定理，很多线性模型可"核化"：
- 核化 LDA (KLDA)：在特征空间中做线性判别分析
- 核岭回归 (KRR)
岭回归的对偶
目标：\(\min_w \frac{1}{2}\|Y - X^T w\|^2 + \frac{\alpha}{2}\|w\|^2\)
闭式解：\(w^* = (XX^T + \alpha I)^{-1}XY\)
Woodbury 恒等式：\((A + UCV)^{-1} = A^{-1} - A^{-1}U(C^{-1} + VA^{-1}U)^{-1}VA^{-1}\)
对偶形式：\(w^* = X(X^T X + \alpha I)^{-1}Y\)
核化后：\(f(x) = \sum_i \alpha_i \kappa(x^{(i)}, x)\)，其中 \(\alpha = (K + \alpha I)^{-1}Y\)。
SVM 与统计学习简史
| 年代 | 事件 |
|---|---|
| 1963 | Vapnik 提出支持向量概念 |
| 1968 | VC 维 [Vapnik & Chervonenkis] |
| 1974 | 结构风险最小化原则 |
| 1995 | SVM 论文发表 + 《The Nature of Statistical Learning》出版 |
| 1998 | SVM 在文本分类上取得巨大成功 |
| 1998 | 《Statistical Learning Theory》出版 |
Vladimir Vapnik (1936-)："Nothing is more practical than a good theory."
George E. P. Box (1919-2013)："All models are wrong, but some are useful."
2026.06