On Discriminative Semi-Supervised Classification

Fei Wang, Changshui ZhangAAAI 2008 · OpenReview

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:

  1. 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.
  2. 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.
  3. 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.

Table 1: Characteristics of the 12 datasets used in the evaluation, including size, number of classes, and dimensionality.

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.

Table 2: Classification accuracy comparison. SSDR and SDSC consistently outperform traditional smoothness-based methods across various data types.

Key findings from the experimental results include:

  • Superior Accuracy: SSDR or SDSC achieved the highest accuracy on nearly every dataset. Notably, on the digit1 dataset, SDSC reached 99.13% accuracy.
  • Robustness to Assumption Violations: On the g241c and g241n datasets—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% on g241c vs. 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

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.
BibTeX
@inproceedings{wang2008discriminative,
  author = {Fei Wang and Changshui Zhang},
  title = {{On Discriminative Semi-Supervised Classification}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
  url = {https://openreview.net/forum?id=BkZtjkWdbr},
}
Figure