Fast Solution in Sparse LDA for Binary Classification
- Created: Saturday, 01 May 2010
Special properties of binary classification and greedy algorithms enable speedup.
An algorithm that performs sparse linear discriminant analysis (Sparse-LDA) finds near-optimal solutions in far less time than the prior art when specialized to binary classification (of 2 classes). Sparse-LDA is a type of feature- or variable-selection problem with numerous applications in statistics, machine learning, computer vision, computational finance, operations research, and bioinformatics. Because of its combinatorial nature, feature- or variable-selection problems are “NP-hard” or computationally intractable in cases involving more than 30 variables or features. Therefore, one typically seeks approximate solutions by means of greedy search algorithms.
Sparse LDA requires solving generalized eigenvalue problems for a large number of variable subsets (represented by the submatrices of the input within-class and between-class covariance matrices). In the general (full-rank) case, the amount of computation scales at least cubically with the number of variables and thus the size of the problems that can be solved is limited accordingly. However, in binary classification, the principal eigenvalues can be found using a special analytic formula, without resorting to costly iterative techniques. The present algorithm exploits this analytic form along with the inherent sequential nature of greedy search itself. Together this enables the use of highly-efficient partitioned-matrix-inverse techniques that result in large speedups of computation in both the forward-selection and backward-elimination stages of greedy algorithms in general.
This work was done by Baback Moghaddam of Caltech for NASA’s Jet Propulsion Laboratory.