Some Advances in Transformation-Based Part of Speech Tagging

Eric BrillAAAI 1994

Abstract

In this 1994 classic, Eric Brill extends his "Transformation-Based Learning" (TBL) framework to close the gap between rule-based and stochastic Part-of-Speech (POS) taggers. By introducing lexicalized rules and a novel approach for handling unknown words, Brill achieves state-of-the-art accuracy (96.5%) using a tiny fraction of the parameters required by traditional statistical models.

Introduction

In the early 1990s, Part-of-Speech (POS) tagging—the task of assigning grammatical categories like "Noun" or "Verb" to words—was dominated by stochastic models, primarily Hidden Markov Models (HMMs). While effective, HMMs functioned as "black boxes," relying on tens of thousands of probabilities that offered little linguistic insight.

Brill’s earlier work demonstrated that simple rule-based systems could compete with these models. However, they faced two significant hurdles: a lack of lexicalization (the ability to capture relationships between specific words) and the "unknown word problem" (difficulty tagging words not seen during training). This paper introduces extensions to the TBL framework to address these limitations and explores "k-best" tagging for high-uncertainty scenarios.

Methodology: Transformation-Based Error-Driven Learning

The core of the system is a "guess and check" algorithm known as Transformation-Based Error-Driven Learning. The process follows an iterative cycle to refine tagging accuracy.

The Transformation-Based Learning process, showing the iterative cycle between the learner, the annotated text, and the truth.
  1. Initial State: The tagger performs a naive first pass, typically tagging every word with its most frequent tag from the training data.
  2. Iterative Improvement: The learner compares its output to a "gold standard" manually tagged corpus. It searches through a predefined space of rule templates (e.g., "Change tag A to B if the next word is X") to identify the single rule that corrects the most errors.
  3. Greedy Search: The best rule is added to an ordered list, the corpus is updated by applying this rule, and the process repeats until no further significant improvements are possible.

Key Extensions

  • Lexicalized Rules: Rules can now reference specific words rather than just tags. For instance, a rule might change a preposition to an adverb if the word two positions to the right is "as."
  • Unknown Word Tagger: A dedicated TBL process analyzes sub-word features—such as prefixes, suffixes, and character presence—alongside surrounding context to predict tags for unseen words.
  • K-Best Tagging: The system can be trained to provide a ranked list of likely tags, ensuring the correct tag is included even in highly ambiguous cases.

Experimental Results

The authors evaluated the system using the Penn Treebank Wall Street Journal (WSJ) corpus. The contextual rules were trained on approximately 600,000 words, while the unknown word rules used 350,000 words.

Comparison of Stochastic and Rule-Based tagging methods, highlighting the efficiency of rules versus probabilities.

As shown in the table above, the TBL tagger outperformed stochastic models while maintaining extreme parameter efficiency. The rule-based system achieved 97.2% accuracy on known words using only 267 rules, whereas a stochastic model required 10,000 probabilities to reach 96.7% accuracy.

Key Insights

  • Simplicity and Interpretability: Much of linguistic structure is better captured by discrete, human-readable rules than by massive tables of statistics.
  • Automated Feature Discovery: The system autonomously "discovers" linguistic patterns, such as identifying "-ing" as a marker for gerunds, without explicit instruction.
  • The Power of Lexicalization: Adding word-specific rules reduced the error rate by 11% compared to previous tag-only versions.

Conclusion

Brill’s extended TBL framework achieved an overall accuracy of 96.5% on the WSJ corpus, the highest reported at the time for an open-vocabulary system. While lexicalized rules are powerful, they face challenges with data sparsity. Future work suggests incorporating semantic information from sources like WordNet to group words into classes, allowing for more generalized rules. This error-driven paradigm remains a versatile tool applicable to various natural language processing tasks beyond POS tagging.

Summary updated

BibTeX
@inproceedings{brill1994some,
  author = {Eric Brill},
  title = {{Some Advances in Transformation-Based Part of Speech Tagging}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure