📄 A Maximum Entropy Model for Part-Of-Speech Tagging

Summary

The paper addresses English part-of-speech tagging, where previous taggers evaluated on the Wall St. Journal portion of the Penn Treebank had achieved roughly 96.5% accuracy. Ratnaparkhi asks whether richer use of context can push this further. He builds a Maximum Entropy (log-linear) tagger that treats tagging as predicting each tag from a "history": the surrounding words within two positions, the two previous tags, and, for rare or unseen words, spelling cues such as prefixes, suffixes, digits, capitals and hyphens. Parameters are estimated with Generalized Iterative Scaling. Decoding uses a beam search, optionally restricted by a tag dictionary. On unseen test data the tagger scores 96.6%, matching or slightly beating Markov-model, decision-tree and transformation-based taggers, and it does so without word classes or elaborate smoothing. The study also finds that word-specific features add little, because annotation in the treebank is inconsistent across annotators. Training and testing on a single annotator's data improves accuracy by about 0.5%. This suggests that corpus noise, more than modelling power, limits WSJ tagging accuracy.

Key points

• Data: WSJ section of the Penn Treebank, split into contiguous parts.
  • Training: 40,000 sentences / 962,687 words.
  • Development: 8,000 / 192,826.
  • Test: 5,485 / 133,805.
  • Unknown words: 6,107 in development and 3,546 in test.
• Baseline on development data with the tag dictionary: 96.43% word accuracy, 86.23% on unknown words, 47.55% whole-sentence accuracy. Without the dictionary, word accuracy is 96.31%.
• Final result on the held-out test set: 96.6%. Comparable systems score about 96.5%, including Brill's TBL (85% on unknown words) and Magerman's SDT.
• Settings and cost:
  • Words seen fewer than 5 times count as "rare."
  • Features occurring fewer than 10 times are discarded, except current-word features.
  • Beam size is 5.
  • Training took about 24 hours on an IBM RS/6000.
• Word-specific features gave little gain. Tag distributions for words like "about" differ by annotator, and a single-annotator setup yields about 0.5% higher accuracy.

Interesting ideas

• I1. Rare words stand in for unknown words. Spelling features are learned only from infrequent training words, which mimic the out-of-vocabulary items seen at test time. This is a cheap way to train OOV handling, and it could transfer to morphologically rich languages like Ukrainian.
• I2. Feature templates with a count cutoff. Yes/no context templates are instantiated automatically from the training data, and rare features are simply dropped. This replaces complex smoothing with one easy-to-tune threshold, which suits any log-linear or feature-based classifier.
• I3. Tag dictionary as a speed tool. Known words are allowed only the tags they appeared with in training. The accuracy gain is tiny, but the search space shrinks a lot. This trade-off is useful wherever decoding speed matters.
• I4. Analysing errors by annotator. Comparing tag distributions per annotator exposes inconsistencies in the gold standard and explains why accuracy plateaus. This is a valuable check before chasing small gains on any treebank, including UD corpora.
• I5. Probabilistic outputs for downstream use. Because the tagger produces a probability for each decision, it can be plugged into larger probabilistic systems such as parsers or chunkers. Rule-based approaches like TBL cannot offer this.