The difficulty in training a support vector machine (SVM) lies in the typically vast number of patterns used for the training process. In this work, we propose an adaptive constraint reduction primal-dual interior-point method for training the SVM with l1 hinge loss. We reduce the computational effort by assembling the normal equation matrix with a subset of well-chosen patterns. Starting with a large portion of the patterns, our proposed scheme excludes more and more unnecessary patterns as the iteration proceeds. Promising numerical results are reported.
Keywords: Constraint Reduction, Column Generation, Primal-Dual Interior-Point Method, Support Vector Machine
View PDF slides
Paper (DRAFT)
CRSVM.m (MATLAB function script)
Run2DToy.m (MATLAB test script)
Minimum requirement: MATLAB 7.0 or higher.