Feature Selection for Nonlinear Kernel Support Vector Machines

An easily implementable mixed-integer algorithm is pro- posed that generates a nonlinear kernel support vector ma- chine (SVM) classifier with reduced input space features. A single parameter controls the reduction. On one publicly available dataset, the algorithm obtains 92.4% accuracy with 34.7% of the features compared to 94.1% accuracy with all features. On a synthetic dataset with 1000 features, 900 of which are irrelevant, our approach improves the ac- curacy of a full-feature classifier by over 30%. The pro- posed algorithm introduces a diagonal matrix E with ones for features present in the classifier and zeros for removed features. By alternating between optimizing the continu- ous variables of an ordinary nonlinear SVM and the integer variables on the diagonal of E, a decreasing sequence of objective function values is obtained. This sequence con- verges to a local solution minimizing the usual data fit and solution complexity while also minimizing the number of features used.