A linear Support Vector Machine solver for a large number of training examples

• Autorzy: Białoń P.
• Języki publikacji: EN

Abstrakty

EN

A new linear Support Vector Machine algorithm and solver are presented. The algorithm is in a twofold way well-suited for problems with a large number of training examples. First, unlike many optimization algorithms, it does not simultaneously keep all the examples in RAM and thus does not exhaust the memory (moreover, it smartly passes through disk files storing the data: two mechanisms reduce the computation time by disregarding some input data without a loss in solution quality). Second, it uses the analytical center cutting plane scheme, appearing as more efficient for hard parameter settings than the Kelley's scheme used in other solvers, like SVM_perf. The experiments with both real-life and artificial examples are described. In one of them the solver proved to be capable of solving a problem with one billion training examples. A critical analysis of the complexity of SVM_perf is given.

Słowa kluczowe

EN

support vector machine (SVM); analytic center cutting plane method; RAM volume required

• Wydawca: Systems Research Institute, Polish Academy of Sciences
• Czasopismo: Control and Cybernetics
• Rocznik: 2009
• Tom: Vol. 38, no 1
• Strony: 281--300
• Opis fizyczny: Bibliogr. 21 poz., wykr.

Twórcy

autor

Białoń P.

• National Institute of Telecommunications, 1 Szachowa Str., Warsaw, Poland

Bibliografia

• ATKINSON, D.S. and VAIDYA, P.M. (1995) A cutting plane algorithm that uses analytic centers. Mathematical Programming, Series B, 69, 1-43.
• BAUSCHKE, H. and BORWEIN, J. (1996) On projection algorithms for solving convex feasibility problems. SIAM Review 38 (3), 367-426.
• BIAŁOŃ, P., CHUDZIAN, C., FLOREK, J. AND MAJDAN, M. (2004) Przetwarzanie informacji i modelowanie w środowiskach rozproszonych (in Polish). Technical Report 06.30.002.4, National Institute of Telecommunications, Warsaw, Poland.
• BORDES, A. and BOTTOU, L. (2005) The Huller: a simple and efficient online SVM. Machine Learning: ECML 2005, Lecture Notes in Artificial Intelligence. Springer Verlag, 505-512.
• DAVIS, T.A. and HAGER W.W. (1999) Modifying a sparse Cholesky Factorization. SIAM J. Matrix Anal. Appl. 20 (3), 606-627.
• DAVIS, T.A. and HAGER W.W. (2007) User Guide for CHOLMOD: a sparse Cholesky factorization and modification package. Dept. of Computing and Information Science and Engineering, Univ.- of Florida, Gainesville, FL, Version 1.5.
• FERRIS, M. and MUNSON, T. (2003) Interior-point methods for massive support vector machines. SIAM J. Optimization, 13 (3), 783-804.
• FINE, S. and SCHEINBERG, K. (2001) Efficient SVM training using low-rank kernel representations. Journal of Machine Learning Research 2, 243-264.
• GOFFIN J.L. and VIAL, J.P. (1999) Convex Nondifferentiable optimization: a survey focused on the analytic center cutting plane method. HEC/Logilab Technical Report 99.02.
• JOACHIMS, T. (1998) Making large-scale support vector machine learning practical. In: B. Scholköpf et al., eds.. Advances in Kernel Methods Support Vector Learning. MIT Press, Cambridge, 148-168.
• JOACHIMS, T. (2006) Training linear SVMs in linear time. Proceedings of the 12th ACM Conference on Knowledge Discovery and Data Mining (KDD), Philadelphia, USA. ACM Press, New York, 217-226.
• KARMARKAR, N. (1984) A new polynomial-time algorithm for linear programming. Combinatorica 4, 373-395.
• KELLEY, J. (1960) The cutting plane method for solving convex programs. Journal of the Society for Industrial Applied Mathematics 8, 703-712.
• KIWIEL, K.C. (1996) The efficiency of subgradient projection methods for convex optimization, Part I: General level methods. SIAM Control Optim., 34 (2), 660-676.
• MUSICANT, D.R. (2000) Data Mining via Mathematical Programing and Machine Learning. Ph.D. thesis. University of Wisconsin, Madison.
• NESTEROV, YU. (2005) Complexity estimates of some cutting plane methods based on the analytic barrier. Mathematical Programming 69, 149-176.
• PLATT, J. (1998) Fast training support vector machines using sequential minimal optimization. In: B. Scholköpf et al., eds., Advances in Kernel Methods Support Vector Learning. MIT Press, 185-208.
• SCHEINBERG, K. (2006) An efficient implementation of an active set method for SVMs. Journal of Machine Learning Research 7, 2237-2257.
• TERLAKY, T. (ed.) (1996) Interior Point Methods of Mathematical Programming. Kluwer, Dordrecht.
• VANDENBERGHE, L. and COMANOR, K. (2003) A sequential analytic centering approach to the support vector machine. Proceedings of SPIE Advanced Signal Processing Algorithms, Architectures, and Implementations XIII, San Diego, USA. SPIE - International Society for Optical Engineering, 209-218.
• VAPNIK, V.N. (1995) The Nature of Statistical Learning Theory. Springer, New York.