Sparse high-dimensional fractional-norm support vector machine via DC programming

作者：Guan Wei^*; Gray Alexander

来源：Computational Statistics & Data Analysis, 2013, 67: 136-148.

DOI：10.1016/j.csda.2013.01.020

• Support vector machine
• Feature selection
• Fractional-norm SVM
• Difference of Convex functions programming
• Reweighted L-1-norm SVM
• Low sample size high dimensional data set

This paper considers a class of feature selecting support vector machines (SVMs) based on L-q-norm regularization, where q is an element of (0, 1). The standard SVM [Vapnik, V., 1995. The Nature of Statistical Learning Theory. Springer, NY.] minimizes the hinge loss function subject to the L-2-norm penalty. Recently, L-1-norm SVM (L-1-SVM) [Bradley, P., Mangasarian, O., 1998. Feature selection via concave minimization and support vector machines. In; Machine Learning Proceedings of the Fifteenth International Conference (ICML98). Citeseer, pp. 82-90.] was suggested for feature selection and has gained great popularity since its introduction. L-0-norm penalization would result in more powerful sparsification, but exact solution is NP-hard. This raises the question of whether fractional-norm (L-q for q between 0 and 1) penalization can yield benefits over the existing L-1, and approximated L-0 approaches for SVMs. The major obstacle to answering this is that the resulting objective functions are non-convex. This paper addresses the difficult optimization problems of fractional-norm SVM by introducing a new algorithm based on the Difference of Convex functions (DC) programming techniques [Pham Dinh, T., Le Thi, H., 1998. A DC optimization algorithm for solving the trust-region subproblem. SIAM J. Optim. 8 (2), 476-505. Le Thi, H., Pham Dinh, T., 2008. A continuous approach for the concave cost supply problem via DC programming and DCA. Discrete Appl. Math. 156 (3), 325-338.], which efficiently solves a reweighted L-1-SVM problem at each iteration. Numerical results on seven real world biomedical datasets support the effectiveness of the proposed approach compared to other commonly-used sparse SVM methods, including L-1-SVM, and recent approximated L-0-SVM approaches.

• 出版日期2013-11