SMO算法的简化及其在非正定核条件下的应用  

Simplification of SMO Algorithm and Its Application in Solving ε-SVR with Non-Positive Kernels

作　　者：周晓剑[1] 马义中[1] 朱嘉钢[2] 

机构地区：[1]南京理工大学经济管理学院,南京210094 [2]江南大学信息工程学院,江苏无锡214122

出　　处：《计算机研究与发展》2010年第11期1962-1969,共8页Journal of Computer Research and Development

基　　金：国家自然科学基金重点项目(70931002);国家自然科学基金项目(70672088)~~

摘　　要：SMO算法是求解大型支持向量机(SVM)的有效算法.已有的算法都必须判定4个Lagrange乘子位于哪个象限,从而使算法的实现更为复杂.此外,现有算法都假定核矩阵是正定的或半正定的,因此使其应用受到了限制.考虑到传统算法的不足,提出了一种用于-εSVR的简化SMO算法,进而将其用于求解非正定核的-εSVR.与已有的算法不同,通过将-εSVR的原始规划问题进行展开并求解其KKT条件,提出的算法只需考虑2个Lagrange乘子,从而有效地简化了算法的实现,并能方便地应用于非正定核SVR的求解.采用一个常用于衡量预测误差的函数对算法进行了测试,实验表明,与-εSVR现有的SMO算法相比,在不增加空间复杂度和时间复杂度的前提下避免了大量繁琐的判别条件,简化了算法的实现,这就为不同的损失函数所对应的SVR提供了一个通用的SMO算法,从而有利于SVR的推广应用.另外,提出的求解非正定核的ε-SVR的方法也为求解其他的非正定核SVR提供了一个思路.Sequential minimal optimization（SMO） algorithm is an effective method for solving large-scale support vector machine（SVM）.The existing algorithms need to judge which quadrant the four Lagrange multipliers lie in,which complicates their implementation.In addition,the existing algorithms all assume that the kernel functions are positive definite or positive semi-definite,limiting their applications.Having considered these deficiencies of the traditional ones,a simplified SMO algorithm based on SVR is proposed,and further applied in solving ε-SVR with non-positive kernels.Different from the existing algorithms,the proposed algorithm in this paper just considers two Lagrange multipliers in implementation by expanding the original dual programming of ε-SVR and solving its KKT conditions,thus it is easily applied in solving ε-SVR with non-positive kernels.The presented algorithm is evaluated by a benchmark problem.Compared with the existing algorithms,the simplified one is much easier to be implemented without sacrificing space and time efficiency,and can achieve an ideal regression accuracy under the premise of ensuring convergence.Therefore it has certain theoretical and practical significance.Furthermore,the proposed algorithm is benefit to present a general-purpose SMO algorithm for SVR with all types of loss functions.Additionally,the proposed method,which is used to deal with ε-SVR,is also available to the other SVR with non-positive kernels.

关 键 词：非正定核 SMO算法 ε-支持向量回归机 支持向量机 拉格朗日乘子 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]