Classification Algorithm of l2-norm LS-SVM via Coordinate Descent
LIU Jian-Wei1,FU Jie1,WANG Shao-Lei2,LUO Xiong-Lin1
1.Department of Automation,China University of Petroleum,Beijing 102249 2.Wenmioil Production Plant of Tuha Oilfield Branch,China National Petroleum Corporation,Shanshan 838202
Abstract：The coordinate descent approach for l2 norm regulated least square support vector machine is studied. The datasets involved in the objective function for machine learning have larger data scale than the memory size has in image processing,human genome analysis,information retrieval,data management,and data mining. Recently,the coordinate descent method for large-scale linear SVM has good classification performance on large scale datasets. In this paper, the results of the work are extended to the least square support vector machine,and the coordinate descent approach for l2 norm regulated least square support vector machine is proposed. The vector optimization of the LS-SVM objective function is reduced to single variable optimization by the proposed algorithm. The experimental results on high-dimension small-sample datasets,middle-scale datasets and large-scale datasets demonstrate its effectiveness. Compared to the state-of-the-art LS-SVM classifiers,the proposed method can be a good candidate when data cannot fit in memory.
[1] Boser B E,Guyon I M,Vapnik V N. A Training Algorithm for Optimal Margin Classifiers // Proc of the 5th Annual ACM Conference on Computational Learning Theory.Pittsburgh,USA,1992: 144-152 [2] Suykens J A K,Van Gestel T,de Brabanter J,et al. Least Squares Support Vector Machines. Singapore: World Scientific,2002 [3] Suykens J A K,Vandewalle J. Least Squares Support Vector Machine Classifiers. Neural Processing Letters,1999,9(3): 293-300 [4] Lazaro J L,Dorronsoro J R. Least 1-Norm SVMs: A New SVM Variant between Standard and LS-SVMs // Proc of the 18th European Symposium on Artificial Neural Networks. Bruges,Belgium,2010: 135-140 [5] Suykens J A K,de Brabanter J,Lukas L,et al. Weighted Least Squares Support Vector Machines: Robustness and Sparse Approximation. Neurocomputing,2002,48(1): 85-105 [6] Valyon J,Horváth G. A Weighted Generalized LS-SVM. Periodica Polytechnica Electrical Engineering,2003,47 (3/4): 229-251 [7] SKI J M. Iteratively Reweighted Least Squares Classifier and Its l2-and l1-Regularized Kernel Versions. Bulletin of The Polish Academy of Sciences: Technical Sciences,2010,58(1): 171-182 [8] Liu Jingli,Li Jianping,Xu Weixuan,et al. A Weighted Lq Adaptive Least Squares Support Vector Machine Classifiers-Robust and Sparse Approximation. Expert Systems with Applications,2011,38(3): 2253-2259 [9] Chang K W,Hsieh C J,Lin C J. Coordinate Descent Method for Large-Scale l2-Loss Linear SVM. Journal of Machine Learning Research,2008,9: 1369-1398 [10] Fan R E,Chang K W,Hsieh C J,et al. LIBLINEAR: A Library for Large Linear Classification. Journal of Machine Learning Research,2008,9: 1871-1874 [11] Hsieh C J,Chang K W,Lin C J,et al. A Dual Coordinate Descent Method for Large-Scale Linear SVM // Proc of the 25th International Conference on Machine Learning. Helsinki,Finland,2008: 408-415 [12] Huang F L,Hsieh C J,Chang K W,et al. Iterative Scaling and Coordinate Descent Methods for Maximum Entropy Models. Journal of Machine Learning Research,2010,11: 815-848 [13] Yu H F,Hsieh C J,Chang K W,et al. Large Linear Classification When Data Cannot Fit in Memory // Proc of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Washington DC,USA,2010: 833-842 [14] Yu H F,Hsieh C J,Chang K W,et al. Large Linear Classification When Data Cannot Fit in Memory. ACM Trans on Knowledge Discovery from Data,2012,5(4): 1-23 [15] Bertsekas D P. Nonlinear Programming. 2nd Edition. Belmont,UK: Athena Scientific,1999 [16] Nesterov Y. Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems. [DB/OL]. [2012-01-05]. http://www.optimization-online.org/DB_FILE/2010/01/2527.pdf
2013, Vol. 26 
