Volume 31, pp. 156-177, 2008.

Adaptive constraint reduction for training support vector machines

Jin Hyuk Jung, Dianne P. O'Leary, and André L. Tits

Abstract

A support vector machine (SVM) determines whether a given observed pattern lies in a particular class. The decision is based on prior training of the SVM on a set of patterns with known classification, and training is achieved by solving a convex quadratic programming problem. Since there are typically a large number of training patterns, this can be expensive. In this work, we propose an adaptive constraint reduction primal-dual interior-point method for training a linear SVM with ${\ell }_1$ penalty (hinge loss) for misclassification. We reduce the computational effort by assembling the normal equation matrix using only a well-chosen subset of patterns. Starting with a large portion of the patterns, our algorithm excludes more and more unnecessary patterns as the iteration proceeds. We extend our approach to training nonlinear SVMs through Gram matrix approximation methods. We demonstrate the effectiveness of the algorithm on a variety of standard test problems.

Full Text (PDF) [435 KB], BibTeX

Key words

Constraint reduction, column generation, primal-dual interior-point method, support vector machine.

AMS subject classifications

90C20, 90C51, 90C59, 68W01.