Spectral Regression: A Regression Framework for Regularized Subspace Learning

Introduction

Spectral methods have recently emerged as a powerful tool for dimensionality reduction and manifold learning. These methods use information contained in the eigenvectors of a data affinity (i.e., item-item similarity) matrix to reveal low dimensional structure in high dimensional data. The most popular manifold learning algorithms include Locally Linear Embedding, Isomap, and Laplacian Eigenmap. However, these algorithms only provide the embedding results of training samples.

There are many extensions of these approaches which try to solve the out-of-sample extension problem by seeking an embedding function in reproducing kernel Hilbert space. A disadvantage of all these approaches is that their computations usually involve eigen-decomposition of dense matrices which is expensive in both time and memory.

Spectral Regression (SR) [1] [2] is a novel regression framework for efficient regularized subspace learning. Some interesting aspects of SR include

• SR casts the problem of learning an embedding function into a regression framework, which avoids eigen-decomposition of dense matrices. With different graph matrix W, SR provides the efficient solutions of Linear Discriminant Analysis (LDA)[3] [7], Locality Preserving Projection (LPP)[7] [10], Neighborhood Preserving Embedding (NPE)[7], Isometric Projection (IsoP)[4], Locality Sensitive Discriminant Analysis (LSDA) and much more.

• With regression as the building block, various kinds of regularization techniques can be easily incorporated in SR which makes it more flexible (e.g., $L_1$-norm regularizer to produce sparse projections [9]).

• SR can be performed in supervised [3], unsupervised [10] and semi-supervised [1] [6] situations. It can make efficient use of both labeled and unlabeled points to discover the intrinsic discriminant structure in the data.

• SR may be conducted in the original space or in the reproducing kernel Hilbert space (RKHS) into which data points are mapped. This gives rise to kernel SR [2] [5] [8] (efficient solutions for many kernel subspace learning algorithms).

Codes

• SR_caller: SR caller (response generation).

• SR: Spectral Regression (Called by SR_caller)
  • lsqr2: A iterative least squares solver, which will be called by SR
  • lars: Least Angle Regression solver, which will be called by SR

  • If you want to learn a sparse SR subspace by specifying the L1-regularization parameter instead of providing the cardinality, you can set the 'LASSOway' as 'SLEP'. Please see SLEP for more details on SLEP software. For your convenience, I extract the functions from SLEP package which will be called by SR:
  • LeastR, initFactor, sll_opts, ep1R.mexw64, ep1R.mexw32

• KSR_caller: SR caller (response generation).

• KSR: Kernel Spectral Regression (Called by KSR_caller)

  ---

  NormalizeFea, constructW, constructKernel, EuDist2 and Eigenmap are also required.

  ---

  The above codes are complicated and hard to follow. To successfully use (or, modify) these codes, one should be very familiar with the subspace learning area. Thus, I provide below some simple interfaces for different scenarios.

  ---

  • Supervised and semi-supervised learning : The following codes show how to use SR (linear) or KSR (nonlinear ) in supervised or semi-supervised (utilize the unlabel data to learn the subspace) settings.

  • Spectral Regression Discriminant Analisys: Supervised (semi-supervised) linear SR.
    • SRDAtrain: function to learn the SRDA model.
    • SRDApredict uses SRDA as a classifier. We implement a nearest center rule in the SRDA subspace for classification.
    • SRDAtest uses SRDA as a dimensionality reduction tool. It will embed the input data to a c-1 dimensional SRDA subspace, where c is the number of classes.
    • Example here
    • Example on Sparse SRDA (Sparse LDA)

    • Deng Cai, Xiaofei He, and Jiawei Han, "SRDA: An Efficient Algorithm for Large-Scale Discriminant Analysis", IEEE TKDE 2008. (pdf)
      Bibtex source

  • Spectral Regression Kernel Discriminant Analisys : Supervised (semi-supervised) non-linear SR.
    • SRKDAtrain: function to learn the SRKDA model.
    • SRKDApredict: uses SRKDA as a classifier. We implement a nearest center rule in the SRKDA subspace for classification.
    • SRKDAtest uses SRKDA as a dimensionality reduction tool. It will embed the input data to a c-1 dimensional SRKDA subspace, where c is the number of classes.
    • Example here
    • More examples on semi-supervised classification

    • Deng Cai, Xiaofei He, Jiawei Han, "Speed Up Kernel Discriminant Analysis", The VLDB Journal, 2011. (pdf)
      Bibtex source

    ---

  • Unsupervised learning : The following codes show how to use SR (linear) or KSR (nonlinear ) in unsupervised settings.

  • Unsupervised Spectral Regression : Unsupervised linear SR.
    • USRtrain: function to learn the SR model.
    • USRtest: uses SR as a dimensionality reduction tool. It will embed the input data to a d dimensional SR subspace, where d is a specified parameter.
    • Example here
    • Example on Sparse Spectral Regression (Sparse LPP)

    • Deng Cai, Xiaofei He, Wei Vivian Zhang, and Jiawei Han, "Regularized Locality Preserving Indexing via Spectral Regression", CIKM'07. (pdf)
      Bibtex source

  • Unsupervised Kernel Spectral Regression : Unsupervised non-linear SR.
    • UKSRtrain: function to learn the KSR model.
    • UKSRtest: uses KSR as a dimensionality reduction tool. It will embed the input data to a d dimensional KSR subspace, where d is a specified parameter.
    • Example here

• Deng Cai, "Spectral Regression: A Regression Framework for Efficient Regularized Subspace Learning", PhD Thesis, Department of Computer Science, UIUC, 2009. (pdf)
  Bibtex source
• Deng Cai, Xiaofei He, Jiawei Han, "Speed Up Kernel Discriminant Analysis", The VLDB Journal, 2011. (pdf)
  Bibtex source
• Deng Cai, Xiaofei He, and Jiawei Han, "SRDA: An Efficient Algorithm for Large-Scale Discriminant Analysis", IEEE TKDE 2008. (pdf)
  Bibtex source
• Deng Cai, Xiaofei He and Jiawei Han, "Spectral Regression for Efficient Regularized Subspace Learning", ICCV'07. (pdf)
  Bibtex source
• Deng Cai, Xiaofei He, Wei Vivian Zhang, and Jiawei Han, "Regularized Locality Preserving Indexing via Spectral Regression", CIKM'07. (pdf)
  Bibtex source

Papers

1. Deng Cai, Xiaofei He, and Jiawei Han. "Semi-Supervised Regression using Spectral Techniques", Department of Computer Science Technical Report No. 2749, University of Illinois at Urbana-Champaign (UIUCDCS-R-2006-2749), July 2006. ( pdf )

2. Deng Cai, Xiaofei He, and Jiawei Han. "Spectral Regression for Dimensionality Reduction", Department of Computer Science Technical Report No. 2856, University of Illinois at Urbana-Champaign (UIUCDCS-R-2007-2856), May 2007. ( pdf )

3. Deng Cai, Xiaofei He, and Jiawei Han. "SRDA: An Efficient Algorithm for Large Scale Discriminant Analysis", Department of Computer Science Technical Report No. 2857, University of Illinois at Urbana-Champaign (UIUCDCS-R-2007-2857), May 2007. ( pdf )

4. Deng Cai, Xiaofei He, and Jiawei Han. "Isometric Projection", Proc. 22nd Conference on Artifical Intelligence (AAAI'07), Vancouver, Canada, July 2007. ( pdf )

5. Deng Cai, Xiaofei He, and Jiawei Han. "Efficient Kernel Discriminant Analysis via Spectral Regression", Department of Computer Science Technical Report No. 2888, University of Illinois at Urbana-Champaign (UIUCDCS-R-2007-2888), August 2007. ( pdf )

6. Deng Cai, Xiaofei He, and Jiawei Han. "Spectral Regression: A Unified Subspace Learning Framework for Content-Based Image Retrieval", ACM Multimedia 2007, Augsburg, Germany, Sep. 2007. ( pdf )

7. Deng Cai, Xiaofei He, and Jiawei Han. "Spectral Regression for Efficient Regularized Subspace Learning", IEEE International Conference on Computer Vision (ICCV'07), Rio de Janeiro, Brazil, Oct. 2007. ( pdf )

8. Deng Cai, Xiaofei He, and Jiawei Han. "Efficient Kernel Discriminant Analysis via Spectral Regression", Proc. 2007 Int. Conf. on Data Mining (ICDM'07), Omaha, NE, Oct. 2007. ( pdf )

9. Deng Cai, Xiaofei He, and Jiawei Han. "Spectral Regression: A Unified Approach for Sparse Subspace Learning", Proc. 2007 Int. Conf. on Data Mining (ICDM'07), Omaha, NE, Oct. 2007. ( pdf )

10. Deng Cai, Xiaofei He, Wei Vivian Zhang, and Jiawei Han. "Regularized Locality Preserving Indexing via Spectral Regression", Proc. 2007 ACM Int. Conf. on Information and Knowledge Management (CIKM'07), Lisboa, Portugal, Nov. 2007. ( pdf )

11. Deng Cai, Xiaofei He, and Jiawei Han. "SRDA: An Efficient Algorithm for Large Scale Discriminant Analysis", IEEE Transactions on Knowledge and Data Engineering, vol. 20, no. 1, pp. 1-12, January, 2008. ( pdf )

12. Deng Cai, Xiaofei He, and Jiawei Han. "Speed Up Kernel Discriminant Analysis", The VLDB Journal, vol. 20, no. 1, pp. 21-33, January, 2011. ( pdf )