A least squares formulation for a class of generalized eigenvalue problems in machine learning

ABSTRACT

Many machine learning algorithms can be formulated as a generalized eigenvalue problem. One major limitation of such formulation is that the generalized eigenvalue problem is computationally expensive to solve especially for large-scale problems. In this paper, we show that under a mild condition, a class of generalized eigenvalue problems in machine learning can be formulated as a least squares problem. This class of problems include classical techniques such as Canonical Correlation Analysis (CCA), Partial Least Squares (PLS), and Linear Discriminant Analysis (LDA), as well as Hypergraph Spectral Learning (HSL). As a result, various regularization techniques can be readily incorporated into the formulation to improve model sparsity and generalization ability. In addition, the least squares formulation leads to efficient and scalable implementations based on the iterative conjugate gradient type algorithms. We report experimental results that confirm the established equivalence relationship. Results also demonstrate the efficiency and effectiveness of the equivalent least squares formulations on large-scale problems.

REFERENCES

• 1: Sameer Agarwal , Kristin Branson , Serge Belongie, Higher order learning with graphs, Proceedings of the 23rd international conference on Machine learning, p.17-24, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143847]
• 2: Mikhail Belkin , Partha Niyogi , Vikas Sindhwani, Manifold Regularization: A Geometric Framework for Learning from Labeled and Unlabeled Examples, The Journal of Machine Learning Research, 7, p.2399-2434, 12/1/2006
• 3: Christopher M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 4: d'Aspremont, A., Ghaoui, L., Jordan, M., & Lanckriet, G. (2004). A direct formulation for sparse PCA using semidefinite programming. Neural Information Processing Systems (pp. 41--48).
• 5: Donoho, D. (2006). For most large underdetermined systems of linear equations, the minimal 11-norm near-solution approximates the sparsest near-solution. Communications on Pure and Applied Mathematics, 59, 907--934.
• 6: Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004). Least angle regression. Annals of Statistics, 32, 407.
• 7: Elisseeff, A., & Weston, J. (2001). A kernel method for multi-labelled classification. Neural Information Processing Systems (pp. 681--687).
• 8: Friedman, J., Hastie, T., Höfling, H., & Tibshirani, R. (2007). Pathwise coordinate optimization. Annals of Applied Statistics, 302--332.
• 9: Golub, G. H., & Van Loan, C. F. (1996). Matrix computations. Baltimore, MD: Johns Hopkins Press.
• 10: Hale, E., Yin, W., & Zhang, Y. (2008). Fixed-point continuation for l₁-minimization: Methodology and convergence. SIAM Journal on Optimization, 19, 1107--1130.
• 11: Hastie, T., Tibshirani, R., & Friedman, J. H. (2001). The elements of statistical learning: Data mining, inference, and prediction. New York, NY: Springer.
• 12: Hotelling, H. (1936). Relations between two sets of variables. Biometrika, 28, 312--377.
• 13: J. J. Hull, A Database for Handwritten Text Recognition Research, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.5, p.550-554, May 1994 [doi>10.1109/34.291440]
• 14: Kazawa, H., Izumitani, T., Taira, H., & Maeda, E. (2005). Maximal margin labeling for multi-topic text categorization. Neural Information Processing Systems (pp. 649--656).
• 15: Christopher C. Paige , Michael A. Saunders, LSQR: An Algorithm for Sparse Linear Equations and Sparse Least Squares, ACM Transactions on Mathematical Software (TOMS), v.8 n.1, p.43-71, March 1982 [doi>10.1145/355984.355989]
• 16: Rosipal, R., & Kräämer, N. (2006). Overview and recent advances in partial least squares. Subspace, Latent Structure and Feature Selection Techniques, Lecture Notes in Computer Science (pp. 34--51).
• 17: Saad, Y. (1992). Numerical methods for large eigenvalue problems. New York, NY: Halsted Press.
• 18: Bernhard Scholkopf , Alexander J. Smola, Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond, MIT Press, Cambridge, MA, 2001
• 19: Liang Sun , Shuiwang Ji , Jieping Ye, Hypergraph spectral learning for multi-label classification, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401971]
• 20: Liang Sun , Shuiwang Ji , Jieping Ye, A least squares formulation for canonical correlation analysis, Proceedings of the 25th international conference on Machine learning, p.1024-1031, July 05-09, 2008, Helsinki, Finland [doi>10.1145/1390156.1390285]
• 21: Dacheng Tao , Xuelong Li , Xindong Wu , Stephen J. Maybank, Geometric Mean for Subspace Selection, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.31 n.2, p.260-274, February 2009 [doi>10.1109/TPAMI.2008.70]
• 22: Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. J. R. Stat. Soc. B, 58, 267--288.
• 23: Yiming Yang , Jan O. Pedersen, A Comparative Study on Feature Selection in Text Categorization, Proceedings of the Fourteenth International Conference on Machine Learning, p.412-420, July 08-12, 1997
• 24: Jieping Ye, Least squares linear discriminant analysis, Proceedings of the 24th international conference on Machine learning, p.1087-1093, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273633]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Least squares methods

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.2 ARTIFICIAL INTELLIGENCE
      I.2.6 Learning
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Performance, Theory