📄 Name Tagging with Word Clusters and Discriminative Training

Summary

The authors, from BBN Technologies, aim to cut the annotation effort needed to build a named-entity tagger from days to hours. They combine three existing techniques. First, Brown-style hierarchical word clusters, which they reimplemented following the Spatter parser, are learned from about 100 million unlabeled words of Wall Street Journal text from CSR-III. Second, the clusters are encoded as bit-string prefix features in a tagger trained with Collins' averaged perceptron, which, unlike a generative HMM, can handle many overlapping features. Third, active learning selects the sentences the model is least confident about. On the seven MUC-6 categories, the full system needs only about 13% of the labeled data that a strong HMM name finder requires for equal accuracy. It reaches 90 F with under 20,000 annotated words, roughly half a working day for one annotator. With 1M training words it still cuts errors by 25%. This shows that unlabeled text plus smart example selection can largely substitute for manual annotation.

Key points

• Clustering: Clusters come from the bigram mutual-information algorithm of Brown et al. (1990), run on the WSJ portion of CSR-III (LDC95T6, about 100M words). Each word gets a binary path in the cluster tree, and the 8-, 12-, 16- and 20-bit prefixes of that path give four cluster granularities.
• Features: The model uses 19 feature classes. Seven mirror a standard HMM tagger: tag bigram, current, previous and next word, capitalization/number shape, and lowercased word. The other twelve are cluster prefixes for the previous, current and next word.
• Tag set: 16 tags cover 8 classes (the 7 MUC classes plus null), each split into START and CONTINUE.
• Training: The averaged perceptron runs for a fixed 5 epochs, with no cross-validation.
• Results:
  • Without clusters, the discriminative tagger is slightly worse than the HMM at mid-size training sets.
  • With clusters, it exceeds 90 F at 50k words, whereas the HMM needs 150k.
  • At 1M words it scores 96.08 F versus 94.72 for the HMM.
  • Adding active learning reaches 90 F with fewer than 20k words.

Interesting ideas

• I1. Multiple cluster granularities: Using several prefix lengths of a hierarchical cluster code as separate features avoids choosing one cluster size in advance. The discriminative learner decides which granularity is useful. This is easy to transfer to any low-resource tagging task, such as Ukrainian NER or POS tagging.
• I2. Cheap confidence measure: Confidence is the margin between the best and second-best scores at each word, computed from forward and backward Viterbi passes. The sentence takes the minimum of its word margins. This gives active-learning selection without any extra model.
• I3. Clusters make active learning work better: Uncertainty is no longer just "seen vs. unseen word", because clusters give partial knowledge about unknown words. Selection therefore becomes informative earlier, so the two techniques reinforce each other.
• I4. Simulated active learning: Selection can be simulated by letting the system pick from an already-annotated pool, which makes experiments cheap and repeatable. The authors warn that the benefit vanishes once the pool is exhausted, so this setup is most meaningful for small training sets.
• I5. Cost-based evaluation: Results are framed in annotator time (about 5,000 words per hour, "4 person-hours vs. 4 person-days"), not just F-score. This is a practical way to report gains for projects that must budget annotation.