支持向量机（五）——SMO算法

〇、说明

支持向量机(Support Vector Machine,SVM)是监督学习中非常经典的算法。笔者主要参考学习的是李航老师《统计学习方法（第二版）》[1]和周志华老师的西瓜书《机器学习》[2]。

如有错误疏漏，烦请指正。如要转载，请联系笔者，hpfhepf@gmail.com。

关于这个算法，读者可以参考算法发明者Platt的原始论文[3][4]。知乎文章《支持向量机原理详解(六): 序列最小最优化(SMO)算法》[5][6]系列也是关于SMO算法不错的文章，读者可一并参考阅读。

一、SMO算法简介

1.1 为什么

支持向量机的学习是一个凸二次规划问题，凸二次规划问题问题具有全局最优解，有许多最优化算法可以用于这一问题。但当训练样本容量很大时，这些算法往往变得比较低效。目前有很多支持向量机的快速实现算法，序列最小最优化（Sequential Minimal Optimization，SMO）算法就是其中一个。[1]

1.2 SMO算法思路

1. 在支持向量机的对偶问题优化中，每一轮迭代，将其它变量看作常数，只优化其中两个变量。

2. 每一轮迭代，启发式地选择优化量最大的两个变量进行优化。

二、SMO算法详述

支持向量机的对偶优化问题如下

优化问题一：

$\begin{split}&\mathop{min}\limits_{\alpha} \ &\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} \\& s.t. & \sum_{i=1}^N \alpha_{i} y_{i}=0 \\&& 0\leq \alpha_{i} \leq C \ \ i=1,2,\dots,N\end{split} \tag{1}$

优化目标是找到使目标函数最小的拉格朗日乘子向量 $\alpha^*=(\alpha^*_{1},\alpha^*_{2},\dots,\alpha^*_{N})^T$ 。

2.1 两个变量的优化方法

每一轮迭代中，假设已选择的两个变量是 $\alpha_{1}$ 和 $\alpha_{2}$ ，其它变量 $\alpha_{i}(i=3,4,\dots,N)$ 是固定的。则式 $(1)$ 表示的优化问题可以写成

优化问题二：

$\begin{split}& \mathop{min}\limits_{\alpha_{1},\alpha_{2}} \ \ & W(\alpha_{1},\alpha_{2})= \frac{1}{2} K_{11} \alpha^2_{1} + \frac{1}{2} K_{22} \alpha^2_{2} + y_{1}y_{2}K_{12}\alpha_{1} \alpha_{2} \\&& \qquad - (\alpha_{1} + \alpha_{2}) + y_{1}\alpha_{1} \sum_{i=3}^N y_{i} \alpha_{i}K_{i1} + y_{2}\alpha_{2} \sum_{i=3}^N y_{i} \alpha_{i}K_{i2} \\& s.t. & \alpha_{1} y_{1} + \alpha_{2} y_{2} = - \sum_{i=3}^N \alpha_{i} y_{i}=\varsigma \\&& 0\leq \alpha_{i} \leq C \ \ i=1,2 \end{split} \tag{2}$

其中， $K_{ij}=K(x_{i},x_{j})$ ， $\varsigma$ 是常数，优化目标函数省略了不含 $\alpha_{1}$ 和 $\alpha_{2}$ 的常数项。

等式约束决定了这个优化问题是一个单变量优化问题，这里考虑为变量 $\alpha_{2}$ 的优化问题。

第一步，求解未经剪辑的最优解

定义

$g(x)=\sum_{i=1}^N \alpha_{i} y_{i} K(x_{i},x)+b \tag{3}$

$E_{i}=g(x_{i}) - y_{i} = (\sum_{j=1}^N \alpha_{j} y_{j} K(x_{j},x_{i})+b)-y_{i} \tag{4}$

$v_{i}= \sum_{i=3}^N \alpha_{j} y_{j} K(x_{i},x_{j}) = g(x_{i}) - \sum_{j=1}^2 \alpha_{j} y_{j} K(x_{i},x_{j})-b \tag{5}$

则目标函数可写为

$\begin{split}W(\alpha_{1},\alpha_{2})= & \frac{1}{2}K_{11} \alpha^2_{1}+\frac{1}{2}K_{22}\alpha^2_{2}+y_{1}y_{2}K_{12}\alpha_{1}\alpha_{2}\\ &-(\alpha_{1}+\alpha_{2})+y_{1}v_{1}\alpha_{1}+y_{2}v_{2}\alpha_{2} \end{split} \tag{6}$

由 $\alpha_{1} y_{1}+\alpha_{2} y_{2} = \varsigma$ 可得 $\alpha_{1} = y_{1}(\varsigma -\alpha_{2} y_{2})$ ，代入上式，目标函数可表示为单变量 $\alpha_{2}$ 的目标函数

$\begin{split}W(\alpha_{2})= & \frac{1}{2}K_{11} (\varsigma -\alpha_{2 } y_{2})^2+\frac{1}{2}K_{22}\alpha^2_{2}+y_{2}K_{12}(\varsigma -\alpha_{2} y_{2})\alpha_{2}\\ &-(y_{1}(\varsigma -\alpha_{2}y_{2})+\alpha_{2})+v_{1}(\varsigma -\alpha_{2}y_{2})+y_{2}v_{2}\alpha_{2} \end{split} \tag{7}$

对 $\alpha_{2}$ 求导

$\begin{split}\frac{\partial}{\partial \alpha_{2}} W(\alpha_{2})= & y_{2} K_{11} (\alpha_{2} y_{2} -\varsigma )+K_{22} \alpha_{2} + y_{2} K_{12} (\varsigma -\alpha_{2} y_{2}) \\& + y_{2} K_{12} (-y_{2}) \alpha_{2} + y_{1} y_{2} -1 - v_{1} y_{2} + y_{2} v_{2} \\= & (K_{11}+K_{22}-2K_{12}) \alpha_{2} +y_{2} \varsigma(K_{12} - K_{11}) \\& + y_{1} y_{2} -1 - v_{1} y_{2} + y_{2} v_{2} \\\end{split} \tag{8}$

令其为0，得到

$\alpha_{2} = \frac{1}{K_{11}+K_{22}-2K_{12}} y_{2}(y_{2}-y_{1}+v_{1}-v_{2}+K_{11}\varsigma -K_{12}\varsigma ) \tag{9}$

将等号左边 $\alpha_{2}$ 用 $\alpha^{new,unc}$ 代替，等号右边代入 $v_{i},i=1,2$ 和 $\varsigma = \alpha^{old}_{1} y_{1} + \alpha^{old}_{2} y_{2}$ ，并令 $\eta =K_{11}+K_{22}-2K_{12}$ ，则有

$\begin{split}\alpha^{new,unc}_{2} = & \frac{1}{\eta} y_{2}[y_{2} - y_{1} + K_{11} \alpha^{old}_{1} y_{1} + K_{11} \alpha^{old}_{2} y_{2} - K_{12} \alpha^{old}_{1} y_{1} - K_{12} \alpha^{old}_{2} y_{2} \\ & + (g(x_{1})-K_{11} \alpha^{old}_{1} y_{1} - K_{12} \alpha^{old}_{2} y_{2} - b) \\& - (g(x_{2}) - K_{12} \alpha^{old}_{1} y_{1} - K_{22} \alpha^{old}_{2} y_{2} - b)] \\= & \frac{1}{\eta} y_{2}[(K_{11} + K_{22} - 2K_{12}) y_{2} \alpha^{old}_{2} + (g(x_{1}) - y_{1}) - (g(x_{2}) - y_{2})] \\= & \alpha^{old}_{2} + \frac{1}{\eta} y_{2}(E_{1} - E_{2})\end{split} \tag{10}$

即

$\alpha^{new,unc}_{2} = \alpha^{old}_{2} + \frac{1}{\eta} y_{2}(E_{1} - E_{2})\tag{11}$

这里需要注意， $\eta =K_{11}+K_{22}-2K_{12} = ||\phi (x_{1}) - \phi(x_{2})||^2$ 。

第二步，确定剪辑边界

两个变量 $(\alpha_{1},\alpha_{2})$ 的约束，如下图所示

图1[4]

式 $(2)$ 不等式约束使得 $\alpha_{1}$ 和 $\alpha_{2}$ 正方形 $[0,C]\times [0,C]$ 内，等式约束使得它们在平行于正方形对角线的直线上。

如上所述，优化问题二（式 $(2)$ ）实质上是一个但变量优化问题，同样，我们为考虑 $\alpha_{2}$ 的优化问题。由于 $\alpha^{new}_{2}$ 需要满足不等式约束，所以有

$L \leq \alpha^{new}_{2} \leq H \tag{12}$

由式 $(2)$ 的等式约束 $\alpha_{1} y_{1} + \alpha_{2} y_{2} = \varsigma$ ，当 $y_{1} \neq y_{2}$ 时， $\alpha_{1} - \alpha_{2} = \gamma$ （ $\gamma$ 是一个常数，满足 $|\gamma |=|\varsigma |$ ），则有

$L = max(0,-\gamma ),\quad H=min(C,C-\gamma ) \tag{13}$

当 $y_{1} = y_{2}$ 时， $\alpha_{1} + \alpha_{2} = \gamma$ ，则有

$L = max(0,\gamma - C),\quad H=min(C,\gamma ) \tag{14}$

第三步，剪辑优化结果

综上所述，经剪辑后的 $\alpha_{2}$ 为

$\alpha^{new}_{2} = \begin{cases}H, & \alpha^{new,unc}_{2} > H \\\alpha^{new,unc}_{2}, & L \leq \alpha^{new,unc}_{2} \leq H \\L, & \alpha^{new,unc}_{2} </p><p><b>第四步，求解<img class=$

根据式 $(2)$ 的等式约束，求解 $\alpha^{new}_{1}$

$\alpha^{new}_{1}=\alpha^{old}_{1} +y_{1} y_{2}(\alpha^{old}_{2} - \alpha^{new}_{2}) \tag{16}$

2.2 第一个待优化变量选择

SMO算法称选择第一个优化变量的过程为外层循环。每次只选择两个变量进行优化，那如何选择呢？

支持向量机是凸优化问题，满足KKT条件的点是支持向量机优化问题的解[7]。

线性支持向量机的符合KKT条件如下

$\begin{align}& y_{i}(w^*\cdot x_{i}+b^*)\geq 1-\xi^* _{i},\ i=1,2,\dots,N \tag{17a}\\& \xi^*_{i} \geq 0, \ i=1,2,\dots,N \tag{17b} \\& \alpha^*_{i} \geq 0, \ i=1,2,\dots,N \tag{17c} \\& \alpha^*_{i}(y_{i}(w^*\cdot x_{i}+b^*)-1+\xi^*_{i})=0,\ i=1,2,\dots,N \tag{17d} \\& \mu^*_{i}\xi^*_{i}=0, \ i=1,2,\dots,N \tag{17e}\\& \frac{\partial}{\partial w} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=w^*-\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i}=0 \tag{17f} \\& \frac{\partial}{\partial b} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=-\sum_{i=1}^N \alpha^*_{i}y_{i}=0 \tag{17g} \\& \frac{\partial}{\partial \xi_{i}} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=C-\alpha^*_{i}-\mu^*_{i}=0 , \ i=1,2,\dots,N\tag{17h} \end{align}$

将式 $(16d)$ 、 $(16e)$ 、 $(16f)$ 和 $(16h)$ 单独拿出来，如下

$\begin{align}& \alpha^*_{i}(y_{i}(w^*\cdot x_{i}+b^*)-1+\xi^*_{i})=0,\ i=1,2,\dots,N \\& \mu^*_{i}\xi^*_{i}=0, \ i=1,2,\dots,N \\& \frac{\partial}{\partial w} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=w^*-\sum_{i=1}^N \alpha^*_{i}y_{i}x_{i}=0 \\& \frac{\partial}{\partial \xi_{i}} L(w^*,b^*,\xi^*;\alpha^*,\mu^*)=C-\alpha^*_{i}-\mu^*_{i}=0 , \ i=1,2,\dots,N \end{align} \tag{18}$

由上式可推导出

$\begin{align} \alpha^*_{i}=0 & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}(x_{i} \cdot x_{j})+b^*) \geq1 \\ 0< \alpha^*_{i} <1 & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}(x_{i} \cdot x_{j})+b^*) =1 \\ \alpha^*_{i}=C & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}(x_{i} \cdot x_{j})+b^*) \leq1\end{align} \tag{19}$

这里需要注意，上式中，“ $\Rightarrow$ ”在李航老师《统计学习方法（第二版）》中，使用的是“ $\Leftrightarrow$ ”，这个是不严谨的。替换成核函数版本，如下

$\begin{align} \alpha^*_{i}=0 & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}K(x_{i} , x_{j})+b^*) \geq1 \\ 0< \alpha^*_{i} <1 & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}K(x_{i} , x_{j})+b^*) =1 \\ \alpha^*_{i}=C & \Rightarrow y_{i}(\sum_{j=1}^N\alpha^*_{j}y_{j}K(x_{i} , x_{j})+b^*) \leq1\end{align} \tag{20}$

代入 $g(x_{i})$ 的定义，在优化过程中， $\alpha=(\alpha_{1},\alpha_{2},\dots,\alpha_{N})^T$ 不是最优解，所以，验证条件应表述为

$\begin{align} \alpha_{i}=0 & \Rightarrow y_{i} g(x_{i}) \geq1 \\ 0< \alpha_{i} <1 & \Rightarrow y_{i} g(x_{i}) =1 \\ \alpha_{i}=C & \Rightarrow y_{i} g(x_{i}) \leq1\end{align} \tag{21}$

这就是SMO算法选择第一个优化变量的条件，也是停机条件。

第一个优化变量的选择方法：首先遍历满足 $0 < \alpha_{i} < C$ 的样本点，检验它们是否满足式 $(6b)$ ；如果这些样本点都不满足约束，则遍历 $\alpha_{i}=0$ 和 $\alpha_{i} = C$ 的样本点，检验是否符合式 $(6a)$ 和 $(6c)$ 的约束。

这里需要注意，在下面选择第二个优化变量时，有可能会抛弃一选择的第一个变量，重新选择第一个变量，详见下文。

2.3 第二个优化变量选择

SMO算法称选择第二个优化变量的过程为内层循环。假设已经找到了第一个优化变量 $\alpha_{1}$ 。第二个优化变量 $\alpha_{2}$ 的选择标准是希望这个变量有足够大的变化。

第一种方式

由式 $(11)$ 可知， $\alpha^{new}_{2}$ 是依赖于 $|E_{1}-E_{2}|$ 的，为了加快计算速度，可以选择使之最大的 $\alpha_{1}$ ，一般来讲就是选择与 $E_{1}$ 符号相反，绝对值最大 $E_{i}$ 对应的 $\alpha_{i}$ 作为第二个优化变量。

通常，为了加快速度， $E_{i}$ 保存在一个列表里。

第二种方式

特殊情况下，如果内层循环找到的 $\alpha_{2}$ 不能使目标函数有足够的下降，则采用另一种启发方式继续选择 $\alpha_{2}$ ：遍历在间隔边界上的支持向量点（满足 $0<\alpha_{i} <C$ 的样本），依次试用，直到目标函数有足够的下降。

如果还找不到合适的 $\alpha_{2}$ ，遍历所有数据集；如果仍然找不到，则放弃这个 $\alpha_{1}$ ，重新选择。

2.4 更新 $b$

为什么要更新 $b$ ，因为后面更新 $E_{i}$ 时要用到。在前面几篇笔记所述的支持向量机[b][c]理论中，参数 $b$ 是根据最优拉格朗日乘子 $\alpha^*$ 来计算的。但是在SMO算法中， $b$ 是跟随 $\alpha_{i}(i=1,2)$ 优化的变量。

如何优化参数 $b$ 呢，KKT条件就是优化的方向（符合KKT条件的解是最优解[5]）。因为是局部优化，需要先分别求解 $b^{new}_{1}$ 和 $b^{new}_{2}$ ，然后再求出 $b^{new}$ ，先求 $b^{new}_{1}$ ，根据式 $(21)$ ，当 $0<\alpha_{1} < C$ 时，

$\begin{split}b^{new}_{1} & = y_{1} - \sum_{i=1}^N \alpha_{i} y_{i} K_{i1} \\ &= y_{1} - \sum_{i=3}^N \alpha_{i} y_{i}K_{i1} - \alpha^{new}_{1} y_{1}K_{11} - \alpha^{new}_{2} y_{2} K_{12}\end{split}\tag{22}$

因为 $E_{1}$ 已经保存在列表里，可以利用其来计算 $b^{new}_{1}$ ，减少计算量。由 $E_{i}$ 定义可知

$\begin{split}E_{1} &= \sum_{i=1}^N \alpha_{i} y_{i}K_{i1} + b^{old} - y_{1} \\&= \sum_{i=3}^N \alpha_{i} y_{i} k_{i1} + \alpha^{old}_{1} y_{1} K_{11} + \alpha^{old}_{2} y_{2} K_{12} + b^{old} - y_{1}\end{split} \tag{23}$

可得

$y_{1} - \sum_{i=3}^N \alpha_{i} y_{i} K_{i1} = -E_{1} + \alpha^{old}_{1} y_{1} K_{11} + \alpha^{old}_{2} y_{2} K_{12} + b^{old} \tag{24}$

代入式 $(22)$ ，可得

$b^{new}_{1} = -E_{1} - y_{1} K_{11}(\alpha^{new}_{1} - \alpha^{old}_{1}) - y_{2} K_{12} (\alpha^{new}_{2} - \alpha^{old}_{2}) + b^{old} \tag{25}$

同理，当 $0<\alpha_{2} < C$ 时，有

$b^{new}_{2} = -E_{2} - y_{1} K_{12}(\alpha^{new}_{1} - \alpha^{old}_{1}) - y_{2} K_{22} (\alpha^{new}_{2} - \alpha^{old}_{2}) + b^{old} \tag{26}$

通过 $b^{new}_{1}$ 和 $b^{new}_{2}$ 计算 $b^{new}$ ，分两种情况：

第一种情况

当 $0<\alpha^{new}_{i} <C,i=1,2$ 时， $b^{new}_{1} = b^{new}_{2}$ ，证明如下

将式 $(16)$ 的变形 $\alpha^{new}_{1} - \alpha^{old}_{1} = -y_{1} y_{2} (\alpha^{new}_{2} - \alpha^{old}_{2})$ 代入式 $(25)$ 和 $(26)$ ，计算

$\begin{split}b^{new}_{1} - b^{new}_{2} &= -(E_{1} - E_{2}) + y_{2} (K_{11} + K_{22} - 2K_{12})(\alpha^{new}_{2} - \alpha^{old}_{2}) \\&=y_{2}\eta (-\frac{y_{2}(E_{1} - E_{2})}{\eta} - \alpha^{old}_{2} + \alpha^{new}_{2}) \\&= y_{2}\eta (\alpha^{new}_{2} - \alpha^{new,unc}_{2})\end{split} \tag{27}$

上式中， $\eta = K_{11} + K_{22} -2K_{12}$ 。当 $0<\alpha^{new}_{i} <C,i=1,2$ 时， $\alpha^{new}_{2}$ 在约束边界内，剪辑前后相同，所以有

$b^{new}_{1} - b^{new}_{2} = 0 \tag{28}$

此时，

$b^{new} = b^{new}_{1} \tag{29}$

第二种情况

当 $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在边界上，且 $L\neq H$ 时，第一种情况求得的值还可以继续使用。 $b^{new}_{1}$ 和 $b^{new}_{2}$ 以及它们之间的数都符合KKT条件（因为证明较复杂，且用到后面的知识，证明放在附录），选择他们的中点作为 $b^{new}$ ，也即

$b^{new} = \frac{1}{2}(b^{new}_{1} + b^{new}_{2}) \tag{30}$

这里需要注意，这里有一个 $L\neq H$ 的条件。为什么有这样一个条件？如下图，当 $L = H$ 时，直线 $\alpha_{1} - \alpha_{2} = \gamma$ 或 $\alpha_{1} + \alpha_{2} = \gamma$ 在约束范围内退化成一个点（读者可自己证明），没有优化的空间，这样的 $(\alpha_{1},\alpha_{2})$ 需要重新选择。

图2

2.5 更新 $E_{i}$

如前所述，挑选和计算 $\alpha^{new}_{2}$ 时，都会用到 $E_{i}$ 。每次迭代都需要更新 $E_{i}$ ，以备下一轮迭代使用。

根据 $E_{i}$ 的定义（式 $(4)$ ），有

$E^{old}_{i} = \sum_{j=3}^N \alpha_{j} y_{j} k_{ij} + \alpha^{old}_{1} y_{1} K_{1i} + \alpha^{old}_{2} y_{2} K_{2i} + b^{old} - y_{i}\tag{31}$

$E^{new}_{i} = \sum_{j=3}^N \alpha_{j} y_{j} k_{ij} + \alpha^{new}_{1} y_{1} K_{1i} + \alpha^{new}_{2} y_{2} K_{2i} + b^{new} - y_{i}\tag{32}$

变换式 $(31)$ 和式 $(32)$ 可得

$E^{new}_{i} = E^{old}_{i} + y_{1}K_{1i}(\alpha^{new}_{1} - \alpha^{old}_{1}) + y_{2} K_{2i}(\alpha^{new}_{2} - \alpha^{old}_{2}) + b^{new} - b^{old} \tag{33}$

可以证明（读者可自行证明），当 $0<\alpha^{new}_{i} <C,i=1,2$ 时，

$E^{new}_{i} = 0 \tag{34}$

原始论文中[4]，作者表示式 $(33)$ 用来更新没有参与优化且不在边界上的支持向量对应的 $E_{i}$ ，也即更新除 $\alpha_{1}$ 和 $\alpha_{2}$ 以外且 $0<\alpha_{i} <C$ 对应的 $E_{i}$ 。

但我认为，当 $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在边界上，不符合式 $(34)$ ，此时至少有一个参与优化的变量对应的 $E_{i}$ 也需要更新。

三、SMO算法总结

第一步，给定精度参数 $\varepsilon$ ，初始化 $\alpha = \boldsymbol 0$ ， $b=0$ 。

第二步，按照2.2节和2.3节选择优化变量，按照2.1节解析求解优化问题，更新这两个变量。

第三步，按照2.4节和2.5节更新 $b$ 和 $E_{i}$ 。

第四步，在精度 $\varepsilon$ 范围内检查是否满足KKT条件（式 $(21)$ ）：若满足，则转第五步；不满足，则转第二步。

第五步，得到最优解 $\alpha^*,b^*$ 。

这里，精度 $\varepsilon$ 内检查读者可参看参考资料[6]。

四、附录

A、 $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在边界上时 $b^{new}$ 符合KKT条件的证明

重复正文2.4节的结论：当 $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在边界上，且 $L\neq H$ 时， $b^{new}_{1}$ 和 $b^{new}_{2}$ 以及它们之间的数都符合KKT条件。

这里参考[8]予以证明。

如正文2.5节所述，当 $0<\alpha^{new}_{i} < C, i=1,2$ 时， $E^{new}_{i} = 0, i=1,2$ 。但当 $(\alpha^{new}_{1},\alpha^{new}_{2})$ 在剪辑边界上时，也即 $\alpha^{new}_{1}$ 和 $\alpha^{new}_{2}$ 至少有一个为0或 $C$ 。当某一个变量为0或C时， $E^{new}_{i},i=1,2$ 不一定为0。更一般的，我们暂时认为它们不为0。由正文式 $(33)$ ，有

$E^{new}_{1} = E^{old}_{1} + y_{1}K_{11}(\alpha^{new}_{1} - \alpha^{old}_{1}) + y_{2} K_{12}(\alpha^{new}_{2} - \alpha^{old}_{2}) + \Delta b \tag{a1}$

$E^{new}_{2} = E^{old}_{2} + y_{1}K_{12}(\alpha^{new}_{1} - \alpha^{old}_{1}) + y_{2} K_{22}(\alpha^{new}_{2} - \alpha^{old}_{2}) + \Delta b \tag{a2}$

当变量在边界时，经过剪辑，由正文式 $(11)$ ，有

$\alpha^{new}_{2} - \alpha^{old}_{2} = \frac{1}{\eta} \lambda y_{2}(E^{old}_{1} - E^{old}_{2}) \tag{a3}$

其中， $0 \leq \lambda \leq 1$ ， $\eta = K_{11} +K_{22} - 2K_{12}$ 。又由正文式 $(16)$ ，有

$\alpha^{new}_{1} - \alpha^{old}_{1} = -y_{1} y_{2}(\alpha^{new}_{2} - \alpha^{old}_{2}) \tag{a4}$

将式 $(a3)$ 代入式 $(a4)$ ，可得

$\alpha^{new}_{1} - \alpha^{old}_{1} = -\frac{1}{\eta} \lambda y_{1} (E^{old}_{1} - E^{old}_{2}) \tag{a5}$

将式 $(a3)$ 和式 $(a5)$ 代入正文式 $(25)$ ，有

$\begin{split}b^{new}_{1} &= -E^{old}_{1} - y_{1} K_{11}(\alpha^{new}_{1} - \alpha^{old}_{1}) - y_{2} K_{12} (\alpha^{new}_{2} - \alpha^{old}_{2}) + b^{old} \\&= - E^{old}_{1} + \frac{1}{\eta} \lambda K_{11} (E^{old}_{1} - E^{old}_{2}) - \frac{1}{\eta} \lambda K_{12} (E^{old}_{1} - E^{old}_{2}) + b^{old}\\&=-E^{old}_{1} + \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) + b^{old}\end{split} \tag{a6}$

同理有

$b^{new}_{2} = -E^{old}_{2} + \frac{1}{\eta} \lambda (K_{12} - K_{22})(E^{old}_{1} - E^{old}_{2}) + b^{old} \tag{a7}$

构造 $b^{new}$ 如下，其中 $0 \leq t \leq 1$ ，使得 $b^{new}$ 在 $b^{new}_{1}$ 和 $b^{new}_{2}$ 之间

$b^{new} = tb^{new}_{1} + (1-t)b^{new}_{2} \tag{a8}$

将式 $(a6)$ 和式 $(a7)$ 代入式 $(a8)$ ，构造 $\Delta b$ ，有

$\begin{split}\Delta b &= & b^{new} - b^{old} \\&= & tb^{new}_{1} + (1 - t) b^{new}_{2} - b^{old} \\&= & t(-E^{old}_{1} + \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) + b^{old}) \\&& + (1 - t)(-E^{old}_{2} + \frac{1}{\eta} \lambda (K_{12} - K_{22})(E^{old}_{1} - E^{old}_{2}) + b^{old}) - b^{old} \\&= & t(-E^{old}_{1} + \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) ) \\&& + (1 - t)(-E^{old}_{2} + \frac{1}{\eta} \lambda (K_{12} - K_{22})(E^{old}_{1} - E^{old}_{2}) ) \end{split} \tag{a9}$

将式 $(a3)$ 、式 $(a4)$ 和式 $(a9)$ 代入式 $(a1)$ ，可得

$\begin{split}E^{new}_{1} &=& E^{old}_{1} + y_{1}K_{11}(\alpha^{new}_{1} - \alpha^{old}_{1}) + y_{2} K_{12}(\alpha^{new}_{2} - \alpha^{old}_{2}) + \Delta b \\&=& E^{old}_{1} - \frac{1}{\eta} \lambda K_{11}(E^{old}_{1} - E^{old}_{2}) + \frac{1}{\eta} \lambda K_{12}(E^{old}_{1} - E^{old}_{2}) + \Delta b \\&=& E^{old}_{1} - \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) + \Delta b \\&=& E^{old}_{1} - \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2}) \\&& + t(-E^{old}_{1} + \frac{1}{\eta} \lambda (K_{11} - K_{12})(E^{old}_{1} - E^{old}_{2})) \\&& +(1 - t)(-E^{old}_{2} + \frac{1}{\eta} \lambda (K_{12} - K_{22})(E^{old}_{1} - E^{old}_{2})) \\&=& E^{old}_{1} - E^{old}_{2} - t(E^{old}_{1} - E^{old}_{2}) \\&& - \frac{1}{\eta} \lambda (K_{11} - 2K_{12} + K_{22})(E^{old}_{1} - E^{old}_{2}) \\&& + \frac{1}{\eta} \lambda t (K_{11} - 2K_{12} + K_{22})(E^{old}_{1} - E^{old}_{2}) \\&=& (1 - t - \lambda + \lambda t)(E^{old}_{1} - E^{old}_{2}) \\&=& (1 - t)(1 - \lambda)(E^{old}_{1} - E^{old}_{2})\end{split}\tag{a10}$

同理可得

$E^{new}_{2} = - t (1 - \lambda)(E^{old}_{1} - E^{old}_{2}) \tag{a11}$

当 $\alpha^{new}_{2} = 0$ 时

$\begin{split} & \alpha^{new}_{2} - \alpha^{old}_{2} \leq 0 \\ \Leftrightarrow \quad &\frac{1}{\eta} \lambda y_{2} (E^{old}_{1} - E^{old}_{2}) \leq 0 \\\Leftrightarrow \quad & y_{2}(E^{old}_{1} - E^{old}_{2}) \leq 0 \\\Leftrightarrow \quad & y_{2}(-t (1 - \lambda)(E^{old}_{1} - E^{old}_{2})) \geq 0 \\\Leftrightarrow \quad & y_{2} E^{new}_{2} \geq 0 \\\Leftrightarrow \quad & y_{2}(g(x_{2}) - y_{2}) \geq 0 \\\Leftrightarrow \quad & y_{2}g(x_{2}) \geq 1\end{split} \tag{a12}$

符合正文式 $(21)$ KKT条件。

当 $\alpha^{new}_{2} = C$ 时

$\begin{split} & \alpha^{new}_{2} - \alpha^{old}_{2} \geq 0 \\ \Leftrightarrow \quad &\frac{1}{\eta} \lambda y_{2} (E^{old}_{1} - E^{old}_{2}) \geq 0 \\\Leftrightarrow \quad & y_{2}(-t (1 - \lambda)(E^{old}_{1} - E^{old}_{2})) \leq 0 \\\Leftrightarrow \quad & y_{2} E^{new}_{2} \leq 0 \\\Leftrightarrow \quad & y_{2}g(x_{2}) \leq 1\end{split} \tag{a13}$