5 SMO算法
在上文中,我们提到了求解对偶问题的序列最小最优化SMO算法,但并未提到其具体解法。首先看下最后悬而未决的问题:
等价于求解:
1998年,Microsoft Research的John C. Platt在论文《Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines》中提出针对上述问题的解法:SMO算法,它很快便成为最快的二次规划优化算法,特别是在针对线性SVM和数据稀疏时性能更优。
接下来,咱们便参考John C. Platt的这篇文章来看看SMO的解法是怎样的。
5.1 SMO算法的推导
5.2 SMO算法的步骤
那么在每次迭代中,如何更新乘子呢?引用这里的两张PPT说明下:
5.3 SMO算法的实现
行文至此,我相信,SVM理解到了一定程度后,是的确能在脑海里从头至尾推导出相关公式的,最初分类函数,最大化分类间隔,max1/||w||,min1/2||w||^2,凸二次规划,拉格朗日函数,转化为对偶问题,SMO算法,都为寻找一个最优解,一个最优分类平面。一步步梳理下来,为什么这样那样,太多东西可以追究,最后实现。如下图所示:
至于下文中将阐述的核函数则为是为了更好的处理非线性可分的情况,而松弛变量则是为了纠正或约束少量“不安分”或脱离集体不好归类的因子。
台湾的林智仁教授写了一个封装SVM算法的libsvm库,大家可以看看,此外这里还有一份libsvm的注释文档。
除了在这篇论文《fast training of support vector machines using sequential minimal optimization》中platt给出了SMO算法的逻辑代码之外,这里也有一份SMO的实现代码,大家可以看下。
6 SVM的应用
或许我们已经听到过,SVM在很多诸如文本分类,图像分类,生物序列分析和生物数据挖掘,手写字符识别等领域有很多的应用,但或许你并没强烈的意识到,SVM可以成功应用的领域远远超出现在已经在开发应用了的领域。
6.1 文本分类
一个文本分类系统不仅是一个自然语言处理系统,也是一个典型的模式识别系统,系统的输入是需要进行分类处理的文本,系统的输出则是与文本关联的类别。由于篇幅所限,其它更具体内容本文将不再详述。
OK,本节虽取标题为证明SVM,但聪明的读者们想必早已看出,其实本部分并无多少证明部分(特此致歉),怎么办呢?可以参阅《支持向量机导论》一书,此书精简而有趣。本节完。