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

Wei Guan and Alexander Gray

Computational Statistics & Data Analysis, 2013, vol. 67, issue C, 136-148

Abstract: This paper considers a class of feature selecting support vector machines (SVMs) based on Lq-norm regularization, where q∈(0,1). The standard SVM [Vapnik, V., 1995. The Nature of Statistical Learning Theory. Springer, NY.] minimizes the hinge loss function subject to the L2-norm penalty. Recently, L1-norm SVM (L1-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. L0-norm penalization would result in more powerful sparsification, but exact solution is NP-hard. This raises the question of whether fractional-norm (Lq for q between 0 and 1) penalization can yield benefits over the existing L1, and approximated L0 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 L1-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 L1-SVM, and recent approximated L0-SVM approaches.

Keywords: Support vector machine; Feature selection; Fractional-norm SVM; Difference of Convex functions programming; Reweighted L1-norm SVM; Low sample size high dimensional data set (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0167947313000352
Full text for ScienceDirect subscribers only.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:csdana:v:67:y:2013:i:c:p:136-148

DOI: 10.1016/j.csda.2013.01.020

Access Statistics for this article

Computational Statistics & Data Analysis is currently edited by S.P. Azen

More articles in Computational Statistics & Data Analysis from Elsevier
Bibliographic data for series maintained by Catherine Liu ().