前言

在经过前面漫长的 SVM 学习之后，是时候学习怎么实现 SVM 了。其实，SVM 常常表现得很好并且有着高效的训练算法，这使得 SVM 曾经非常盛行。只是近些年来，由于深度学习起势，SVM 才不再那么盛行，但它依旧是很好用的分类算法。所以探究 SVM 的原理及思想显得非常有必要，那么现在我们就谈谈 SMO 算法。
首先，在前面的 SVM 学习中，我们有如下对偶问题:

并且需要满足KKT条件:

1. 当 αi=0${\alpha }_i=0$， yi(wTxi+b)≥1$y_i\left(w^T{x}_i+b\right)\ge 1$;
2. 当 0<αi<C$0<{\alpha }_i<C$， yi(wTxi+b)=1$y_i\left(w^T{x}_i+b\right)=1$；
3. 当 αi=C${\alpha }_i=C$， yi(wTxi+b)≤1$y_i\left(w^T{x}_i+b\right)\le 1$。

那么，由于一个训练样本 (xi,yi)$\left(x_i,y_i\right)$ 对应一个 αi${\alpha }_i$，因此我们只需要找到这样一组 αi${\alpha }_i$ 满足上述条件，这就是该对偶问题的最优解。有了这组 αi${\alpha }_i$ ,w$w$、b 以及分类函数 f(x)$f\left(x\right)$就可以顺其自然地得到求解。

上述对偶问题是个凸二次规划问题，它具有全局最优解。一般可以使用现有的 QP 工具来进行求解。但是，当训练容量非常大的时候，训练算法反而耗时且低效。因此，有必要寻找更优的求解算法来代替实现。虽然出现了很多优化算法，但比较著名的是一个叫做 John C. Platt 的研究者提出的序列最小化算法 (Sequential Minimal Optimization，简称 SMO)。而它的思想是：将大优化的问题分解成多个小优化的问题。这些小问题往往比较容易求解，然后对他们进行顺序求解。这样之后得到的结果与将他们作为整体来求解的结果完全一致并且最重要的是 SMO 的求解时间更短了。
在介绍 SMO 之前，先介绍下坐标梯度下降算法，这也是 SMO 中利用到的简单的算法思想。

坐标梯度下降(上升)

坐标下降是一种非梯度优化算法(坐标下降用于优化最小值，而坐标上升用于优化最大值，可通过加负号相互转换)。因为算法在每次迭代中，只会从当前点处沿一个坐标方向进行一维搜索以求得一个函数的局部极小值，并在迭代的过程中不断变化优化的坐标方向，直至函数得到收敛。
例如，我们要寻找函数 f(x,y)=5x2−6xy+5y2$f\left(x,y\right)=5x^2-6xy+5y^2$ 的最小值。那么坐标优化的迭代过程如下图所示:

我们从某个起始点开始寻找，然后沿着一个方向往等高线上数值小的高度前进(类似下山)，在前进的时候，可以改变方向，例如此处可以往上或往右走，直至不断走向中心点，也就是收敛到最优解。

SMO 算法

SMO 算法和坐标梯度下降思想差不多，只是 SMO 一次迭代优化的是两个变量 αi${\alpha }_i$、αj${\alpha }_j$。所以它的思想就是将带有多个优化变量的二次规划大问题分解为多个只含两个优化变量的二次规划小问题，这样既节省了时间成本也降低了内存消耗。

那么为什么需要一次优化两个变量呢？这是因为在 SVM 中存在着 ∑mi=1αiyi=c$\sum _{i=1}^m{\alpha }_i{y}_i=c$ 约束，这是一个线性组合关系。而 SMO 在优化前会先固定暂时不进行优化的变量，那么如果仅优化一个变量，那么这个变量就会被其他已固定的参数表示出来，则它就不再是变量，因此，需要再找一个变量。即 SMO 算法先要确定一对 αi,αj${\alpha }_i,{\alpha }_j$，其他的变量则先固定。

那么固定参数之后，就可以得到 αi${\alpha }_i$ 和 αj${\alpha }_j$ 的等式关系了。即：

那么我们就可以消去上述对偶问题中的 αi${\alpha }_i$了，然后就得到了仅关于 αi${\alpha }_i$ 的单变量二次规划问题，然后利用费马引理进行求解即可。解出 αj${\alpha }_j$ 之后，αi${\alpha }_i$ 便可由等式轻易推出，这样就是一次迭代过程。迭代一次仅调整两个拉格朗日乘子。那么这样看来，SMO 之所以高效的原因就在于它是对单变量进行优化，可想而知单变量的收敛速度是比较快的。
总之，一次迭代的三个步骤是:

1. 确定一对 (αi,αj)$\left({\alpha }_i,{\alpha }_j\right)$;
2. 固定其他 (m-2) 个变量后，消去其中一个变量，得到含单变量的优化式子；
3. 根据优化后的 αi,αj${\alpha }_i,{\alpha }_j$，更新阈值 b。

关于 αi${\alpha }_i$ 和 αj${\alpha }_j$ 的 选择

现在我们需要从 m 个变量中确定两个变量，那么可能的组合非常多。如何确定到底是哪一对呢？首先，我们的优化目标其实就是尽量使大部分的样本都满足 KKT 条件，即使大部分的样本得到正确分类。那么，我们就需要先纠正违反 KKT 条件最严重的那个样本对应的优化变量，就好像先把最难的事情做了，接下来再做简单的事，这样就会很轻松。那么第二个变量怎么选？它选择的标准是必须有足够大的变化，也就是能够对目标函数沿着优化方向下降幅度最大的那个变量。这样选择的依据是，对它们进行更新可以加快目标函数的收敛速度。

SMO 算法公式推导

求解未被修剪的 αnew,unclippedi${\alpha }_i^{new,unclipped}$ ，αnew,unclippedj${\alpha }_j^{new,unclipped}$

首先，我们把 SVM 中对偶问题的目标函数写为:

并且用 ki,j$k_{i,j}$ 代替 k(xi,xj)$k\left(x_i,x_j\right)$ 表示。
然后，假设我们选中的待优化变量为 α1${\alpha }_1$ ，α2${\alpha }_2$ 。那么 α3${\alpha }_3$,α4${\alpha }_4$，…，αm${\alpha }_m$ 则被固定，当做常数处理。那么将 SVM 的优化问题展开后得到：

其中将与 α1${\alpha }_1$、α2${\alpha }_2$ 无关的 C1$C_1$ 和 ∑mi=3∑mj=3αiyiαjyjki,j$\sum _{i=3}^m\sum _{j=3}^m{\alpha }_i{y}_i{\alpha }_j{y}_j{k}_{i,j}$ 合并为常数项 C。
又已知 α1y1+α2y2=ξ${\alpha }_1{y}_1+{\alpha }_2{y}_2=\xi$ ,yiyi=1$y_i{y}_i=1$，然后等式两边同时乘上 y1$y_1$ 得到:

另外，记 v1=∑mi=3αiyiki,1$v_1=\sum _{i=3}^m{\alpha }_i{y}_i{k}_{i,1}$，v2=∑mi=3αiyiki,2$v_2=\sum _{i=3}^m{\alpha }_i{y}_i{k}_{i,2}$，最后将所有式子带入 w(α1,α2)$w\left({\alpha }_1,{\alpha }_2\right)$ 得到：

接下来利用费马引理求极值，令 w$w$ 对 α2${\alpha }_2$ 的导数为零，得:

然后，现在我们要将 ξ$\xi$ 消去。
已知 SVM 分类函数公式:f(xi)=∑mi=1αiyiki,i+b$f\left(x_i\right)=\sum _{i=1}^m{\alpha }_i{y}_i{k}_{i,i}+b$，那么:


得到： v1−v2=f(x1)−f(x2)−k1,1ξ+k1,2ξ+(k1,1+k2,2−2k1,2)y2α2$v_1-v_2=f\left(x_1\right)-f\left(x_2\right)-k_{1,1}\xi +k_{1,2}\xi +\left(k_{1,1}+k_{2,2}-2k_{1,2}\right)y_2{\alpha }_2$
现在，我们需要区别下迭代前和迭代之后的变量。其实我们固定的 m-2 个拉格朗日乘子都是上一次迭代的值，所以 v1$v_1$ 和 v2$v_2$ 所表示的式子都是前一次迭代的量，那么，由他们推导出来的 α1${\alpha }_1$ 和 α2${\alpha }_2$ 当然也是前一次迭代的量。
那么现在我们以 old 和 new 上角标分别区别前一次迭代和当前迭代的优化量，那么区分后式子改为：


接下来，合并两个式子，再得：

然后，我们记 Ei$E_i$ 为 SVM 的预测值和实际值的误差: Ei=f(xi)−yi$E_i=f\left(x_i\right)-y_i$，并且令 η=k1,1+k2,2−2k1,2$\eta =k_{1,1}+k_{2,2}-2k_{1,2}$，所以最终的一阶求导公式为：

那么就可以解出:

修剪解出的最优解

上面解出的 α1${\alpha }_1$ 和 α2${\alpha }_2$ 并未考虑约束条件。那么，现在我们需要将约束条件加上，然后对所求出的最优解进行范围的修剪以得到最终满足约束条件的最优解。
即:

由于约束条件 0≤α1≤C$0\le {\alpha }_1\le C$ 、 0≤α2≤C$0\le {\alpha }_2\le C$ 以及 α1y1+α2y2=k,k为常数${\alpha }_1{y}_1+{\alpha }_2{y}_2=k,k为常数$ 的存在，所以我们需要给 α1${\alpha }_1$ 和 α2${\alpha }_2$ 找到区间 [L,H]$\left[L,H\right]$。由于只有两个变量，因此约束可以用二维空间中的图形来表示，如下图所示(方形约束)。

那么对于约束 α1y1+α2y2=k${\alpha }_1{y}_1+{\alpha }_2{y}_2=k$
根据左图：当 y1≠y2$y_1\ne y_2$ 时，此约束简化为：α1−α2=k${\alpha }_1-{\alpha }_2=k$，那么根据 k 的正负可以得到上下界为：

• 下界：L=max(0,αold2−αold1)$L=max\left(0,{\alpha }_2^{old}-{\alpha }_1^{old}\right)$;
• 上界：H=min(C,C+αold2−αold1)$H=min\left(C,C+{\alpha }_2^{old}-{\alpha }_1^{old}\right)$。

根据右图：当 y1=y2$y_1=y_2$ 时，此约束简化为：α1+α2=k${\alpha }_1+{\alpha }_2=k$，上下界表示为：

• 下界：L=max(0,αold1+αold2−C)$L=max\left(0,{\alpha }_1^{old}+{\alpha }_2^{old}-C\right)$;
• 上界：H=min(C,αold1+αold2)$H=min\left(C,{\alpha }_1^{old}+{\alpha }_2^{old}\right)$。

那么，有了上下界之后，如果优化之后的 α1${\alpha }_1$ 和 α2${\alpha }_2$跑出了边界，那么我们就需要纠正它，所以有：

得到了 αnew2${\alpha }_2^{new}$，再根据 αnew1y1+αnew2y2=αold1y1+αold2y2${\alpha }_1^{new}{y}_1+{\alpha }_2^{new}{y}_2={\alpha }_1^{old}{y}_1+{\alpha }_2^{old}{y}_2$ ，然后两边同乘以 y1$y_1$ 可解出 αnew1${\alpha }_1^{new}$，即:

这样，我们就得到了两个优化的拉格朗日乘子 αnew1${\alpha }_1^{new}$ 和 αnew2${\alpha }_2^{new}$

计算更新后的阈值 b

在每一次迭代中，优化 αnew1${\alpha }_1^{new}$ 和 αnew2${\alpha }_2^{new}$ 之后，就要更新阈值 b$b$。那么为了使得被优化的样本都满足 KKT 条件，此时需要分为样本在边界上和样本不在边界上两种情况进行讨论。

• 当优化后的 αnew1${\alpha }_1^{new}$ 不在边界上，也就是满足约束 0≤αnew1≤C$0\le {\alpha }_1^{new}\le C$ ，那么根据 KKT 条件得知该样本为支持向量，所以 y1f(x1)=1$y_{1}f\left(x_1\right)=1$,则阈值 b1$b_1$是有效的。那么两边同时乘以 y1$y_1$，并展开式子得: ∑mi=1αiyiki,1+b=y1$\sum _{i=1}^m{\alpha }_i{y}_i{k}_{i,1}+b=y_1$，那么解出 bnew1$b_1^{new}$ 为:
  
  bnew1=y1−∑i=3mαiyiki,1−αnew1y1k1,1−αnew2y2k2,1$$b_1^{new}=y_1-\sum _{i=3}^m{\alpha }_i{y}_i{k}_{i,1}-{\alpha }_1^{new}{y}_1{k}_{1,1}-{\alpha }_2^{new}{y}_2{k}_{2,1}$$
  
  
  =−E1+αold1y1k1,1+αold2y2k2,1+bold−αnew1y1k1,1−αnew2y2k2,1$$=-E_1+{\alpha }_1^{old}{y}_1{k}_{1,1}+{\alpha }_2^{old}{y}_2{k}_{2,1}+b^{old}-{\alpha }_1^{new}{y}_1{k}_{1,1}-{\alpha }_2^{new}{y}_2{k}_{2,1}$$
  
  
  =−E1−y1k1,1(αnew1−αold1)−y2k2,1(αnew2−αold2)+bold$$=-E_1-y_1{k}_{1,1}\left({\alpha }_1^{new}-{\alpha }_1^{old}\right)-y_2{k}_{2,1}\left({\alpha }_2^{new}-{\alpha }_2^{old}\right)+b^{old}$$
  
  同理可计算出 bnew2$b_2^{new}$：
  
  bnew2=−E2−y1k1,2(αnew1−αold1)−y2k2,2(αnew2−αold2)+bold$$b_2^{new}=-E_2-y_1{k}_{1,2}\left({\alpha }_1^{new}-{\alpha }_1^{old}\right)-y_2{k}_{2,2}\left({\alpha }_2^{new}-{\alpha }_2^{old}\right)+b^{old}$$
  
  另外，当 bnew1$b_1^{new}$ 和 bnew2$b_2^{new}$ 均有效时，bnew=bnew1=bnew2$b^{new}=b_1^{new}=b_2^{new}$
• 当优化后的 αnew1${\alpha }_1^{new}$ 和 αnew2${\alpha }_2^{new}$ 都在边界上，即 (αnew1=0${\alpha }_1^{new}=0$ 或 αnew1=C${\alpha }_1^{new}=C$，同时 αnew2=0${\alpha }_2^{new}=0$ 或 αnew2=C${\alpha }_2^{new}=C$)，那么在 bnew1$b_1^{new}$ 和 bnew2$b_2^{new}$ 之间的阈值都是满足 KKT 条件的，一般我们取它们的中间值来更新阈值，即：bnew=bnew1+bnew22$b^{new}={\displaystyle \frac{b_1^{new}+b_2^{new}}{2}}$。

参考

[1] Sequential Minimal Optimization:
A Fast Algorithm for Training Support Vector Machines by John C. Platt
[2] 机器学习算法与Python实践之（四）支持向量机（SVM）实现 by zouxy
[3] 机器学习算法实践-SVM中的SMO算法 by PytLab酱