支持向量机原理详解(七): 序列最小最优化(SMO)演算法(Part II)

接前文序列最小最优化(SMO)演算法(Part I)，本文继续介绍SMO演算法，内容如下：

阈值的更新
差值的更新，Error Cache
SMO演算法流程总结

10.5 阈值的更新

前文提到，通过求解两变数QP子问题得到的最优解 $alpha_1^{new}, alpha_2^{new}$ 未必满足KKT条件：

$egin{align} alpha_i = 0 &Rightarrow y_id_igeq 1\ 0< alpha_i < C &Rightarrow y_id_i = 1\ alpha_i = C &Rightarrow y_id_ileq 1\ end{align}$

为此，在每一步优化完两个变数 (得到 $alpha_1^{new}, alpha_2^{new}$ )后，都要更新 $d_i=sum_{j=1}^{N}{y_j alpha_j k_{ji}} + b$ 中的阈值 ，目的是使刚才这一步优化的两个样本 满足KKT条件。

关于的更新，需要根据 $alpha_1^{new}, alpha_2^{new}$ 的取值分情况讨论，具体如下：

(一)若 $0<alpha_1^{new}<C$

则根据KKT条件 $y_1 d_1 = y_1 left( sum_{j=1}^{N}{y_j k_{j1}alpha_j} + b ight)=1$ 来更新，此时有

$b_1^{new}=y_1-sum_{j=3}^{N}{y_j k_{j1} alpha_j^{old}} - y_1 k_{11} alpha_1^{new}- y_2 k_{21} alpha_2^{new}$

又因为 $E_1^{old} = d_1^{old}-y_1= sum_{j=1}^{N}{y_j k_{j1} alpha_j^{old}} +b^{old}- y_1$ ，代入上式得

$egin{align} b_1^{new}&=-E_1^{old}+ y_1 k_{11} alpha_1^{old}+ y_2 k_{21} alpha_2^{old}- y_1 k_{11} alpha_1^{new}- y_2 k_{21} alpha_2^{new}+b^{old}\ &=-E_1^{old}- y_1 k_{11} left(alpha_1^{new}-alpha_1^{old} ight)- y_2 k_{21} left( alpha_2^{new}- alpha_2^{old} ight)+b^{old} ag{1} \ end{align}$

按(1)式更新后，满足KKT条件；此时另一个样本也是满足KKT条件的。这一点可结合下面第(三)种情况的 $b_1^{new}=b_2^{new}$ 来说明：若 $0<alpha_1^{new}<C, alpha_2^{new}inleft{ 0,C ight}$ ，则根据 $alpha_2^{new}$ 的KKT条件，应有 $b_2^{new}leq b_1^{new}$ 或 $b_2^{new}geq b_1^{new}$ ，也就是说 $b_1^{new}$ 也能使 $alpha_2^{new}$ 对应的样本满足KKT条件。所以当 $0<alpha_1^{new}<C$ 时，按(1)式更新即可，不需要再根据 $alpha_2^{new}$ 的值进一步讨论。

(二)若 $0<alpha_2^{new}<C$

则根据 $y_2 d_2 = y_2 left( sum_{j=1}^{N}{y_j alpha_j k_{j2}} + b ight)=1$ 来更新，和(一)类似，有

$egin{align} b_2^{new}=-E_2^{old}- y_1 k_{12} left(alpha_1^{new}-alpha_1^{old} ight)- y_2 k_{22} left( alpha_2^{new}- alpha_2^{old} ight)+b^{old} ag{2}\ end{align}$

(三)若 $0<alpha_1^{new}<C quad and quad 0<alpha_2^{new}<C$

则(1)和(2)计算出的 $b_1^{new}=b_2^{new}$ 。

关于 $b_1^{new},b_2^{new}$ 为何相等，参考文献[1-4]均省略了推导。这里我们来证明一下。

首先， $alpha_1^{new}, alpha_2^{new}$ 均不在边界上，说明 $alpha_2^{new}$ 未经过修剪， $alpha_2^{new}=alpha_2^{unclipped}$ ；因为如果修剪过，则 $alpha_1^{new}, alpha_2^{new}$ 至少有一个在边界上。

然后，由两变数QP子问题的等式约束(见前文)有：

$alpha_1^{new} - alpha_1^{old}=-y_1y_2left( alpha_2^{new}-alpha_2^{old} ight)$

将上式代入(1)和(2)，同时结合前文的(6)式，有

$egin{align} &b_1^{new}=b_2^{new}\ &Leftrightarrow -E_1^{old}+ y_2 k_{11} left(alpha_2^{new}-alpha_2^{old} ight)- y_2 k_{21} left( alpha_2^{new}- alpha_2^{old} ight)\ & =-E_2^{old}+ y_2 k_{12} left(alpha_2^{new}-alpha_2^{old} ight)- y_2 k_{22} left( alpha_2^{new}- alpha_2^{old} ight)\ &Leftrightarrow y_2left( k_{11}+k_{22}-2k_{12} ight) left(alpha_2^{new}-alpha_2^{old} ight) = E_1^{old}-E_2^{old}\ &Leftrightarrow alpha_2^{new}=alpha_2^{old}+frac{y_2left( E_1^{old}-E_2^{old} ight)}{k_{11}+k_{22}-2k_{12}}\ &Leftrightarrow alpha_2^{new}=alpha_2^{unclipped} ag{3}end{align}$

(3)式成立，所以 $b_1^{new}=b_2^{new}$ 得证。

(四)若 $alpha_1^{new}, alpha_2^{new}in left{ 0, C ight} quad and quad L e H$

则 $b_1^{new},b_2^{new}$ 之间的值都能使两个样本满足KKT条件，取 $b^{new} = frac{1}{2}left( b_1^{new}+b_2^{new} ight)$ 。

至于为什么 $b_1^{new},b_2^{new}$ 之间的值都能使两个样本满足KKT条件，参考文献也都没有解释。这里我们来推导一下。

(实际上，Platt1998, 1999里给出的这个条件非常重要，但文献[3][4]中似乎省略了。)

前文已推导，若，则 $L=maxleft(0, alpha_1^{old}+alpha_2^{old}-C ight), H=minleft( C, alpha_1^{old}+alpha_2^{old} ight)$ ；

若，则 $L=maxleft(0, alpha_2^{old}-alpha_1^{old} ight), H=minleft( C, alpha_2^{old}-alpha_1^{old}+C ight)$ 。

所以分以下四种情况讨论：

当 $alpha_1^{new}=alpha_2^{new}=0$ 时，若，则有

$egin{align} &y_1alpha_1^{new} + y_2alpha_2^{new}= y_1alpha_1^{old}+y_2alpha_2^{old}\ &Rightarrow alpha_1^{new}+y_1y_2alpha_2^{new}=alpha_1^{old}+y_1y_2alpha_2^{old}\ &Rightarrow alpha_1^{old}+alpha_2^{old}=alpha_1^{new}+alpha_2^{new}=0\ &Rightarrow L=H=0 end{align}$

所以如果，只能是，异号。由KKT条件

$y_1 d_1 = y_1 left( sum_{j=1}^{N}{y_j k_{j1}alpha_j} + b ight)geq 1\ y_2 d_2 = y_2 left( sum_{j=1}^{N}{y_j k_{j2}alpha_j} + b ight)geq 1$

因为异号，所以上面两个不等式会形成一个在 $b_1^{new}, b_2^{new}$ 之间的闭区间，这个区间内的值都能使两个样本满足KKT条件。在SMO中，这种情况取 $b^{new} = frac{1}{2}left( b_1^{new}+b_2^{new} ight)$ 。

同理，当 $alpha_1^{new}=alpha_2^{new}=C$ 时，若，则 $alpha_1^{old}+alpha_2^{old}=2CRightarrow L=H=C$ ，

所以，异号，KKT条件同样形成一个闭区间。

当 $alpha_1^{new}=0, alpha_2^{new}=C$ 时，若，则

$egin{align} &alpha_1^{new}+y_1y_2alpha_2^{new}=alpha_1^{old}+y_1y_2alpha_2^{old}\ &Rightarrow alpha_1^{old}-alpha_2^{old}=alpha_1^{new}-alpha_2^{new}=-C\ &Rightarrow L=H=C end{align}$

所以如果，只能是，同号。KKT条件形成一个在 $b_1^{new}, b_2^{new}$ 之间的闭区间，这个区间内的值都能使两个样本满足KKT条件。

当 $alpha_1^{new}=C, alpha_2^{new}=0$ 时，若，则 $alpha_1^{old}-alpha_2^{old}=CRightarrow L=H=0$ ；

所以，同号，KKT条件形成一个闭区间。

至于为什么采用这个奇怪的条件，可能是因为这样程序更简洁吧。。。

<关于 $alpha_1^{new}, alpha_2^{new}in left{ 0, C ight} quad and quad L= H$ 的情况>

这种情况Platt1998, 1999并没有提及，但其给出的伪代码的takeStep()函数中有语句

$Compute L, H\ {f if} (L==H) \ {f return} 0$

说明计算后，先判断两者是否相等，如果相等就直接return了，没有对这两个变数的QP子问题进行解析求解。

个人猜测：和前面类似可推导，这种情况下两个样本的KKT条件形成一个单侧无界区间，需根据具体情况比较 $b_1^{new},b_2^{new}$ 的大小，程序上更新略显繁琐。所以在Platt的伪代码中，如果则跳过这一步的子问题。

10.6 差值的更新，Error Cache

在根据启发式规则选择第二个优化变数时，需要用到样本的差值。差值的更新(或者说计算)发生在每一步优化完两个变数 $alpha_1^{new}, alpha_2^{new}$ 并更新阈值之后。

由定义，有

$egin{align} E_i^{new}=d_i^{new}-y_i&=sum_{j=1}^{N}{y_j k_{ji} alpha_j^{new}} + b^{new} -y_i\ &=sum_{support\vectors}{y_j k_{ji} alpha_j^{new}} + b^{new} -y_i\ end{align}\ ag{4}$

(4)式就是文献[3][4]中给出的公式。

Platt1999中给出了更新(non-bound样本的)差值的另一公式，下面进行推导。因为

$egin{align} E_i^{new}=d_i^{new}-y_i&=sum_{j=3}^{N}{y_j k_{ji} alpha_j^{old}} + y_1 k_{1i} alpha_1^{new}+y_2 k_{2i} alpha_2^{new}+b^{new} -y_i\ end{align}\ ag{5}$

又

$egin{align} E_i^{old}=d_i^{old}-y_i&=sum_{j=1}^{N}{y_j k_{ji} alpha_j^{old}}+b^{old} -y_i\&=sum_{j=3}^{N}{y_j k_{ji} alpha_j^{old}} + y_1 k_{1i} alpha_1^{old}+y_2 k_{2i} alpha_2^{old}+b^{old} -y_i ag{6}\ end{align}\$

所以由(5)(6)两式得，

$egin{align} E_i^{new}=E_i^{old} + y_1 k_{1i} (alpha_1^{new}-alpha_1^{old})+y_2 k_{2i} (alpha_2^{new}-alpha_2^{old})+b^{new}-b^{old} ag{7}\ end{align}$

文献[3][4]提到，保存所有样本的可以节省计算时间，按这个意思应该采用(7)式。。。

不过根据Platt1998, 1999，只保存non-bound样本的，而不保存bound样本的；当需要用到时，如果是non-bound样本，就到error cache(误差缓存)里查找；如果是bound样本，就用决策函数和当前的来计算(具体公式未给出，推测应该是(4)式)。

在每一步优化之后的两个变数，如果是non-bound，则将其保存的差值设置为0，因为 $y_id_i^{new}=1Rightarrow d_i^{new} = y_i Rightarrow E_i^{new}=d_i^{new}-y_i=0$ 。而对于未参与这一步优化的其他non-bound样本，根据(7)式更新其。

个人理解：Platt1998, 1999中，只保存non-bound样本的是为了节省存储空间，因为最终non-bound样本只占训练集的一小部分；而bound的样本，尤其是的样本(非支持向量)占大部分。此外，在一次交替遍历中，non-bound子集会多次遍历直至收敛，而bound子集只遍历一次。

10.7 SMO演算法流程总结

根据参考文献[1-4]，将SMO演算法流程简单总结如下：

(1)初始化；给定精度，一般可取 $10^{-3}$ ~ $10^{-2}$ ；

初值满足停机条件中的等式约束，所以接下来每一步优化都会满足这个等式约束；
关于的初始化，文献里没有具体提到，Platt1999的伪代码中是赋初值为0；
个人认为阈值的初值影响不大，因为是无约束的，第一步优化后就根据KKT条件更新了。

(2)按启发式规则选取一对优化变数，记为；解析求解两变数QP子问题，得到最优解并更新；然后更新，；

(3)在精度内检查是否满足停机条件；

若满足，则转(4)；
若不满足，则回到(2)，继续按启发式规则选择变数进行优化。

(4)得到问题的最优解，SVM训练完成，退出程序。

To be continued...

参考文献

[1] John C. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. Technical Report MSR-TR-98-14, Microsoft Research, 1998.

[2] John C. Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods - Support Vector Learning. B. Scholkopf, C. J. C. Burges, and A. J. Smola, Eds. MIT Press, Cambridge, MA, 1999: 185-208.

[3] 李航，统计学习方法，清华大学出版社，北京，2012年。第7章。

[4] 邓乃扬，田英杰，数据挖掘中的新方法——支持向量机，科学出版社，北京，2004年。

[5] Osuna, E., Freund, R., Girosi, F., An improved training algorithm for support vector machines. Proc. IEEE NNSP 』97, 1997.