SVM系列第十二讲--SMO算法

今天我们来探究一下比较令人头疼的一个问题，SMO算法。

1、求解问题

我们首先来回顾一下我们要解决的问题，在将SVM原始问题转换成为对偶问题之后，我们先求的了w和b的值，带回到原式中并化简，得到了如下的最优化问题：

优化问题

可以看到，我们共有n个决策变量需要处理，每两个决策变量还会以乘积的形式出现在目标函数中，那么这个问题如何求解，就要用到我们的SMO算法。
序列最小最优化算法(SMO)可以高效的求解上述SVM问题，它把原始求解N个参数二次规划问题分解成很多个子二次规划问题分别求解，每个子问题只需要求解2个参数，方法类似于坐标上升，节省时间成本和降低了内存需求。每次启发式选择两个变量进行优化，不断循环，直到达到函数最优值。

2、SMO算法的主要步骤

这里我只想简单的介绍一下SMO算法的主要步骤，至于复杂的数学推导过程，大家可以参考：http://blog.csdn.net/luoshixian099/article/details/51227754
SMO算法的主要步骤如下图：

概括来说，主要分为以下两步：
(1) 选择接下来要更新的一对 αi 和 αj:采用启发式的方法进行选择，以使目标函数最大程度地接近其全 局最优值
(2) 将目标函数对 αi 和 αj 进行优化，保持其它所有的 αk (k<> i, j ) 不变