Optimal Feature Selection for Support Vector Machine Classifiers

Binary classification is a fundamental task in machine learning. It consists of learning a relationship between observable features of a set of training objects and their observable membership to either of two classes to predict as accurately as possible the class membership of new test objects whose features are observable but whose class membership is unknown. One of the most successful methods for binary classification is the support vector machine classifier that aims at finding a hyperplane in the feature space separating the training objects of the two classes. However, the accuracy of this classifier in predicting the correct classes strongly depends on the features selected for determining the hyperplane. In this paper, we propose the first exact approach, which is based on mixed-integer quadratic programming and delayed constraint generation, to identify an optimal set of relevant features for determining the hyperplane. The results of a computational experiment demonstrate that the proposed approach is able to successfully select an optimal set of relevant features in a short running time even for classification tasks with over 10,000 objects and 100 features.