A Convergent Hybrid Decomposition Algorithm Model for SVM Training
Authors:
- Stefano LucidiSLStefano Lucidi
- Laura PalagiLPLaura Palagi
- Arnaldo RisiARArnaldo Risi
- Marco SciandroneMSMarco Sciandrone
- 8 May 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Neural Networks
- Vol. 20 (6) , 1055-1060
Abstract
Training of support vector machines (SVMs) requires to solve a linearly constrained convex quadratic problem. In real applications, the number of training data may be very huge and the Hessian matrix cannot be stored. In order to take into account this issue, a common strategy consists in using decomposition algorithms which at each iteration operate only on a small subset of variables, usually referred to as the working set. Training time can be significantly reduced by using a caching technique that allocates some memory space to store the columns of the Hessian matrix corresponding to the variables recently updated. The convergence properties of a decomposition method can be guaranteed by means of a suitable selection of the working set and this can limit the possibility of exploiting the information stored in the cache. We propose a general hybrid algorithm model which combines the capability of producing a globally convergent sequence of points with a flexible use of the information in the cache. As an example of a specific realization of the general hybrid model, we describe an algorithm based on a particular strategy for exploiting the information deriving from a caching technique. We report the results of computational experiments performed by simple implementations of this algorithm. The numerical results point out the potentiality of the approach.Keywords
This publication has 9 references indexed in Scilit:
- A Study on SMO-Type Decomposition Methods for Support Vector MachinesIEEE Transactions on Neural Networks, 2006
- On the convergence of a modified version of SVMlightalgorithmOptimization Methods and Software, 2005
- Polynomial-Time Decomposition Algorithms for Support Vector MachinesMachine Learning, 2003
- Asymptotic convergence of an SMO algorithm without any assumptionsIEEE Transactions on Neural Networks, 2002
- Interior-Point Methods for Massive Support Vector MachinesSIAM Journal on Optimization, 2002
- Convergence of a Generalized SMO Algorithm for SVM Classifier DesignMachine Learning, 2002
- On the convergence of the decomposition method for support vector machinesIEEE Transactions on Neural Networks, 2001
- The analysis of decomposition methods for support vector machinesIEEE Transactions on Neural Networks, 2000
- Gradient-based learning applied to document recognitionProceedings of the IEEE, 1998