Abstract
The recent years have witnessed a surge of interests in semi-supervised learning methods. A common strategy for these algorithms is to require that the predicted data labels should be sufficiently smooth with respect to the intrinsic data manifold. In this paper, we argue that rather than penalizing the label smoothness, we can directly punish the discriminality of the classification function to achieve a more powerful predictor, and we derive two specific algorithms: Semi-Supervised Discriminative Regularization (SSDR) and Semi-parametric Discriminative Semi-supervised Classification (SDSC). Finally many experimental results are presented to show the effectiveness of our method.
Introduction
In many machine learning scenarios, labeled data is a luxury, while unlabeled data is plentiful. Semi-supervised learning (SSL) bridges this gap by using the structure of unlabeled data to improve classification. Most existing SSL methods rely on the manifold assumption: the idea that the classification function should be "smooth," meaning nearby points should have the same label.
However, there is a fundamental tension in this approach: the ultimate goal of classification is to discriminate between classes. A perfectly smooth function might struggle to find the sharp discontinuities required at decision boundaries. This paper proposes shifting the focus from "how smooth is the function?" to "how well does the function separate different classes?"
Methodology
The proposed framework prioritizes the "discriminality" of the classification function through two main components:
- The Discriminative Kernel: The authors derive an unsupervised discriminative kernel ($D$) based on classical discriminant analysis. This kernel captures the intrinsic geometric structure of the data in a way that encourages high between-class dissimilarity and high within-class similarity.
- Proposed Algorithms:
- Semi-Supervised Discriminative Regularization (SSDR): This modifies the popular Manifold Regularization framework. Instead of penalizing the "smoothness" of the function on the manifold, it penalizes the "discriminality" using the new kernel.
- Semi-parametric Discriminative Semi-supervised Classification (SDSC): This uses a semi-parametric regression approach. It combines a non-parametric component (learned from labeled data) with a parametric component (derived from the eigenvectors of the discriminative kernel) that "corrects" the predictor using the global geometry of the unlabeled data.
Experimental Setup
The authors evaluated their methods on 12 diverse datasets to ensure robustness, ranging from toy datasets designed to violate standard cluster assumptions to high-dimensional image and text data.
Results and Analysis
The authors compared SSDR and SDSC against four state-of-the-art methods (GRF, LLGC, LLReg, and LapRLS) using only 10% labeled data.
Key findings from the experimental results include:
- Superior Accuracy: SSDR or SDSC achieved the highest accuracy on nearly every dataset. Notably, on the
digit1dataset, SDSC reached 99.13% accuracy. - Robustness to Assumption Violations: On the
g241candg241ndatasets—specifically built to trip up SSL methods that rely on cluster assumptions—the discriminative approach significantly outperformed the competition (e.g., SDSC hit 83.41% ong241cvs. GRF's 56.34%). - Text Classification Performance: The methods showed a clear edge in high-dimensional text data, with SSDR performing particularly well on the WebKB datasets (
cornell,texas, etc.).
Discussion and Conclusion
The core insight of this work is that smoothness is merely a proxy for what we actually desire in a classifier. By targeting discrimination directly, models can better handle decision boundaries where labels must change abruptly. While the results are promising, future work is needed to address the $O(n^3)$ computational complexity of matrix inversions for large-scale datasets and to explore automated selection of parametric components in the SDSC algorithm.
Summary updated