支持向量机（SVM）的序列最小优化（SMO）算法原理与参数求解过程

字数 2503 2025-11-24 16:11:16

支持向量机（SVM）的序列最小优化（SMO）算法原理与参数求解过程

题目描述
序列最小优化（Sequential Minimal Optimization, SMO）是支持向量机（SVM）的一种高效训练算法，用于求解SVM的对偶问题。SMO通过将大规模二次规划问题分解为最小的子问题（每次只优化两个拉格朗日乘子）来迭代更新参数，从而避免复杂的数值优化方法。本题目要求详细解释SMO算法的步骤，包括乘子选择、解析求解和阈值更新。

解题过程

问题回顾
SVM的对偶问题可表示为：

\[ \max_{\alpha} \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 K(x_i, x_j) \]

约束条件为：

\[ \sum_{i=1}^n \alpha_i y_i = 0, \quad 0 \leq \alpha_i \leq C \ (i=1,\dots,n) \]

其中 $\alpha_i$ 是拉格朗日乘子，$K(\cdot)$ 是核函数，$C$ 是惩罚参数。SMO的目标是高效求解 $\alpha$。

SMO的核心思想
- 将问题分解为固定其他乘子、仅优化两个乘子 $\alpha_1$ 和 $\alpha_2$ 的子问题。
- 通过解析方法直接求解子问题，避免迭代数值优化。
- 利用更新后的乘子调整模型参数（如阈值 $b$），逐步逼近最优解。
乘子选择策略
- 外层循环：选择违反KKT条件最严重的乘子 $\alpha_1$。例如，检查样本是否满足：
  - 若 $\alpha_i = 0$，则 $y_i f(x_i) \geq 1$；
  - 若 $0 < \alpha_i < C$，则 $y_i f(x_i) = 1$；
  - 若 $\alpha_i = C$，则 $y_i f(x_i) \leq 1$。
- 内层循环：选择与 $\alpha_1$ 差异最大的乘子 $\alpha_2$，以最大化目标函数下降幅度。通常通过计算 $|E_1 - E_2|$ 选择，其中 $E_i = f(x_i) - y_i$ 为预测误差。
解析求解两个乘子
假设选中 $\alpha_1$ 和 $\alpha_2$，其约束关系为：

\[ \alpha_1^{\text{new}} y_1 + \alpha_2^{\text{new}} y_2 = \alpha_1^{\text{old}} y_1 + \alpha_2^{\text{old}} y_2 = \zeta \]

定义核函数值 $K_{ij} = K(x_i, x_j)$，并计算上下界 $L$ 和 $H$：

若 $y_1 \neq y_2$，则 $L = \max(0, \alpha_2^{\text{old}} - \alpha_1^{\text{old}})$，$H = \min(C, C + \alpha_2^{\text{old}} - \alpha_1^{\text{old}})$；
若 $y_1 = y_2$，则 $L = \max(0, \alpha_1^{\text{old}} + \alpha_2^{\text{old}} - C)$，$H = \min(C, \alpha_1^{\text{old}} + \alpha_2^{\text{old}})$。
进而计算未裁剪的解：

\[ \alpha_2^{\text{new,unc}} = \alpha_2^{\text{old}} + \frac{y_2 (E_1 - E_2)}{K_{11} + K_{22} - 2K_{12}} \]

最终裁剪解为：

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

再通过约束关系得 $\alpha_1^{\text{new}} = \alpha_1^{\text{old}} + y_1 y_2 (\alpha_2^{\text{old}} - \alpha_2^{\text{new}})$。

更新阈值 $b$ 和误差缓存
- 计算新阈值 $b^{\text{new}}$：
  - 若 $0 < \alpha_1^{\text{new}} < C$，则 $b^{\text{new}} = b^{\text{old}} - E_1 - y_1 (\alpha_1^{\text{new}} - \alpha_1^{\text{old}}) K_{11} - y_2 (\alpha_2^{\text{new}} - \alpha_2^{\text{old}}) K_{12}$；
  - 否则用 $\alpha_2$ 类似计算，或取两者平均值。
- 更新误差缓存 $E_i$ 用于后续乘子选择。
迭代收敛
重复步骤3-5，直到所有乘子满足KKT条件或目标函数变化小于预设阈值。最终得到最优乘子 $\alpha^*$ 和阈值 $b^*$，用于构建分类函数 $f(x) = \sum_{i=1}^n \alpha_i^* y_i K(x_i, x) + b^*$。

总结
SMO算法通过将复杂问题分解为可解析求解的子问题，结合启发式乘子选择，实现了SVM的高效训练。其核心在于平衡计算效率与收敛性，适用于大规模数据集。

支持向量机（SVM）的序列最小优化（SMO）算法原理与参数求解过程题目描述序列最小优化（Sequential Minimal Optimization, SMO）是支持向量机（SVM）的一种高效训练算法，用于求解SVM的对偶问题。SMO通过将大规模二次规划问题分解为最小的子问题（每次只优化两个拉格朗日乘子）来迭代更新参数，从而避免复杂的数值优化方法。本题目要求详细解释SMO算法的步骤，包括乘子选择、解析求解和阈值更新。解题过程问题回顾 SVM的对偶问题可表示为： $$ \max_ {\alpha} \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 K(x_ i, x_ j) $$ 约束条件为： $$ \sum_ {i=1}^n \alpha_ i y_ i = 0, \quad 0 \leq \alpha_ i \leq C \ (i=1,\dots,n) $$ 其中 $\alpha_ i$ 是拉格朗日乘子，$K(\cdot)$ 是核函数，$C$ 是惩罚参数。SMO的目标是高效求解 $\alpha$。 SMO的核心思想将问题分解为固定其他乘子、仅优化两个乘子 $\alpha_ 1$ 和 $\alpha_ 2$ 的子问题。通过解析方法直接求解子问题，避免迭代数值优化。利用更新后的乘子调整模型参数（如阈值 $b$），逐步逼近最优解。乘子选择策略外层循环：选择违反KKT条件最严重的乘子 $\alpha_ 1$。例如，检查样本是否满足：若 $\alpha_ i = 0$，则 $y_ i f(x_ i) \geq 1$；若 $0 < \alpha_ i < C$，则 $y_ i f(x_ i) = 1$；若 $\alpha_ i = C$，则 $y_ i f(x_ i) \leq 1$。内层循环：选择与 $\alpha_ 1$ 差异最大的乘子 $\alpha_ 2$，以最大化目标函数下降幅度。通常通过计算 $|E_ 1 - E_ 2|$ 选择，其中 $E_ i = f(x_ i) - y_ i$ 为预测误差。解析求解两个乘子假设选中 $\alpha_ 1$ 和 $\alpha_ 2$，其约束关系为： $$ \alpha_ 1^{\text{new}} y_ 1 + \alpha_ 2^{\text{new}} y_ 2 = \alpha_ 1^{\text{old}} y_ 1 + \alpha_ 2^{\text{old}} y_ 2 = \zeta $$ 定义核函数值 $K_ {ij} = K(x_ i, x_ j)$，并计算上下界 $L$ 和 $H$：若 $y_ 1 \neq y_ 2$，则 $L = \max(0, \alpha_ 2^{\text{old}} - \alpha_ 1^{\text{old}})$，$H = \min(C, C + \alpha_ 2^{\text{old}} - \alpha_ 1^{\text{old}})$；若 $y_ 1 = y_ 2$，则 $L = \max(0, \alpha_ 1^{\text{old}} + \alpha_ 2^{\text{old}} - C)$，$H = \min(C, \alpha_ 1^{\text{old}} + \alpha_ 2^{\text{old}})$。进而计算未裁剪的解： $$ \alpha_ 2^{\text{new,unc}} = \alpha_ 2^{\text{old}} + \frac{y_ 2 (E_ 1 - E_ 2)}{K_ {11} + K_ {22} - 2K_ {12}} $$ 最终裁剪解为： $$ \alpha_ 2^{\text{new}} = \begin{cases} H & \text{if} \ \alpha_ 2^{\text{new,unc}} > H \\ \alpha_ 2^{\text{new,unc}} & \text{if} \ L \leq \alpha_ 2^{\text{new,unc}} \leq H \\ L & \text{if} \ \alpha_ 2^{\text{new,unc}} < L \end{cases} $$ 再通过约束关系得 $\alpha_ 1^{\text{new}} = \alpha_ 1^{\text{old}} + y_ 1 y_ 2 (\alpha_ 2^{\text{old}} - \alpha_ 2^{\text{new}})$。更新阈值 $b$ 和误差缓存计算新阈值 $b^{\text{new}}$：若 $0 < \alpha_ 1^{\text{new}} < C$，则 $b^{\text{new}} = b^{\text{old}} - E_ 1 - y_ 1 (\alpha_ 1^{\text{new}} - \alpha_ 1^{\text{old}}) K_ {11} - y_ 2 (\alpha_ 2^{\text{new}} - \alpha_ 2^{\text{old}}) K_ {12}$；否则用 $\alpha_ 2$ 类似计算，或取两者平均值。更新误差缓存 $E_ i$ 用于后续乘子选择。迭代收敛重复步骤3-5，直到所有乘子满足KKT条件或目标函数变化小于预设阈值。最终得到最优乘子 $\alpha^ $ 和阈值 $b^ $，用于构建分类函数 $f(x) = \sum_ {i=1}^n \alpha_ i^* y_ i K(x_ i, x) + b^* $。总结 SMO算法通过将复杂问题分解为可解析求解的子问题，结合启发式乘子选择，实现了SVM的高效训练。其核心在于平衡计算效率与收敛性，适用于大规模数据集。