Prototype-Driven Learning for Sequence Models

Aria Haghighi, Dan KleinNAACL 2006 · OpenReview

TL;DR

This paper introduces "prototype-driven learning" for sequence modeling, a method that leverages a few canonical examples (prototypes) of each desired label to guide unsupervised learning. By combining these prototypes with distributional similarity features in a log-linear model, the authors achieve significant error reductions on tasks like part-of-speech tagging and information extraction, outperforming previous unsupervised and semi-supervised approaches.

What Problem Does This Paper Address?

Traditional supervised learning for sequence tasks like part-of-speech (POS) tagging requires extensive labeled data, which is expensive and time-consuming to create. Unsupervised methods aim to reduce this burden but often struggle to achieve competitive performance or require significant model customization. The authors identify a gap in methods that can effectively inject prior knowledge into unsupervised sequence models without demanding full supervision or complex model engineering. They propose a "prototype-driven learning" approach as a more efficient way to specify prior knowledge, arguing that providing a few representative examples of each label is a more natural and compact way to communicate task requirements than full annotation.

Methods

The core of the paper is the prototype-driven learning framework. Instead of providing labeled sentences, the authors define a "prototype list" containing a few example words for each target label. This sparse information is then integrated into a log-linear generative model.

The key innovation lies in how this prototype information is propagated:

  1. Distributional Similarity: Words are linked to prototypes based on their distributional similarity. This means words that appear in similar contexts are considered related. The paper uses context vectors (counts of surrounding words) and Singular Value Decomposition (SVD) to compute similarity.
  2. Feature Engineering: These distributional similarity links are encoded as features in the log-linear model. Specifically, for a word w, if it's distributionally similar to a prototype z associated with label y, a feature PROTO = z is activated for w when it's assigned label y. This allows the model to generalize from prototypes to similar words.
  3. Log-Linear Generative Model: The model is a chain-structured Markov Random Field (MRF), similar to a Hidden Markov Model (HMM) but modeling the joint probability of observations and labels. The parameters of this model are learned by maximizing the data likelihood, with the prototype features influencing the learning process.

Datasets

The paper evaluates its approach on three tasks:

  • English Part-of-Speech (POS) Tagging: Utilized the Wall Street Journal (WSJ) portion of the English Penn Treebank. Experiments were conducted on two sizes: 48K tokens (2000 sentences) and 193K tokens (8000 sentences).
  • Chinese Part-of-Speech (POS) Tagging: Used the Chinese Treebank. Experiments were conducted on 60K word tokens.
  • Information Extraction (Classified Ads): Used the CLASSIFIEDS dataset, as described in previous work by Grenager et al. (2005).

Key Insights and Ideas

  • Compact Knowledge Specification: Providing a few "prototypical" examples for each label is a surprisingly effective way to inject prior knowledge into unsupervised learning, requiring far less effort than full annotation.
  • Distributional Similarity as a Bridge: The paper demonstrates that distributional similarity is a powerful mechanism to generalize sparse prototype information to unseen words, effectively propagating the "meaning" of prototypes.
  • Feature-Based Integration: Encoding prototype information as features in a log-linear model is more successful than simply constraining prototype words to their labels, as it allows for more nuanced learning and generalization.
  • "Sticky" Labels: For tasks with "sticky" labels (where consecutive tokens tend to have the same label, like in classified ad segmentation), distributional similarity naturally encourages this behavior, reducing the need for custom model structures.

Key Results

  • English POS Tagging: Achieved an accuracy of 80.5% on the 193K token dataset using only three examples per tag and no dictionary constraints. This is a substantial improvement over a baseline model (41.3%) and a significant error reduction.
  • Chinese POS Tagging: Showed similar trends, with the PROTO+SIM model achieving 57.4% accuracy, a significant improvement over the BASE (34.4%) and PROTO (39.0%) settings.
  • Information Extraction (Classified Ads): The PROTO+SIM model achieved 71.5% accuracy, a 38.4% error reduction over the baseline. Adding a specific "BOUNDARY" prototype further boosted accuracy to 74.1%, closely approaching supervised results.
  • Efficiency: The prototype-driven approach requires significantly less human effort compared to traditional semi-supervised methods that rely on partially labeled datasets.

Limitations and Future Work

  • Prototype List Creation: While the paper argues for the efficiency of prototype creation, the method used for English POS tagging involved extracting prototypes from already labeled data. The authors acknowledge this and suggest that tuning the prototype list could further reduce errors. They also note that for Chinese, they lacked expertise and relied on an automatic extraction method.
  • Comparison to Full Supervision: While competitive, the results still lag behind fully supervised systems, especially when those systems have access to extensive dictionaries.
  • Future Work: The authors suggest that further exploration of prototype list construction and tuning, as well as applying this framework to other sequence modeling tasks, would be valuable. They also highlight the potential for this approach to bridge the gap between unsupervised word clustering and supervised sequence modeling.

Summary updated

Abstract

We investigate prototype-driven learning for primarily unsupervised sequence modeling. Prior knowledge is specified declaratively, by providing a few canonical examples of each target annotation label. This sparse prototype information is then propagated across a corpus using distributional similarity features in a log-linear generative model. On part-of-speech induction in English and Chinese, as well as an information extraction task, prototype features provide substantial error rate reductions over competitive baselines and outperform previous work. For example, we can achieve an English part-of-speech tagging accuracy of 80.5% using only three examples of each tag and no dictionary constraints. We also compare to semi-supervised learning and discuss the system's error trends.
BibTeX
@inproceedings{haghighi2006prototype,
  author = {Aria Haghighi and Dan Klein},
  title = {{Prototype-Driven Learning for Sequence Models}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
  url = {https://openreview.net/forum?id=rkVAG7-uZS},
}
Figure