Generalized spectral bounds for sparse LDA

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.

REFERENCES

• 1: Alon et al. (1999). Broad patterns of gene expression revealed by clustering analysis of tumor and normal colon cancer tissues Cell Biology, 96, 6745--6750.
• 2: Avrim L. Blum , Pat Langley, Selection of relevant features and examples in machine learning, Artificial Intelligence, v.97 n.1-2, p.245-271, Dec. 1997 [doi>10.1016/S0004-3702(97)00063-5]
• 3: d'Aspremont, A., Ghaoui, L. E., Jordan, M. I., & Lanckriet, G. R. G. (2004). A direct formulation for sparse PCA using semidefinite programming. Advances in Neural Information Processing Systems 17 (pp. 803--809). MIT Press.
• 4: Isabelle Guyon , André Elisseeff, An introduction to variable and feature selection, The Journal of Machine Learning Research, 3, 3/1/2003
• 5: Isabelle Guyon , Jason Weston , Stephen Barnhill , Vladimir Vapnik, Gene Selection for Cancer Classification using Support Vector Machines, Machine Learning, v.46 n.1-3, p.389-422, 2002 [doi>10.1023/A:1012487302797]
• 6: Roger A. Horn , Charles R. Johnson, Matrix analysis, Cambridge University Press, New York, NY, 1985
• 7: Ko, C., Lee, J., & Queyranne, M. (1995). An exact algorithm for maximum entropy sampling. Operations Research, 43, 684--691.
• 8: Kohavi, R., & John, G. (2003). Wrappers for feature subset selection. Artificial Intelligence Journal, 3, 1157--1182.
• 9: Mika, S., Rätsch, G., & Müüller, K.-R. (2001). A mathematical programming approach to the kernel fisher algorithm. Advances in Neural Information Processing Systems 13 (pp. 591--597). MIT Press.
• 10: Moghaddam, B., Weiss, Y., & Avidan, S. (2006). Spectral Bounds for Sparse PCA: Exact & Greedy Algorithms. Advances in Neural Information Processing Systems 18 (pp. 915--922). MIT Press.
• 11: George L. Nemhauser , Laurence A. Wolsey, Integer and combinatorial optimization, Wiley-Interscience, New York, NY, 1988
• 12: Fast Branch & Bound Algorithms for Optimal Feature Selection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.7, p.900-912, July 2004 [doi>10.1109/TPAMI.2004.28]
• 13: Tibshirani, R. (1995). Regression shrinkage and selection via Lasso. Journal of the Royal Statistical Society B, 58, 267--288.
• 14: Zou, H., Hastie, T., & Tibshirani, R. (2004). Sparse principal component analysis (Technical Report). Statistics Department, Stanford University.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Eigenvalues and eigenvectors (direct and iterative methods)

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Statistical
      I.5.2 Design Methodology

General Terms:
Algorithms