SMO序列最小最优化算法

SMO算法实际上用于SVM对偶问题求解中 α ∗ \boldsymbol{\alpha^*} α∗的确定。根据之前的推导，当求得 α ∗ \boldsymbol{\alpha^*} α∗使得对偶问题取得最大值时，即对偶问题取得最优解，同样的也是原始问题的最优解。SMO方法事实上和坐标上升/梯度下降的方法有所相似，都是固定部分变量，更新所需要的变量，不断迭代直至收敛的一种方法。

变量更新

首先，需要更新参数。为方便，注意到 max ⁡ L ( w , b , ξ , α , β ) = max ⁡ ∑ i = 1 n α i − 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j x i ⊤ x j \max L(\boldsymbol{w}, b,\boldsymbol{\xi},\boldsymbol{\alpha},\boldsymbol{\beta}) = \max\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 \boldsymbol{x_i}^\top \boldsymbol{x_j} maxL(w,b,ξ,α,β)=max∑i=1n​αi​−21​∑i=1n​∑j=1n​αi​αj​yi​yj​xi​⊤xj​中存在 x i ⊤ x j \boldsymbol{x_i}^\top \boldsymbol{x_j} xi​⊤xj​在后续的算法过程中将其写成内积的形式，记为 K i , j K_{i, j} Ki,j​（其实是前面提到过的核函数的形式…后续再进行引入）。
假设从 ( α 1 , α 2 ) (\alpha_1, \alpha_2) (α1​,α2​)开始，将其他变量固定，因此需要保留与 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​有关的变量，设M为与 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​无关的变量，由于固定，将其视作常数。此外，约束也要转换为对 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​的约束。得到如下的有约束的关于 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​的函数：
W ( α 1 , α 2 )   = α 1 + α 2 − 1 2 α 1 2 y 1 2 K 1 , 1 − 1 2 α 2 2 y 2 2 K 2 , 2 − α 1 α 2 y 1 y 2 K 1 , 2 − α 1 y 1 ∑ i = 3 n α i y i K 1 , i − α 2 y 2 ∑ i = 3 n α i y i K 2 , i + ∑ i = 3 n α i − 1 2 ∑ i = 3 n ∑ j = 3 n α i α j y i y j K i , j s . t .   0 ≤ α 1 ≤ C 0 ≤ α 2 ≤ C ∑ i n α i y i = 0 (1) \begin{aligned} W(\alpha_1, \alpha_2)\ =&\alpha_1+\alpha_2-\frac{1}{2}\alpha_1^2y_1^2K_{1,1}- \frac{1}{2}\alpha_2^2y_2^2K_{2,2}-\alpha_1\alpha_2y_1y_2K_{1,2}-\alpha_1y_1\sum_{i=3}^{n}\alpha_iy_iK_{1,i}\\ &-\alpha_2y_2\sum_{i=3}^{n}\alpha_iy_iK_{2,i} + \sum_{i=3}^{n}\alpha_i - \frac{1}{2}\sum_{i=3}^{n}\sum_{j=3}^{n}\alpha_i\alpha_jy_iy_jK_{i, j}\\ s.t.\ \quad &0 \le \alpha_1 \le C\\ &0 \le \alpha_2 \le C\\ &\sum_{i}^{n}\alpha_iy_i=0\tag1 \end{aligned} W(α1​,α2​) =s.t. ​α1​+α2​−21​α12​y12​K1,1​−21​α22​y22​K2,2​−α1​α2​y1​y2​K1,2​−α1​y1​i=3∑n​αi​yi​K1,i​−α2​y2​i=3∑n​αi​yi​K2,i​+i=3∑n​αi​−21​i=3∑n​j=3∑n​αi​αj​yi​yj​Ki,j​0≤α1​≤C0≤α2​≤Ci∑n​αi​yi​=0​(1)

其中，为表示方便，将与 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​无关的部分用字母表示，即记:
v 1 = ∑ i = 3 n α i y i K 1 , i v 2 = ∑ i = 3 n α i y i K 2 , i M = ∑ i = 3 n α i − 1 2 ∑ i = 3 n ∑ j = 3 n α i α j y i y j K i , j \begin{aligned} v_1 &= \sum_{i=3}^{n}\alpha_iy_iK_{1,i}\\ v_2 &= \sum_{i=3}^{n}\alpha_iy_iK_{2,i}\\ M &= \sum_{i=3}^{n}\alpha_i - \frac{1}{2}\sum_{i=3}^{n}\sum_{j=3}^{n}\alpha_i\alpha_jy_iy_jK_{i, j} \end{aligned} v1​v2​M​=i=3∑n​αi​yi​K1,i​=i=3∑n​αi​yi​K2,i​=i=3∑n​αi​−21​i=3∑n​j=3∑n​αi​αj​yi​yj​Ki,j​​

则函数1可写为：
W ( α 1 , α 2 )   = α 1 + α 2 − 1 2 α 1 2 y 1 2 K 1 , 1 − 1 2 α 2 2 y 2 2 K 2 , 2 − α 1 α 2 y 1 y 2 K 1 , 2 − α 1 y 1 v 1 − α 2 y 2 v 2 + M (2) \begin{aligned} W(\alpha_1, \alpha_2)\ =\alpha_1+\alpha_2-\frac{1}{2}\alpha_1^2y_1^2K_{1,1}- \frac{1}{2}\alpha_2^2y_2^2K_{2,2}-\alpha_1\alpha_2y_1y_2K_{1,2}-\alpha_1y_1v_1-\alpha_2y_2v_2 + M\tag2 \end{aligned} W(α1​,α2​) =α1​+α2​−21​α12​y12​K1,1​−21​α22​y22​K2,2​−α1​α2​y1​y2​K1,2​−α1​y1​v1​−α2​y2​v2​+M​(2)

此时存在 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​两个变量，需要根据两个变量之间的关系更新变量的值。设如公式1的优化问题初始的可行解为 ( α 1 o l d , α 2 o l d ) (\alpha_1^{old},\alpha_2^{old}) (α1old​,α2old​)，最优解为 α 1 n e w , α 2 n e w ) \alpha_1^{new},\alpha_2^{new}) α1new​,α2new​)需要确定可行解和最优解的范围。
而根据之前的约束，可以得到 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​之间的关系如公式3所示，并且可绘制出如下图所示的在定义域内的关系图。
α 1 y 1 + α 2 y 2 = − ∑ i = 3 n α i y i = ζ ⇒ α 1 y 1 y 2 + α 2 y 2 2 = y 2 ζ ⇒ α 1 = − y 1 y 2 α 2 + y 1 ζ (3) \begin{aligned} &\alpha_1y_1+\alpha_2y_2 = -\sum_{i=3}^{n}\alpha_iy_i = \zeta \\ &\Rightarrow \alpha_1y_1y_2+\alpha_2y_2^2 = y_2\zeta\\ &\Rightarrow \alpha_1 = -y_1y_2\alpha_2 + y_1\zeta\tag3 \end{aligned} ​α1​y1​+α2​y2​=−i=3∑n​αi​yi​=ζ⇒α1​y1​y2​+α2​y22​=y2​ζ⇒α1​=−y1​y2​α2​+y1​ζ​(3)

由图可知，最优值位于正方形内的一条线段上，又因为 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​之间存在关系，优化问题可以从原来的多变量优化问题转换为单变量的最优化问题。并且假设在上述两种情况中下界为L，上界为H，则，最优解 α 1 n e w \alpha_1^{new} α1new​的取值范围为：
L ≤ α 1 n e w ≤ H L \le \alpha_1^{new} \le H L≤α1new​≤H

其中，若 y 1 y 2 = − 1 y_1y_2 = -1 y1​y2​=−1，则 L = max ⁡ { 0 , y i ζ } , H = min ⁡ { C , C + y i ζ } L = \max\{0, y_i\zeta\}, H = \min\{C, C+y_i\zeta\} L=max{0,yi​ζ},H=min{C,C+yi​ζ},转换成用初始的可行解表示为 L = max ⁡ { 0 , α 1 o l d − α 2 o l d } , H = min ⁡ { C , C + α 1 o l d − α 2 o l d } L = \max\{0, \alpha_1^{old} - \alpha_2^{old}\}, H = \min\{C, C+\alpha_1^{old} - \alpha_2^{old}\} L=max{0,α1old​−α2old​},H=min{C,C+α1old​−α2old​}；若 y 1 y 2 = 1 y_1y_2 = 1 y1​y2​=1，则 L = max ⁡ { 0 , α 1 o l d + α 2 o l d − C } , H = min ⁡ { C , α 1 o l d + α 2 o l d } L = \max\{0, \alpha_1^{old}+\alpha_2^{old}-C\}, H = \min\{C, \alpha_1^{old}+\alpha_2^{old}\} L=max{0,α1old​+α2old​−C},H=min{C,α1old​+α2old​}。
确定了最优值的上下界后，将 α 1 = − y 1 y 2 α 2 + y 1 ζ \alpha_1 = -y_1y_2\alpha_2 + y_1\zeta α1​=−y1​y2​α2​+y1​ζ代入原公式，将其转换为单变量的优化问题。
W ( α 2 ) = − y 1 y 2 α 2 + y 1 ζ + α 2 − 1 2 ( − y 1 ( y 2 α 2 − ζ ) ) ) 2 y 1 2 K 1 , 1 − 1 2 α 2 2 y 2 2 K 2 , 2 + ( y 1 y 2 α 2 − y 1 ζ ) α 2 y 1 y 2 K 1 , 2 + ( y 1 y 2 α 2 − y 1 ζ ) y 1 v 1 − α 2 y 2 v 2 + M = − y 1 y 2 α 2 + y 1 ζ + α 2 − 1 2 y 1 2 ( y 2 2 α 2 2 − 2 y 2 ζ + ζ 2 ) y 1 2 K 1 , 1 − 1 2 α 2 2 y 2 K 2 , 2 + y 1 2 y 2 2 α 2 2 K 1 , 2 − y 1 2 y 2 ζ α 2 K 1 , 2 + y 1 2 y 2 α 2 v 1 − α 2 y 2 v 2 − y 1 2 ζ v 1 + M = α 2 2 ( − 1 2 K 1 , 1 − 1 2 K 2 , 2 + K 1 , 2 ) + α 2 y 2 ( y 2 − y 1 + ζ K 1 , 1 − ζ K 1 , 2 + v 1 − v 2 ) − y 1 2 ζ v 1 + M (4) \begin{aligned} W(\alpha_2) =&-y_1y_2\alpha_2+y_1\zeta+\alpha_2-\frac{1}{2}(-y_1(y_2\alpha_2-\zeta)))^2y_1^2K_{1,1}-\frac{1}{2}\alpha_2^2y_2^2K_{2,2}\\ &+(y_1y_2\alpha_2-y_1\zeta)\alpha_2y_1y_2K_{1,2}+(y_1y_2\alpha_2-y_1\zeta)y_1v_1-\alpha_2y_2v_2+M\\ =&-y_1y_2\alpha_2+y_1\zeta+\alpha_2-\frac{1}{2}y_1^2(y_2^2\alpha_2^2-2y_2\zeta+\zeta^2)y_1^2K_{1,1}-\frac{1}{2}\alpha_2^2y_2K_{2,2}\\ &+y_1^2y_2^2\alpha_2^2K_{1,2}-y_1^2y_2\zeta\alpha_2K_{1,2}+y_1^2y_2\alpha_2v_1-\alpha_2y_2v_2-y_1^2\zeta v1+M\\ =&\alpha_2^2(-\frac{1}{2}K_{1,1}-\frac{1}{2}K_{2,2}+K_{1,2})+\alpha_2y_2(y_2-y_1+\zeta K_{1,1}-\zeta K_{1,2}+v_1-v_2)\\ &-y_1^2\zeta v_1+M\tag4 \end{aligned} W(α2​)===​−y1​y2​α2​+y1​ζ+α2​−21​(−y1​(y2​α2​−ζ)))2y12​K1,1​−21​α22​y22​K2,2​+(y1​y2​α2​−y1​ζ)α2​y1​y2​K1,2​+(y1​y2​α2​−y1​ζ)y1​v1​−α2​y2​v2​+M−y1​y2​α2​+y1​ζ+α2​−21​y12​(y22​α22​−2y2​ζ+ζ2)y12​K1,1​−21​α22​y2​K2,2​+y12​y22​α22​K1,2​−y12​y2​ζα2​K1,2​+y12​y2​α2​v1​−α2​y2​v2​−y12​ζv1+Mα22​(−21​K1,1​−21​K2,2​+K1,2​)+α2​y2​(y2​−y1​+ζK1,1​−ζK1,2​+v1​−v2​)−y12​ζv1​+M​(4)

因为要求最优解，因此对 α 2 \alpha_2 α2​求偏导得到：
∂ W ( α 2 ) ∂ α 2 = α 2 ( − K 1 , 1 − K 2 , 2 + 2 K 1 , 2 ) + y 2 ( y 2 − y 1 + ζ K 1 , 1 − ζ K 1 , 2 + v 1 − v 2 ) = 0 ⇒ α 2 n e w ′ ( K 1 , 1 + K 2 , 2 − 2 K 1 , 2 ) = y 2 ( y 2 − y 1 + ζ K 1 , 1 − ζ K 1 , 2 + v 1 − v 2 ) (5) \begin{aligned} \frac{\partial W(\alpha_2)}{\partial \alpha_2} &= \alpha_2(-K_{1,1}-K_{2,2}+2K_{1,2})+y_2(y_2-y_1+\zeta K_{1,1}-\zeta K_{1,2}+v_1-v_2) = 0 \\ &\Rightarrow \alpha_2^{new'}(K_{1,1}+K_{2,2}-2K_{1,2}) = y_2(y_2-y_1+\zeta K_{1,1}-\zeta K_{1,2}+v_1-v_2)\tag5 \end{aligned} ∂α2​∂W(α2​)​​=α2​(−K1,1​−K2,2​+2K1,2​)+y2​(y2​−y1​+ζK1,1​−ζK1,2​+v1​−v2​)=0⇒α2new′​(K1,1​+K2,2​−2K1,2​)=y2​(y2​−y1​+ζK1,1​−ζK1,2​+v1​−v2​)​(5)

由于我们需要利用初始的可行解求得最优解，因此需要将等式右边转换成带可行解的，方便更新的式子。首先将 ζ = α 1 y 1 + α 2 y 2 \zeta = \alpha_1y_1+\alpha_2y_2 ζ=α1​y1​+α2​y2​代入公式中。
α 2 n e w ( K 1 , 1 + K 2 , 2 − K 1 , 2 ) = y 2 ( y 2 − y 1 + ( α 1 y 1 + α 2 y 2 ) K 1 , 1 + ( α 1 y 1 − α 2 y 2 ) K 1 , 2 + v 1 − v 2 ) = y 2 ( y 2 − y 1 + α 1 o l d y 1 ( K 1 , 1 − K 1 , 2 ) + α 2 o l d y 2 ( K 1 , 1 − K 1 , 2 ) + v 1 − v 2 ) (6) \begin{aligned} \alpha_2^{new}(K_{1,1}+K_{2,2}-K_{1,2}) &= y_2(y_2-y_1+(\alpha_1y_1+\alpha_2y_2)K_{1,1}+(\alpha_1y_1-\alpha_2y_2)K_{1,2}+v_1-v_2)\\ &=y_2(y_2-y_1+\alpha_1^{old}y_1(K_{1,1}-K_{1,2})+\alpha_2^{old}y_2(K_{1,1}-K_{1,2})+v_1-v_2)\tag6 \end{aligned} α2new​(K1,1​+K2,2​−K1,2​)​=y2​(y2​−y1​+(α1​y1​+α2​y2​)K1,1​+(α1​y1​−α2​y2​)K1,2​+v1​−v2​)=y2​(y2​−y1​+α1old​y1​(K1,1​−K1,2​)+α2old​y2​(K1,1​−K1,2​)+v1​−v2​)​(6)

看到这个式子，尤其是右边也有 K 1 , 1 K_{1,1} K1,1​和 K 1 , 2 K_{1,2} K1,2​应该考虑如果要是有 K 2 , 2 K_{2,2} K2,2​就好了，说不定能够凑够系数，把右边的系数约去呢（数学敏感性）！那么这个 K 2 , 2 K_{2,2} K2,2​哪里来呢？又注意到我们的 v 1 v_1 v1​和 v 2 v_2 v2​原来是为了方便表示，其实也是有原因的。
我们将所构建的模型是得到的预测值记为 f ( x ) f(x) f(x)，并将之前求得的 w \boldsymbol{w} w表达式代入模型表达式中得到：
f ( x ) = w ⊤ x + b = ∑ i = 1 n α i y i x ⊤ x + b = ∑ i = 1 n α i y i K x i , x + b (7) \begin{aligned} f(\boldsymbol{x}) &= \boldsymbol{w^\top}\boldsymbol{x}+b\\ &=\sum_{i=1}^{n}\alpha_iy_i\boldsymbol{x^\top}\boldsymbol{x}+b\\ &=\sum_{i=1}^{n}\alpha_iy_iK_{x_i, x}+b\tag7 \end{aligned} f(x)​=w⊤x+b=i=1∑n​αi​yi​x⊤x+b=i=1∑n​αi​yi​Kxi​,x​+b​(7)

f ( x 1 ) = ∑ i = 1 n α i y i K i , 1 + b = ∑ i = 1 n α i y i K i , 1 + b (8) \begin{aligned} f(\boldsymbol{x_1}) &=\sum_{i=1}^{n}\alpha_iy_iK_{i, 1}+b\\ &=\sum_{i=1}^{n}\alpha_iy_iK_{i, 1}+b\tag8 \end{aligned} f(x1​)​=i=1∑n​αi​yi​Ki,1​+b=i=1∑n​αi​yi​Ki,1​+b​(8)

f ( x 2 ) = ∑ i = 1 n α i y i K i , 1 + b = ∑ i = 1 n α i y i K i , 2 + b (9) \begin{aligned} f(\boldsymbol{x_2}) &=\sum_{i=1}^{n}\alpha_iy_iK_{i, 1}+b\\ &=\sum_{i=1}^{n}\alpha_iy_iK_{i, 2}+b\tag9 \end{aligned} f(x2​)​=i=1∑n​αi​yi​Ki,1​+b=i=1∑n​αi​yi​Ki,2​+b​(9)

根据公式7-9其实就可以从 v 1 v_1 v1​和 v 2 v_2 v2​中得到我们想要的。
v 1 = f ( x 1 ) − α 1 y 1 K 1 , 1 − α 2 y 2 K 1 , 2 v 2 = f ( x 2 ) − α 1 y 1 K 1 , 2 − α 2 y 2 K 2 , 2 (10) \begin{aligned} v_1=f(\boldsymbol{x_1}) - \alpha_1y_1K_{1,1}-\alpha_2y_2K_{1,2}\\ v_2=f(\boldsymbol{x_2}) - \alpha_1y_1K_{1,2}-\alpha_2y_2K_{2,2}\tag{10} \end{aligned} v1​=f(x1​)−α1​y1​K1,1​−α2​y2​K1,2​v2​=f(x2​)−α1​y1​K1,2​−α2​y2​K2,2​​(10)
将 v 1 v_1 v1​和 v 2 v_2 v2​的表达式公式10代入公式6中得到 α 2 n e w \alpha_2^{new} α2new​并可以根据 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​之间的关系得到 α 1 n e w \alpha_1^{new} α1new​。此外，预测值与实际值的差即为误差，我们将 E i E_i Ei​记为 f ( x i ) − y i f(\boldsymbol{x_i})-y_i f(xi​)−yi​。
α 2 n e w ′ ( K 1 , 1 + K 2 , 2 − 2 K 1 , 2 ) = y 2 ( y 2 − y 1 + α 1 o l d y 1 ( K 1 , 1 − K 1 , 2 ) + α 2 o l d y 2 ( K 1 , 1 − K 1 , 2 ) + f ( x 1 ) − α 1 y 1 K 1 , 1 − α 2 y 2 K 1 , 2 − f ( x 2 ) + α 1 y 1 K 1 , 2 + α 2 y 2 K 2 , 2 ) = y 2 ( y 2 − y 1 + f ( x 1 ) − f ( x 2 ) + α 2 o l d y 2 ( K 1 , 1 + K 2 , 2 − 2 K 1 , 2 ) ) (11) \begin{aligned} \alpha_2^{new'}(K_{1,1}+K_{2,2}-2K_{1,2}) =& y_2(y_2-y_1+\alpha_1^{old}y_1(K_{1,1}-K_{1,2})+\alpha_2^{old}y_2(K_{1,1}-K_{1,2})+f(x_1)\\ &- \alpha_1y_1K_{1,1}-\alpha_2y_2K_{1,2}-f(x_2) + \alpha_1y_1K_{1,2}+\alpha_2y_2K_{2,2})\\ =&y_2(y_2-y_1+f(x_1)-f(x_2)+\alpha_2^{old}y_2(K_{1,1}+K_{2,2}-2K_{1,2}))\tag{11} \end{aligned} α2new′​(K1,1​+K2,2​−2K1,2​)==​y2​(y2​−y1​+α1old​y1​(K1,1​−K1,2​)+α2old​y2​(K1,1​−K1,2​)+f(x1​)−α1​y1​K1,1​−α2​y2​K1,2​−f(x2​)+α1​y1​K1,2​+α2​y2​K2,2​)y2​(y2​−y1​+f(x1​)−f(x2​)+α2old​y2​(K1,1​+K2,2​−2K1,2​))​(11)

因此，可以得到 α 2 n e w \alpha_2^{new} α2new​的值如下：
α 2 n e w ′ = α 2 o l d + ( f ( x 1 ) − y 1 ) − ( f ( x 2 ) − y 2 ) K 1 , 1 + K 2 , 2 − 2 K 1 , 2 = α 2 o l d + ( E 1 − E 2 ) K 1 , 1 + K 2 , 2 − 2 K 1 , 2 (12) \begin{aligned} \alpha_2^{new'} &= \alpha_2^{old} + \frac{(f(x_1)-y_1)-(f(x_2)-y_2)}{K_{1,1}+K_{2,2}-2K_{1,2}}\\ &=\alpha_2^{old} + \frac{(E_1-E_2)}{K_{1,1}+K_{2,2}-2K_{1,2}}\tag{12} \end{aligned} α2new′​​=α2old​+K1,1​+K2,2​−2K1,2​(f(x1​)−y1​)−(f(x2​)−y2​)​=α2old​+K1,1​+K2,2​−2K1,2​(E1​−E2​)​​(12)

然而，此时的 ( α 1 n e w ′ , α 2 n e w ′ ) (\alpha_1^{new'}, \alpha_2^{new'}) (α1new′​,α2new′​)并不一定是更新以后的值，我们还要根据之前求得的值域来确定更新后的值，即：
α 2 n e w = { L , α 2 n e w ′ ≤ L α 2 n e w ′ , L ≤ α 2 n e w ′ ≤ H H , α 2 n e w ′ ≥ H \alpha_2^{new} = \left\{ \begin{array}{ll} L,&\alpha_2^{new'} \le L\\ \alpha_2^{new'},&L \le \alpha_2^{new'} \le H\\ H, &\alpha_2^{new'} \ge H \end{array} \right. α2new​=⎩⎨⎧​L,α2new′​,H,​α2new′​≤LL≤α2new′​≤Hα2new′​≥H​

再由 α 2 \alpha_2 α2​和 α 1 \alpha_1 α1​的关系可以得到：
α 1 n e w = α 1 o l d + y 1 y 2 ( α 2 o l d − α 2 n e w ) (13) \begin{aligned} \alpha_1^{new} = \alpha_1^{old}+y_1y_2(\alpha_2^{old}-\alpha_2^{new})\tag{13} \end{aligned} α1new​=α1old​+y1​y2​(α2old​−α2new​)​(13)

更新变量的选取

SMO算法需要选择一对变量进行迭代更新修正，很显然，对于违反KKT条件的点是我们需要进行更新的。因此，我们第一个变量选取违法KKT条件最严重的点。主要是支持向量对模型产生影响，则先遍历 0 ≤ α i ≤ C 0 \le \alpha_i \le C 0≤αi​≤C的样本点，检查是否违反KKT条件即是否满足 y i ( w ⊤ x + b ) = 1 y_i(\boldsymbol{w^\top}\boldsymbol{x}+b) = 1 yi​(w⊤x+b)=1。若都满足，则再考虑 α i = 0 \alpha_i=0 αi​=0时，是否满足 y i ( w ⊤ x + b ) ≥ 1 y_i(\boldsymbol{w^\top}\boldsymbol{x}+b) \ge 1 yi​(w⊤x+b)≥1和 α i = C \alpha_i =C αi​=C时，是否满足 y i ( w ⊤ x + b ) ≤ 1 y_i(\boldsymbol{w^\top}\boldsymbol{x}+b) \le 1 yi​(w⊤x+b)≤1。若遇到一个样本点不满足，则将其选为第一个变量。
而第二个变量，根据公式，我们希望更新更快，则需要步伐大一点，在第一个变量 α 1 \alpha_1 α1​确定后，要求第二个变量使得 ∣ E 1 − E 2 ∣ \vert E_1-E_2 \vert ∣E1​−E2​∣尽可能大。因此， E 1 ≥ 0 E_1\ge 0 E1​≥0时，选取最小的 E i E_i Ei​作为 E 2 E_2 E2​；而 E 1 ≤ 0 E_1 \le 0 E1​≤0时，则需要选取最大的 E i E_i Ei​作为 E 2 E_2 E2​

b b b和误差 E i E_i Ei​的计算

每更新一次后，都需要重新计算b和误差。然而，此时需要考虑 α \alpha α的值。根据KKT条件 0 ≤ α 1 n e w ≤ C 0 \leq \alpha_1^{new} \leq C 0≤α1new​≤C时可得 ξ 1 = 0 \xi_1 = 0 ξ1​=0那么， y 1 = w ⊤ x 1 + b y_1=\boldsymbol{w^\top}\boldsymbol{x_1}+b y1​=w⊤x1​+b，可求得 b 1 n e w b_1^{new} b1new​如下公式所示:
b 1 n e w = y 1 − w ⊤ x 1 = y 1 − ∑ i = 1 n α i y 1 K 1 , i = y 1 − ∑ i = 3 n α i y i K i , 1 − α 1 n e w y 1 K 1 , 1 − α 2 n e w y 2 K 2 , 1 \begin{aligned} b_1^{new}&= y_1- \boldsymbol{w^\top}\boldsymbol{x_1}\\ &=y_1-\sum_{i=1}^{n}\alpha_iy_1K_{1,i}\\ &=y_1-\sum_{i=3}^{n}\alpha_iy_iK_{i,1}-\alpha_1^{new}y_1K_{1,1}-\alpha_2^{new}y_2K_{2,1} \end{aligned} b1new​​=y1​−w⊤x1​=y1​−i=1∑n​αi​y1​K1,i​=y1​−i=3∑n​αi​yi​Ki,1​−α1new​y1​K1,1​−α2new​y2​K2,1​​

其实我们是并不希望在更新的时候看到 ∑ i = 3 n α i y i K i , 1 \sum_{i=3}^{n}\alpha_iy_iK_{i,1} ∑i=3n​αi​yi​Ki,1​的，而是希望通过能够根据旧的或者已知的参数去表示。此时看到 y 1 − ∑ i = 3 n α i y i K i , 1 y_1-\sum_{i=3}^{n}\alpha_iy_iK_{i,1} y1​−∑i=3n​αi​yi​Ki,1​有点眼熟，它和之前我们定义的误差很接近（数学敏感性!），因此我们将其转换为误差得到：
b 1 n e w = − E 1 + b o l d + y 1 K 1 , 1 ( α 1 o l d − α 1 n e w ) + y 2 K 2 , 1 ( α 2 o l d − α 2 n e w ) (14) \begin{aligned} b_1^{new} = -E_1+b^{old}+y_1K_{1,1}(\alpha_1^{old}-\alpha_1^{new})+y_2K_{2,1}(\alpha_2^{old} - \alpha_2^{new})\tag{14} \end{aligned} b1new​=−E1​+bold+y1​K1,1​(α1old​−α1new​)+y2​K2,1​(α2old​−α2new​)​(14)

同样的，当 0 ≤ α 2 n e w ≤ C 0 \leq \alpha_2^{new} \leq C 0≤α2new​≤C时，更新b为：
KaTeX parse error: No such environment: align at position 8: \begin{̲a̲l̲i̲g̲n̲}̲ \label{equa:b…

此时，问题来了，当 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​都满足是 ( 0 , C ) (0,C) (0,C)时， b b b应该如何更新呢？注意， b b b是对于每一对 ( α 1 , α 2 ) (\alpha_1,\alpha_2) (α1​,α2​)优化后进行更新，并不是求得 α 1 n e w \alpha_1^{new} α1new​进行更新，求得 α 2 n e w \alpha_2^{new} α2new​再更新一次。答案是，此时 b 1 n e w = b 2 n e w b_1^{new} = b_2^{new} b1new​=b2new​。因为在这种情况下，说明两个点都位于间隔边界上，此时的 w w w是确定的，同时到分割平面的距离都是1，所以是相等的。其实直接用公式也可以证明，直接将 ( α 1 n e w , α 2 n e w ) (\alpha_1^{new},\alpha_2^{new}) (α1new​,α2new​)和 ( α 1 o l d , α 2 o l d ) (\alpha_1^{old},\alpha_2^{old}) (α1old​,α2old​)代入公式14和公式15可以得到二者相等。
然而，上面讨论的是 ( 0 , C ) (0,C) (0,C)的情况，当取0和 C C C的时候呢？当 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​都取边界值时，仅有 y 1 y 2 = − 1 y_1y_2=-1 y1​y2​=−1时， α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​可以同时取 0 0 0或 C C C。而当 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​同时为0时，说明两个点均分类正确，假设 y 1 = 1 y_1 = 1 y1​=1， y 2 = − 1 y_2=-1 y2​=−1代入KKT条件得到：
b 1 n e w ≥ − E 1 + b o l d + y 1 K 1 , 1 ( α 1 o l d − α 1 n e w ) + y 2 K 2 , 1 ( α 2 o l d − α 2 n e w ) b 2 n e w ≤ − E 2 + b o l d + y 1 K 1 , 2 ( α 1 o l d − α 1 n e w ) + y 2 K 2 , 2 ( α 2 o l d − α 2 n e w ) \begin{aligned} b_1^{new} \ge -E_1+b^{old}+y_1K_{1,1}(\alpha_1^{old}-\alpha_1^{new})+y_2K_{2,1}(\alpha_2^{old} - \alpha_2^{new})\\ b_2^{new} \le -E_2+b^{old}+y_1K_{1,2}(\alpha_1^{old}-\alpha_1^{new})+y_2K_{2,2}(\alpha_2^{old} - \alpha_2^{new}) \end{aligned} b1new​≥−E1​+bold+y1​K1,1​(α1old​−α1new​)+y2​K2,1​(α2old​−α2new​)b2new​≤−E2​+bold+y1​K1,2​(α1old​−α1new​)+y2​K2,2​(α2old​−α2new​)​

如下图所示，其中两条虚线分别为 b 1 n e w b_1^{new} b1new​和 b 2 n e w b_2^{new} b2new​对应的分割超平面。两个平面一个向上移，一个向下移， b 1 n e w b_1^{new} b1new​和 b 2 n e w b_2^{new} b2new​都满足KKT条件则其中见也满足KKT条件。其他形式的边界值搭配也可以同样地代入到KKT条件中，并且进行解释。

然而，这样是有问题的，有可能两个平面移动的轨迹并不重合。对于SMO算法中的缺陷，Keerthi在论文中已经进行修改。当然，因为我们其实只是为了对b进行更新而已，在这种情况下，我们可以考虑不进行更新，也就是会慢一步。如果是轨迹有重合的部分，我们采用 b 1 n e w + b 2 n e w 2 \frac{b_1^{new}+b_2^{new}}{2} 2b1new​+b2new​​来对 b b b进行更新。若不考虑上面提出的Platt提出的传统SMO算法的缺陷，则应按照下式对 b b b进行更新：
b n e w = { b 1 n e w ,   0 ≤ α 1 n e w ≤ C b 2 n e w ,   0 ≤ α 2 n e w ≤ C b 1 n e w + b 2 n e w 2 ,   o t h e r s b^{new} = \left\{ \begin{array}{ll} b_1^{new},\ &0 \leq \alpha_1^{new} \leq C\\ b_2^{new},\ &0 \leq \alpha_2^{new} \leq C\\ \frac{b_1^{new}+b_2^{new}}{2},\ &others \end{array} \right. bnew=⎩⎨⎧​b1new​, b2new​, 2b1new​+b2new​​, ​0≤α1new​≤C0≤α2new​≤Cothers​

更新完b后，还需要对误差进行更新。记所有支持向量的集合为S，得到误差为：
E i n e w = ∑ S α j y j K i , j + b n e w − y i E_i^{new} = \sum_{S}\alpha_jy_jK_{i,j}+b^{new}-y_i Einew​=S∑​αj​yj​Ki,j​+bnew−yi​

最终，当 α i n e w − α i o l d ≤ ϵ \alpha_i^{new}-\alpha_i^{old} \le \epsilon αinew​−αiold​≤ϵ时，检查其是否满足KKT条件，若满足则停止迭代，否则继续迭代。

至此，SMO算法告一段落，修正后的SMO算法待后续补充。