Abstract | ||
---|---|---|
We present a discrete spectral framework for the sparse or cardinality-constrained solution of a generalized Rayleigh quotient. This NP-hard combinatorial optimization problem is central to supervised learning tasks such as sparse LDA, feature selection and relevance ranking for classification. We derive a new generalized form of the Inclusion Principle for variational eigenvalue bounds, leading to exact and optimal sparse linear discriminants using branch-and-bound search. An efficient greedy (approximate) technique is also presented. The generalization performance of our sparse LDA algorithms is demonstrated with real-world UCI ML benchmarks and compared to a leading SVM-based gene selection algorithm for cancer classification. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1145/1143844.1143925 | ICML |
Keywords | Field | DocType |
generalized rayleigh quotient,feature selection,generalized spectral bound,new generalized form,optimal sparse linear discriminants,np-hard combinatorial optimization problem,sparse lda algorithm,inclusion principle,cancer classification,sparse lda,leading svm-based gene selection,supervised learning,branch and bound,gene selection | Rayleigh quotient,Feature selection,Ranking,Pattern recognition,Combinatorial optimization problem,Computer science,Sparse approximation,Support vector machine,Supervised learning,Artificial intelligence,Machine learning,Eigenvalues and eigenvectors | Conference |
ISBN | Citations | PageRank |
1-59593-383-2 | 43 | 3.63 |
References | Authors | |
7 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
baback moghaddam | 1 | 3353 | 701.90 |
Yair Weiss | 2 | 10240 | 834.60 |
Shai Avidan | 3 | 3291 | 208.12 |