Learning sparse classifiers with difference of convex functions algorithms

Abstract

Sparsity of a classifier is a desirable condition for high-dimensional data and large sample sizes. This paper investigates the two complementary notions of sparsity for binary classification: sparsity in the number of features and sparsity in the number of examples. Several different losses and regularizers are considered: the hinge loss and ramp loss, and ℓ₂, ℓ₁, approximate ℓ₀, and capped ℓ₁ regularization. We propose three new objective functions that further promote sparsity, the capped ℓ₁ regularization with hinge loss, and the ramp loss versions of approximate ℓ₀ and capped ℓ₁ regularization. We derive difference of convex functions algorithms (DCA) for solving these novel non-convex objective functions. The proposed algorithms are shown to converge in a finite number of iterations to a local minimum. Using simulated data and several data sets from the University of California Irvine (UCI) machine learning repository, we empirically investigate the fraction of features and examples required by the different classifiers.

Keywords:

• sparse features and examples
• binary classification
• DCA

Notes

^†This paper was presented at the International Conference on Optimization: Techniques, Applications (ICOTA 8), Shanghai, 10–13 December 2010.

http://www.python.org

http://abel.ee.ucla.edu/cvxopt/