SMO算法流程
SMO 算法流程
python代码见github
问题简介
SMO(Sequential Minimal
Optimization)用于解决支持向量机中的对偶问题的最优化求解过程,该问题为:
而此问题也满足KKT条件要求
流程
该问题是一种凸二次规划问题,但是如果当作一般情况处理,计算过于繁琐。好在我们可以利用该问题特殊情况,得以特殊处理以简化流程。
SMO算法的核心思想是利用
以下,为了表述方便,我们每次选择的变量定为
这里引入我们之前的条件,并设定
带入
其中
我们需要对其最大化,这里进行求导,赋值0求极值
至此,问题似乎得以解决,我们似乎只需要通过该等式解出
所以,这里我们考虑如何调整
这里
所以我们将
将其带入
其中
但此时,我们还没有考虑到条件:
由于
其中(2)(3)可以归为一种情况
在这种情况下,应满足
此外,(1)(4)可以归为另一种情况
在这种情况下,应满足
所以最后更新
至此我们确定了
这里我们需要明确一件事情,到目前为止,我们所作的事情就是求
接下来,我们将讨论偏置
最后,我们来讨论,如何进行变量的选取。首先我们应该确定第一个变量,此时,我们变量样本集,选取第一个不满足KKT条件的样本。这里写作KKT条件为:
然后依照规则选取第二个变量,执行优化。当完成后,我们开始遍历非边界样例集(即满足
关于选取第二个变量的规则,我们的原则是让
如果非边界集上没有,则在整个样本集上选择第二个变量,
如果整个样本集依然不存在,则重新选择第一个变量。
参考
1.https://blog.csdn.net/luoshixian099/article/details/51227754
2.https://www.cnblogs.com/jerrylead/archive/2011/03/18/1988419.html
3.https://www.jianshu.com/p/0c433f6f4141
4.https://zhuanlan.zhihu.com/p/257866920
5.John Platt.Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines (https://www.microsoft.com/en-us/research/publication/sequential-minimal-optimization-a-fast-algorithm-for-training-support-vector-machines/)