Abstract
Motivated by the remarkable successes of Graph-based Transduction (GT) and Sparse Representation (SR), we present a novel classifier named Sparse Graph-based Classifier (SGC) for image classification. In SGC, SR is leveraged to measure the correlation (similarity) between samples, and a graph is constructed to encode these correlations. Laplacian eigenmapping is then adopted to derive the graph Laplacian. Finally, SGC is obtained by integrating the graph Laplacian into the conventional GT framework. SGC inherits the merits of both GT and SR, improving robustness and discriminating power while alleviating the undercomplete dictionary issue suffered by SR. Evaluation on four popular image databases demonstrates that SGC achieves promising performance, particularly in small training sample and noisy sample cases.
Introduction
In image classification, researchers often face two conflicting challenges: the "Small Data" problem and the "Undercomplete Dictionary" problem. Traditional supervised learners require significant labeled data. While transductive learning (GT) helps by analyzing relationships between labeled and unlabeled data, it typically relies on k-nearest-neighbor (k-NN) graphs that are easily confused by noise. Conversely, Sparse Representation (SR) is robust to noise but requires a massive "dictionary" of training samples to function effectively. SGC addresses these issues by using SR to build a superior, adaptive graph for GT.
Methodology
The core innovation of SGC is the synthesis of SR and GT through a three-step process:
- Sparse Graph Construction: Instead of using simple Euclidean distance, SGC employs $\ell_1$-norm minimization. For every image in the dataset (labeled and unlabeled), the algorithm finds a sparse combination of all other images that best reconstructs it. This creates an affinity matrix where edges represent meaningful, learned correlations.
- Laplacian Derivation: From this sparse affinity matrix, a graph Laplacian is derived to capture the underlying manifold structure of the data.
- Transductive Inference: This Laplacian is plugged into a standard GT framework, solving a Regularized Least Squares (RLS) problem to propagate labels from training sets to unlabeled testing samples.
By including testing samples in the graph-building phase, the "dictionary" for sparse representation is effectively expanded, solving the undercomplete dictionary problem inherent in pure SR methods.
Key Insights and Ideas
- Adaptive Neighborhoods: Unlike k-NN graphs that force a fixed number of neighbors, the sparse graph is adaptive. It connects samples based on discriminative relevance, making the graph significantly more accurate for classification.
- Testing Data as a Resource: Testing data is treated as a structural resource. By using these samples to help build the sparse graph, the algorithm learns the "shape" of the data space more accurately.
- Noise as a Filter: Because SR naturally ignores non-sparse noise (like random pixels), the resulting graph is much cleaner than a traditional k-NN graph, which would likely create false connections between noisy images.
Experimental Results
SGC was evaluated on the Yale, AR, and FERET face databases, as well as the Caltech256 object category dataset. The results consistently showed SGC outperforming state-of-the-art classifiers like SRC (Sparse Representation-based Classifier) and standard GT methods.
- Accuracy: On the Yale database, SGC achieved a classification error of just 2.78%, compared to 3.33% for SRC and 8.89% for standard GT.
- Small Sample Performance: The advantage of SGC was most pronounced when training data was limited, maintaining lower error rates than competitors even with only 10% training data.
- Robustness: In experiments with 30% "salt-and-pepper" noise, SGC’s performance degraded gracefully, maintaining high accuracy while standard GT methods failed completely.
Conclusion
SGC represents a robust marriage between Sparse Representation and Graph-based Transduction. By leveraging the strengths of both, it provides a highly effective solution for image classification in challenging environments. Future work may involve exploring more advanced regression techniques or custom loss functions to further improve the framework's scalability and precision.
Summary updated