支持向量机

概述

支持向量机(Support Vector Machine, SVM)是一种二分类模型，它的基本思想是：在特征空间中找到一个最优的分离超平面，使得不同类别的样本被正确分开，并且分离超平面到两类样本的间隔最大。

为什么叫”支持向量”？

想象你要在平面上画一条线，把圆圈和叉叉分开。你会发现：

大部分点离这条线很远，移动它们不会影响这条线的位置
只有最靠近分界线的几个点，才真正决定了这条线的位置
这些关键的点就叫做**”支持向量”**(Support Vectors)

SVM 的三种情况

根据训练数据的特点，SVM 可以分为三种：

线性可分支持向量机:当数据线性可分时,使用硬间隔最大化
线性支持向量机:当数据近似线性可分时,使用软间隔最大化
非线性支持向量机:当数据线性不可分时,使用核技巧将数据映射到高维空间

学习方法

SVM 的学习策略是间隔最大化，可以形式化为一个凸二次优化问题。

学习的基本步骤：

构造最优化问题(原始问题)
转化为对偶问题(更容易求解)
使用 SMO 等算法求解
得到分离超平面和分类决策函数

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

线性可分支持向量机

基本概念

线性可分：给定训练数据集 $T = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)}$，其中 $x_i \in \mathbb{R}^n$, $y_i \in {+1, -1}$。如果存在某个超平面 $S$ 能够将正负样本完全正确地划分到超平面的两侧，则称数据集线性可分。

分离超平面：超平面可以用线性方程表示：

$$
w \cdot x + b = 0
$$

其中：

$w$ 是超平面的法向量，决定了超平面的方向
$b$ 是截距，决定了超平面与原点的距离

分类决策函数：

$$
f(x) = \text{sign}(w \cdot x + b)
$$

当 $w \cdot x + b > 0$ 时，预测 $y = +1$
当 $w \cdot x + b < 0$ 时，预测 $y = -1$

通俗理解

想象你在平面上有红球和蓝球：

超平面就是分界线（在 3 维空间就是一个平面，高维就是超平面）
法向量 $w$ 就像一个箭头，指向超平面的”正面”
截距 $b$ 决定了分界线在坐标系中的位置

函数间隔和几何间隔

为了找到”最好的”分离超平面，我们需要定义样本点到超平面的”距离”。

函数间隔

对于给定的训练数据集 $T$ 和超平面 $(w, b)$，定义超平面关于样本点 $(x_i, y_i)$ 的函数间隔为：

$$
\hat{\gamma}_i = y_i(w \cdot x_i + b)
$$

超平面关于训练数据集的函数间隔是所有样本点函数间隔的最小值：

$$
\hat{\gamma} = \min_{i=1,\cdots,N} \hat{\gamma}_i
$$

理解函数间隔：

$w \cdot x_i + b$ 的绝对值表示点到超平面的”距离”
乘以 $y_i$ 是为了统一正负类：
- 如果分类正确，$y_i(w \cdot x_i + b) > 0$，函数间隔为正
- 如果分类错误，$y_i(w \cdot x_i + b) < 0$，函数间隔为负
函数间隔越大，分类越确信

问题：函数间隔不是真正的距离！

如果把 $(w, b)$ 成比例地改变为 $(2w, 2b)$，超平面不变，但函数间隔变成 2 倍
所以需要对法向量加以约束，引出几何间隔

几何间隔

对于给定的训练数据集 $T$ 和超平面 $(w, b)$，定义超平面关于样本点 $(x_i, y_i)$ 的几何间隔为：

$$
\gamma_i = y_i \left( \frac{w}{|w|} \cdot x_i + \frac{b}{|w|} \right) = \frac{\hat{\gamma}_i}{|w|}
$$

超平面关于训练数据集的几何间隔是所有样本点几何间隔的最小值：

$$
\gamma = \min_{i=1,\cdots,N} \gamma_i = \frac{\hat{\gamma}}{|w|}
$$

理解几何间隔：

几何间隔 = 函数间隔 / $|w|$，相当于对 $w$ 进行了规范化
$|w|$ 是 $w$ 的 $L_2$ 范数：$|w| = \sqrt{w_1^2 + w_2^2 + \cdots + w_n^2}$
几何间隔就是点到超平面的真实欧氏距离
几何间隔不随 $(w, b)$ 的成比例缩放而改变

两种间隔的关系

函数间隔和几何间隔的关系：

$$
\gamma = \frac{\hat{\gamma}}{|w|}
$$

如果令 $|w| = 1$，则两者相等。

间隔最大化

最大间隔分离超平面

支持向量机的核心思想：不仅要正确分类所有样本，还要让分类的”确信度”最大化。

具体来说，就是要找到几何间隔最大的超平面。这可以表示为约束最优化问题：

$$
\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, \cdots, N
\end{aligned}
$$

约束条件的含义：每个样本点的几何间隔都要不小于 $\gamma$（即最小几何间隔）。

转化为更简单的形式

由于 $\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, \cdots, N
\end{aligned}
$$

关键技巧：函数间隔 $\hat{\gamma}$ 的大小不影响最优化问题的解（因为可以通过等比例缩放 $w, b$ 来改变 $\hat{\gamma}$）。因此，我们不妨令 $\hat{\gamma} = 1$，这样最优化问题变成：

$$
\begin{aligned}
\max_{w, b} \quad & \frac{1}{|w|} \
\text{s.t.} \quad & y_i (w \cdot x_i + b) \geq 1, \quad i = 1, 2, \cdots, N
\end{aligned}
$$

最大化 $\frac{1}{|w|}$ 等价于最小化 $\frac{1}{2}|w|^2$（加 $\frac{1}{2}$ 是为了求导时的方便）。

最终的优化问题（原始问题）

$$
\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, \cdots, N
\end{aligned}
$$

这是一个凸二次规划问题：

目标函数是二次的
约束条件是线性的
一定存在全局最优解

支持向量

在线性可分情况下，训练数据集的样本点中：

距离超平面最近的点使等号成立：$y_i(w \cdot x_i + b) - 1 = 0$
这些点就是支持向量(Support Vector)

支持向量在两个平行超平面上：

$H_1: w \cdot x + b = 1$（正类支持向量所在超平面）
$H_2: w \cdot x + b = -1$（负类支持向量所在超平面）

两个超平面之间的距离（即间隔）为 $\frac{2}{|w|}$。

重要性质：

只有支持向量决定了分离超平面，其他训练样本不起作用
如果移动非支持向量，分离超平面不变
支持向量的个数一般很少，这使得 SVM 很高效

正例点： $x_1=(3,3)^T,x_2=(4,3)^T$，负例点：$x_3=(1,1)^T$，求最大间隔分离超平面

![[images/截屏2026-04-13 13.46.29.png]]

$$
\begin{aligned}
\min_{w,b}\quad\frac{1}{2}(\omega_1^2+\omega_2^2)
\newline
\text{s.t.}\quad 3\omega_1+3\omega_2+b\geq1
\newline
4\omega_1+3\omega_2+b\geq1
\newline
-\omega_1-\omega_2-b\geq1
\end{aligned}
$$

对 $\frac{1}{2}(\omega_1^2+\omega_2^2)$ 求导，取极小值点（局部最优为全局最优），解得：$\omega_1=\omega_2=\frac{1}{2},b=-2$，于是最大间隔分离超平面为：

$$
\frac{1}{2}x^{(1)}+\frac{1}{2}x^{(2)}-2=0
$$

$x_1=(3,3)^T$ 和 $x_3=(1,1)^T$ 为支持向量

学习的对偶算法

为什么要用对偶算法？

对偶问题往往更容易求解：将原始问题的约束条件变成了对偶问题的等式约束
引入核函数：在对偶问题中，训练样本只以内积形式出现，便于使用核技巧
支持向量直接体现：通过对偶变量 $\alpha_i$ 可以直接看出哪些是支持向量

构造拉格朗日函数

对每个不等式约束引入拉格朗日乘子 $\alpha_i \geq 0$，定义拉格朗日函数：

$$
L(w, b, \alpha) = \frac{1}{2}|w|^2 - \sum_{i=1}^{N} \alpha_i [y_i(w \cdot x_i + b) - 1]
$$

其中 $\alpha = (\alpha_1, \alpha_2, \cdots, \alpha_N)^T$ 是拉格朗日乘子向量。

原始问题

原始问题可以表示为：

$$
\min_{w, b} \max_{\alpha} L(w, b, \alpha)
$$

其中 $\alpha_i \geq 0$。

对偶问题

根据拉格朗日对偶性，原始问题的对偶问题是：

$$
\max_{\alpha} \min_{w, b} L(w, b, \alpha)
$$

求解步骤：

第一步：求 $\min_{w, b} L(w, b, \alpha)$

对 $w, b$ 求偏导并令其为 0：

$$
\nabla_w L(w, b, \alpha) = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0
$$

$$
\nabla_b L(w, b, \alpha) = -\sum_{i=1}^{N} \alpha_i y_i = 0
$$

得到：

$$
w = \sum_{i=1}^{N} \alpha_i y_i x_i
$$

$$
\sum_{i=1}^{N} \alpha_i y_i = 0
$$

第二步：将上述结果代入拉格朗日函数

代入后得到对偶问题：

$$
\begin{aligned}
\max_{\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 (x_i \cdot x_j) \
\text{s.t.} \quad & \sum_{i=1}^{N} \alpha_i y_i = 0 \
& \alpha_i \geq 0, \quad i = 1, 2, \cdots, 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 \
& \alpha_i \geq 0, \quad i = 1, 2, \cdots, N
\end{aligned}
$$

求解对偶问题

假设 $\alpha^* = (\alpha_1^, \alpha_2^, \cdots, \alpha_N^*)^T$ 是对偶问题的解，则：

计算 $w^*$：

$$
w^* = \sum_{i=1}^{N} \alpha_i^* y_i x_i
$$

计算 $b^*$：

选择 $\alpha^$ 的一个正分量 $\alpha_j^ > 0$（对应的 $x_j$ 是支持向量），计算：

$$
b^* = y_j - \sum_{i=1}^{N} \alpha_i^* y_i (x_i \cdot x_j)
$$

实际计算时，通常取所有支持向量对应的 $b$ 的平均值以提高数值稳定性。

构造分离超平面和决策函数：

分离超平面：

$$
\sum_{i=1}^{N} \alpha_i^* y_i (x \cdot x_i) + b^* = 0
$$

分类决策函数：

$$
f(x) = \text{sign}\left( \sum_{i=1}^{N} \alpha_i^* y_i (x \cdot x_i) + b^* \right)
$$

KKT 条件

最优解 $(w^, b^, \alpha^*)$ 必须满足 KKT(Karush-Kuhn-Tucker)条件：

$$
\begin{aligned}
\nabla_w L(w^, b^, \alpha^) &= 0 \
\nabla_b L(w^, b^, \alpha^) &= 0 \
\alpha_i^* [y_i(w^* \cdot x_i + b^) - 1] &= 0, \quad i = 1, \cdots, N \
y_i(w^ \cdot x_i + b^) - 1 &\geq 0, \quad i = 1, \cdots, N \
\alpha_i^ &\geq 0, \quad i = 1, \cdots, N
\end{aligned}
$$

重要性质：第三个条件 $\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^*) > 1$，$x_i$ 不是支持向量

这说明：只有支持向量对应的 $\alpha_i^ > 0$，其余样本的 $\alpha_i^ = 0$**。

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

线性支持向量机

为什么需要软间隔？

在实际问题中，训练数据往往不是完全线性可分的，原因可能是：

存在噪声或异常点：个别异常点导致数据不可分
类别本身有重叠：在某些特征值下，两类样本本质上无法完全分开

如果仍然使用硬间隔（要求所有点都被正确分类），可能会出现：

无解：不存在能正确分类所有样本的超平面
过拟合：为了迁就个别异常点，分离超平面过于复杂

软间隔的思想：允许某些样本点不满足约束条件 $y_i(w \cdot x_i + b) \geq 1$，但要付出代价。

软间隔最大化

对每个样本点 $(x_i, y_i)$，引入松弛变量 $\xi_i \geq 0$，使约束条件变为：

$$
y_i(w \cdot x_i + b) \geq 1 - \xi_i
$$

松弛变量的含义：

$\xi_i = 0$：样本点在间隔边界上或外侧（满足硬间隔约束）
$0 < \xi_i < 1$：样本点在间隔内，但分类正确
$\xi_i = 1$：样本点在分离超平面上
$\xi_i > 1$：样本点被误分类

同时，目标函数需要加上对松弛变量的惩罚：

$$
\frac{1}{2}|w|^2 + C \sum_{i=1}^{N} \xi_i
$$

其中 $C > 0$ 是惩罚参数：

$C$ 越大，对误分类的惩罚越大，倾向于减少误分类（但可能过拟合）
$C$ 越小，对误分类的惩罚越小，倾向于增大间隔（但可能欠拟合）
$C$ 是需要通过交叉验证等方法选择的超参数

线性支持向量机的学习问题（原始问题）

$$
\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, \cdots, N \
& \xi_i \geq 0, \quad i = 1, 2, \cdots, N
\end{aligned}
$$

这仍然是一个凸二次规划问题。

软间隔支持向量

在软间隔情况下，支持向量包括：

在间隔边界上的样本点：$y_i(w \cdot x_i + b) = 1$, $\xi_i = 0$
在间隔内但分类正确的样本点：$0 < y_i(w \cdot x_i + b) < 1$, $0 < \xi_i < 1$
被误分类的样本点：$y_i(w \cdot x_i + b) < 0$, $\xi_i > 1$

所有满足 $\alpha_i > 0$ 的样本都是支持向量。

学习的对偶算法

软间隔的拉格朗日函数

类似于硬间隔，我们引入拉格朗日乘子 $\alpha_i \geq 0$ 和 $\mu_i \geq 0$，构造拉格朗日函数：

$$
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
$$

对偶问题的推导

第一步：求 $\min_{w,b,\xi} L(w, b, \xi, \alpha, \mu)$

对 $w, b, \xi$ 分别求偏导并令其为 0：

$$
\nabla_w L = w - \sum_{i=1}^{N} \alpha_i y_i x_i = 0 \Rightarrow w = \sum_{i=1}^{N} \alpha_i y_i x_i
$$

$$
\nabla_b L = -\sum_{i=1}^{N} \alpha_i y_i = 0 \Rightarrow \sum_{i=1}^{N} \alpha_i y_i = 0
$$

$$
\nabla_{\xi_i} L = C - \alpha_i - \mu_i = 0 \Rightarrow \alpha_i + \mu_i = C
$$

第二步：将上述结果代入拉格朗日函数

得到对偶问题：

$$
\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 \
& 0 \leq \alpha_i \leq C, \quad i = 1, 2, \cdots, N
\end{aligned}
$$

注意：与硬间隔的区别在于约束条件变成了 $0 \leq \alpha_i \leq C$，这是因为 $\alpha_i + \mu_i = C$ 且 $\mu_i \geq 0$。

求解对偶问题

求得最优解 $\alpha^*$ 后：

计算 $w^*$：

$$
w^* = \sum_{i=1}^{N} \alpha_i^* y_i x_i
$$
计算 $b^*$：

选择一个满足 $0 < \alpha_j^* < C$ 的分量（对应的样本在间隔边界上），计算：

$$
b^* = y_j - \sum_{i=1}^{N} \alpha_i^* y_i (x_i \cdot x_j)
$$

KKT 条件

软间隔的 KKT 条件：

$$
\begin{aligned}
\nabla_w L &= 0 \
\nabla_b L &= 0 \
\nabla_{\xi_i} L &= 0 \
\alpha_i[y_i(w \cdot x_i + b) - 1 + \xi_i] &= 0 \
\mu_i \xi_i &= 0 \
y_i(w \cdot x_i + b) - 1 + \xi_i &\geq 0 \
\xi_i &\geq 0 \
\alpha_i &\geq 0 \
\mu_i &\geq 0
\end{aligned}
$$

由于 $\alpha_i + \mu_i = C$，可以分析：

若 $\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$ 可能大于 0，样本在间隔内或被误分类

合页损失函数

从损失函数角度理解软间隔 SVM

线性支持向量机的原始问题可以改写为无约束优化问题：

$$
\min_{w, b} \left[ \frac{1}{2}|w|^2 + C \sum_{i=1}^{N} \max(0, 1 - y_i(w \cdot x_i + b)) \right]
$$

其中 $\max(0, 1 - y_i(w \cdot x_i + b))$ 称为合页损失函数(Hinge Loss)：

$$
L(y(w \cdot x + b)) = \max(0, 1 - y(w \cdot x + b))
$$

合页损失函数的特点

几何意义：

当样本被正确分类且函数间隔 $\geq 1$ 时，损失为 0
当函数间隔 $< 1$ 时，损失线性增长

与其他损失函数的比较：

0-1 损失：$L_{0-1}(y(w \cdot x + b)) = \begin{cases} 1, & y(w \cdot x + b) < 0 \ 0, & y(w \cdot x + b) \geq 0 \end{cases}$，不连续，难以优化
合页损失：连续，是 0-1 损失的上界，便于优化
logistic 损失：$L_{\text{log}}(y(w \cdot x + b)) = \log(1 + e^{-y(w \cdot x + b)})$，处处可导

优化目标：

$$
\min_{w, b} \sum_{i=1}^{N} [1 - y_i(w \cdot x_i + b)]_+ + \lambda |w|^2
$$

其中 $[z]_+ = \max(0, z)$ 是合页损失，$\lambda$ 是正则化参数，与 $C$ 的关系为 $\lambda = \frac{1}{2C}$。

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

核技巧

为什么需要核函数?

对于非线性可分的数据,一个自然的想法是:将数据从原始空间映射到更高维的特征空间,在高维空间中数据可能变成线性可分的。

例子:二维平面上的同心圆问题

在原始的 $(x_1, x_2)$ 空间,内圆和外圆无法用直线分开
映射到 $(x_1, x_2, x_1^2 + x_2^2)$ 空间,可以用平面分开

映射函数

设原始空间为 $\mathcal{X} \subset \mathbb{R}^n$,特征空间为 $\mathcal{H}$(通常是高维甚至无穷维的希尔伯特空间)。定义映射:

$$
\phi: \mathcal{X} \rightarrow \mathcal{H}
$$

将 $x$ 映射为 $\phi(x)$。

核函数的定义

在对偶问题中,训练样本只以内积形式 $x_i \cdot x_j$ 出现。如果直接计算 $\phi(x_i) \cdot \phi(x_j)$,当特征空间维度很高时,计算量会非常大。

核函数的思想:定义函数 $K(x, z)$ 使得:

$$
K(x, z) = \phi(x) \cdot \phi(z)
$$

即不需要显式计算映射 $\phi(x)$,就能直接计算高维空间中的内积。这称为核技巧(Kernel Trick)。

核函数的条件

正定核定理:设 $K: \mathcal{X} \times \mathcal{X} \rightarrow \mathbb{R}$ 是对称函数,则 $K(x, z)$ 为正定核函数的充要条件是:对任意 $x_i \in \mathcal{X}$ $(i=1,\cdots,m)$,对应的 Gram 矩阵:

$$
K = [K(x_i, x_j)]_{m \times m}
$$

是半正定的。

常用核函数

1. 多项式核函数

$$
K(x, z) = (x \cdot z + 1)^p
$$

其中 $p$ 是多项式的次数。

特例:当 $p=1$ 时,退化为线性核 $K(x, z) = x \cdot z$。

对应的映射:例如二维情况下 $p=2$:

$$
\phi(x_1, x_2) = (1, \sqrt{2}x_1, \sqrt{2}x_2, \sqrt{2}x_1x_2, x_1^2, x_2^2)
$$

2. 高斯核函数(RBF 核)

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

其中 $\sigma > 0$ 是带宽参数。

特点:

对应无穷维的特征空间
$\sigma$ 越小,模型越复杂(可能过拟合)
$\sigma$ 越大,模型越简单(可能欠拟合)
最常用的核函数之一

性质:

$K(x, z) \in (0, 1]$
当 $x = z$ 时,$K(x, x) = 1$
当 $|x - z| \rightarrow \infty$ 时,$K(x, z) \rightarrow 0$

3. 字符串核函数

用于文本分类,基于字符串的子序列匹配。

核函数的组合

若 $K_1, K_2$ 是核函数,则下列函数也是核函数:

线性组合:$\gamma_1 K_1 + \gamma_2 K_2$ (其中 $\gamma_1, \gamma_2 > 0$)
乘积:$K_1 \cdot K_2$
直积:$K_1 \otimes K_2$

非线性支持向量机

学习算法

给定训练数据集 $T = {(x_1, y_1), \cdots, (x_N, y_N)}$,选择适当的核函数 $K(x, z)$ 和惩罚参数 $C$,求解对偶问题:

$$
\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 \
& 0 \leq \alpha_i \leq C, \quad i = 1, 2, \cdots, N
\end{aligned}
$$

求得最优解 $\alpha^* = (\alpha_1^, \cdots, \alpha_N^)^T$。

分类决策函数

选择 $\alpha^$ 的一个正分量 $0 < \alpha_j^ < C$,计算:

$$
b^* = y_j - \sum_{i=1}^{N} \alpha_i^* y_i K(x_i, x_j)
$$

构造决策函数:

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

注意:

只有支持向量对应的 $\alpha_i^* > 0$
决策函数实际上只依赖于支持向量
预测时,只需计算新样本与支持向量的核函数值

序列最小最优化算法(SMO)

算法概述

SMO(Sequential Minimal Optimization)算法是一种高效求解 SVM 对偶问题的算法,由 John Platt 于 1998 年提出。

基本思想

SVM 的对偶问题是一个凸二次规划问题,变量个数等于训练样本数。当样本数很大时,通用的二次规划算法会非常慢。

SMO 算法的思想:

如果所有变量都满足 KKT 条件,则优化问题已解决
否则,选择两个变量,固定其他变量,构造一个二变量的二次规划问题
这个子问题有解析解,可以快速求解
不断迭代,直到收敛

为什么选择两个变量?

由于约束条件 $\sum_{i=1}^{N} \alpha_i y_i = 0$,如果只选择一个变量 $\alpha_i$,它的值由其他变量唯一确定,无法优化。因此至少要选择两个变量。

两个变量的子问题

问题设定

假设选择变量 $\alpha_1, \alpha_2$,固定其他变量,则优化问题变为:

$$
\begin{aligned}
\min_{\alpha_1, \alpha_2} \quad & W(\alpha_1, \alpha_2) = \frac{1}{2}K_{11}\alpha_1^2 + \frac{1}{2}K_{22}\alpha_2^2 + y_1y_2K_{12}\alpha_1\alpha_2 \
& \quad - (\alpha_1 + \alpha_2) + y_1\alpha_1\sum_{i=3}^{N}y_i\alpha_iK_{i1} + y_2\alpha_2\sum_{i=3}^{N}y_i\alpha_iK_{i2} \
\text{s.t.} \quad & \alpha_1 y_1 + \alpha_2 y_2 = -\sum_{i=3}^{N} y_i \alpha_i = \zeta \
& 0 \leq \alpha_1, \alpha_2 \leq C
\end{aligned}
$$

其中 $K_{ij} = K(x_i, x_j)$,$\zeta$ 是常数。

约束条件的几何意义

约束 $\alpha_1 y_1 + \alpha_2 y_2 = \zeta$ 和 $0 \leq \alpha_1, \alpha_2 \leq C$ 将可行域限制在 $[0, C] \times [0, C]$ 正方形中的一条线段上。

设 $\alpha_2$ 的上下界为 $L$ 和 $H$:

若 $y_1 \neq y_2$:
- $L = \max(0, \alpha_2 - \alpha_1)$
- $H = \min(C, C + \alpha_2 - \alpha_1)$
若 $y_1 = y_2$:
- $L = \max(0, \alpha_2 + \alpha_1 - C)$
- $H = \min(C, \alpha_2 + \alpha_1)$

解析解

定义:

$E_i = f(x_i) - y_i$ 为预测值与真实值的误差
$\eta = K_{11} + K_{22} - 2K_{12}$

未经剪辑的解:

$$
\alpha_2^{\text{new, unc}} = \alpha_2^{\text{old}} + \frac{y_2(E_1 - E_2)}{\eta}
$$

剪辑后的解:

$$
\alpha_2^{\text{new}} = \begin{cases}
H, & \alpha_2^{\text{new, unc}} > H \
\alpha_2^{\text{new, unc}}, & L \leq \alpha_2^{\text{new, unc}} \leq H \
L, & \alpha_2^{\text{new, unc}} < L
\end{cases}
$$

相应地更新 $\alpha_1$:

$$
\alpha_1^{\text{new}} = \alpha_1^{\text{old}} + y_1 y_2 (\alpha_2^{\text{old}} - \alpha_2^{\text{new}})
$$

更新阈值 $b$

当 $0 < \alpha_1^{\text{new}} < C$ 时:

$$
b_1^{\text{new}} = -E_1 - y_1K_{11}(\alpha_1^{\text{new}} - \alpha_1^{\text{old}}) - y_2K_{21}(\alpha_2^{\text{new}} - \alpha_2^{\text{old}}) + b^{\text{old}}
$$

当 $0 < \alpha_2^{\text{new}} < C$ 时：

$$
b_2^{\text{new}} = -E_2 - y_1K_{12}(\alpha_1^{\text{new}} - \alpha_1^{\text{old}}) - y_2K_{22}(\alpha_2^{\text{new}} - \alpha_2^{\text{old}}) + b^{\text{old}}
$$

若 $b_1$ 和 $b_2$ 都有效，则它们相等；否则取它们的平均值。

变量的选择方法

第一个变量的选择(外层循环)

选择违反 KKT 条件最严重的变量。

KKT 条件:

$$
\begin{aligned}
\alpha_i = 0 &\Rightarrow y_i f(x_i) \geq 1 \
0 < \alpha_i < C &\Rightarrow y_i f(x_i) = 1 \
\alpha_i = C &\Rightarrow y_i f(x_i) \leq 1
\end{aligned}
$$

启发式方法:

首先遍历所有满足 $0 < \alpha_i < C$ 的样本(在间隔边界上)
然后遍历整个训练集
重复上述过程直到收敛

第二个变量的选择(内层循环)

选择使 $|E_1 - E_2|$ 最大的变量,这样能使目标函数下降最快。

启发式方法:

如果 $E_1$ 为正,选择最小的 $E_i$ 作为 $E_2$
如果 $E_1$ 为负,选择最大的 $E_i$ 作为 $E_2$

SMO 算法流程

输入:训练数据集 $T$,精度 $\epsilon$

输出:近似解 $\hat{\alpha}$

步骤:

初始化 $\alpha = 0$,$b = 0$
选择第一个变量 $\alpha_1$
选择第二个变量 $\alpha_2$
求解两个变量的优化问题,更新 $\alpha_1, \alpha_2, b$
检验所有样本是否满足 KKT 条件(精度 $\epsilon$ 内)
- 若满足,结束
- 否则,转到步骤 2

收敛性:SMO 算法的收敛性已被证明,在有限步内必然收敛。

复杂度:

每次迭代的时间复杂度是 $O(N)$
总体上比通用 QP 求解器快得多,特别是对大规模数据

总结

SVM 的优缺点

优点

泛化能力强:基于结构风险最小化原理,而非经验风险最小化
全局最优解:凸优化问题,不存在局部最优
适用于高维数据:通过核函数可以处理高维甚至无穷维特征
稀疏性:只有支持向量影响决策,对异常值相对鲁棒
理论基础扎实:有完备的数学理论支持

缺点

对参数敏感:核函数的选择和参数 $C, \sigma$ 的调整需要经验
训练时间长:对大规模数据,训练速度较慢
多分类问题:原始 SVM 是二分类器,需要构造多分类策略
对缺失数据敏感:需要预处理
概率输出困难:SVM 输出的是决策值,不是概率

多分类 SVM

SVM 本身是二分类模型,处理多分类问题有以下策略:

1. 一对多(One-vs-Rest, OvR)

训练 $K$ 个分类器,第 $k$ 个分类器将第 $k$ 类与其余类分开
预测时,选择决策函数值最大的类

2. 一对一(One-vs-One, OvO)

训练 $\frac{K(K-1)}{2}$ 个分类器,每个分类器区分一对类别
预测时,采用投票法,选择获胜次数最多的类

3. 有向无环图(DAG)

构造有向无环图,每个节点是一个二分类器
预测时,从根节点开始,逐步排除类别

应用场景

SVM 广泛应用于:

文本分类:垃圾邮件识别、情感分析
图像识别:人脸识别、手写数字识别
生物信息学:蛋白质分类、基因分类
时间序列预测:通过 SVR(支持向量回归)
异常检测:单类 SVM(One-Class SVM)

与其他算法的比较

特性	SVM	神经网络	决策树
训练速度	较慢	慢	快
预测速度	快	快	非常快
可解释性	中等	差	好
参数调优	较复杂	复杂	简单
过拟合风险	低	高	中等
高维数据	好	好	差

参考资料

李航. 统计学习方法(第 2 版). 清华大学出版社, 2019.
Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer.
Platt, J. (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines.
Cortes, C., & Vapnik, V. (1995). Support-vector networks. Machine learning, 20(3), 273-297.