支持向量机

线性可分支持向量机与硬间隔最大化

支持向量机（Support Vector Machine, SVM）是统计学习中最优美的模型之一。它的核心思想极其简洁：在所有能正确分类的超平面中，选择间隔最大的那一个。这一节我们从线性可分的最简单情形出发，一步步建立硬间隔最大化的完整理论——从问题的提出，到对偶形式的推导，再到解的存在唯一性证明。

线性可分支持向量机

线性可分性的严格定义

定义（线性可分性） 给定训练数据集 $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\}$，$i = 1, 2, \ldots, N$。若存在某个超平面 $S$：

能将数据集的正实例点和负实例点完全正确地划分到超平面的两侧，即对所有 $y_i = +1$ 的实例有 $\mathbf{w} \cdot \mathbf{x}_i + b > 0$，对所有 $y_i = -1$ 的实例有 $\mathbf{w} \cdot \mathbf{x}_i + b < 0$，则称数据集 $T$ 为线性可分的（linearly separable）。

等价地，线性可分意味着存在 $(\mathbf{w}, b)$ 使得：

直觉上，线性可分就是说在特征空间里能找到一张"平板"（超平面），把两类点完全隔开，没有任何一个点被错分。

超平面与决策函数

超平面 $\mathbf{w} \cdot \mathbf{x} + b = 0$ 由法向量 $\mathbf{w} \in \mathbb{R}^n$ 和截距 $b \in \mathbb{R}$ 唯一确定。法向量 $\mathbf{w}$ 指向超平面的"正侧"，垂直于超平面本身；$b$ 控制超平面离原点的偏移量——原点到超平面的有符号距离为 $b / \|\mathbf{w}\|$。

给定超平面后，对任意新输入 $\mathbf{x}$，分类决策函数为：

几何意义很清晰：看新点落在超平面的哪一侧，就归为哪一类。

线性可分支持向量机的定义

对于线性可分数据，能正确分类的超平面有无穷多个（感知机的收敛解就取决于初始化）。线性可分支持向量机要在这无穷多个解中找到一个"最优"的——间隔最大的那个。

定义（线性可分支持向量机） 给定线性可分训练数据集 $T$，通过间隔最大化学习得到的分离超平面为 $\mathbf{w}^* \cdot \mathbf{x} + b^* = 0$，以及对应的分类决策函数 $f(\mathbf{x}) = \text{sign}(\mathbf{w}^* \cdot \mathbf{x} + b^*)$，称为线性可分支持向量机。

函数间隔与几何间隔

要量化"间隔"到底有多大，我们需要精确定义距离的度量方式。

函数间隔

定义（函数间隔） 对于给定超平面 $(\mathbf{w}, b)$，定义超平面关于样本点 $(\mathbf{x}_i, y_i)$ 的函数间隔为：

定义超平面关于训练数据集 $T$ 的函数间隔为所有样本点函数间隔的最小值：

函数间隔的符号反映分类的正确性：$\hat{\gamma}_i > 0$ 时分类正确，$\hat{\gamma}_i < 0$ 时分类错误。其绝对值可以相对地表示点距超平面的远近——值越大，"确信度"越高。

函数间隔的缺陷：尺度不变性

函数间隔有一个根本缺陷：不具有尺度不变性。将 $\mathbf{w}$ 和 $b$ 同时乘以正常数 $\lambda$，超平面本身不变，但函数间隔变成了原来的 $\lambda$ 倍：

仅仅通过放大 $\mathbf{w}$ 的模长，就能让函数间隔任意大——但超平面和它与数据点的实际距离根本没变。因此，函数间隔不能直接作为最大化的目标。

几何间隔

定义（几何间隔） 对于给定超平面 $(\mathbf{w}, b)$，定义超平面关于样本点 $(\mathbf{x}_i, y_i)$ 的几何间隔为：

定义超平面关于训练数据集 $T$ 的几何间隔为 $\gamma = \min_i \gamma_i$。

几何间隔就是点到超平面的有符号欧氏距离。它对 $(\mathbf{w}, b)$ 的等比例缩放不敏感：

两种间隔的关系

当 $\|\mathbf{w}\| = 1$ 时两者相等。函数间隔是"未归一化的距离"，几何间隔才是"真正的距离"。

间隔最大化

最大间隔分离超平面的直觉

为什么要最大化间隔？

1. 鲁棒性：间隔越大，决策边界离最近的训练点越远，对测试数据的扰动越不敏感。
2. 泛化能力：VC 维理论表明，间隔越大，分类器的 VC 维越低，泛化误差上界越紧。

优化问题的逐步推导

目标：最大化几何间隔，同时要求每个样本的几何间隔都不小于 $\gamma$：

约束的规范化：令函数间隔为 1。 由于函数间隔有缩放自由度，我们令 $\hat{\gamma} = 1$（将 $(\mathbf{w}, b)$ 缩放为 $(\mathbf{w}/\hat{\gamma}, b/\hat{\gamma})$ 即可）。此时：

• 约束变为 $y_i(\mathbf{w} \cdot \mathbf{x}_i + b) \geq 1$
• 几何间隔 $\gamma = 1 / \|\mathbf{w}\|$
• 最大化 $\gamma$ 等价于最小化 $\frac{1}{2}\|\mathbf{w}\|^2$

最终的凸二次规划形式

原始问题（线性可分 SVM）

这是一个凸二次规划（QP）：目标函数是严格凸的二次函数，约束是线性不等式，全局最优解唯一。

解的存在性与唯一性

定理（存在唯一性） 若训练数据集 $T$ 线性可分，则原始问题存在唯一的最优解 $(\mathbf{w}^*, b^*)$。

证明要点：

• 存在性：可行域非空（线性可分保证）且目标函数下有界，连续函数在紧集上取到最小值。
• $\mathbf{w}^*$ 的唯一性：若存在两个最优解 $\mathbf{w}_1 \neq \mathbf{w}_2$，其中点 $(\mathbf{w}_1+\mathbf{w}_2)/2$ 可行且 $\|(\mathbf{w}_1+\mathbf{w}_2)/2\| < \|\mathbf{w}_1\| = \|\mathbf{w}_2\|$（范数严格凸性），与最优性矛盾。
• $b^*$ 的唯一性：由正类和负类支持向量的约束取等号直接确定。$\blacksquare$

试试切换下面的三条线，观察间隔宽度的差异：

那些刚好满足 $y_i(\mathbf{w} \cdot \mathbf{x}_i + b) = 1$ 的点叫支持向量——它们"撑住"间隔边界。

对偶问题的算法

将原始问题转化为对偶问题有三大好处：（1）揭示解的稀疏结构；（2）数据只以内积形式出现，为核技巧打开大门；（3）当 $N \ll n$ 时对偶更高效。

构造拉格朗日函数

对每个约束引入乘子 $\alpha_i \geq 0$：

由 Slater 条件，强对偶性成立：$\min_{\mathbf{w},b}\max_{\boldsymbol{\alpha}\geq 0} L = \max_{\boldsymbol{\alpha}\geq 0} \min_{\mathbf{w},b} L$。

对 $\mathbf{w}$ 和 $b$ 求极小

第一个等式意义深远：最优权重是训练样本的线性组合，系数为 $\alpha_i y_i$。

代回得到对偶问题

将 $\mathbf{w}^*$ 代入 $L$ 并化简：

两项相减加上 $\sum \alpha_i$，得到对偶目标：

对偶问题

关键特征：数据只以内积 $\mathbf{x}_i \cdot \mathbf{x}_j$ 出现——将内积替换为核函数就能做非线性分类。

KKT 条件与互补松弛

在最优解处，互补松弛条件：

这意味着：

• $\alpha_i^* = 0$：点在间隔外，不影响决策边界（非支持向量）。
• $\alpha_i^* > 0$：$y_i(\mathbf{w}^* \cdot \mathbf{x}_i + b^*) = 1$，点恰在间隔边界上（支持向量）。

只有支持向量对最终分类超平面有贡献。 删掉非支持向量，最优解不变。这就是 SVM 名字的由来和模型稀疏性的数学根源。

从对偶解恢复原始解

对偶形式的决策函数

预测只需计算新样本与支持向量的内积，计算量与支持向量数成正比。

线性支持向量机与软间隔最大化

硬间隔要求所有点正确分类且在间隔外——现实数据有噪声，一两个离群点就可能让问题无解或扭曲边界。本节引入松弛变量和惩罚参数，得到实际应用中真正使用的线性支持向量机。

线性支持向量机

松弛变量的引入

对每个样本引入松弛变量 $\xi_i \geq 0$，将硬约束放松为：

$\xi_i$ 的几何含义：

• $\xi_i = 0$：样本在间隔边界外（满足硬约束）
• $0 < \xi_i < 1$：在间隔内但正确分类
• $\xi_i = 1$：恰在决策超平面上
• $\xi_i > 1$：被错误分类

软间隔优化问题

$C > 0$ 的作用（偏差-方差权衡）：

• $C$ 大 → 对误分类惩罚严厉，间隔窄，容易过拟合
• $C$ 小 → 容许更多违反，间隔宽，可能欠拟合
• $C \to \infty$ 退化为硬间隔 SVM

拖动下面的滑块，观察 $C$ 对间隔和决策边界的影响：

对偶问题的推导

构造拉格朗日函数

引入两组乘子：$\alpha_i \geq 0$（对应主约束）和 $\mu_i \geq 0$（对应 $\xi_i \geq 0$）：

对原始变量求偏导

由 $\mu_i \geq 0$ 得 $\alpha_i \leq C$。这就是软间隔的箱约束：$0 \leq \alpha_i \leq C$。

代入化简

所有含 $\xi_i$ 的项因为 $C - \alpha_i - \mu_i = 0$ 完全消去。最终得到：

软间隔 SVM 的对偶问题：

与硬间隔目标函数完全相同，唯一区别是 $\alpha_i$ 多了上界 $C$。

支持向量

利用 KKT 条件，训练样本分为三类：

自由支持向量（$0 < \alpha_i < C$）最为重要——用它们计算 $b^*$：

有界支持向量（$\alpha_i = C$）的影响力被限制在 $C$——这保证了模型对离群值的鲁棒性。

合页损失函数与无约束优化

等价的无约束形式

定理（等价性） 软间隔 SVM 等价于：

其中 $[z]_+ = \max(0, z)$ 就是合页损失（hinge loss）。

证明： 在最优解处 $\xi_i^* = \max(0, 1 - y_i(\mathbf{w} \cdot \mathbf{x}_i + b)) = [1 - y_i f(\mathbf{x}_i)]_+$，代入原目标函数即得。$\square$

合页损失的性质

记函数间隔 $m = y \cdot f(\mathbf{x})$：

• 当 $m \geq 1$ 时损失为零——不只分类正确，还要有足够"间隔"
• 是 0-1 损失的凸上界：$[1-m]_+ \geq \mathbb{1}[m \leq 0]$
• 不处处可微，但处处有次梯度

与其他损失的对比

正则化框架的统一视角

• Hinge + L2 = SVM
• Logistic + L2 = Logistic 回归（weight decay）
• Hinge + L1 = 稀疏 SVM

深度学习中的 "loss + weight decay" 与 SVM 在数学结构上完全同构。

SMO 算法

对偶问题的标准求解方法是 SMO（Sequential Minimal Optimization, Platt 1998）：每次只更新两个 $\alpha_i$（等式约束要求至少改两个变量）。

核心更新公式：

然后剪切到 $[L, H] \cap [0, C]$ 的合法范围内。

下面的可视化展示了 SMO 的逐步求解过程：

SMO 的优雅之处：不需要矩阵运算，内存友好，收敛快。这是 libsvm 和 sklearn 底层使用的算法。

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

线性分类器只能画超平面。对环形分布、XOR 型数据，无论怎么调参都无法线性分开。核心思想：把数据映射到高维空间，使其线性可分，然后在高维做线性 SVM。 核函数让这个过程在计算上可行——你永远不需要显式计算高维坐标。

核技巧

从 XOR 问题说起

四个点：$(1,1) \to +1$，$(-1,-1) \to +1$，$(1,-1) \to -1$，$(-1,1) \to -1$。无论怎么画直线都分不开。

定义映射 $\phi(\mathbf{x}) = (x_1^2, \sqrt{2}\,x_1 x_2, x_2^2)$，四点变为：

新空间中超平面 $z_2 = 0$ 完美分开两类。非线性问题在特征空间中变成了线性问题。

核函数的定义

定义。 函数 $K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ 称为核函数，如果存在映射 $\phi: \mathcal{X} \to \mathcal{H}$ 使得：

核技巧的本质

SVM 对偶问题中数据只通过内积 $\mathbf{x}_i \cdot \mathbf{x}_j$ 出现。将内积替换为 $K(\mathbf{x}_i, \mathbf{x}_j) = \langle\phi(\mathbf{x}_i), \phi(\mathbf{x}_j)\rangle$，就等价于在高维特征空间中做线性 SVM——但无需显式计算 $\phi(\mathbf{x})$。

具体例子

对 $\mathbf{x}, \mathbf{z} \in \mathbb{R}^2$，映射 $\phi(\mathbf{x}) = (x_1^2, \sqrt{2}\,x_1 x_2, x_2^2)$ 的内积：

核函数 $K(\mathbf{x}, \mathbf{z}) = (\mathbf{x} \cdot \mathbf{z})^2$ 只需 $O(d)$ 计算，等价于在三维特征空间做内积。对一般 $d$ 维输入和 $p$ 次多项式，特征空间维度为 $\binom{d+p}{p}$（指数级），但核计算始终 $O(d)$。

下面的可视化展示了核技巧如何把非线性可分数据"拉直"：

正定核

什么函数有资格当核函数？Mercer 定理给出完整回答。

Gram 矩阵与正定性

定义（正定核）。 $K: \mathcal{X} \times \mathcal{X} \to \mathbb{R}$ 称为正定核，如果满足：

1. 对称性：$K(\mathbf{x}, \mathbf{z}) = K(\mathbf{z}, \mathbf{x})$
2. 正半定性：对任意 $\{x_1, \ldots, x_n\}$ 和 $c_1, \ldots, c_n \in \mathbb{R}$：

即 Gram 矩阵 $G_{ij} = K(x_i, x_j)$ 半正定。

Mercer 定理

定理。 $K$ 是合法核函数 $\iff$ $K$ 是正定核 $\iff$ 对任何有限样本集，Gram 矩阵半正定。

必要性证明： 若 $K(\mathbf{x}, \mathbf{z}) = \langle\phi(\mathbf{x}), \phi(\mathbf{z})\rangle$，则：

充分性（构造性）： 定义 $\phi(x) = K(\cdot, x)$（映射为函数），则 $\langle\phi(x), \phi(z)\rangle = K(x,z)$（再生性质）。构造出的空间称为再生核 Hilbert 空间（RKHS）。

核函数的运算封闭性

• 线性组合：$a_1 K_1 + a_2 K_2$（$a_i \geq 0$）仍是正定核
• 乘积：$K_1 \cdot K_2$ 仍是正定核（Schur 乘积定理）
• 极限：逐点收敛的正定核序列的极限仍是正定核
• 指数：$\exp(K)$ 仍是正定核

这意味着你可以通过组合已知核构造新核，无需显式写出 $\phi$。

常用核函数

线性核

特征空间 = 输入空间。适用于高维稀疏数据（文本 TF-IDF、基因组），$d \gg N$ 时通常已够用。

多项式核

特征空间维度 $\binom{d+p}{p}$。$p=2,3$ 最常见，$p$ 太大易过拟合。适合存在特征交互的场景。

高斯 RBF 核

对应无穷维特征空间。 证明：展开 $\exp(2\gamma\,\mathbf{x}\cdot\mathbf{z}) = \sum_{n=0}^{\infty} \frac{(2\gamma)^n}{n!}(\mathbf{x}\cdot\mathbf{z})^n$，每一项是 $n$ 次多项式核，无穷求和对应无穷维特征。

$\gamma$ 的含义：

• $\gamma$ 大 → 核衰减快，决策边界曲折，易过拟合
• $\gamma$ 小 → 核衰减慢，边界平滑，趋近线性

RBF 是最常用的默认选择，能逼近任意连续决策边界。

Sigmoid 核

与两层神经网络的联系：每个隐藏单元计算 $\tanh(\mathbf{w}\cdot\mathbf{x}+b)$。注意：不是对所有参数都正定，已较少使用。

核函数对比

选择指南： 先试线性核 → 默认 RBF → 有领域知识时用多项式。数据必须先标准化。用网格搜索 + 交叉验证选 $C$ 和 $\gamma$。

非线性支持向量分类机

完整算法

输入： 训练集 $T$，核函数 $K$，惩罚参数 $C$

步骤 1. 求解对偶问题：

步骤 2. 计算阈值（取自由支持向量平均）：

步骤 3. 决策函数：

预测复杂度：$O(|SV| \cdot d)$，只需遍历支持向量。

核化 SMO

SMO 直接适用于核化版本——将 $\mathbf{x}_i \cdot \mathbf{x}_j$ 替换为 $K(\mathbf{x}_i, \mathbf{x}_j)$：

• 误差：$E_i = \sum_{k \in SV} \alpha_k y_k K(\mathbf{x}_k, \mathbf{x}_i) + b - y_i$
• 二阶项：$\eta = K_{ii} + K_{jj} - 2K_{ij}$（$\phi(\mathbf{x}_i) - \phi(\mathbf{x}_j)$ 在特征空间中的范数平方）

计算复杂度

大规模时的替代方案：随机 Fourier 特征（Rahimi & Recht 2007）将 RBF 核近似为有限维映射，转化为线性 SVM。

多类分类

SVM 本质是二分类器。多类扩展：

• 一对一（OvO）：$\binom{K}{2}$ 个分类器，投票。libsvm/sklearn 默认。
• 一对多（OvA）：$K$ 个分类器，取 $f_i(\mathbf{x})$ 最大的类。