支持向量机增广拉格朗日方法的探究
|
摘要
支持向量机是机器学习中一种非常重要的分类方法,它在文本分类、语音识别、图像分析、信息安全等诸多领域均有重要的应用.提出了基于支持向量机对偶问题的一种非精确增广拉格朗日算法,讨论了所提算法的收敛性结果,并利用支持向量机模型的稀疏特性,结合矩阵不完全Cholesky分解以及Sherman-Morrison-Woodbury公式等程序实现技巧,极大地减少了所提算法的时间与空间复杂度.数值结果验证了提出算法的可行性和高效性.
Support vector machine is one of important classification methods in machine learning,which has important applications in varieties of fields,including text classification,speech recognition,image analysis,information security,and so on.This paper proposes an inexact augmented Lagrangian method for the dual problem of support vector machine,and carries out the analysis on convergence of the proposed algorithm.Based on the sparse property of support vector machines and some implementation techniques such as incomplete Cholesky decomposition and Sherman-MorrisonWoodbury formula,the complexities of time and space of our proposed algorithm are greatly reduced.Numerical experiments verify the feasibility and high efficiency of the proposed algorithm.
Support vector machine is one of important classification methods in machine learning,which has important applications in varieties of fields,including text classification,speech recognition,image analysis,information security,and so on.This paper proposes an inexact augmented Lagrangian method for the dual problem of support vector machine,and carries out the analysis on convergence of the proposed algorithm.Based on the sparse property of support vector machines and some implementation techniques such as incomplete Cholesky decomposition and Sherman-MorrisonWoodbury formula,the complexities of time and space of our proposed algorithm are greatly reduced.Numerical experiments verify the feasibility and high efficiency of the proposed algorithm.
引文
[1]VAPNIK V N.The nature of statistical learning theory[M].New York:Springer-Verlag,2000.
[2]BOSER E B,GUYON I M,VAPNIK V N.A training algorithm for optimal margin classifiers[C]∥HAUSSLER D.Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory,Pittsburgh.PA:ACM Press,1992:144-152.
[3]OSUNA E,FREUND R,GIROSI F.An improved training algorithm for support vector machines[C].Neural Networks for Signal Processing.IEEE Xplore,1997:276-285.
[4]JOACHIMS T.Making large-scale SVM learning practical[C].Technische UniversitDortmund,Sonderforschungsbereich 475:Komplexittsreduktion in multivariaten Datenstrukturen,1999:499-526.
[5]PLATT J.A fast algorithm for training support vector machines[J].Journal of Information Technology,1998,2(5):1-28.
[6]VOGT M.SMO Algorithms for support vector machines without Bias[C].Institute Report,Institute of Automatic Control.2002.
[7]SHEVADE S K,KEERTHI S S,BHATTACHARYYA C,et al.Improvements to the SMO algorithm for SVM regression[J].IEEE Transactions on Neural Networks,2000,11(5):1188-1193.
[8]KEERTHI S S,SHEVADE S K,BHATTACHATYYA C,et al.Improvements to Platt's SMO Algorithm for SVM Classifier Design[J].Neural Computation,2001,13(3):637-649.
[9]FAN R E,CHEN P H,LIN C J.Working set selection using second order information for training support vector machines[J].Journal of Machine Learning Research,2005,6(4):1889-1918.
[10]GLASMACHERS T,IGEL C.Second-order SMO improves SVM online and active learning[J].Neural Computation,2008,20(2):374-382.
[11]SUYKENS J A.First and second order SMO algorithms for LS-SVM Classifiers[M].Neural Precessing Letters,2011,33(1):31-44.
[12]CHANG C C,LIN C J.LIBSVM:a library for support vector machines[J].ACM,2011,2(3):1-27.
[13]ROCKAFELLAR R T.Augmented Lagrangian and applications of the proximal point algorithm in convex programming[J].Mathematics of Operations Research,1976,1(2):97-116.
[14]ROCKAFELLAR R T.Monotone operators and the proximal point algorithm[J].SIAM Journal on Control and Optimization,1976,14(5):877-898.
[15]LUQUE F J.Asymptotic convergence analysis of the proximal point algorithm[J].SIAM Journal on Control and Optimization,1984,22(2):277-293.
[16]MIFFLIN R.Semismooth and semiconvex functions in constrained optimization[J].SIAM Journal on Control and Optimization,1977,15(6):959-972.
[17]QI L,SUN J.A nonsmooth version of Newton’s method[J].Mathematical Programming,1993,58(1/3):353-367.
[18]ZHAO X Y,SUN D F,TOH K C.A Newton-CG augmented Lagrangian method for semidefinite programming[J].SIAM Journal on Optimization,2010,20(4):1737-1765.
[19]邓乃扬,田英杰.支持向量机:理论、算法与拓展[M].北京:科学出版社,2009.
[20]FERRIS M C,MUNSON T S.Semismooth support vector machines[J].Mathematical Programming,2004,101(1):185-204.
[21]FINE S,SCHEINBERG K.Efficient SVM training using low-rank kernel representations[J].Journal of Machine Learning Research,2001,2(4):243-264.
[2]BOSER E B,GUYON I M,VAPNIK V N.A training algorithm for optimal margin classifiers[C]∥HAUSSLER D.Proceedings of the 5th Annual ACM Workshop on Computational Learning Theory,Pittsburgh.PA:ACM Press,1992:144-152.
[3]OSUNA E,FREUND R,GIROSI F.An improved training algorithm for support vector machines[C].Neural Networks for Signal Processing.IEEE Xplore,1997:276-285.
[4]JOACHIMS T.Making large-scale SVM learning practical[C].Technische UniversitDortmund,Sonderforschungsbereich 475:Komplexittsreduktion in multivariaten Datenstrukturen,1999:499-526.
[5]PLATT J.A fast algorithm for training support vector machines[J].Journal of Information Technology,1998,2(5):1-28.
[6]VOGT M.SMO Algorithms for support vector machines without Bias[C].Institute Report,Institute of Automatic Control.2002.
[7]SHEVADE S K,KEERTHI S S,BHATTACHARYYA C,et al.Improvements to the SMO algorithm for SVM regression[J].IEEE Transactions on Neural Networks,2000,11(5):1188-1193.
[8]KEERTHI S S,SHEVADE S K,BHATTACHATYYA C,et al.Improvements to Platt's SMO Algorithm for SVM Classifier Design[J].Neural Computation,2001,13(3):637-649.
[9]FAN R E,CHEN P H,LIN C J.Working set selection using second order information for training support vector machines[J].Journal of Machine Learning Research,2005,6(4):1889-1918.
[10]GLASMACHERS T,IGEL C.Second-order SMO improves SVM online and active learning[J].Neural Computation,2008,20(2):374-382.
[11]SUYKENS J A.First and second order SMO algorithms for LS-SVM Classifiers[M].Neural Precessing Letters,2011,33(1):31-44.
[12]CHANG C C,LIN C J.LIBSVM:a library for support vector machines[J].ACM,2011,2(3):1-27.
[13]ROCKAFELLAR R T.Augmented Lagrangian and applications of the proximal point algorithm in convex programming[J].Mathematics of Operations Research,1976,1(2):97-116.
[14]ROCKAFELLAR R T.Monotone operators and the proximal point algorithm[J].SIAM Journal on Control and Optimization,1976,14(5):877-898.
[15]LUQUE F J.Asymptotic convergence analysis of the proximal point algorithm[J].SIAM Journal on Control and Optimization,1984,22(2):277-293.
[16]MIFFLIN R.Semismooth and semiconvex functions in constrained optimization[J].SIAM Journal on Control and Optimization,1977,15(6):959-972.
[17]QI L,SUN J.A nonsmooth version of Newton’s method[J].Mathematical Programming,1993,58(1/3):353-367.
[18]ZHAO X Y,SUN D F,TOH K C.A Newton-CG augmented Lagrangian method for semidefinite programming[J].SIAM Journal on Optimization,2010,20(4):1737-1765.
[19]邓乃扬,田英杰.支持向量机:理论、算法与拓展[M].北京:科学出版社,2009.
[20]FERRIS M C,MUNSON T S.Semismooth support vector machines[J].Mathematical Programming,2004,101(1):185-204.
[21]FINE S,SCHEINBERG K.Efficient SVM training using low-rank kernel representations[J].Journal of Machine Learning Research,2001,2(4):243-264.