Question

1. 支持向量机的学习问题可以形式化为求解凸二次规划问题。这样的凸二次规划问题具有全局最优解，并且有多种算法可以用于这一问题的求解。

   当训练样本容量非常大时，这些算法往往非常低效。而序列最小最优化(sequential minimal optimization:SMO）算法可以高效求解。

2. SMO算法的思路：

   • 若所有变量都满足条件，则最优化问题的解就得到了。

   • 否则，选择两个变量的同时固定其他所有变量，针对这两个变量构建一个二次规划子问题。

     • 这个二次规划子问题关于这两个变量的解应该更接近原始二次规划问题的解，因为这会使得原始二次规划问题的目标函数值变得更小。

     • 更重要的是，这个二次规划子问题可以通过解析的方法求解。

     • 此时子问题有两个变量，至少存在一个变量不满足约束条件（否则就是所有变量满足条件了）。

       假设其中一个是违反约束最严重的那个，另一个由约束等式自动确定： $ MathJax-Element-394 $ 。

3. SMO 算法将原始问题不断地分解为子问题并且对子问题求解，进而达到求解原问题的目的。

   整个 SMO 算法包括两部分：

   • 求解两个变量二次规划的解析方法。
   • 选择变量的启发式方法。

6.1 子问题的求解

1. 假设选择的两个变量是 $ MathJax-Element-454 $ ， 其他变量 $ MathJax-Element-396 $ 是固定的。

   于是 SMO 的最优化问题的子问题为：

   $ \min_{\alpha_1,\alpha_2} L(\alpha_1,\alpha_2)=\frac 12 K_{11}\alpha_1^{2}+\frac 12K_{22}\alpha_2^{2}+\tilde y_1\tilde y_2K_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)\\ +\tilde y_1\alpha_1\sum_{i=3}^{N}\tilde y_i\alpha_iK_{i1}+\tilde y_2\alpha_2\sum_{i=3}^{N}\tilde y_i\alpha_iK_{i2}\\ s.t.\quad \alpha_1\tilde y_1+\alpha_2\tilde y_2=-\sum_{i=3}^{N}\tilde y_i\alpha_i=\gamma\\ 0 \le \alpha_i \le C,i=1,2 $

   其中 $ MathJax-Element-397 $ 为常数， 且目标函数式中省略了不含 $ MathJax-Element-454 $ 的常数项。

6.1.1 取值范围约束

1. $ MathJax-Element-454 $ 的约束条件为：

   • 当 $ MathJax-Element-409 $ 异号时， $ MathJax-Element-454 $ 位于直线 $ MathJax-Element-402 $ ，且在矩形范围内。矩形的长为 $ MathJax-Element-504 $ ，宽为 $ MathJax-Element-504 $ ， 起始点坐标为(0,0) ： 此时 $ MathJax-Element-490 $ 和 $ MathJax-Element-492 $ 的取值范围为：

     • 当 $ MathJax-Element-407 $ 时（上面那条线）：

       $ \gamma \le \alpha_2 \le C\\ 0\le\alpha_1\le C-\gamma $

     • 当 $ MathJax-Element-408 $ 时（下面那条线）：

       $ 0 \le \alpha_2 \le C-\gamma\\ \gamma\le\alpha_1\le C $

   • 当 $ MathJax-Element-409 $ 同号时， $ MathJax-Element-454 $ 位于直线 $ MathJax-Element-411 $ ，且在矩形范围内。矩形的长为 $ MathJax-Element-504 $ ，宽为 $ MathJax-Element-504 $ ， 起始点坐标为(0,0) ：

     此时 $ MathJax-Element-454 $ 取值范围为：

     • 当 $ MathJax-Element-431 $ 时：（上面那条线）
     $ \gamma-C \le \alpha_2 \le C\\ \gamma-C \le \alpha_1 \le C $

     • 当 $ MathJax-Element-433 $ 时：（下面那条线）

       $ 0 \le \alpha_2 \le \gamma\\ 0 \le \alpha_1 \le \gamma $

2. 假设 $ MathJax-Element-490 $ 的最优解为 $ MathJax-Element-473 $ ，其初始可行解为 $ MathJax-Element-419 $ ； $ MathJax-Element-492 $ 的初始可行解为 $ MathJax-Element-421 $ 。

   • 既然是初始可行解，则需要满足约束条件。因此有

     $ |\alpha_1^{old}-\alpha_2^{old}|=\gamma,\quad \text{if } \tilde y_1\ne \tilde y_2\\ \alpha_1^{old}+\alpha_2^{old}=\gamma,\quad \text{if } \tilde y_1 = \tilde y_2 $

   • 假设 $ MathJax-Element-473 $ 的取值范围为 $ MathJax-Element-423 $ ，则有：

     • 当 $ MathJax-Element-424 $ 时：

       若 $ MathJax-Element-425 $ ，则 $ MathJax-Element-426 $ ；若 $ MathJax-Element-427 $ ，则 $ MathJax-Element-428 $ 。

       根据：

       $ \gamma=|\alpha_1^{old}-\alpha_2^{old}|=\begin{cases} \alpha_2^{old}-\alpha_1^{old},&\text{if} \;\alpha_2^{old}\ge \alpha_1^{old}\\ \alpha_1^{old}-\alpha_2^{old},&\text{else} \end{cases} $

       则有： $ MathJax-Element-429 $ 。

     • 当 $ MathJax-Element-430 $ 时：

       若 $ MathJax-Element-431 $ ，则 $ MathJax-Element-432 $ ；若 $ MathJax-Element-433 $ ， 则 $ MathJax-Element-434 $ 。

       根据 $ MathJax-Element-435 $ ，则有： $ MathJax-Element-436 $

6.1.2 解析解

1. 令 $ MathJax-Element-437 $ 。它表示解得 $ MathJax-Element-438 $ 参数之后，对 $ MathJax-Element-439 $ 的预测值。预测值的正负代表了分类的结果。

   令 $ MathJax-Element-440 $ 。

   • $ MathJax-Element-496 $ 表示 $ MathJax-Element-442 $ 的预测值与真实输出 $ MathJax-Element-443 $ 之差。
   • $ MathJax-Element-484 $ 表示 $ MathJax-Element-445 $ 的预测值与真实输出 $ MathJax-Element-446 $ 之差。

2. 根据 $ MathJax-Element-447 $ ，将 $ MathJax-Element-448 $ 代入 $ MathJax-Element-449 $ 中。

   求解 $ MathJax-Element-450 $ ，即可得到 $ MathJax-Element-490 $ 的最优解（不考虑约束条件）：

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

   其中：

   • $ MathJax-Element-452 $
     
   • $ MathJax-Element-453 $ 中的 $ MathJax-Element-454 $ 分别为 $ MathJax-Element-465 $ （它们表示初始的可行解，用于消掉 $ MathJax-Element-456 $ ）。

3. 将 $ MathJax-Element-457 $ 截断，则得到 $ MathJax-Element-473 $ 的解析解为：

   $ \alpha_2^{new}=\begin{cases} H, & \alpha_2^{new,unc} \gt H\\ \alpha_2^{new,unc}, & L \le \alpha_2^{new,unc} \le H\\ L, & \alpha_2^{new,unc} \lt L \end{cases} $

   其中 $ MathJax-Element-465 $ 为初始可行解， $ MathJax-Element-473 $ 为最终解。

4. 根据 $ MathJax-Element-461 $ ，以及 $ MathJax-Element-462 $ ，得到 $ MathJax-Element-466 $ ：

   $ MathJax-Element-464 $ 。

   其中 $ MathJax-Element-465 $ 为初始可行解， $ MathJax-Element-466 $ 为最终解。

6.2 变量选择

1. SMO 算法在每个子问题中选择两个变量进行优化，其中至少一个变量是违反约束条件的。如果都不违反约束条件，则说明已经求解了。

6.2.1 外层循环

1. 第一个变量的选择过程称为外层循环。

2. 外层循环在训练样本中选择违反约束条件最严重的样本点，并将对应的变量作为第一个变量。

   具体来讲，就是检验训练样本点 $ MathJax-Element-467 $ 是否满足约束条件(KKT条件)：

   $ \alpha_i=0 \Leftrightarrow \tilde y_ig(\mathbf {\vec x}_i)\ge 1\\ 0 \lt \alpha_i \lt C \Leftrightarrow \tilde y_ig(\mathbf {\vec x}_i)=1\\ \alpha_i=C \Leftrightarrow \tilde y_ig(\mathbf {\vec x}_i) \le 1 $

   其中， $ MathJax-Element-524 $ 。

3. 检验时：

   • 外层循环首先遍历所有满足条件 $ MathJax-Element-469 $ 的样本点，即间隔边界上的支持向量点。
   • 如果这些样本点都满足条件，再遍历整个训练集，检验是否满足条件。

6.2.2 内存循环

1. 第二个变量的选择过程称为内层循环。

2. 假设已经在外层循环中找到第一个变量 $ MathJax-Element-492 $ ， 现在要在内层循环中找到第二个变量 $ MathJax-Element-490 $ 。第二个变量选择标准是希望能够使得 $ MathJax-Element-490 $ 有足够大的变化。

3. 由前面式子可知， $ MathJax-Element-473 $ 依赖于 $ MathJax-Element-474 $ 。一种简单的做法是选择 $ MathJax-Element-490 $ ，使得对应的 $ MathJax-Element-476 $ 最大。因为 $ MathJax-Element-492 $ 已经确定， $ MathJax-Element-496 $ 也已经确定。

   • 如果 $ MathJax-Element-496 $ 为正数，则选择最小的 $ MathJax-Element-508 $ 作为 $ MathJax-Element-484 $ 。
   • 如果 $ MathJax-Element-496 $ 为负数，则选择最大的 $ MathJax-Element-508 $ 作为 $ MathJax-Element-484 $ 。

   为了节省计算时间，可以将所有 $ MathJax-Element-508 $ 值保存在一个列表中。

4. 特殊情况下，若内层循环找到的 $ MathJax-Element-490 $ 不能使得目标函数有足够的下降，则采用以下的启发式规则继续选择 $ MathJax-Element-490 $ ：

   • 遍历在间隔边界上的支持向量点，依次将其对应的变量作为 $ MathJax-Element-490 $ 试用，直到目标函数有足够的下降。
   • 若还是找不到合适的 $ MathJax-Element-490 $ ，则遍历训练数据集寻找。
   • 若还是找不到合适的 $ MathJax-Element-490 $ ，则放弃找到的 $ MathJax-Element-492 $ ，再通过外层循环寻求另外的 $ MathJax-Element-492 $ 。

6.2.3 参数更新

1. 每次完成两个变量的优化后，都要重新计算 $ MathJax-Element-493 $ 。根据约束条件有：

   • 当 $ MathJax-Element-494 $ 时： $ MathJax-Element-495 $ 。

     代入 $ MathJax-Element-496 $ 的定义式有： $ MathJax-Element-497 $ 。

   • 同样，当 $ MathJax-Element-498 $ 时有： $ MathJax-Element-499 $ 。

   • 如果 $ MathJax-Element-500 $ 同时满足 $ MathJax-Element-501 $ ，则有： $ MathJax-Element-502 $

   • 如果 $ MathJax-Element-503 $ 或者为 0，或者为 $ MathJax-Element-504 $ ，则 $ MathJax-Element-505 $ 区间内的数都可以作为 $ MathJax-Element-509 $ 。此时一个选择是：

     $ b^{new}=\frac{b_1^{new}+b_2^{new}}{2} $

2. 每次完成两个变量的优化后，需要更新对应的 $ MathJax-Element-508 $ 值。 $ MathJax-Element-508 $ 的更新要用到 $ MathJax-Element-509 $ 以及所有支持向量对应的 $ MathJax-Element-510 $ 。

6.3 SMO算法

1. SMO 算法：

   • 输入：

     • 训练数据集 $ MathJax-Element-511 $ ，其中 $ MathJax-Element-512 $
     • 精度 $ MathJax-Element-521 $

   • 输出：近似解 $ MathJax-Element-514 $

   • 算法步骤：

     • 取初值 $ MathJax-Element-515 $ ， $ MathJax-Element-516 $

     • 选取优化变量 $ MathJax-Element-517 $ ，解析求解两个变量的最优化问题，求得最优解 $ MathJax-Element-518 $ ，更新 $ MathJax-Element-519 $ 为 $ MathJax-Element-520 $ 。

     • 若在精度 $ MathJax-Element-521 $ 范围内满足停机条件：

       $ \sum_{i=1}^{N}\alpha_i\tilde y_i=0\\ 0 \le \alpha_i \le C,i=1,2,\cdots,N\\ \tilde y_ig(\mathbf {\vec x}_i)=\begin{cases} \ge 1, & \alpha_i=0 \\ =1, & 0 \lt \alpha_i \lt C \\ \le 1, & \alpha_i = C \end{cases} $

       则退出迭代并令 $ MathJax-Element-522 $ ；否则令 $ MathJax-Element-523 $ ，继续迭代。

       其中 $ MathJax-Element-524 $ 。