Cheng Soon Ong, Le Thi Hoai An: "Learning sparse classifiers with Difference of Convex functions Algorithms".

Abstract: Sparsity of a classi er is a desirable condition for high dimensional data and large sample sizes. This paper investigates the two complementary notions of sparsity for binary classi cation: sparsity in the number of features and sparsity in the number of examples. Several di erent losses and regularizers are considered: the hinge loss and ramp loss, and l2, l1, approximate l0, and capped l1 regularization. We propose three new objective functions that further promote sparsity, the capped l1 regularization with hinge loss, and the ramp loss versions of approximate l0 and capped l1 regularization. We derive di erence of convex functions algorithms (DCA) for solving these novel non-convex objective functions. The proposed algorithms are shown to converge in a nite number of iterations to a local minimum. Using simulated data and several datasets from the UCI machine learning repository, we empirically investigate the fraction of features and examples required by the di erent classi ers.

 
Keywords: Sparse features and examples, binary classi cation, DCA.

Citation: Cheng Soon Ong, Le Thi Hoai An, Learning sparse classifiers with Difference of Convex functions Algorithms, Optimization Methods and Software 28:4, pp. 830-854,  2013.
 
Download link