从零开始-Machine Learning学习笔记(12)-SMO算法解析

​ SMO-Sequential Minimal Optimization，序列最小优化，SMO的基本思路就是：先固定αi${\alpha }_i$之外的所有参数，然后求αi${\alpha }_i$的极值。但是问题中存在约束条件：∑mi=0αiyi=0$\sum _{i=0}^m{\alpha }_i{y}_i=0$。如果固定了αi${\alpha }_i$之外的其他变量，则αi${\alpha }_i$可以由其他的变量导出。于是，一次只留一个参数，固定其余参数的方法在这里是不适用的，但是这个思想却给了我们不错的启发。那么，SMO可以每次选择两个变量αi${\alpha }_i$和αj${\alpha }_j$，并固定其他参数。这样，在参数初始化之后，SMO不断迭代重复下面的步骤，直至收敛：

• 选取一对新的αi${\alpha }_i$和αj${\alpha }_j$;

• 固定αi${\alpha }_i$和αj${\alpha }_j$之外的参数，求解前面的优化问题，获取更新后的αi${\alpha }_i$和αj${\alpha }_j$。

  假设我们选择α1${\alpha }_1$与α2${\alpha }_2$是变量，其余的αi${\alpha }_i$是定值，常数，那么原来的目标函数：
  

  minα12∑i=1N∑j=1NαiαjyiyjK(xi⋅xj)−∑i=1Nαis.t.∑i=1Nαiyi=00≤αi≤C,i=1,2,…N$$\begin{array}{l}\underset{\alpha }{min}\frac{1}{2}\sum _{i=1}^N\sum _{j=1}^N{\alpha }_i{\alpha }_j{y}_i{y}_{j}K\left(x_i\cdot x_j\right)-\sum _{i=1}^N{\alpha }_i\\ s.t.\sum _{i=1}^N{\alpha }_i{y}_i=0\\ 0\le {\alpha }_i\le C,i=1,2,\dots N\end{array}$$

就变为对α1${\alpha }_1$与α2${\alpha }_2$的优化：

1. 原目标函数化简

​ 我们来逐步化简原来的目标函数，其中只有α1${\alpha }_1$与α2${\alpha }_2$是变量，其余的都是常数：

我们分别取

i=1,j=1$i=1,j=1$

i=1,j=2$i=1,j=2$

i=1,j≠1,2$i=1,j\ne 1,2$

j=1,i≠1,2$j=1,i\ne 1,2$

i=2,j=1$i=2,j=1$

i=2,j=2$i=2,j=2$

i=2,j≠1,2$i=2,j\ne 1,2$

j=2,i≠1,2$j=2,i\ne 1,2$

i≠1,2,j≠1,2$i\ne 1,2,j\ne 1,2$

这样我们就可以把目标函数化成只有变量α1${\alpha }_1$与α2${\alpha }_2$，其余的项都可以合并为常数C：

其中：

于是，我们的目标函数就转化为上式的样子。

2. 解的范围

要求解上述的优化问题，必定先确定解的范围，根据原来的约束条件我们知道：

其中我们知道y2i=1$y_i^2=1$，所以对于第一个约束条件我们可以有两种表示方式：

y1=y2时，α1+α2=K$y_1=y_2时，{\alpha }_1+{\alpha }_2=K$

y1≠y2时，α1−α2=K$y_1\ne y_2时，{\alpha }_1-{\alpha }_2=K$

​ k具体是多少我们并不关心，但是我们知道α1和α2的取值都落在途中的直线上。k无非就是一个截距，随着k的变化，这根直线在方框内会上下移动，交点也变，但是一定要在方框范围内，所以边界一定会落在方框与直线的交点上。设L为α2可能的最小取值，H为α2可能的最大取值,那么有：

1. y1=y2时，α1+α2=K，则α2=K−α1$y_1=y_2时，{\alpha }_1+{\alpha }_2=K，则{\alpha }_2=K-{\alpha }_1$

   我们都知道0<α1<C,0<α2<C$0<{\alpha }_1<C,0<{\alpha }_2<C$;

   当α1=C${\alpha }_1=C$时，α2${\alpha }_2$取得最小值,即α2=K−C${\alpha }_2=K-C$,但是，0<α2$0<{\alpha }_2$,所以最小值在这两者中取得，于是：
   

   L=max{0,K−C}=max{0,α1+α2−C}$$L=max\{0,K-C\}=max\{0,{\alpha }_1+{\alpha }_2-C\}$$
   
   当α1=0${\alpha }_1=0$时，α2${\alpha }_2$取得最大值,即α2=K${\alpha }_2=K$但是，α2<C${\alpha }_2<C$,所以最大值在这两者中取得，于是：
   
   H=min{K,C}=min{α1+α2,C}$$H=min\{K,C\}=min\{{\alpha }_1+{\alpha }_2,C\}$$

2. y1≠y2时，α1−α2=K，则α2=α1−K$y_1\ne y_2时，{\alpha }_1-{\alpha }_2=K，则{\alpha }_2={\alpha }_1-K$

   我们都知道0<α1<C,0<α2<C$0<{\alpha }_1<C,0<{\alpha }_2<C$;

   当α1=0${\alpha }_1=0$时，α2${\alpha }_2$取得最小值,即α2=−K${\alpha }_2=-K$但是，0<α2$0<{\alpha }_2$以最小值在这两者中取得，于是：

​ 当α1=C${\alpha }_1=C$时，α2${\alpha }_2$取得最大值,即α2=C−K${\alpha }_2=C-K$但是，α2<C${\alpha }_2<C$,所以最大值在这两者中取得，于是：

3.求解过程

​ 先将α1${\alpha }_1$用α2${\alpha }_2$来表示，因为α1y1+α2y2=k（const）${\alpha }_1{y}_1+{\alpha }_2{y}_2=k（const）$，两边同时乘以y1$y_1$,于是有：

带入到我们之前化简的目标函数中，那么目标函数就变为只有变量α2${\alpha }_2$的优化问题了：

其中，v1与v2需要变换一下，不能直接运算，因为SVM的模型为：

所以可以间接求出v1与v2为：

所以，此时目标函数就只是一元函数，我们对其求倒数，并使其为0，就可以求出α2${\alpha }_2$:

此时我们把v1与v2带入就可以得到迭代公式：

于是我们可以得到递推公式：

其中Ej$E_j$是预测值与实际值之差，η=K11+K22−2K12$\eta =K_{11}+K_{22}-2K_{12}$

最后将α2${\alpha }_2$的值进行约束：

得到α2${\alpha }_2$之后就可以由约束条件α1y1+α2y2=αnew1y1+αnew2=k${\alpha }_1{y}_1+{\alpha }_2{y}_2={\alpha }_1^{new}{y}_1+{\alpha }_2^{new}=k$得到α1${\alpha }_1$：

大部分情况下，η>0$\eta >0$，但是当η≤0$\eta \le 0$的时候就比较麻烦了，需要更为复杂的求解手段。详情可以见我后面附上的参考博客。在现实中，这种情况不常发生，因此忽略也无伤大雅，在程序中遇到了一般的处理是跳过此次循环。

4、求解w与b

w的求解可以通过：w∗=∑i=1mα∗iyixi$w^{\ast }=\sum _{i=1}^m{\alpha }_i^{\ast }{y}_i{x}_i$求得。

b可以通过kkt条件求出：

这是原优化问题的KKT条件：

1. 当αi=0${\alpha }_i=0$时，分类是正确的；
2. 当0≤αi≤C$0\le {\alpha }_i\le C$时，这时的样本点是支持向量，处在边界上；
3. 当αi=C${\alpha }_i=C$时，位于边界之间。

参考上面的KKT条件进行分类讨论：

1. 如果0<α1<C$0<{\alpha }_1<C$，则(x1,y1)为支持向量，满足yi(∑mi=1αiyiKi1+b1)=1$y_i({\sum }_{i=1}^m{\alpha }_i{y}_i{K}_{i1}+b_1)=1$：
   

   α∗1y1K11+α∗2y2K21+∑i=3mαiyiKi1+b∗1=y1$${\alpha }_1^{\ast }{y}_1{K}_{11}+{\alpha }_2^{\ast }{y}_2{K}_{21}+\sum _{i=3}^m{\alpha }_i{y}_i{K}_{i1}+b_1^{\ast }=y_1$$
   b∗1=y1−∑i=3mαiyiKi1−α∗1y1K11−α∗2y2K21=y1−v1−α∗1y1K11−α∗2y2K21=y1−[f(x1)−α1y1K11−α2y2K12−b]−α∗1y1K11−α∗2y2K21=b1−E1−y1K11(α∗1−α1)−y2K21(α∗2−α2)$$\begin{gathered} b_1^{\ast }=y_1-\sum _{i=3}^m{\alpha }_i{y}_i{K}_{i1}-{\alpha }_1^{\ast }{y}_1{K}_{11}-{\alpha }_2^{\ast }{y}_2{K}_{21} \\ =y_1-v_1-{\alpha }_1^{\ast }{y}_1{K}_{11}-{\alpha }_2^{\ast }{y}_2{K}_{21} \\ =y_1-[f(x_1)-{\alpha }_1{y}_1{K}_{11}-{\alpha }_2{y}_2{K}_{12}-b]-{\alpha }_1^{\ast }{y}_1{K}_{11}-{\alpha }_2^{\ast }{y}_2{K}_{21} \\ =b_1-E_1-y_1{K}_{11}({\alpha }_1^{\ast }-{\alpha }_1)-y_2{K}_{21}({\alpha }_2^{\ast }-{\alpha }_2) \end{gathered}$$

2.如果0<α2<C$0<{\alpha }_2<C$，则(x2,y2)为支持向量,那么可以得到b2$b_2$:

3.如果同时有0<α1<C，0<α2<C$0<{\alpha }_1<C，0<{\alpha }_2<C$,那么有b∗1=b∗2$b_1^{\ast }=b_2^{\ast }$。

4.如果均不满足0≤αi≤C$0\le {\alpha }_i\le C$就取两者中点：b∗=b∗1+b∗22$b^{\ast }=\frac{b_1^{\ast }+b_2^{\ast }}{2}$

在周志华老师的《机器学习》中，还给出了一个更为鲁棒的求法：使用所有支持向量求解的平均值：

其中S是所有支持向量的下标集合。

5.总结

​ SMO的公式推导还是比较复杂的，但是越推就越觉得Platt这些人确实厉害，能推导出如此美丽的公式。钦佩之余，自己又在机器学习的道路上前进了许多，也愈发的觉得自己懂的还是太少，即便是全部推完了这些公式，不会应用的惶恐之心又涌上心头。但是，学无止境，只要一直在路上就一定会到达目的地！

​ 下一篇博客中，我会去研究SMO中启发式的变量选择，看这种方式是如何提高算法的效率的！

参考资料：

周志华《机器学习》-支持向量机

机器学习入门笔记：（4.3）SMO算法

支持向量机（五）SMO算法