在SVM的前三篇里，我们优化的目标函数最终都是一个关于α$\alpha$向量的函数。而怎么极小化这个函数，求出对应的α$\alpha$向量，进而求出分离超平面我们没有讲。本篇就对优化这个关于α$\alpha$向量的函数的SMO算法做一个总结。

1. 回顾SVM优化目标函数

　　　　我们首先回顾下我们的优化目标函数：

2. SMO算法的基本思想

3. SMO算法目标函数的优化

　　　　为了求解上面含有这两个变量的目标优化问题，我们首先分析约束条件，所有的α1,α2${\alpha }_1,{\alpha }_2$都要满足约束条件，然后在约束条件下求最小。

　　　　根据上面的约束条件α1y1+α2y2=ς0≤αi≤Ci=1,2${\alpha }_1{y}_1+{\alpha }_2{y}_2=\varsigma 0\le {\alpha }_i\le Ci=1,2$，又由于y1,y2均只能取值1或者-1, 这样α1,α2在[0,C]和[0,C]形成的盒子里面，并且两者的关系直线的斜率只能为1或者-1，也就是说α1,α2${\alpha }_1,{\alpha }_2$的关系直线平行于[0,C]和[0,C]形成的盒子的对角线，如下图所示：

4. SMO算法两个变量的选择

　　　　SMO算法需要选择合适的两个变量做迭代，其余的变量做常量来进行优化，那么怎么选择这两个变量呢？

4.1 第一个变量的选择

　　　　SMO算法称选择第一个变量为外层循环，这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点，要满足的KKT条件我们在第一节已经讲到了： 

　　　　一般来说，我们首先选择违反0<α∗i<C⇒yig(xi)=1$0<{\alpha }_i^{\ast }<C\Rightarrow y_{i}g(x_i)=1$这个条件的点。如果这些支持向量都满足KKT条件，再选择违反α∗i=0⇒yig(xi)≥1${\alpha }_i^{\ast }=0\Rightarrow y_{i}g(x_i)\ge 1$ 和 α∗i=C⇒yig(xi)≤1${\alpha }_i^{\ast }=C\Rightarrow y_{i}g(x_i)\le 1$的点。

4.2 第二个变量的选择

 　　　　SMO算法称选择第二一个变量为内层循环，假设我们在外层循环已经找到了α1${\alpha }_1$, 第二个变量α2${\alpha }_2$的选择标准是让|E1−E2|$|E1-E2|$有足够大的变化。由于α1${\alpha }_1$定了的时候,E1$E_1$也确定了，所以要想|E1−E2|$|E1-E2|$最大，只需要在E1为正时，选择最小的Ei作为E2， $E_1$为负时，选择最大的E$i_{}$作为E2，可以将所有的Ei保存下来加快迭代。

　　　　如果内存循环找到的点不能让目标函数有足够的下降， 可以采用遍历支持向量点来做α2,直到目标函数有足够的下降， 如果所有的支持向量做α2都不能让目标函数有足够的下降，可以跳出循环，重新选择α1　

4.3 计算阈值b和差值Ei

. SMO算法总结

　　　　输入是m个样本(x1,y1),(x2,y2),...,(xm,ym),$(x_1,y_1),(x_2,y_2),...,(x_m,y_m),$,其中x为n维特征向量。y为二元输出，值为1，或者-1.精度e。

　　　　输出是近似解α$\alpha$

　　　　1)取初值α0=0,k=0

　　　　2)按照4.1节的方法选择αk1${\alpha }_1^k$,接着按照4.2节的方法选择αk2${\alpha }_2^k$，求出新的αnew,unc2

　SMO算法终于写完了，这块在以前学的时候是非常痛苦的，不过弄明白就豁然开朗了。希望大家也是一样。写完这一篇， SVM系列就只剩下支持向量回归了，胜利在望！