笔记(总结)-SVM(支持向量机)的理解-4
前三篇主要是介绍SVM的原理。最初SVM的原问题是凸二次优化问题,有现成的算法可以求解,费尽周折转换到对偶问题,一是在对偶问题形势下可以使用核函数,二是对偶问题我们可以高效求解。本篇主要介绍如何求解SVM。
SMO:Sequential Minimal Optimization
Coordinate Ascent(坐标上升法)
回到我们的对偶问题:
上述问题仅仅是关于一系列的优化问题,即:
考虑使用坐标上升法解决该问题:
算法内层循环将看做变量,其他的看做常量进行优化。在二维情况下,函数等高线图的优化路线如下:
可以看到,每一步优化中,都固定了一个变量,让另一个变量取值使目标函数“最优”,交替更新两个变量直到收敛或达到某种停止条件。然而由于如下限制,无法在对偶问题中使用坐标上升法求解:
假如我们想固定其他变量,更新,由于对偶问题的约束,固定其他变量后为常量。
SMO Algorithm
只选取一个更新是不行的,那么考虑一次至少更新两个变量。这便是SMO算法的动机由来,算法如下:
算法思想很简洁,先按某种方式选定要更新的两个变量,然后固定其它变量对进行更新来优化。
优化步骤
例如我们现在想优化,由约束可以得到:
又由对偶问题约束可以得到可行解如下图,必须位于直线被矩形区域截断的线段上:
由直线约束可以将表示为的函数,即:
由此得到目标函数的表达式为:
将目标函数展开,得到一个关于的开口向下的二次函数,当不考虑矩形区域约束时可以直接求导,得到最优解。然而实际情况中由于矩形约束,通常有取值区间,考虑最优解和取值区间的关系,更新得到实际最优值:
当得到后,可以依据直线约束更新。
选择步骤
选择违反KKT条件最多的样本对应的作为第一个变量,即对于每个训练样本,检查是否满足KKT条件(可参考SVM第2篇),选择不满足中程度最大者:
对于第二个变量,应该选择一个使目标函数数值增长最快的变量,但由于比较各变量所对应的目标函数值增幅的复杂度过高,SMO采用启发式规则,使选取的两变量对应样本之间间隔最大,直观上看,这样选取的两个变量差异较大,相比于对两个相似变量进行更新,差异更大的变量能对目标函数带来更大的变化。
至此我们得到了SMO的完整算法。
四篇过后,SVM基本讲述清楚。参考来源之前的总结博客有记述传送门,同时还参考了国科大《模式识别与机器学习》091M4042H课程兰艳艳老师slides。