机器学习算法系列(12)：SVM(4)—SMO

SMO算法是⼀一种启发式算法，其基本思想是：如果所有变量量的解都满⾜足最优化问题的KKT条件，那么这个优化问题的解就得到了了，因为KKT条件是该优化问题的充分必要条件。否则，选择两个变量量，固定其他变量量，针对这两个变量量构建⼀一个⼆二次规划问题。这个⼆二次规划问题关于这两个变量量的解应该是更更接近原始⼆二次规划问题的解，因为这会使得原始⼆二次规划问题的⽬目标函数值变得更更⼩小。重要的是，这时⼦子问题可以通过解析⽅方法求解，这样就可以⼤大⼤大提升整个算法的计算速度。⼦子问题有两个变量量，⼀一个是违反KKT条件最严重的那个，另⼀一个由约束条件⾃自动确定。如果SMO算法将原问题不不断分解为⼦子问题并对⼦子问题求解，进⽽而达到求解原问题的⽬目的。

四、序列列最⼩小最优化算法（SMO）

通常对于优化问题，我们没有办法的时候就会想到最笨的办法，也就是梯度下降。注意我们这⾥里里的问题是要求最⼤大值，只要在前⾯面加上⼀一个负号就可以转化为求最⼩小值，所以GradientDescent和的⽅方向，因此只要沿着梯度的反⽅方向⾛走，就能使得函数值减⼩小得越⼤大，从⽽而期望迅速达到最⼩小不不过对于⼆二次规划问题，极值只有⼀一个，所以是没有局部极值的问题。

GradientAscend并没有什什么本质的区别，其基本思想直观上来说就是：梯度是函数值增幅最⼤大

值。当然普通的GradientDescent并不不能保证达到最⼩小值，因为很有可能陷⼊入⼀一个局部极⼩小值。另外还有⼀一种叫做CoordinateDescend的变种，它每次只选择⼀一个维度，例例如

程⼀一个⼀一元函数，然后针对这个⼀一元函数求最⼩小值，如此反复轮换不不同的维度进⾏行行迭代。

a=(a1,···,an)，它每次选取ai为变量量，⽽而将其他都看成是常数，从⽽而原始的问题在这⼀一步编CoordinateDescend的主要⽤用处在于那些原本很复杂，但是如果只限制在⼀一维的情况下则变得

很简单甚⾄至可以直接求极值的情况，例例如我们这⾥里里的问题，暂且不不管约束条件，如果只看⽬目标函数的话，当a只有⼀一个分量量是变量量的时候，这就是⼀一个普通的⼀一元⼆二次函数的极值问题，初中⽣生也会做，带⼊入公式即可。

然后这⾥里里还有⼀一个问题就是约束条件的存在，其实如果没有约束条件的话，本身就是⼀一个多元的⼆二次规划问题，也是很好求解的。但是有了了约束条件，结果让CoordinateDescend变得很尴尬

N

了了，直接根据第⼆二个约束条件∑i=1aiyi=0,a1的值⽴立即就可以定下来，事实上，迭代每个坐标维度，最后发现优化根本进⾏行行不不下去，因为迭代了了⼀一轮之后会发现根本没有任何进展，⼀一切停留留在初始值。

所以SMO⼀一次选取了了两个坐标来进⾏行行优化。例例如，我们假设现在选取a1和a2为变量量，其余为常量量，则根据约束条件我们有：

N

0⟹=−

N

−⟺(K−)

1ay=0⟹a2=−aiyi−a1y1⟺y2(K−a1y1)∑ii∑y2(i=3)i=1

其中那个从3到n的作和都是常量量，我们统⼀一记作K。将这个式⼦子代⼊入原来的⽬目标函数中，可以消去

NN

a2，从⽽而变成⼀一个⼀一元⼆二次函数。总之现在变成了了⼀一个带区间约束的⼀一元⼆二次函数极值问题。唯

⼀一要注意的就是这⾥里里的约束条件，⼀一个就是a1本身需要满⾜足0≤ai≤C,然后由于a2也要满⾜足同样的约束，即：0≤y2(K−a1y1)≤C，可以得带a1的⼀一个可⾏行行区间，同[0,C]交集即可得到最终的可⾏行行区间。投影到a1轴上所对应的区间即是a1的取值范围，在这个区间内求⼆二次函数的

最⼤大值即可完成SMO的⼀一步迭代。

同CoordinateDescent⼀一样，SMO也会选取不不同的两个coordinate维度进⾏行行优化，可以看出由

于每⼀一个迭代步骤实际上是⼀一个可以直接求解的⼀一元⼆二次函数极值问题，所以求解⾮非常⾼高效。此外，SMO也并不不是⼀一次或随机地选取两个坐标函数极值问题，⽽而是有⼀一些启发式的策略略来选取最优的两个坐标维度。