十三、SMO初识

序列最小优化算法 (Sequential minimal optimization, SMO) 是一种用于解决SVM训练过程中所产生的优化问题的算法。 于1998年由John Platt发明，论文详见：《Sequencial Minimal Optimization-a Fast Alg for Training SVM.pdf》

回顾线性可分SVM求解步骤：

假定存在一个β*=(β1,β2,...,βm)是我们最终的最优解，那么根据KKT条件我们可以计算出w和b的最优解，如下：

进而我们可以得到最终的分离超平面为:

拉格朗日乘子法和KKT的对偶互补条件为：

β、μ和C之间的关系为：C - β_i - μ_i = 0

根据这个对偶互补条件，我们有如下关系式：

也就是说我们找出的最优的分割超平面必须满足下列的目标条件(g(x)):

拉格朗日对偶化要求的两个限制的初始条件为:

---

从而可以得到解决问题的思路如下：

1、初始化后一个β值，让它满足对偶问题的两个__初始限制条件__；

2、不断优化这个β值，使得由它确定的分割超平面满足__g(x)目标条件__；而且在优化过程中，始终保证β值满足__初始限制条件__。

__PS：__这个求解过程中，和传统的思路不太一样，不是对目标函数求最小值，而是让__g(x)目标条件__尽可能的满足。

在这样一个过程中，到底如何优化这个β值呢？？？

整理可以发现β值的优化须遵循以下两个基本原则：

1、每次优化的时候，必须同时优化β的两个分量；因为如果只优化一个分量的话，新的β值就没法满足__初始限制条件中__的__等式约束条件__了。

2、每次优化的两个分量应该是违反__g(x)目标条件__比较多的。也就是说，本来应当是大于等于1的，越是小于1违反__g(x)目标条件__就越多；

或者换一种思路来理解，因为目标函数中存在m个变量，直接优化比较难，利用启发式的方法/EM算法的思想，每次优化的时候，只优化两个变量，将其它的变量看成常数项，这样SMO算法就将一个复杂的优化算法转换为一个比较简单的两变量优化问题了。

十四、SMO算法推导

1、构建β1、β2的函数

认为β1、β2是变量，其它β值是常量，从而将__目标函数转换__如下：

由于β₁y¹ + β₂y² = k，并且y² = 1，使用β2来表示β1的值：

将上式带入目标优化函数，就可以消去β1，从而只留下仅仅包含β2的式子。

深入分析__最终求得的公式__：

2、求解β₂的值

深入分析步骤1：

求解完最优的β值后，我们接下来要考虑限制条件。

---

3、考虑β1和β2的取值限定范围

考虑β1和β2的取值限定范围，假定新求出来的β值是满足我们的边界限制的，即如下所示：

当y1=y2的时候，β1+β2=k； 由于β的限制条件，我们可以得到：

当y1≠y2的时候，β1-β2=k；由于β的限制条件，我们可以得到：

结合β的取值限制范围以及函数W的β最优解，我们可以得带迭代过程中的最优解为：

然后根据β1和β2的关系，从而可以得到迭代后的β1的值：

求解β的过程中，相关公式如下：

---

求解最优β讨论到这里，不明白的可以私信。

下章讨论如何选择最初的β变量。