A Self-Representation Induced Classifier

Pengfei Zhu, Lei Zhang, Wangmeng Zuo, Xiangchu Feng, Qinghua Hu

Introduction

In pattern recognition, representation-based classifiers like Sparse Representation-based Classification (SRC) and Collaborative Representation-based Classification (CRC) have set high benchmarks for accuracy. These methods typically represent a query sample as a linear combination of all available training samples. However, they suffer from significant scalability issues. As the training set size ($n$) grows, the computational cost of solving optimization problems (like $l_1$-norm minimization) for every query sample becomes prohibitive. Furthermore, these methods require keeping all training samples in memory during inference.

This paper introduces the Self-Representation Induced Classifier (SRIC) and its discriminative variant (DSRIC). These methods shift the focus from a "sample-oriented" perspective to a "feature-oriented" one. By learning how the features of a specific class represent themselves, the authors develop a classifier that is orders of magnitude faster and more memory-efficient than current state-of-the-art methods while maintaining competitive accuracy.

Methodology

Self-Representation Induced Classifier (SRIC)

The core innovation is the self-representation property. Instead of reconstructing a query image from other images, SRIC asks how each feature (e.g., a pixel) in a class relates to other features within that same class. For each class $k$, the algorithm learns a self-representation matrix $B_k$ by minimizing the reconstruction error: $$\|X_k - B_k X_k\|_F^2 + \lambda \|B_k\|_F^2$$ where $X_k$ is the training data for class $k$. Once learned, a new sample $z$ is classified by projecting it onto each $B_k$ and identifying the class with the smallest residual error.

Visualization of self-representation matrices $B_k$ and reconstructed digits $B_k z$ for a query digit $z$.

Discriminative SRIC (DSRIC)

While the basic SRIC is generative, DSRIC adds a discriminative term to the objective function. It forces the matrix $B_k$ to represent its own class features accurately while simultaneously pushing the reconstruction of other classes toward zero. This significantly enhances the model's ability to distinguish between similar classes by widening the gap in residuals.

Theoretical Foundations

The authors prove that basic SRIC is mathematically equivalent to an $l_2$-norm regularized Nearest Subspace Classifier (NSC) and is closely related to Principal Component Analysis (PCA) with eigenvalue shrinkage. Unlike SRC, which requires iterative optimization, DSRIC offers a closed-form solution, making testing a simple matter of matrix-vector multiplication.

Experimental Results

The authors evaluated DSRIC on diverse benchmarks, including UCI datasets, handwritten digits (USPS, MNIST), and face recognition (LFW, AR face database).

Performance and Efficiency

  • Speed: On the MNIST dataset, DSRIC was 18,000 times faster than the Nearest Neighbor Classifier (NNC) and 51 times faster than SRC. On UCI datasets, it achieved a speedup of approximately 547x over SRC.
  • Memory: DSRIC only needs to store $K$ matrices of size $d \times d$ (where $d$ is the feature dimension), rather than the entire training set of $n$ samples.
  • Accuracy: DSRIC achieved 60.8% accuracy on the LFW face database, outperforming both SRC (60.4%) and CRC (58.8%). On UCI datasets, it averaged 85.4% accuracy, roughly 2% higher than its competitors.
Comparison of SRIC and DSRIC on a face recognition task, showing query face, reconstructed outputs, and representation residuals.

Discussion and Conclusion

SRIC and DSRIC represent a paradigm shift in representation-based classification. By decoupling the testing complexity from the number of training samples, these methods are uniquely suited for "Big Data" scenarios.

Key Insights: * Independence from Sample Size: Testing complexity depends only on the feature dimension $d$, making it highly scalable. * Exploiting Correlation: The method effectively captures the high correlation between features in visual data.

Limitations: While highly efficient, the training phase still requires the full training set to compute $B_k$ matrices. Additionally, the current model is linear; future work may explore non-linear "kernelized" versions to handle more complex data manifolds. Despite these areas for growth, DSRIC stands as a powerful, efficient alternative for high-speed pattern recognition.

Summary updated

Abstract

Almost all the existing representation based classifiers represent a query sample as a linear combination of training samples, and their time and memory cost will increase rapidly with the number of training samples. We investigate the representation based classification problem from a rather different perspective in this paper, that is, we learn how each feature (i.e., each element) of a sample can be represented by the features of itself. Such a self-representation property of sample features can be readily employed for pattern classification and a novel self-representation induced classifier (SRIC) is proposed. SRIC learns a self-representation matrix for each class. Given a query sample, its self-representation residual can be computed by each of the learned self-representation matrices, and classification can then be performed by comparing these residuals. In light of the principle of SRIC, a discriminative SRIC (DSRIC) method is developed. For each class, a discriminative self-representation matrix is trained to minimize the self-representation residual of this class while representing little the features of other classes. Experimental results on different pattern recognition tasks show that DSRIC achieves comparable or superior recognition rate to state-of-the-art representation based classifiers, however, it is much more efficient and needs much less storage space.
BibTeX
@inproceedings{zhu2016self,
  author = {Pengfei Zhu and Lei Zhang and Wangmeng Zuo and Xiangchu Feng and Qinghua Hu},
  title = {{A Self-Representation Induced Classifier}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure