Generalization Guarantees of Self-Training of Halfspaces under Label Noise Corruption

Lies Hadjadj, Massih-Reza Amini, Sana LouhichiIJCAI 2023 · DOI

TL;DR

This paper introduces a novel self-training algorithm for halfspace classification that provides theoretical guarantees on generalization error, even when dealing with noisy labels. The method iteratively refines a classifier by leveraging unlabeled data and a pruning mechanism, demonstrating that it doesn't degrade performance compared to using only the initial labeled data.

What Problem Does This Paper Address?

Semi-supervised learning (SSL) aims to improve model performance by utilizing both labeled and unlabeled data. A key challenge in SSL is understanding when and how unlabeled data actually helps, especially when the labeling process itself is imperfect. This paper focuses on the specific scenario of learning halfspaces (linear classifiers) in the presence of label noise. Existing theoretical work often assumes clean labels or relies on strong assumptions about data distribution. This paper tackles the problem of providing theoretical guarantees for a self-training approach in a more realistic setting where pseudo-labels generated during the self-training process are inherently noisy, modeled by the Massart noise model. The goal is to ensure that this self-training strategy not only learns effectively but also doesn't perform worse than a purely supervised approach trained on the initial, potentially noisy, labeled data.

Methods

The core of the paper is a novel self-training algorithm designed for halfspaces. This algorithm operates in two main phases:

  • Exploration: In each round, the algorithm learns a halfspace by maximizing the unsigned margin on unlabeled data. It then assigns pseudo-labels to unlabeled points that have a distance (margin) greater than a dynamically determined threshold. These pseudo-labeled points, which are assumed to be corrupted by noise, are added to the training set, and a new classifier is trained. This process continues until no more unlabeled data can be effectively pseudo-labeled.
  • Pruning: After the exploration phase, a pruning step is introduced. Pseudo-labeled examples that have a margin smaller than the threshold determined in the exploration phase are discarded. This step aims to remove potentially more corrupted samples.

The theoretical contributions include:

  1. A generalization bound for this self-training algorithm under the Massart noise model for pseudo-labels.
  2. A proof that the proposed semi-supervised approach never degrades the performance compared to a classifier trained solely on the initial labeled data.

The algorithm utilizes projected Stochastic Gradient Descent (SGD) for optimizing the halfspace parameters.

Datasets

The paper evaluates the proposed algorithm on several benchmark datasets, primarily from the semi-supervised learning literature:

  • Textual Data: baseball-hockey, pc-mac, religion-atheism (extracted from 20-newsgroups, using tf-idf representation).
  • Other Datasets: spambase, one-two, odd-even, weather, mediamill2, delicious2.

The datasets vary in size and dimensionality, providing a diverse testbed for the algorithm. No new datasets were introduced.

Key Insights and Ideas

  • Theoretical Guarantees for Noisy Self-Training: The paper provides a significant theoretical contribution by offering generalization bounds for self-training in the presence of label noise, a crucial aspect for practical applicability.
  • Pruning as a Noise Mitigation Strategy: The introduction of a pruning step after pseudo-labeling is a key novelty. This step aims to filter out less confident or more corrupted pseudo-labels, thereby improving the robustness of the learning process.
  • No Degradation Guarantee: A critical finding is the proof that the self-training algorithm, even with noisy pseudo-labels, does not perform worse than the initial supervised classifier. This is a strong theoretical endorsement for using unlabeled data in this manner.
  • Margin as a Confidence Indicator: The algorithm leverages the margin of data points to unlabeled data as an indicator of confidence for pseudo-labeling, aligning with the low-density separation assumption in SSL.

Key Results

The experimental results, summarized in Table 2, show that the proposed self-training algorithm (Lm) consistently outperforms the supervised halfspace (LTF) and often achieves the best or second-best performance among various baseline methods (SVM, LTF, LP, GM, ERLR) across different datasets and labeled data sizes (l ∈ {10, 50, 100}). For instance, on the 'one-two' dataset with l=100, Lm achieves 94.62% accuracy, outperforming LTF (92.50%) and SVM (96.15%). The paper highlights that while some semi-supervised methods can outperform supervised ones, Lm demonstrates robust performance across the board, reinforcing its theoretical guarantees.

Limitations and Future Work

  • Massart Noise Model Assumption: The theoretical guarantees are based on the Massart noise model. The performance in the presence of other types of label noise might differ.
  • Computational Complexity: While the paper mentions polynomial time complexity, the practical runtime and scalability for very large datasets are not extensively detailed.
  • Future Work: The authors suggest exploring the real gain of combining labeled and unlabeled data compared to a fully supervised scheme. Quantifying this gain more precisely and investigating the algorithm's performance with different noise models are potential future directions.

Summary updated

BibTeX
@inproceedings{hadjadj2023generalization,
  author = {Lies Hadjadj and Massih-Reza Amini and Sana Louhichi},
  title = {{Generalization Guarantees of Self-Training of Halfspaces under Label Noise Corruption}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/420},
}
Figure