|
|
|
| Coordinate Descent Algorithms for Large-Scale SVDD |
| TAO Qing, LUO Qiang, ZHU Ye-Lei, CHU De-Jun |
| The Chinese Peoples Liberation Army Officer Academy,Hefei 230031 |
|
|
|
|
Abstract Support vector data description (SVDD) is an unsupervised learning method with significant application in image recognition and information security. Coordinate descent is an effective method for large-scale classification problems with simple operation and high convergence speed. In this paper, an efficient coordinate descent algorithm for solving large-scale SVDD is presented. The solution of concerned sub-problem at each iteration is derived in closed form and the computational cost is decreased through the accelerating strategy and cheap computation. Meanwhile, three methods for selecting sub-problem, analyzing and comparing their advantage and disadvantage are developed. The experiments on simulation and real large-scale database validate the performance of the proposed algorithm. Compared with LibSVDD, the proposed algorithm has great superiority which takes less than 1.4 seconds to solve a text database from ijcnn with 105 training examples.
|
|
Received: 14 July 2011
|
|
|
|
|
|
[1] Tax D M J,Duin R P W.Support Vector Domain Description.Pat-
tern Recognition Letters,1999,20(11/12/13): 1191-1199
[2] Schlkopf B,Platt J,Shawe-Taylor J,et al.Estimating the Support of a High-Dimensional Distribution .Neural Computation,2001,13(7): 1443-1471
[3] Tax D M J,Duin R P W.Support Vector Data Description.Machine Learning,2004,54: 45-66
[4] Tsang I W,Kwok J T,Cheung P M.Core Vector Machines: Fast SVM Training on Very Large Data Sets.Journal of Machine Learning Research,2005,6: 363-392
[5] Loosli G,Canu S.Comments on the “Core Vector Machines: Fast SVM Training on Very Large Data Sets”.Journal of Machine Learning Research,2007,8: 291-301
[6] 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
[7] Zhang T.Solving Large Scale Linear Prediction Problems Using Stochastic Gradient Descent Algorithms // Proc of the 21st International Conference on Machine Learning. Haifa,Israel,2004: 919-926
[8] Shalev-Shwartz S,Singer Y,Srebro N.Pegasos: Primal Estimated Sub-Gradient Solver for SVM // Proc of the 24th International Conference on Machine Learning.Corvallis,USA,2007: 807-814
[9] Bordes A,Bottou L.Careful Quasi-Newton Stochastic Gradient Descent.Journal of Machine Learning Research,2009,10: 1737-1754
[10] Joachims T.Training Linear SVMs in Linear Time // Proc of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.Philadelphia,USA,2006: 82-95
[11] Smola A J,Vishwanathan S V N,Le Q.Bundle Methods for Machine Learning // Platt J C,Koller D,Singer Y,et al,eds.Advances in Neural Information Processing Systems.Cambridge,USA: MIT Press,2007,XX: 1377-1384
[12] Lin C J,Weng R C,Keerthi S S.Trust Region Newton Method for Large-Scale Logistic Regression.Journal of Machine Learning Research,2008,9: 627-650
[13] 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
[14] Wu Yichao,Liu Yufeng.Robust Truncated Hinge Loss Support Vector Machines.Journal of the American Statistical Association,2007,102(479): 974-983
[15] Wu M,Ye J.A Small Sphere and Large Margin Approach for Novelty Detection Using Training Data with Outliers.IEEE Trans on Pattern Analysis and Machine Intelligence,2009,31(11): 2088-2092
[16] Saha A,Tewari A.On the Finite Time Convergence of Cyclic Coordinate Descent Methods [EB/OL].[2011-06-27].http://arxiv.org/abs/1005.2146
[17] Nesterov Y.Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems[EB/OL].[2010-01-01].http://130.104.5.100/cps/ucl/doc /core/documents/coredp2010_2web.pdf |
|
|
|
2012, Vol. 25 
