Decomposition methods for linear support vector machines.
Journal
2003 IEEE International Conference on Acoustics, Speech, and Signal Processing, ICASSP '03, Hong Kong, April 6-10, 2003
Pages
868-871
Date Issued
2003
Author(s)
Abstract
We explain that decomposition methods, in particular, SMO-type algorithms, are not suitable for linear SVMs with more data than attributes. To remedy this difficulty, we consider a recent result by S.S. Keerthi and C.-J. Lin (see http://www.csie.ntu.edu.tw//spl sim/cjlin/papers/limit.ps.gz, 2002) that for an SVM which is not linearly separable, after C is large enough, the dual solutions are at similar faces. Motivated by this property, we show that alpha seeding is extremely useful for solving a sequence of linear SVMs. It largely reduces the number of decomposition iterations to the point that solving many linear SVMs requires less time than the original decomposition method for one single SVM. We also conduct comparisons with other methods which are efficient for linear SVMs, and demonstrate the effectiveness of the proposed approach for helping the model selection.
Type
conference paper