A General L1-norm Support Vector Machine for Feature Selection

In this paper, we introduce a new general formulation of L1-norm SVM (GL1-SVM) for feature selection and represent it as a polynomial mixed 0-1 programming problem. We prove that solving the new proposed optimization problem gives smaller error penalty and enlarges the margin between two support vector hyper-planes, thus possibly gives better generalization capability of SVM than solving the traditional L1-norm SVM proposed by Bradley and Mangasarian. We also propose a new search method that ensures the globally feature subsets by means of the new GL1-SVM. The proposed search method is based on solving a mixed 0-1 linear programming problem by using branch and bound algorithm. Experimental results obtained over the UCI and LIBSVM data sets show that the new general L1-norm SVM gives better generalization capability, while in many cases selecting fewer features than the traditional L1-norm SVM does.