📄 Nymble: a High-Performance Learning Name-finder

Summary

Bikel and colleagues present Nymble, a trainable system for the MUC-6 named-entity (NE) task. The task covers person, organization and location names, plus dates, times, percentages and money amounts. Earlier systems mostly used hand-written finite-state patterns, which have to be rewritten for each new language or entity type. Nymble instead learns from annotated text with a modified hidden Markov model. Each name class acts as its own small bigram language model, and the Viterbi algorithm picks the most probable class sequence for a sentence. Words carry a simple deterministic feature, such as number shape or capitalization type. Sparse statistics are handled by a separately trained unknown-word model and a chain of back-off estimates. The system was tested on English MUC-6 data from WSJ and on Spanish MET data from AFP. It reached F-measures of about 90 or higher, which the authors describe as the best published result for a learned name-finder and close to hand-built systems. It needed only about 100,000 words of training data. This shows that statistical NE recognition can be ported across languages cheaply.

Key points

• Model structure: an ergodic HMM with eight name-class states (including NOT-A-NAME) and special START-OF-SENTENCE and END-OF-SENTENCE states. Each class has its own internal bigram model.
• Word features: 14 deterministic features (e.g., twoDigitNum, containsDigitAndDash, allCaps, capPeriod, firstWord, initCap, lowercase). Feature computation is the only language-dependent part, at roughly ten lines of code.
• Test data: English was evaluated on the MUC-6 test set of 30 WSJ documents and Spanish on the MET test set of AFP articles. Only blind-test scores are reported.
• Scores: Table 4.1 is garbled in the extracted text. It appears to show Nymble at about 93 F on mixed-case English, 91 on upper-case English and 90 on Spanish. The corresponding best reported scores appear to be 96, 89 and 93.
• Training-data size:
  • English had 450,000 training words. Halving this barely hurt performance, and dropping to about 100,000 words cost only 1–2 points. At 50,000 words the drop was larger.
  • Spanish (223,000 words) showed almost no change when cut to about 100,000 words.

Interesting ideas

• I1. Name class as a mini language model. Each entity type gets its own bigram model. The class-switching probability is conditioned on the previous class and the previous word. This captures cues like a title before a person name, and is a compact design for any sequence-labeling task.
• I2. Ordered, deterministic word features. Overlapping feature classes are resolved by a fixed precedence order. A dedicated firstWord flag records that capitalization at sentence start is uninformative. This is a cheap way to add shape information for low-resource languages, though the authors found Spanish lower-case organization and location words to be a pitfall.
• I3. Swapped halves for unknown words. The vocabulary is built on one half of the training data and unknown-word statistics are gathered on the other half, then the roles are reversed. All the data thus contributes to estimating unseen-word behavior, which helps when the corpus is small.
• I4. Explicit end-of-class token. A special +end+ token lets the model score where an entity stops. When predicting the next class, it falls back to the last real word of the previous class. This is a tidy boundary-modeling trick for segmenting tasks.
• I5. Learning curves by repeated halving. Training on successive halves of the data gives a quick, honest estimate of how much annotation a new language really needs. It helps decide whether to annotate more data or to build richer models.