接下来的内容将转向SMO算法的第二个核心组成部分——选择要优化的乘数的启发式方法。在这篇博客中，我们将探讨算法如何通过启发式选择策略高效地识别和更新拉格朗日乘数。通过对比直接优化的分析方法和启发式方法的策略选择，我们能够更全面地理解SMO算法在解决支持向量机（SVM）优化问题中的独特优势。

二、选择要优化的乘数的启发式方法

SMO算法包含两个主要步骤：选择需要优化的拉格朗日乘数对和优化这些乘数。算法采用启发式方法选择乘数对，加快收敛速度并确保选择的对最可能迅速改善模型性能。

1.外层循环 - 选择 ${\alpha }_1$：

• 遍历所有训练样本，识别违反KKT条件最严重的样本作为 ${\alpha }_1$。
• 如果某个样本不满足以下条件之一，它就被认为违反了KKT条件：
  • 如果 ${\alpha }_i=0$，则要求 $y_i{u}_i\ge 1$。
  • 如果 $0<{\alpha }_i<C$，则要求 $y_i{u}_i=1$。
  • 如果 ${\alpha }_i=C$，则要求 $y_i{u}_i\le 1$。
• 如果所有在边界上的支持向量满足KKT条件，则扩展搜索至整个训练集。

2.内层循环 - 选择 ${\alpha }_2$：

• 选择使得 $|E_1-E_2|$ 最大的 ${\alpha }_2$，其中 $E_i=u_i-y_i$ 是样本 $i$ 的预测误差，这有助于实现 ${\alpha }_2$ 的最大变化。

3. 计算和更新 ${\alpha }_1$ 和 ${\alpha }_2$：

推导过程，请见博客：复现SMO算法：深入探索序列最小优化的分析方法【三、算法原理揭秘-1】

在SMO算法中，${\alpha }_1$ 和 ${\alpha }_2$ 的优化是算法的核心。这两个乘数的更新是通过解析方法完成的，目的是最大化SVM的目标函数。这一过程可以分为几个步骤：

1. 计算误差差值：
   $$E_1=u_1-y_1,E_2=u_2-y_2$$
   其中，$u_i$ 是模型对第 $i$ 个样本的预测输出，$y_i$ 是实际标签。

2. 计算二乘数的上下界：
   为了满足约束条件 $0\le {\alpha }_i\le C$ 和 ${\sum }_{i=1}^N{\alpha }_i{y}_i=0$，我们需要计算 ${\alpha }_2$ 的上下界（L 和 H）。

   • 如果 $y_1\ne y_2$：
     $$L=\max (0,{\alpha }_2^{old}-{\alpha }_1^{old}),H=\min (C,C+{\alpha }_2^{old}-{\alpha }_1^{old})$$
   • 如果 $y_1=y_2$：
     $$L=\max (0,{\alpha }_1^{old}+{\alpha }_2^{old}-C),H=\min (C,{\alpha }_1^{old}+{\alpha }_2^{old})$$

3. 计算 ${\alpha }_2$ 的新值：
   ${\alpha }_2$ 的新值由下式给出：
   $${\alpha }_2^{new}={\alpha }_2^{old}+\frac{y_2(E_1-E_2)}{\eta }$$
   其中，$\eta$ 是核函数 $K(x_1,x_2)$ 的二阶导数，可以理解为对问题的“曲率”或调整步幅的影响因子。

4. 剪辑 ${\alpha }_2$：
   ${\alpha }_2^{new}$ 需要在其界限 L 和 H 之间被剪辑：
   $${\alpha }_2^{new,clipped}=\min (\max ({\alpha }_2^{new},L),H)$$

5. 更新 ${\alpha }_1$：
   根据 ${\alpha }_2$ 的变化更新 ${\alpha }_1$：
   $${\alpha }_1^{new}={\alpha }_1^{old}+y_1{y}_2({\alpha }_2^{old}-{\alpha }_2^{new,clipped})$$

更新偏置 $b$ 和误差 $E_i$：

• 根据新的乘数值重新计算偏置 $b$：
  $$b_{new}=b_{old}-\Delta b$$
• $\Delta b$ 根据 ${\alpha }_1$ 和 ${\alpha }_2$ 的变化量及其对应样本的 $y_i$ 和 $E_i$ 值计算得出。
• 重新计算所有样本的误差 $E_i$：
  $$E_i=({\mathbf{w}}^T{\mathbf{x}}_i+b)-y_i$$
• 更新权重向量 $\mathbf{w}$：
  $$\mathbf{w}=\sum _{j=1}^m{\alpha }_j{y}_j{\mathbf{x}}_j$$

关键问题解析

问题一：如何判定违反KKT条件最严重？

违反KKT条件的程度是通过样本的乘数 ${\alpha }_i$ 和它们的函数间隔 $y_i{u}_i$ 的关系来判定的。具体方法如下：

• ${\alpha }_i=0$ 的样本：理论上应满足 $y_i{u}_i\ge 1$。如果 $y_i{u}_i<1-ϵ$，这种违反被视为严重。
• $0<{\alpha }_i<C$ 的样本：应精确满足 $y_i{u}_i=1$。偏

离1超过 $ϵ$ 的情况被认为违反严重。

• ${\alpha }_i=C$ 的样本：应满足 $y_i{u}_i\le 1$。如果 $y_i{u}_i>1+ϵ$，同样视为严重违反。

问题二：计算 $|E_1-E_2|$ 最大的 ${\alpha }_2$

• 误差 $E_i$ 的计算公式为：
  $$E_i=(\sum _{j=1}^m{\alpha }_j{y}_{j}K(x_j,x_i)+b)-y_i$$
• 选择 ${\alpha }_2$ 通过寻找最大化 $|E_1-E_2|$ 的 ${\alpha }_j$ 实现，即：
  $$j=\arg \underset{j}{\max }|E_1-E_j|$$

伪代码实现

初始化所有乘数 alpha_i = 0
为所有 i 初始化误差 E_i
k = 0

重复直至收敛:
    // 外部循环选择 alpha_1
    对每个样本 i:
        计算 u_i = sum(alpha_j * y_j * K(x_j, x_i)) + b
        检查KKT条件
        如果违反:
            alpha_1 = alpha_i
            E_1 = E_i

            // 内部循环选择 alpha_2
            找到最大化 |E_1 - E_j| 的 j
            alpha_2 = alpha_j
            E_2 = E_j

            // 优化 alpha_1 和 alpha_2
            更新 alpha_1 和 alpha_2
            更新 b 重新计算误差

    k += 1
    检查收敛条件