📄 Prototype-Driven Learning for Sequence Models

Summary

The paper asks how to build sequence labelers with minimal human effort. Full supervision needs costly annotated sentences, and pure unsupervised learning needs expert tinkering with model structure. Haghighi and Klein instead propose prototype-driven learning: the user lists the target labels and a handful of typical words for each, without labeling any sentence. These sparse hints are spread across unlabeled text through distributional similarity. Each word gets features pointing to the prototypes it resembles, and these features feed a log-linear generative model (a chain-structured MRF trained with L-BFGS on unlabeled data). The approach is tested on English and Chinese part-of-speech induction (Penn treebanks) and on segmenting rental classified ads (CLASSIFIEDS). With only three prototypes per tag and no tag dictionary, English tagging accuracy rises from 41.3% to 80.5%. On classified ads the method beats the best earlier unsupervised result and nearly matches a supervised HMM. This shows that a compact, declarative task specification can replace large dictionaries or hand-designed model structure.

Key points

• On English POS with the 45 Penn treebank tags and three prototypes each, accuracy at 193K tokens moves as follows:
  • BASE: 41.3%
  • PROTO (prototypes as features only): 68.8%
  • PROTO+SIM (adding similarity features): 80.5%
• On the 48K-token English set, the same three settings reach 42.2%, 61.9% and 79.1%.
• On CLASSIFIEDS, accuracy improves step by step:
  • BASE: 46.4%
  • Adding prototypes: 53.7%
  • PROTO+SIM: 71.5%, a 38.4% error reduction
  • PROTO+SIM+BOUND: exceeds Grenager et al.'s best unsupervised 72.4% and approaches their supervised HMM at 74.4%
• In a standard semi-supervised comparison, about 25% of the ad data had to be fully labeled to equal the prototype system.
• Making the model's normalizer tractable required a trick. The partition function was approximated by summing over all observation sequences up to a large length K, using a lattice version of forward-backward. Gradients are differences of feature expectations.

Interesting ideas

• I1. Specify the task as a prototype list. A few example words per label are roughly what you would hand a human annotator anyway. This makes it a cheap way to bootstrap taggers or field extractors for languages or domains that lack treebanks or lexicons.
• I2. Encode prior knowledge as features, not hard constraints. Forcing prototype words to their labels was too sparse to help. Treating "similar to prototype z" as an ordinary feature lets the learner decide how much to trust it. The authors also found this more effective than a KL-style penalty term.
• I3. Choose the similarity notion to fit the task. Syntactic tagging used directional neighbor contexts. Topical segmentation used undirected counts from a wider window (±3 tokens), reduced by SVD to 50 dimensions. Because nearby words then share prototypes, the model naturally produces long runs of the same label, with no need to hand-bias the transitions.
• I4. Express structural cues as an extra label. Field boundaries were handled by adding a BOUNDARY entry with a few prototypes, plus a simple post-processing rule that copies the preceding label. This is a lightweight alternative to redesigning the model.
• I5. Measure the value of prior knowledge in labeled data. Reporting how much annotated data a supervised setup needs to match the prototype system makes the savings concrete. The same comparison is useful for judging any weak-supervision method.