Semi-Supervised Learning with Adversarially Missing Label Information

Umar Syed, Ben TaskarNeurIPS 2010 · OpenReview

This paper challenges a fundamental assumption in semi-supervised learning (SSL): that labels are missing at random. In the real world, data isn't labeled by a coin flip; it’s labeled by users who choose what to tag or workers who might skip difficult examples. The authors propose a framework and an algorithm called GAME to handle these "adversarially" missing labels.

The Problem with "Missing at Random"

Semi-supervised learning typically relies on a small set of labeled data and a large set of unlabeled data. The standard theoretical "missing-at-random" (MAR) assumption suggests that the labeled subset is a representative, uniform sample of the whole.

However, the authors argue this is rarely true for naturally occurring data. For instance:

  • User Discretion: On sites like Flickr, users tag photos they find interesting, not a random sample.
  • Worker Bias: On platforms like Amazon Mechanical Turk, workers might skip "hard" examples to maximize their hourly rate, leaving the learner with only the "easy" labels.
  • Complex Constraints: Sometimes we don't have per-example labels, but rather group constraints (e.g., "at least one of these ten images contains a cat").

If a learning algorithm assumes MAR but the labeling is actually biased, the model's performance can degrade significantly. This paper seeks to make SSL robust to these adversarial or unhelpful labeling patterns.

The GAME Framework

The authors treat the missing label problem as a game against an adversarial labeler.

  1. Label Regularization Functions ($R$): Instead of simple labels, they use a function $R$ to encode what we know. $R$ assigns a low value to labelings that are consistent with the provided info and a high (or infinite) value to those that aren't. This covers standard SSL, ambiguous labels, and graph-based constraints.
  2. The Adversarial Framework: They assume the labeler is "equivocal" but not "untruthful." The labeler can hide information or choose the least helpful examples to label, but they cannot lie about the labels they do provide.
  3. The GAME Algorithm: Short for "Game for Adversarially Missing Evidence," this algorithm solves a convex minimax problem: $$\min_{\theta} \max_{q} (E_{\hat{x},q}[L(\theta, x, y)] - R(q)) + \alpha \|\theta\|^2$$ Essentially, the model ($\theta$) tries to minimize loss while the adversary ($q$) tries to find a soft labeling consistent with the known info ($R$) that makes the model look as bad as possible.

  4. Optimization: They solve this by taking the dual of the inner maximization, resulting in a concave objective that can be efficiently optimized using exponentiated-gradient-style algorithms.

Pessimism as a Defense

Traditional SSL is "optimistic"—it assumes the missing labels probably agree with the model’s current best guess (e.g., Transductive SVMs). GAME is "pessimistic"—it assumes the missing labels are the ones that would hurt the model the most. This pessimism leads to much better robustness. The authors provide nearly matching upper and lower generalization bounds, proving that their approach is theoretically sound even when the labeler is trying to be difficult.

Experimental Results

The authors evaluated their approach on three standard datasets, modifying the labeling process to be "unhelpful" or "lazy":

  • BCI (Brain-Computer Interface): EEG scans.
  • COIL (Columbia Object Image Library): Images of objects.
  • Labeled Faces in the Wild (LFW): A subset of 500 face photographs of the top 10 most frequent characters.

Robustness to Bias

To simulate an "unhelpful" labeler, they only provided labels for the "outliers" (examples whose neighbors belong to different classes). On the BCI and COIL datasets, when only the most difficult examples were labeled, GAME significantly outperformed Laplacian SVMs and Transductive SVMs. The performance advantage of GAME was most pronounced when the fraction of labeled data was very small.

Performance comparison on dataset with an unhelpful labeler

Handling Ambiguity

To simulate a "lazy" labeler, they provided ambiguous label sets for examples near class boundaries, forcing the algorithm to figure out which of the possible labels was correct. In the LFW face recognition task with ambiguous labels, GAME outperformed standard "Uniform" (averaging possible labels) and "EM" (Expectation-Maximization) baselines.

Performance comparison on LFW dataset with a lazy labeler

Limitations and Future Work

  • No Protection Against Liars: The framework assumes the labeler is "equivocal" (withholds info) but not "malicious" (provides false info). If the labeler provides wrong labels, the current theoretical bounds become vacuous.
  • Computational Complexity: While the authors use efficient gradient methods, solving minimax problems is generally more complex than standard empirical risk minimization.
  • Future Directions: The authors suggest extending this to structured prediction (like sequences or trees) and exploring interactive learning, where the algorithm can specifically ask the labeler for the most useful missing information.

Summary updated

Abstract

We address the problem of semi-supervised learning in an adversarial setting. Instead of assuming that labels are missing at random, we analyze a less favorable scenario where the label information can be missing partially and arbitrarily, which is motivated by several practical examples. We present nearly matching upper and lower generalization bounds for learning in this setting under reasonable assumptions about available label information. Motivated by the analysis, we formulate a convex optimization problem for parameter estimation, derive an efficient algorithm, and analyze its convergence. We provide experimental results on several standard data sets showing the robustness of our algorithm to the pattern of missing label information, outperforming several strong baselines.
BibTeX
@inproceedings{syed2010semi,
  author = {Umar Syed and Ben Taskar},
  title = {{Semi-Supervised Learning with Adversarially Missing Label Information}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
  url = {https://openreview.net/forum?id=By7I0dZ_br},
}
Figure