Structured Output Learning with Indirect Supervision

Ming-Wei Chang, Vivek Srikumar, Dan Goldwasser, Dan RothICML 2010 · OpenReview

TL;DR

Training models for structured output tasks (like parsing or alignment) usually requires expensive, hand-labeled data. This paper introduces J-LIS, a framework that boosts performance by using "indirect supervision" from easier-to-obtain binary labels—essentially teaching a model to recognize what a "good" structure looks like by solving a companion yes/no decision task.

What Problem Does This Paper Address?

Structured output learning is the backbone of many NLP and Computer Vision tasks, where the goal is to predict complex objects like sequences, trees, or alignments. The "bottleneck" is data: asking a human to manually align phonetic characters between English and Hebrew or to label every part-of-speech in a sentence is slow and expensive.

However, the authors observe that these complex tasks often have a "companion" binary problem that is much easier to label. For example:

  • Structure Task: Align the characters of "Italy" with its Hebrew transliteration. (Hard to label)
  • Companion Binary Task: Are these two words actually transliterations of each other? (Easy to label)

The challenge is creating a mathematical framework that can learn from both types of data simultaneously, especially since the binary labels don't explicitly tell the model what the correct internal structure is—only that some valid structure must exist.

Methods

The authors propose Joint Learning with Indirect Supervision (J-LIS). This is a large-margin framework that extends the standard Structural SVM.

  1. The Objective Function: J-LIS minimizes a joint loss function. One part handles the "direct" supervision (standard structural loss), while the other handles "indirect" supervision (binary labels).
  2. The Latent Assumption: For a positive binary example (e.g., a valid transliteration pair), the model assumes there exists at least one high-scoring structure. For a negative example, all possible structures must score poorly.
  3. Optimization: Because the "at least one" requirement for positive examples introduces non-convexity, the authors use an iterative algorithm inspired by the Concave-Convex Procedure (CCCP). They alternate between finding the best latent structure for the positive binary examples using the current model, and updating the model weights by solving a convex optimization problem.
Comparison of standard Structural SVM and J-LIS margin boundaries.

Datasets

The researchers evaluated J-LIS on three distinct NLP domains:

  • Phonetic Transliteration Alignment: English-Hebrew name pairs (300 pairs for direct labels; 11,000 pairs for binary indirect labels).
  • Part-of-Speech (POS) Tagging: Wall Street Journal corpus (WSJ). Binary labels were generated by using original sentences as "positive" and randomly shuffled sentences as "negative."
  • Information Extraction (IE): Two datasets—one for citations (author, title, year) and one for Craigslist advertisements (size, rent, neighborhood).

Key Insights and Ideas

  • Negative Examples are High-Signal: Unlike traditional semi-supervised learning, which often only uses "unlabeled" data (assumed to be positive), J-LIS explicitly uses negative examples (invalid structures). Shuffling a sentence to create a "bad" example provides a powerful constraint on the model's weight space, as visualized in the methods section.
  • The "Companion" Synergy: The binary task acts as a regularizer. By forcing the model to score all structures of a "bad" input lowly, it learns to better distinguish the features of "good" structures in the primary task.
  • Efficiency in Data-Poor Regimes: The biggest "aha moment" is how much indirect supervision helps when you have almost no labeled data. With just 10 hand-labeled examples, the binary task can cut the error rate significantly.

Key Results

  • Transliteration: Adding indirect supervision reduced the error rate by 26.2% when only 10 structured examples were available.
  • POS Tagging: In a low-data setting (200 tokens), accuracy jumped from 71% to 76% by adding indirect supervision. Even with full data, J-LIS slightly outperformed the standard supervised SVM.
POS Tagging accuracy improvements using J-LIS across different sizes of structured and binary datasets.
  • Information Extraction: On the advertisement dataset, using only 500 labeled tokens plus indirect supervision outperformed a standard model trained on 1,000 labeled tokens.
  • Comparison to Contrastive Estimation (CE): J-LIS was found to be more computationally efficient than CE because it only searches for the "best" structure rather than marginalizing over all possible structures.

Limitations and Future Work

  • Initialization Sensitivity: Because the objective function is non-convex, the model's performance can depend on the initial weight vector (usually provided by the small set of direct labels).
  • Task Specificity: The framework relies on the existence of a meaningful companion binary task. While common in NLP, it might be harder to define for some abstract reasoning tasks.
  • Future Directions: The authors suggest exploring more complex domain-specific constraints within the J-LIS framework to further reduce the need for any direct supervision at all.

Summary updated

Abstract

We present a novel approach for structure prediction that addresses the difficulty of obtaining labeled structures for training. We observe that structured output problems often have a companion learning problem of determining whether a given input possesses a good structure. For example, the companion problem for the part-of-speech (POS) tagging task asks whether a given sequence of words has a corresponding sequence of POS tags that is "legitimate". While obtaining direct supervision for structures is difficult and expensive, it is often very easy to obtain indirect supervision from the companion binary decision problem. In this paper, we develop a large margin framework that jointly learns from both direct and indirect forms of supervision. Our experiments exhibit the significant contribution of the easy-to-get indirect binary supervision on three important NLP structure learning problems.
BibTeX
@inproceedings{chang2010structured,
  author = {Ming-Wei Chang and Vivek Srikumar and Dan Goldwasser and Dan Roth},
  title = {{Structured Output Learning with Indirect Supervision}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=HJZPtsbOZB},
}
Figure