Equations for Part-of-Speech Tagging

Eugene Charniak, Curtis Hendrickson, Neil Jacobson, Mike PerkowitzAAAI 1993

Introduction

This 1993 paper from Eugene Charniak and his colleagues at Brown University is a foundational text in the transition of Natural Language Processing (NLP) from rule-based systems to the probabilistic, data-driven methods we recognize today. While modern Large Language Models (LLMs) have moved far beyond these techniques, this paper remains a masterclass in how to build and evaluate statistical models from the ground up.

In the early 90s, Part-of-Speech (POS) tagging—the task of labeling every word in a sentence with its grammatical category—suffered from a lack of mathematical rigor. The authors set out to rectify this by showing exactly how various tagging models are derived from first principles. Their goal was to provide a "clean mathematical notation" that would move the field toward more transparent and scientific discussion.

Methodology

The paper builds complexity step-by-step across three main models:

  1. The Baseline Model: A simple approach that ignores context entirely, assigning to each word the tag it most frequently appeared with in the training data.
  2. The Standard Hidden Markov Model (HMM): This model considers transition probabilities (how likely tag $B$ is to follow tag $A$) and emission probabilities (how likely tag $A$ is to produce word $W$). The authors notably compare a "mathematically pure" HMM derivation against common heuristics, proving the pure version yields significantly fewer errors.
  3. The Improved Model (Smoothing & Morphology): To handle "sparse data" (words or tag sequences not seen during training), the authors introduced advanced smoothing using "frequency classes" and morphological analysis to account for word roots and suffixes.
Conceptual diagram illustrating the transition from a simple tag assignment model (top) to a more complex smoothed model using frequency classes (bottom).

Experimental Results

The researchers used the Brown Corpus, a standard 1-million-word collection of English text, with a 90/10 training/testing split. They evaluated their models on two versions of the corpus: the full set (471 distinct tags) and a reduced set (186 tags).

The results demonstrate a clear progression of accuracy as mathematical rigor and smoothing techniques are added. Simply picking the most common tag for a word (ignoring all context) achieves approximately 90% accuracy, highlighting why POS tagging is a "solved" problem at the macro level but difficult to perfect at the margins.

Accuracy results for different equation combinations across the 471-tag and 186-tag sets.

As shown in the table, the "pure" HMM derivation (Equation 19) outperformed the then-common heuristic (Equation 20). The final model, incorporating smoothing and morphology, achieved a state-of-the-art accuracy of 96.45% on the 186-tag set.

Key Insights and Conclusion

The paper's primary contribution was the formalization of smoothing—treating the "newness" of a tag as a measurable probability based on how many times a word has been seen before. Furthermore, when the model encounters an unknown word, looking at the suffix (morphology) provides a statistically significant boost in accuracy.

The authors conclude that while statistical methods are powerful, moving beyond 96.5% accuracy would likely require deeper lexical and thematic information—understanding the meaning of the words rather than just their statistical distribution.

Summary updated

BibTeX
@inproceedings{charniak1993equations,
  author = {Eugene Charniak and Curtis Hendrickson and Neil Jacobson and Mike Perkowitz},
  title = {{Equations for Part-of-Speech Tagging}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
}
Figure