今天我们来探究一下比较令人头疼的一个问题,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 ) 不变