支持向量机与SMO算法

1. 线性支持向量机

1.1 最大间隔超平面

给定训练数据集 $\{(\mathbf{x}_i, y_i)\}_{i=1}^N$，其中 $\mathbf{x}_i \in \mathbb{R}^d$，$y_i \in \{-1, +1\}$。线性SVM的目标是找到一个超平面 $\mathbf{w}^\top \mathbf{x} + b = 0$ 能将两类正确分开，并且使距离超平面最近的样本点（即支持向量）到超平面的距离之和最大，即间隔最大化。间隔定义为 $2 / \|\mathbf{w}\|$，因此最大化间隔等价于最小化 $\frac{1}{2}\|\mathbf{w}\|^2$，同时要求所有样本满足 $y_i(\mathbf{w}^\top \mathbf{x}_i + b) \ge 1$。

1.2 软间隔与松弛变量

当数据线性不可分时，引入松弛变量 $\xi_i \ge 0$ 允许部分样本点违反硬间隔约束。优化问题变为：

其中 $C>0$ 是惩罚参数，平衡间隔大小与分类误差。

1.3 对偶形式

构造拉格朗日函数，导出对偶问题：

其中 $\alpha_i$ 为拉格朗日乘子。最终分类决策函数为 $f(\mathbf{x}) = \text{sign}\left(\sum_{i=1}^N \alpha_i y_i \mathbf{x}_i^\top \mathbf{x} + b\right)$。只有支持向量（$\alpha_i > 0$）对决策起作用。

2. 核技巧

2.1 从线性到非线性

对于非线性问题，可将原始输入空间映射到高维特征空间 $\phi(\mathbf{x})$，使得数据在特征空间中线性可分。但直接计算 $\phi(\mathbf{x})$ 可能维度极高甚至无穷维，导致计算困难。核技巧通过定义核函数 $K(\mathbf{x}_i, \mathbf{x}_j) = \phi(\mathbf{x}_i)^\top \phi(\mathbf{x}_j)$，隐式地在特征空间中进行内积运算，避免显式映射。

2.2 常用核函数

• 线性核：$K(\mathbf{x}_i, \mathbf{x}_j) = \mathbf{x}_i^\top \mathbf{x}_j$。
• 多项式核：$K(\mathbf{x}_i, \mathbf{x}_j) = (\gamma \mathbf{x}_i^\top \mathbf{x}_j + r)^p$。
• 高斯径向基核（RBF）：$K(\mathbf{x}_i, \mathbf{x}_j) = \exp(-\gamma \|\mathbf{x}_i - \mathbf{x}_j\|^2)$。
• Sigmoid核：$K(\mathbf{x}_i, \mathbf{x}_j) = \tanh(\gamma \mathbf{x}_i^\top \mathbf{x}_j + r)$。

2.3 核SVM的对偶形式

将对偶问题中的内积替换为核函数：

决策函数变为 $f(\mathbf{x}) = \text{sign}\left(\sum_{i=1}^N \alpha_i y_i K(\mathbf{x}_i, \mathbf{x}) + b\right)$。

3. SMO算法

3.1 算法动机

核SVM的对偶问题是一个凸二次规划，约束条件为框式约束和一个线性等式。当样本数 $N$ 很大时，传统二次规划求解器（如内点法）计算代价过高。SMO算法将原问题分解为一系列最小的子问题——每次只优化两个变量，其余固定，从而获得解析解，极大提高效率。

3.2 两个变量的子问题

固定除 $\alpha_1, \alpha_2$ 外的所有变量，利用等式约束 $\sum_{i=1}^N \alpha_i y_i = 0$ 可得：

通过代入目标函数并剪辑，可得解析解 $\alpha_2^{\text{new}}$，进而求出 $\alpha_1^{\text{new}}$。

3.3 算法流程

SMO 算法每次优化两个拉格朗日乘子，具体步骤如下：

1. 初始化：设拉格朗日乘子向量 \(\boldsymbol{\alpha} = \mathbf{0}\)，阈值 \(b = 0\)。计算初始误差 \(E_i = g(\mathbf{x}_i) - y_i\)，其中 \(g(\mathbf{x}_i) = \sum_{j=1}^{N} \alpha_j y_j K(\mathbf{x}_j, \mathbf{x}_i) + b\)。
2. 外层循环：寻找违反 KKT 条件的第一个变量 \(\alpha_i\)。违反条件包括：
   • \(0 < \alpha_i < C\) 且 \(y_i E_i \neq 0\)
   • \(\alpha_i = 0\) 且 \(y_i E_i < 0\)
   • \(\alpha_i = C\) 且 \(y_i E_i > 0\)
   优先扫描间隔边界上的样本（\(0 < \alpha_i < C\)），再遍历整个训练集。找到后进入内层循环。若仍无违反者，算法终止。
3. 内层循环：选择第二个乘子 \(\alpha_j\)
   
   • 阶段一：在非边界样本中，按 \(|E_i - E_j|\) 降序生成候选列表
   • 阶段二：若阶段一未找到有效配对，则从剩余样本中随机打乱顺序依次尝试
   • 若所有候选均失败，则返回外层循环选择下一个 \(i\)
4. 更新 \(\alpha_i, \alpha_j\)：
   • 根据类别异同计算边界 \(L\) 和 \(H\)：
     若 \(y_i = y_j\)：\(L = \max(0, \alpha_i + \alpha_j - C)\)，\(H = \min(C, \alpha_i + \alpha_j)\)
     若 \(y_i \neq y_j\)：\(L = \max(0, \alpha_j - \alpha_i)\)，\(H = \min(C, C + \alpha_j - \alpha_i)\)
   • 计算 \(\eta = 2K_{i,j} - K_{i,i} - K_{j,j}\)，其中 \(K_{i,j} = K(\mathbf{x}_i, \mathbf{x}_j)\)。
   • 未剪辑的 \(\alpha_j\) 更新量为 \(\alpha_j - \frac{y_j(E_i - E_j)}{\eta}\)，剪辑后得到 \(\alpha_j^{\text{new}}\)： \[ \alpha_j^{\text{new}} = \begin{cases} L, & \alpha_j - \dfrac{y_j(E_i - E_j)}{\eta} < L \\[2ex] \alpha_j - \dfrac{y_j(E_i - E_j)}{\eta}, & L \leq \alpha_j - \dfrac{y_j(E_i - E_j)}{\eta} \leq H \\[2ex] H, & \alpha_j - \dfrac{y_j(E_i - E_j)}{\eta}> H \end{cases} \]
   • 更新 \(\alpha_i^{\text{new}} = \alpha_i + y_i y_j (\alpha_j - \alpha_j^{\text{new}})\)。
5. 更新阈值 \(b\) 和误差 \(E\)：
   • 计算中间变量： \[ b_i = b - E_i - y_i(\alpha_i^{\text{new}} - \alpha_i)K_{i,i} - y_j(\alpha_j^{\text{new}} - \alpha_j)K_{i,j} \] \[ b_j = b - E_j - y_i(\alpha_i^{\text{new}} - \alpha_i)K_{i,j} - y_j(\alpha_j^{\text{new}} - \alpha_j)K_{j,j} \]
   • 新阈值 \(b^{\text{new}}\) 由以下规则确定：
     若 \(0 < \alpha_i^{\text{new}} < C\)，则 \(b^{\text{new}}=b_i\)
     若 \(0 < \alpha_j^{\text{new}} < C\)，则 \(b^{\text{new}}=b_j\)
     否则 \(b^{\text{new}} = (b_i + b_j)/2\)
   • 更新所有样本的误差： \[ E_k^{\text{new}} = E_k + y_i(\alpha_i^{\text{new}} - \alpha_i)K_{i,k} + y_j(\alpha_j^{\text{new}} - \alpha_j)K_{j,k} + b^{\text{new}} - b \]
6. 终止条件检查：若所有样本满足 \(|y_i g(\mathbf{x}_i) - 1| < tol\) 或迭代次数达到 \(max\_iter\)，则停止。
7. 输出模型：得到 \(\boldsymbol{\omega} = \sum_{i=1}^{N} \alpha_i y_i K(\cdot, \mathbf{x}_i)\)，决策函数 \(f(\mathbf{x}) = \operatorname{sign}\big(\boldsymbol{\omega} \cdot \mathbf{x} + b\big)\)。