Adaptive Constraint Reduction for Training Support Vector Machines

Jin Hyuk Jung (jjungcs.umd.edu)
Dianne P. O'Leary (olearycs.umd.edu)
Andre L. Tits (andreumd.edu)

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.

Keywords: Constraint Reduction, Column Generation, Primal-Dual Interior Point Method, Support Vector Machine

Category 1: Nonlinear Optimization (Quadratic Programming )

Category 2: Applications -- Science and Engineering (Data-Mining )

Citation: University of Maryland, College Park, Maryland, October 2007.

Download: [PDF]

Entry Submitted: 10/31/2007
Entry Accepted: 10/31/2007
Entry Last Modified: 11/30/2007

Modify/Update this entry