Argonne National Laboratory

Mixed-Integer Support Vector Machine

TitleMixed-Integer Support Vector Machine
Publication TypeConference Paper
Year of Publication2009
AuthorsGuan, W, Gray, A, Leyffer, S
Conference Name2nd NIPS Workshop on Optimization for Machine Learning (OPT 2009)
Conference LocationSutcliffe, England
Other NumbersANL/MCS-P1697
AbstractIn this paper, we propose a formulation of a feature selecting support vector machine based on the L0-norm. We explore a perspective relaxation of the optimization problem and solve it using mixed-integer nonlinear programming (MINLP) techniques. Given a training set of labeled data instances, we construct a max-margin classifier that minimizes the hinge loss as well as the cardinality of the weight vector of the separating hyperplane ||w||0, effectively performing feature selection and classification simultaneously in one optimization. We compare this relaxation with the standard SVM, recursive feature elimination (RFE), L1-norm SVM, and two approximated L0-norm SVM methods, and show promising results on real-world datasets in terms of accuracy and sparsity.