Support Vector Machine (SVM) has been widely applied in machine learning and data mining. However, a sparse representation of a SVM classifier with respect to input features is desirable for many applications. In this paper, by introducing a 0-1 control variable to each input feature, the $l_0$-norm sparse SVM (SSVM) is converted to a mixed integer programming (MIP) problem. Rather than directly solving this MIP, we propose an efficient cutting plane algorithm combining with the multiple kernel learning (MKL) to solve its convex relaxation. We also give a proof of global convergence for our proposed method. Comprehensive experimental results on one synthetic and 10 real world datasets show that our proposed method can obtain better or competitive performance compared with existing SVM-based feature selection methods in term of sparsity and generalization performance. Moreover, our proposed method can effectively handle large-scale and extremely high dimensional problems.
Download PDF