序列最小最优化(Sequential Minimal Optimization, SMO)算法是一种对SVM参数进行求解的算法。互联网上针对SVM基础理论的文章已经很多了，从最大化最小类间隔，到拉格朗日乘数法求解不等式约束凸二次优化问题等。然而关于SMO算法介绍的还不是那么多，而且现有资料似乎不是很容易理解。所以这篇文章将会以尽量容易理解的方式来阐述SMO算法的一些细节。

简介

由于SVM本质上是一个不等式约束的二次规划(Quadratic Programming, QP)问题，而QP问题已经有一些算法进行最优化求解了。然而这些方法的效率都比较低，尤其是当训练数据规模庞大时，明明只有支持向量对参数取值有影响，但仍然需要对所有样本输入相互内积（或计算核函数值）。尽管可以将内积的结果（核函数值）缓存起来，但这种遍历的时间和空间开销仍然不小。于是John C. Platt在1998年就提出了SMO算法[1]。这种算法对于「SVM这种特殊约束形式（只有不等式约束、每个样本代表一个约束条件）」通过启发式搜索的方法能够快速逼近最优的拉格朗日乘数（即表征了样本是否为支持向量的参数）。

原始问题与对偶问题

SVM的原始问题可以看作是一个不等式约束凸二次优化问题：

$$\begin{align} \min_{w,b,\xi} ~~~~& \frac{1}{2}||w||^2+C\sum_{i=1}^N\xi_i & \\ s.t. ~~~~& y_i(w\cdot x_i+b)\geq 1 - \xi_i, & i=1,2,\dots,N \\ &\xi_i\geq0, &i=1,2,\dots,N \end{align}$$

对于这个不等式约束下的凸二次优化问题，我们可以通过拉格朗日对偶性来找到它的等价对偶问题：

$$\begin{align} \min_\alpha ~~~~& \frac{1}{2}\sum_{i=1}^N\sum_{j=1}^N\alpha_i\alpha_jy_iy_j(x_i\cdot x_j)-\sum_{i=1}^N\alpha_i \\ s.t. ~~~~& \sum_{i=1}^N\alpha_iy_i=0 \\ & 0\leq\alpha_i\leq C, ~~~~i=1,2,\dots,N \end{align}$$

关于这个对dual form的来源，可以参考之前的另一篇文章：求解SVM时为什么要最大化拉格朗日函数？

对于文章最后得到的极小极大问题，只需要交换$\min$和$\max$的位置，即将极小极大问题换成极大极小问题，就能得到它的对偶问题。再将其中的最优化部分展开，就能得到上面的对偶问题的形式。

理论上能够证明：对于SVM来说，对偶问题的最优解即是原始问题的最优解。

转化成对偶问题是有很多好处的。

首先，对于对偶问题，我们能够直接使用核技巧（Kernel Trick）来将核函数通过非常简单的方式（注意对偶问题中的$x_i\cdot x_j$）施加在原始问题中，从而能够将线性SVM变成利用各种不同核函数的非线性SVM。

另一方面，对偶问题的约束条件(只有一个equality constraint $\sum_{i=1}^N\alpha_i y_i=0$和一个boundary constraint $0\leq\alpha_i\leq C$)相比原始问题的约束条件($y_i(w\cdot x_i+b)-1\geq 0$)来说要简洁得多。而这个更加简洁的约束条件内部所蕴藏的特殊结构，使得SMO算法加速寻找最优解成为了可能。

SMO算法

SMO考虑到了对偶问题的两个约束条件。它是一个迭代式的算法，在每一次迭代时，会先从所有拉格朗日乘数(Lagrange Multiplier)中挑选出一个最值得优化的乘数，在满足约束条件的情况下调整这个乘数，使得被优化的函数朝着目标更进一步。于是这个迭代算法包含两个部分：1. 如何优化这个最值得优化的乘数。2. 如何选择最值得优化的乘数。

对双变量二次规划问题的求解

SMO将「如何优化最值得优化的乘数」看作是「两个变量约束下的二次规划求解问题」。为什么是两个变量？

由于等式约束的存在($\sum_{i=1}^N\alpha_iy_i=0$)，调整任何一个乘数，势必会打破原有的约束。于是SMO算法实际上是挑出两个乘数，将剩余的$N-2$个乘数固定不变，对挑出来的两个乘数进行优化：依然是优化那个”最值得优化”的乘数，但同时调整被挑出来的另一个乘数，从而维持约束不被打破。这就好比有四个变量$A$, $B$, $C$, $D$。为了满足等式约束$A+B+C+D=0$，我们可以不管并固定住$C$和$D$的取值不变，只修改变量$A,B$：如果$A\leftarrow A+1$那么$B\leftarrow B-1$，就仍然能够保持总和一致、等式约束不被打破。

除了在优化过程中不能打破等式约束以外，还要满足不等式约束（即要求两个乘数都满足$0\leq\alpha_i\leq C, i=1,2$）。然而，如果我们肆意地修改第一个乘数，而通过被动地修改第二个乘数以满足等式约束，哪怕第一个乘数的修改在不等式约束的限制范围内，也仍然可能会导致第二个乘数修改之后不满足上面的这个不等式约束。于是这就要求我们对修改量要进行一个裁剪(clip)的过程：如果对第一个乘数的主动修改量，导致第二个乘数为了维持等式约束而不得不进行的被动反向修改突破了不等式约束的限制，那么我们只需要减小第一个乘数的修改量，从而让第二个乘数始终保持在不等式约束框架内。所以现在的问题是：第一个乘数的修改量应该减为多小，才能既保证了不等式约束仍然成立，还能让第一个乘数获得了足够多的优化？

和其他资料和教程顺序相反，为了便于理解，我打算先解释「如何在无约束的情况下优化这两个乘数」，然后讨论「如何在更新乘数值的时候进行clip操作」。

无约束对两个乘数的优化过程

首先，假设我们通过某种方法，选取到的两个准备进行修正的乘数分别是$\alpha_1$和$\alpha_2$。然后SMO算法优化上面对偶问题的子问题：

$$\begin{align} \min_{\alpha_1,\alpha_2} ~~~~ &W(\alpha_1,\alpha_2)=\frac{1}{2}K_{11}\alpha_1^2+\frac{1}{2}K_{22}\alpha_2^2+y_1y_2K_{12}\alpha_1\alpha_2-(\alpha_1+\alpha_2)+y_1\alpha_1\sum_{i=3}^Ny_i\alpha_iK_{i1}+y_2\alpha_2\sum_{i=3}^Ny_i\alpha_iK_{i2} \\ s.t. ~~~~ &\alpha_1y_1+\alpha_2y_2 = -\sum_{i=3}^Ny_i\alpha_i=\varsigma \\ & 0\leq\alpha_i\leq C,~~i=1,2 \end{align}$$

公式(7)相对于公式(4)来说，只是将与$\alpha_1$和$\alpha_2$相关的项单独拿出来。同时，公式(8)则是将与$\alpha_1$和$\alpha_2$取值无关的部分放在一起作为一个常数来看待。

此时其实我们能够发现一个隐藏的信息：就是无论$\alpha_1$和$\alpha_2$如何修改，它们始终符合$\alpha_1y_1+\alpha_2y_2=\varsigma$这个约束，即：

$$\alpha_1^{(new)}y_1+\alpha_2^{(new)}y_2 = \varsigma = \alpha_1^{(old)}y_1 + \alpha_2^{(old)}y_2$$

为了方便后续的推导，我们设：

$$\begin{align} f(x)&=\sum_{i=1}^N\alpha_iy_iK(x_i,x)+b \\ E_i&=f(x_i)-y_i = \left(\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b\right) - y_i, ~~~~ i=1,2 \\ v_i&=\sum_{j=3}^N\alpha_jy_jK(x_i,x_j) \end{align}$$

其中$f(x)$是分类器，即当前状态下模型的输出。于是公式(7)中的目标函数可以更简洁地表示成：

考虑前面的约束(8) $\alpha_1y_1+\alpha_2y_2=\varsigma$，且由于$y_i^2=1$，所以：

$$\alpha_1=(\varsigma-\alpha_2y_2)$$

将上面这个$\alpha_1$带入目标函数$W(\alpha_1,\alpha_2)$得到只含有乘数$\alpha_2$的目标函数（注意$y_i^2=1$仍然成立，部分系数可以约去）：

$$\begin{align} W(\alpha_2)=\frac{1}{2}K_{11}(\varsigma-\alpha_2y_2)^2+\frac{1}{2}K_{22}\alpha_2^2+y_2K_{12}(\varsigma-\alpha_2y_2)\alpha_2-(\varsigma-\alpha_2y_2)y_2-\alpha_2+v_1(\varsigma-\alpha_2y_2)+y_2v_2\alpha_2 \end{align}$$

然后求$\alpha_2$对$W(\alpha_2)$的偏微分：

$$\frac{\partial W}{\partial\alpha_2}=K_{11}\alpha_2+K_{22}\alpha_2-2K_{12}\alpha_2-K_{11}\varsigma y_2+K_{12}\varsigma y_2+y_1y_2-1-v_1y_2+v_2y_2$$

让其等于0，从而得到：

$$\begin{align} (K_{11}+K_{22}-2K_{12})\alpha_2&=y_2(y_2-y_1+\varsigma K_{11}-\varsigma K_{12}+v_1-v_2) \end{align}$$

此时我们将等式左边的$\alpha_2$看作是更新后的乘数$\alpha_2^{(new,unc)}$ (其中$unc$是指unconstrained即未施加限制、有可能破坏约束条件的值)，然后将$\varsigma \alpha_1^{(old)}y_1+\alpha_2^{(old)}y_2$带入上面的公式中，经过一系列整理后能够得到：

$$\begin{align} (K_{11}+K_{22}-2K_{12})\alpha_2^{(new,unc)} &= y_2((K_{11}+K_{22}-2K_{12})\alpha_2^{(old)}y_2+y_2-y_2+f(x_1)-f(x_2)) \\ &=(K_{11}+K_{12}-2K_{12})\alpha_2^{(old)} + y_2(E_1 - E_2) \end{align}$$

设$\eta=K_{11}+K_{22}- 2K_{12}$，带入上式，最终得到：

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

也就是说，对于乘数$\alpha_2$，我们先利用当前模型的参数运算得到等式右边的值，即是乘数$\alpha_2$的新值。

然而，从上面的推导中我们发现，我们只对等式约束进行了限制，而完全没有考虑不等式约束$0\leq\alpha_i\leq C$的情况。以及在选定了合适的$\alpha_2^{(new)}$之后，该如何更新$\alpha_1^{(new)}$？

Clip与另一个乘数的更新规则

为了让修正后的$\alpha_2$仍然能够使不等式约束成立，我们需要讨论一下$\alpha_1$和$\alpha_2$取值的情况。

首先我们前面已经解释过，选出来的两个乘数，在更后仍然要满足等式约束：

$$\alpha_1^{(new)}y_1+\alpha_2^{(new)}y_2 = \varsigma = \alpha_1^{(old)}y_1 + \alpha_2^{(old)}y_2$$

同时，他们还应该满足不等式约束：

$$0\leq\alpha_1,\alpha_2\leq C$$

由于只考虑$\alpha_1$和$\alpha_2$这两个变量，所以可以将这两个参数满足约束条件的取值看作是下面这个盒子：

如果将整个平面看作是$\alpha_1,\alpha_2$的无约束定义域，其中横轴表示的$\alpha_1$的取值范围，纵轴表示了$\alpha_2$的取值范围，那么盒子里就是同时满足上面不等式约束的情况。

同时，在不等式约束的基础上，由于还存在着$\alpha_1y_1+\alpha_2y_2=\varsigma$的等式约束，这就说明这两个参数中一个的取值会影响另一个的取值，而这个影响是线性的。所以实际上$\alpha_1$和$\alpha_2$的取值应该是这个举行内的一条直线段。

而由于$y_i\in[0,1]$，所以约束直线一定是平行于这个方形内两条对角线中的一条：

1. 当$y_1=y_2$时，约束线段平行于这个方形从左上到又下的对角线，如下面的左图。
2. 当$y_1\neq y_2$时，约束线段平行于这个方形从左下到右上的对角线，如下面的右图。

如果我们继续细分，并且在已知$\alpha_1^{(new)}y_1+\alpha_2^{(new)}y_2 = \varsigma = \alpha_1^{(old)}y_1 + \alpha_2^{(old)}y_2$的情况下，可以将上面两种情况每种再细分成两种。

首先，对于$y_1=y_2$时，说明$\alpha_1^{(new)} + \alpha_2^{(new)} = \varsigma = \alpha_1^{(old)} + \alpha_2^{(old)}$：

1. 当约束线段在对角线下方（如上左图）时。$\alpha_2$能够取到最低点0。但最高点并不能取到$C$，而是只能取到斜线与左边界交点处（图中圆点），说明此时$\alpha_1^{(new)}=0$。所以$\alpha_2^{(new)}=\alpha_1^{(old)} + \alpha_2^{(old)}$
2. 当约束线段在对角线上方（如上右图）时。$\alpha_2$能取到最高点$C$。但最低点并不能取到$0$，而是只能取到斜线与右边界交点处（图中圆点），说明此时$\alpha_1^{(new)}=C$，所以$\alpha_2^{(new)}=\alpha_1^{(old)} + \alpha_2^{(old)} - C$

于是$\alpha_2^{(new)}$的下界是$L=\max(0, \alpha_1^{(old)} + \alpha_2^{(old)} - C)$。上界是$H=\min(\alpha_1^{(old)} + \alpha_2^{(old)}, C)$。

同理，对于$y_1\neq y_2$时，说明$\alpha_1^{(new)} - \alpha_2^{(new)} = \varsigma = \alpha_1^{(old)} - \alpha_2^{(old)}$：

1. 当约束线段在对角线下方（如上左图）时。$\alpha_2$能够取到最低点0。但最高点并不能取到$C$，而是只能取到斜线与左边界交点处（图中圆点），说明此时$\alpha_1^{(new)}=0$。所以$\alpha_2^{(new)}=\alpha_2^{(old)} - \alpha_1^{(old)}$
2. 当约束线段在对角线上方（如上右图）时。$\alpha_2$能取到最高点$C$。但最低点并不能取到$0$，而是只能取到斜线与右边界交点处（图中圆点），说明此时$\alpha_1^{(new)}=C$，所以$\alpha_2^{(new)}=\alpha_2^{(old)} - \alpha_2^{(old)} + C$

于是$\alpha_2^{(new)}$的下界是$L=\max(0, \alpha_2^{(old)} - \alpha_1^{(old)})$。上界是$H=\min(\alpha_2^{(old)} - \alpha_1^{(old)} + C, C)$。

最后，当我们找到了各种情况下的上下界，就可以直接进行clip了：

$$\alpha_2^{(new)} = \left\{ \begin{array}{ll} H, &\alpha_2^{(new,unc)} > H \\ \alpha_2^{(new,unc)}, &L\leq\alpha_2^{(new,unc)}\leq H \\ L, &\alpha_2^{(new,unc)} <L \end{array} \right.$$

利用$\alpha_2^{(new)}$可以求$\alpha_1^{(new)}$：

$$\alpha_1^{(new)}=\alpha_1^{(old)} + y_1y_2(\alpha_2^{(old)} - \alpha_2^{(new)})$$

对优化乘数的启发式搜索

当我们挑出两个乘数，直到该如何进行优化之后，下一个问题就是：「该挑出哪两个乘数来优化？」

当然，最直接的方法就是：随机挑。完全可以随机挑选两个乘数进行优化。然而SMO算法虽然单次迭代（只修正两个乘数）速度非常快，但迭代次数非常多。而由于对偶问题的解总是小于等于原始问题的解，只有遵循KKT条件的时候，对偶问题的解才等于原始问题的解。所以我们只需要从所有样本中找到违反KKT条件的作为$\alpha_2$，再加上另一个随机挑选的作为$\alpha_1$用来优化即可。

所以我们首先遍历所有样本，然后判断其是否满足KKT条件：

$$\begin{align} \alpha_i=0 \Leftrightarrow y_if(x_i)\geq 1 \\ 0<\alpha_i<C \Leftrightarrow y_if(x_i) = 1 \\ \alpha_i=C \Leftrightarrow y_if(x_i)\leq 1 \end{align}$$

其中$f(x_i)=\sum_{j=1}^N\alpha_jy_jK(x_i,x_j) + b$。

除此之外，如果数据集规模非常庞大的时候，遍历所有样本点、或者挑选第一个违反KKT条件的样本点并不一定是”最好”的样本点。所以我们可以先从所有$0<\alpha_i<C$对应的样本点中寻找不满足KKT条件的作为$\alpha_1$。然后由于$\alpha_2$的取值和$|E_1-E_2|$有关，所以我们可以挑选一个使$|E_1-E_2|$最大的点对应的乘数作为$\alpha_2$：因为当$\alpha_1$已确定，$E_1$也就确定了，此时如果$E_1>0$直接选择最小的$E_i$作为$E_2$，如果$E_1<0$，则选择最大的$E_i$作为$E_2$。

然而，这种方式找到的$\alpha_1$和$\alpha_2$可能无法让目标函数下降，那么可以依次尝试以分隔边界上的点作为$\alpha_2$，如果仍然无法下降，那就放弃这个$\alpha_1$，再用前面的方法寻找下一个$\alpha_1$。

对阈值$b$的更新

在每次完成对两个乘数的更新之后，相当于模型也要发生变化，所以需要重新计算作为参数之一的阈值$b$。

由于更新完毕之后仍然要满足不等式约束$0<\alpha_1^{(new)}<C$，由KKT条件可得：

$$\sum_{i=1}^N\alpha_iy_iK_{i1}+b=y_1$$

所以有：

$$b_1^{(new)} = y_1 - \sum_{i=3}^N\alpha_iy_iK_{i1} - \alpha_1^{(new)}y_1K_{11} - \alpha_2^{(new)}y_2K_{21}$$

同时：

$$\begin{align} E_1&=f(x_1)-y_1=\sum_{i=1}^N\alpha_iy_iK_{i1}+b^{(old)} - y_1 \\ & = \sum_{i=3}^N\alpha_iy_iK_{i1} + \alpha_1^{(old)}y_1K_{11} + \alpha_2^{(old)}y_2K_{21} + b^{(old)} - y_1 \end{align}$$

于是

$$y_1-\sum_{i=3}^N\alpha_iy_iK_{i1} = -E_1+\alpha_1^{(old)}y_1K_{11} + \alpha_2^{(old)}y_2K_{21}+b^{(old)}$$

带入到上方$b_1^{(new)}$的公式中可得：

$$b_1^{(new)} = -E_1-y_1K_{11}(\alpha_1^{(new)} - \alpha_1^{(old)}) - y_2K_{21}(\alpha_2^{(new)} - \alpha_2^{(old)}) + b^{(old)}$$

同理，如果$0<\alpha_2^{(new)}<C$，则有：

$$b_2^{(new)} = -E_2 - y_1K_{12}(\alpha_1^{(new)} - \alpha_1^{(old)}) - y_2K_{22}(\alpha_2^{(new)} - \alpha_2^{(old)}) + b ^ {(old)}$$

为什么会得到两个新的$b^{(new)}$？因为如果$0<\alpha_1^{(new)},\alpha_2^{(new)}<C$时，这两个乘数对应的向量都是支持向量，此时$b_1^{(new)} = b_2^{(new)}$。而当$\alpha_1^{(new)},\alpha_2^{(new)}$在边界上时，则$[b_1^{(new)}, b_2^{(new)}]$(或者$[b_2^{(new)}, b_1^{(new)}]$)之间任何值都可以作为$b^{(new)}$。通常会取$b^{(new)} = \frac{1}{2}(b_1^{(new)} + b_2^{(new)})$。

整理与总结

综上所述，我们可以将SMO算法整理成如下的形式：

首先根据前面的方法挑选两个优化的乘数$\alpha_1$和$\alpha_2$。然后计算$E_1$和$E_2$:

$$E_i=f(x_i)-y_i = \left(\sum_{j=1}^N\alpha_jy_jK(x_j,x_i)+b\right) - y_i, ~~~~ i=1,2$$

然后计算$\eta$:

$$\eta = K_{11}+K_{22}-2K_{12}$$

然后计算边界情况：

$$\begin{align} L&=\left\{ \begin{array}{ll} \max(0, \alpha_2^{(old)} - \alpha_1^{(old)}), &y_1\neq y_2 \\ \max(0, \alpha_2^{(old)} + \alpha_1^{(old)} - C), &y_1=y_2 \end{array} \right. \\ H&=\left\{ \begin{array}{ll} \min(C+\alpha_2^{(old)} - \alpha_1^{(old)}, C), &y_1\neq y_2 \\ \min(\alpha_2^{(old)} + \alpha_1^{(old)}, C), &y_1=y_2 \end{array} \right. \end{align}$$

然后计算无约束情况下的$\alpha_2^{(new,unc)}$：

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

然后进行clip操作，更新$\alpha_2$： $\alpha_2^{(new)} = \left\{ \begin{array}{ll} H, &\alpha_2^{(new,unc)} > H \\ \alpha_2^{(new,unc)}, &L\leq\alpha_2^{(new,unc)}\leq H \\ L, &\alpha_2^{(new,unc)} <L \end{array} \right.$

然后更新$\alpha_1$：

$$\alpha_1^{(new)}=\alpha_1^{(old)} + y_1y_2(\alpha_2^{(old)} - \alpha_2^{(new)})$$

然后计算$b_1^{(new)},b_2^{(new)}$，并更新$b$：

$$\begin{align} b_1^{(new)} &= -E_1-y_1K_{11}(\alpha_1^{(new)} - \alpha_1^{(old)}) - y_2K_{21}(\alpha_2^{(new)} - \alpha_2^{(old)}) + b^{(old)} \\ b_2^{(new)} &= -E_2 - y_1K_{12}(\alpha_1^{(new)} - \alpha_1^{(old)}) - y_2K_{22}(\alpha_2^{(new)} - \alpha_2^{(old)}) + b ^ {(old)} \\ b^{(new)} &= \frac{1}{2}(b_1^{(new)} + b_2^{(new)}) \end{align}$$

重复上述过程，直到满足停止条件：

$$\sum_{i=1}^N\alpha_iy_i=0, ~~~~0\leq\alpha_i\leq C, ~~~~i=1,2,\dots,N$$ $$y_i\cdot f(x_i)=y_i\left(\sum_{j=1}^N\alpha_jy_jK(x_j, x_i) + b\right) = \left\{ \begin{array}{ll} \geq 1, ~~~~~~\left\{x_i|\alpha_i=0\right\} \\ =1, ~~~~~~\left\{x_i|0<\alpha_i<C\right\} \\ \leq 1, ~~~~~~\left\{x_i|\alpha_i=C\right\} \end{array} \right.$$

达到停止条件之后，即得到了最优化的拉格朗日乘数$\alpha_i^$和$b^$。

则该SVM的决策函数为：

$$f(x)=\text{sign}\left(\sum_{i=1}^N\alpha_i^*y_iK(x,x_i)+b^*\right)$$

参考资料

1. Platt, John. (1998). Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines. Advances in Kernel Methods-Support Vector Learning. 208.
2. NCTU OCW: Sequential Minimal Optimization 1&2
3. 李航 《统计学习方法》