基于改进停机准则的SMO算法
2014-07-07韩顺成马小晴陈进东潘丰
韩顺成,马小晴,陈进东,潘丰
江南大学轻工过程先进控制教育部重点实验室,江苏无锡 214122
◎理论研究、研发设计◎
基于改进停机准则的SMO算法
韩顺成,马小晴,陈进东,潘丰
江南大学轻工过程先进控制教育部重点实验室,江苏无锡 214122
在序列最小优化(Sequential Minimal Optimization,SMO)算法训练过程中,采用标准的KKT(Karush-Kuhn-Tucker)条件作为停机准则会导致训练后期速度下降。由最优化理论可知,当对偶间隙为零时,凸二次优化问题同样可以取得全局最优解。因此本文将对偶间隙与标准KKT条件同时作为SMO算法的停机准则,从而提出了改进停机准则的SMO算法。在保证训练精度的情况下,提高了SMO算法的训练速度。通过对一维和二维函数的两个仿真实验,验证了改进SMO算法的有效性。
支持向量机回归;序列最小优化算法;对偶间隙;KKT条件;停机准则
1 引言
支持向量机(Support Vector Machine,SVM)由V.Vapnik等人提出,是一种以统计学理论、结构风险最小原则和Wolfe对偶化理论为基础的机器学习方法[1]。目前SVM已被广泛应用于模式识别、回归估计、概率密度估计等各个领域。SVM可分为支持向量分类(Support Vector Classification,SVC)和支持向量回归(Support Vector Regression,SVR)[2]。
常见的SVM算法有选块算法、分解算法、SMO算法等,其中Platt提出的SMO算法[3]是目前SVM处理大规模数据较为有效的训练方法。SMO算法起初主要用于模式分类问题,后来得到扩展并应用于回归问题,本文主要针对SMO算法在SVR训练中的问题展开。
在SVR训练过程中,SMO算法一般采用KKT条件作为停机准则[4]。经研究发现,采用KKT条件作为停机准则,SMO算法在训练刚开始时目标函数变化很快,但训练后期则变化缓慢,从而导致了训练的速度下降[5-6]。……
