第七章：支持向量机

7.1 章节概述

支持向量机（Support Vector Machine，SVM）是一种基于间隔最大化原则的分类与回归学习方法，由Vapnik等人于1990年代提出，在文本分类、图像识别、生物信息学等领域取得了巨大成功。SVM的核心思想是通过在特征空间中寻找一个最大间隔的超平面，将不同类别的样本分隔开。间隔最大化不仅使分类边界更加清晰，还赋予了SVM优秀的泛化能力——即使在训练样本有限的情况下，SVM也能表现出良好的分类性能。

SVM的发展历程可以分为三个阶段：第一阶段是线性可分SVM（硬间隔SVM），处理严格线性可分的数据；第二阶段是线性SVM（软间隔SVM），允许一定的分类错误以处理近似线性可分的数据；第三阶段是非线性SVM，通过核函数将数据映射到高维特征空间，处理非线性的分类问题。这三个阶段构成了SVM完整的理论体系。

SVM之所以重要，是因为它具有坚实的统计学习理论支撑——结构风险最小化原则。SVM通过最大化间隔，实际上是在最小化VC维，从而获得更好的泛化性能。本章将系统介绍SVM的数学基础、算法推导和工程实现。

7.2 关键问题与研究动机

SVM要解决的核心问题是：如何在特征空间中找到一个最优的分类边界，使得两个类别之间的间隔最大化？这一问题的重要性在于，最大间隔的分类边界具有更好的鲁棒性——即使训练样本略有波动，分类结果也能保持稳定。

线性可分问题的挑战。 当数据线性可分时，理论上存在无穷多个可以将两类分开的超平面。例如在二维空间中，任意一条穿过两类样本"缝隙"的直线都能正确分类。这些不同的分类边界虽然都能使训练误差为零，但它们的泛化性能可能差异巨大。SVM通过间隔最大化准则，从无穷多个可行解中选出唯一的最优解。

非线性分类的挑战。 现实世界中的数据往往不是线性可分的，例如XOR问题就无法用任何线性边界正确分类。处理非线性问题的一种思路是直接在原始特征空间中寻找复杂的分类边界，但这容易导致过拟合。SVM的解决思路是：通过非线性变换将数据映射到高维特征空间，在高维空间中寻找线性分类边界。由于SVM只涉及高维空间中的内积运算，可以巧妙地避免显式计算高维映射，这就是"核技巧"。

计算效率的挑战。 SVM的优化问题是一个二次规划问题，直接求解的复杂度为 $O(n^3)$，其中 $n$ 是训练样本数。对于大规模数据集，直接求解是不可行的。SMO（Sequential Minimal Optimization）算法通过将大的QP问题分解为一系列小的QP子问题，实现了SVM的高效训练，使得SVM能够处理百万级样本的大规模数据。

7.3 主要公式与推导

7.3.1 线性可分支持向量机

函数间隔与几何间隔。 对于给定的训练数据集 $T = \{(\mathbf{x}_1, y_1), (\mathbf{x}_2, y_2), \ldots, (\mathbf{x}_N, y_N)\}$，其中 $\mathbf{x}_i \in \mathbb{R}^n$，$y_i \in \{-1, +1\}$，超平面 $f(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b = 0$ 对样本 $(\mathbf{x}_i, y_i)$ 的函数间隔定义为：

\[\hat{\gamma}_i = y_i(\mathbf{w} \cdot \mathbf{x}_i + b)\]

几何间隔是函数间隔除以 $\|\mathbf{w}\|$：

\[\gamma_i = \frac{y_i(\mathbf{w} \cdot \mathbf{x}_i + b)}{\|\mathbf{w}\|}\]

几何间隔具有旋转不变性，当 $\|\mathbf{w}\|$ 改变时，几何间隔保持不变。

间隔最大化目标。 SVM的几何间隔定义为所有样本几何间隔的最小值：

\[\gamma = \min_{i=1,2,\ldots,N} \gamma_i\]

间隔最大化的优化问题为：

\[\max_{\mathbf{w}, b} \quad & \gamma \\\\ \text{s.t.} \quad & \frac{y_i(\mathbf{w} \cdot \mathbf{x}_i + b)}{\|\mathbf{w}\|} \geq \gamma, \quad i = 1, 2, \ldots, N\]

令 $\gamma = 1/\|\mathbf{w}\|$，上述问题等价于：

\[\min_{\mathbf{w}, b} \quad & \frac{1}{2}\|\mathbf{w}\|^2 \\\\ \text{s.t.} \quad & y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1, \quad i = 1, 2, \ldots, N\]

这是一个凸二次规划问题，存在唯一全局最优解。

拉格朗日对偶。 通过拉格朗日乘子法引入拉格朗日乘子 $\boldsymbol{\alpha} = (alpha_1, \alpha_2, \ldots, \alpha_N)^T \geq 0$，拉格朗日函数为：

\[\mathcal{L}(\mathbf{w}, b, \boldsymbol{\alpha}) = \frac{1}{2}\|\mathbf{w}\|^2 - \sum_{i=1}^{N} \alpha_i y_i(\mathbf{w} \cdot \mathbf{x}_i + b) + \sum_{i=1}^{N} \alpha_i\]

对 $\mathbf{w}$ 和 $b$ 求偏导并令其为零：

\[\frac{\partial \mathcal{L}}{\partial \mathbf{w}} = \mathbf{w} - \sum_{i=1}^{N} \alpha_i y_i \mathbf{x}_i = 0 \Rightarrow \mathbf{w} = \sum_{i=1}^{N} \alpha_i y_i \mathbf{x}_i\]

\[\frac{\partial \mathcal{L}}{\partial b} = -\sum_{i=1}^{N} \alpha_i y_i = 0 \Rightarrow \sum_{i=1}^{N} \alpha_i y_i = 0\]

代入原函数，得到对偶问题：

\[\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 \cdot \mathbf{x}_j) \\\\ \text{s.t.} \quad & \sum_{i=1}^{N} \alpha_i y_i = 0 \\\\ \quad & \alpha_i \geq 0, \quad i = 1, 2, \ldots, N\]

设 $\boldsymbol{\alpha}^* = (\alpha_1^*, \alpha_2^*, \ldots, \alpha_N^*)^T$ 是对偶问题的最优解，则：

\[\mathbf{w}^* = \sum_{i=1}^{N} \alpha_i^* y_i \mathbf{x}_i\]

$b^*$ 可以通过任意支持向量（$\alpha_i^* > 0$ 的样本）求得：

\[b^* = y_j - \sum_{i=1}^{N} \alpha_i^* y_i (\mathbf{x}_i \cdot \mathbf{x}_j)\]

分类决策函数为：

\[f(\mathbf{x}) = \text{sign}(\mathbf{w}^* \cdot \mathbf{x} + b^*) = \text{sign}\left(\sum_{i=1}^{N} \alpha_i^* y_i (\mathbf{x}_i \cdot \mathbf{x}) + b^*\right)\]

KKT条件。 支持向量机解的KKT条件为：

\[\alpha_i^* \geq 0\]

\[y_i(\mathbf{w}^* \cdot \mathbf{x}_i + b^*) - 1 \geq 0\]

\[\alpha_i^*(y_i(\mathbf{w}^* \cdot \mathbf{x}_i + b^*) - 1) = 0\]

第三个条件表明：只有 $\alpha_i^* > 0$ 的样本（支持向量）对 $\mathbf{w}^*$ 有贡献，非支持向量的样本对分类边界没有影响。

7.3.2 线性支持向量机（软间隔）

软间隔SVM允许部分样本不满足约束 $y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1$，引入松弛变量 $\xi_i \geq 0$，约束变为：

\[y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i\]

优化目标中加入惩罚项：

\[\min_{\mathbf{w}, b, \boldsymbol{\xi}} \quad & \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^{N} \xi_i \\\\ \text{s.t.} \quad & y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1 - \xi_i, \quad i = 1, 2, \ldots, N \\\\ \quad & \xi_i \geq 0, \quad i = 1, 2, \ldots, N\]

其中 $C > 0$ 是惩罚参数，$C$ 越大对错误的惩罚越重。软间隔SVM的拉格朗日对偶问题与硬间隔类似，只是 $\alpha_i$ 的上界变为 $C$：

\[\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 \cdot \mathbf{x}_j) \\\\ \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\]

7.3.3 非线性支持向量机与核函数

核技巧。 核技巧的基本思想是：找一个非线性映射 $\phi(\mathbf{x})$ 将原始特征空间 $\mathbb{R}^n$ 映射到高维特征空间 $\mathcal{H}$，使得在 $\mathcal{H}$ 中可以线性分割。核函数的定义为：

\[K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x}) \cdot \phi(\mathbf{z})\]

核函数的价值在于：我们不需要知道 $\phi(\cdot)$ 的具体形式，只需要计算 $K(\mathbf{x}, \mathbf{z})$ 就能完成所有运算。

常用核函数。

多项式核函数：

\[K(\mathbf{x}, \mathbf{z}) = (\gamma \mathbf{x} \cdot \mathbf{z} + r)^d, \quad \gamma > 0, r \geq 0\]

高斯径向基函数（RBF核）：

\[K(\mathbf{x}, \mathbf{z}) = \exp\left(-\frac{\|\mathbf{x} - \mathbf{z}\|^2}{2\sigma^2}\right)\]

字符串核函数：

\[K_{\text{string}}(s, t) = \sum_{n=1}^{\infty} \lambda_n \sum_{i:|u|=n} [u \in s][u \in t]\]

非线性SVM的对偶问题。 将内积 $\mathbf{x}_i \cdot \mathbf{x}_j$ 替换为核函数 $K(\mathbf{x}_i, \mathbf{x}_j)$，得到非线性SVM的分类决策函数：

\[f(\mathbf{x}) = \text{sign}\left(\sum_{i=1}^{N} \alpha_i^* y_i K(\mathbf{x}_i, \mathbf{x}) + b^*\right)\]

7.3.4 SMO算法

SMO（Sequential Minimal Optimization）是SVM的高效训练算法。其核心思想是将大的QP问题分解为一系列只有两个变量的子问题。

对于两个变量 $\alpha_1$ 和 $\alpha_2$，约束 $\sum_{i=1}^{N} \alpha_i y_i = 0$ 可以写成：

\[\alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^{N} \alpha_i y_i = \zeta\]

由此解得 $\alpha_1$ 和 $\alpha_2$ 的关系，代入目标函数得到关于 $\alpha_2$ 的二次函数。SMO的步骤是：首先选择两个变量 $\alpha_1$ 和 $\alpha_2$（通常使用启发式方法选择违反KKT条件最严重的样本），然后固定其他变量，求解关于 $\alpha_1$ 和 $\alpha_2$ 的优化问题。这个过程迭代进行，直到所有变量都满足KKT条件。

7.3.5 支持向量回归

支持向量回归（Support Vector Regression，SVR）将SVM的思想应用于回归问题。SVR假设模型与目标之间的偏差小于 $\varepsilon$ 是可以接受的，引入 $\varepsilon$-不敏感损失：

\[L_\varepsilon(f(\mathbf{x}), y) = \max(0, |f(\mathbf{x}) - y| - \varepsilon)\]

SVR的优化问题为：

\[\min_{\mathbf{w}, b} \quad & \frac{1}{2}\|\mathbf{w}\|^2 + C \sum_{i=1}^{N} L_\varepsilon(f(\mathbf{x}_i), y_i) \\\\ \text{s.t.} \quad & -\varepsilon - \xi_i \leq y_i - (\mathbf{w} \cdot \mathbf{x}_i + b) \leq \varepsilon + \hat{\xi}_i\]

其中 $\xi_i, \hat{\xi}_i \geq 0$ 是松弛变量。SVR的解同样具有稀疏性——只有落在 $\varepsilon$-管道外部的样本（支持向量）对模型有贡献。

7.4 算法与建模方法

线性可分SVM建模。 第一步确定模型形式为超平面 $f(\mathbf{x}) = \mathbf{w} \cdot \mathbf{x} + b$；第二步定义间隔（几何间隔 $2/\|\mathbf{w}\|$）；第三步建立优化问题 $\min_{\mathbf{w},b} \frac{1}{2}\|\mathbf{w}\|^2$ s。t。 $y_i(\mathbf{w}\cdot\mathbf{x}_i+b) \geq 1$；第四步求解拉格朗日对偶问题得到 $\boldsymbol{\alpha}^*$；第五步计算 $\mathbf{w}^* = \sum_i \alpha_i^* y_i \mathbf{x}_i$，由支持向量确定 $b^*$。

软间隔SVM建模。 与线性可分SVM类似，但引入松弛变量 $\xi_i$ 和惩罚参数 $C$，约束变为 $y_i(\mathbf{w}\cdot\mathbf{x}_i+b) \geq 1 - \xi_i$。参数 $C$ 的选择对模型性能影响很大：$C$ 过大容易过拟合，$C$ 过小容易欠拟合。通常使用交叉验证选择 $C$。

核函数选择。 RBF核是最常用的核函数，因为它在各种数据集上都有较好的性能。当特征维度较高而样本数较少时，可以考虑线性核。当需要明确特征交互时，可以考虑多项式核。核函数的选择本质上决定了特征空间的结构，需要根据具体问题进行尝试。

7.5 主要结论

第一，间隔最大化是SVM的核心原则。几何间隔最大化使SVM具有更好的泛化性能，支持向量的稀疏性使SVM具有良好的计算效率。

第二，核技巧使SVM能够处理非线性问题。通过将数据映射到高维特征空间，SVM可以在高维空间中寻找线性分类边界，而核函数的使用避免了显式计算高维映射。

第三，SMO算法使SVM能够处理大规模数据。SMO通过分解策略将大的QP问题分解为小的QP子问题，实现了高效的SVM训练。

第四，SVM的理论基础是结构风险最小化。SVM通过最大化间隔控制了模型的VC维，从而获得更好的泛化性能。

7.6 挑战与开放问题

参数选择问题。 SVM的性能高度依赖于超参数的选择（如 $C$、核函数参数 $\sigma$ 等）。网格搜索和交叉验证是常用的参数选择方法，但计算成本较高。贝叶斯优化等自动调参方法可以提高参数选择效率。

大规模数据处理。 虽然SMO算法提高了SVM的训练效率，但对于真正大规模的数据集（如互联网广告点击预测），随机梯度下降等在线学习方法仍然是更实际的选择。

多分类问题。 SVM本来是二分类器，处理多分类问题需要采用一对一或一对多的策略。一对一策略需要训练 $K(K-1)/2$ 个分类器，计算成本较高；一对多策略需要训练 $K$ 个分类器，但存在类别不平衡问题。

7.7 个人思考与批判性分析

支持向量机是机器学习领域最具影响力的算法之一。Vapnik等人的工作将统计学习理论、凸优化和核方法完美结合，创造了一个既有坚实理论基础又有卓越实用性能的算法。

本章最有价值的内容是对SVM从线性到非线性、从硬间隔到软间隔的完整推导过程。这种循序渐进的教学设计使读者能够清晰地理解每个步骤的动机和逻辑。特别是对核技巧的介绍，揭示了SVM处理非线性问题的本质。

然而，本章的讲解也存在一些不足。首先，对于SVM收敛性的数学证明讲解相对简略，Novikoff定理的证明没有给出。其次，对于SVM与感知机、逻辑斯谛回归的关系讨论不够深入。此外，$\varepsilon$-SVR和 $\nu$-SVM等变体的介绍也比较简略。

总体而言，本章系统全面地介绍了SVM的核心内容，为读者深入学习和应用SVM奠定了坚实基础。

公式汇总表

编号	公式名称	公式形式	说明	类型
(7.1)	函数间隔	$\hat{\gamma}_i = y_i(\mathbf{w} \cdot \mathbf{x}_i + b)$	超平面对样本的函数间隔	定义
(7.2)	几何间隔	$\gamma_i = \frac{y_i(\mathbf{w} \cdot \mathbf{x}_i + b)}{\\|\mathbf{w}\\|}$	几何间隔具有旋转不变性	公式
(7.3)	间隔最大化	$\min_{\mathbf{w},b} \frac{1}{2}\\|\mathbf{w}\\|^2$ s。t。 $y_i(\mathbf{w}\cdot\mathbf{x}_i+b) \geq 1$	线性可分SVM优化问题	目标
(7.4)	对偶问题	$\max_{\boldsymbol{\alpha}} \sum\alpha_i - \frac{1}{2}\sum\alpha_i\alpha_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j)$	SVM拉格朗日对偶	公式
(7.5)	w解	$\mathbf{w}^* = \sum_{i=1}^{N} \alpha_i^* y_i \mathbf{x}_i$	w由支持向量线性组合	公式
(7.6)	KKT条件	$\alpha_i^(y_i(\mathbf{w}^ \cdot \mathbf{x}_i + b^*) - 1) = 0$	支持向量条件	条件
(7.7)	软间隔目标	$\min \frac{1}{2}\\|\mathbf{w}\\|^2 + C\sum\xi_i$	线性SVM（软间隔）优化目标	目标
(7.8)	软间隔对偶	$0 \leq \alpha_i \leq C$	软间隔SVM对偶约束	约束
(7.9)	核函数定义	$K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x}) \cdot \phi(\mathbf{z})$	核技巧基本定义	定义
(7.10)	RBF核	$K(\mathbf{x}, \mathbf{z}) = \exp(-\\|\mathbf{x}-\mathbf{z}\\|^2/2\sigma^2)$	高斯径向基函数核	核函数
(7.11)	多项式核	$K(\mathbf{x}, \mathbf{z}) = (\gamma \mathbf{x} \cdot \mathbf{z} + r)^d$	多项式核函数	核函数
(7.12)	非线性决策	$f(\mathbf{x}) = \text{sign}(\sum_i \alpha_i^* y_i K(\mathbf{x}_i, \mathbf{x}) + b^*)$	非线性SVM分类决策函数	公式
(7.13)	SVR损失	$L_\varepsilon(f(\mathbf{x}), y) = \max(0,	f(\mathbf{x}) - y	- \varepsilon)$
(7.14)	SVR目标	$\min \frac{1}{2}\\|\mathbf{w}\\|^2 + C\sum L_\varepsilon(f(\mathbf{x}_i), y_i)$	支持向量回归优化目标	目标

编号	公式名称	公式形式	说明	类型
(7.1)	函数间隔	\(\hat{\gamma}_i = y_i(\mathbf{w} \cdot \mathbf{x}_i + b)\)	超平面对样本的函数间隔	定义
(7.2)	几何间隔	\(\gamma_i = \frac{y_i(\mathbf{w} \cdot \mathbf{x}_i + b)}{\\|\mathbf{w}\\|}\)	几何间隔具有旋转不变性	公式
(7.3)	间隔最大化	\(\min_{\mathbf{w},b} \frac{1}{2}\\|\mathbf{w}\\|^2\) s。t。 \(y_i(\mathbf{w}\cdot\mathbf{x}_i+b) \geq 1\)	线性可分SVM优化问题	目标
(7.4)	对偶问题	\(\max_{\boldsymbol{\alpha}} \sum\alpha_i - \frac{1}{2}\sum\alpha_i\alpha_j y_i y_j (\mathbf{x}_i\cdot\mathbf{x}_j)\)	SVM拉格朗日对偶	公式
(7.5)	w解	\(\mathbf{w}^* = \sum_{i=1}^{N} \alpha_i^* y_i \mathbf{x}_i\)	w由支持向量线性组合	公式
(7.6)	KKT条件	\(\alpha_i^(y_i(\mathbf{w}^ \cdot \mathbf{x}_i + b^*) - 1) = 0\)	支持向量条件	条件
(7.7)	软间隔目标	\(\min \frac{1}{2}\\|\mathbf{w}\\|^2 + C\sum\xi_i\)	线性SVM（软间隔）优化目标	目标
(7.8)	软间隔对偶	\(0 \leq \alpha_i \leq C\)	软间隔SVM对偶约束	约束
(7.9)	核函数定义	\(K(\mathbf{x}, \mathbf{z}) = \phi(\mathbf{x}) \cdot \phi(\mathbf{z})\)	核技巧基本定义	定义
(7.10)	RBF核	\(K(\mathbf{x}, \mathbf{z}) = \exp(-\\|\mathbf{x}-\mathbf{z}\\|^2/2\sigma^2)\)	高斯径向基函数核	核函数
(7.11)	多项式核	\(K(\mathbf{x}, \mathbf{z}) = (\gamma \mathbf{x} \cdot \mathbf{z} + r)^d\)	多项式核函数	核函数
(7.12)	非线性决策	\(f(\mathbf{x}) = \text{sign}(\sum_i \alpha_i^* y_i K(\mathbf{x}_i, \mathbf{x}) + b^*)\)	非线性SVM分类决策函数	公式
(7.13)	SVR损失	$L_\varepsilon(f(\mathbf{x}), y) = \max(0,	f(\mathbf{x}) - y	- \varepsilon)$
(7.14)	SVR目标	\(\min \frac{1}{2}\\|\mathbf{w}\\|^2 + C\sum L_\varepsilon(f(\mathbf{x}_i), y_i)\)	支持向量回归优化目标	目标