Maximum-gain working set selection for SVMs. (English) Zbl 1222.90040

Summary: Support vector machines are trained by solving constrained quadratic optimization problems. This is usually done with an iterative decomposition algorithm operating on a small working set of variables in every iteration. The training time strongly depends on the selection of these variables. We propose the maximum-gain working set selection algorithm for large scale quadratic programming. It is based on the idea to greedily maximize the progress in each single iteration. The algorithm takes second order information from cached kernel matrix entries into account. We prove the convergence to an optimal solution of a variant termed hybrid maximum-gain working set selection. This method is empirically compared to the prominent most violating pair selection and the latest algorithm using second order information. For large training sets our new selection scheme is significantly faster.


90C20 Quadratic programming
90C06 Large-scale problems in mathematical programming
68T05 Learning and adaptive systems in artificial intelligence


SVMlight; LIBSVM; UCI-ml
Full Text: Link