Part-of-Speech Tagging using a Variable Memory Markov Model

Hinrich Schütze, Yoram SingerACL 1994 · OpenReview

Abstract

We present a new approach to disambiguating syntactically ambiguous words in context, based on Variable Memory Markov (VMM) models. In contrast to fixed-length Markov models, which predict based on fixed-length histories, variable memory Markov models dynamically adapt their history length based on the training data, and hence may use fewer parameters. In a test of a VMM based tagger on the Brown corpus, 95.81% of tokens are correctly classified.

Introduction

Part-of-speech (POS) tagging—the process of assigning grammatical categories such as "noun," "verb," or "adjective" to words—is a cornerstone of natural language processing. The central difficulty in tagging is lexical ambiguity. For instance, the word "book" can be a noun ("read a book") or a verb ("book a flight"). Resolving these ambiguities requires context.

Historically, researchers have employed two main types of stochastic models. Fixed-order Markov models predict the next tag based on a constant history of $k$ previous tags. However, these models suffer from the "curse of dimensionality": with a large tag set, the number of parameters grows exponentially, leading to data sparsity issues where most possible sequences are never observed during training. Alternatively, Hidden Markov Models (HMMs) can be trained on untagged data but are prone to converging on local minima, making their performance highly dependent on initial parameters. This paper, originally published by Hinrich Schütze and Yoram Singer, proposes Variable Memory Markov (VMM) models as a solution that provides deep context where necessary while maintaining a compact parameter space.

Methodology: Variable Memory Markov Models

The core innovation of this work is the use of VMMs, implemented via Prediction Suffix Trees. Unlike standard models, a VMM does not assume a fixed history length. Instead, it selectively "grows" its memory based on the statistical properties of the training data.

Selective Memory and Statistical Surprise

The model begins with a memory of zero and incrementally adds preceding tags to its history only if doing so significantly improves the prediction of the next tag. This growth is governed by the Kullback-Leibler (KL) divergence, a measure of relative entropy. If the "surprise" of seeing a specific tag sequence is high enough compared to its shorter suffix, the longer sequence is promoted to a state in the model.

Table 1: Comparison of transition probabilities for one-symbol vs. two-symbol states. This data demonstrates how adding context (e.g., 'AT' before 'JJ') significantly shifts the probability distribution for the subsequent tag, justifying the use of a longer memory for specific sequences.

As shown in the experimental data, the model "discovered" that most tags only require a single-tag history. Longer histories were only retained for specific linguistic patterns, such as an Article followed by an Adjective (AT JJ), which strongly predicts a following Noun.

Tag Conversion Smoothing

Handling unseen words is a perennial challenge in NLP. The authors introduced a novel "tag conversion" smoothing technique. Rather than treating all parts of speech equally, this method estimates the probability that a word seen as one tag might actually belong to another. This respects the distinction between "open-class" words (like nouns and verbs, which frequently gain new members) and "closed-class" words (like articles and pronouns, which rarely change).

Table 2: Estimated probabilities for tag conversions. This smoothing technique allows the model to better handle ambiguous or previously unseen words by leveraging linguistic patterns of category membership.

Experimental Setup and Results

The VMM tagger was trained and evaluated on the Brown Corpus. The training set consisted of approximately 1 million tagged tokens, while the test set comprised 114,392 words. The original 471 tags were consolidated into a set of 184 distinct tags by removing stylistic modifiers.

The model achieved a high accuracy of 95.81% on the test set. More impressively, the resulting VMM automaton was incredibly lean, consisting of only 49 states:

  • 1 null state
  • 43 first-order states (1-tag history)
  • 5 second-order states (2-tag history)

This parsimony is a stark contrast to a full second-order model, which would theoretically require over 33,000 states for the same tag set.

Discussion and Conclusion

The success of the VMM tagger highlights that context in language is often local. By only expanding memory when statistically justified, the model avoids the overfitting and sparsity issues of high-order Markov models while matching the performance of more complex state-of-the-art systems of the time.

However, limitations remain. The model's error rate on words not seen during training was 57%, indicating that pure statistical transition models need to be supplemented with broader lexical information or dictionaries. Furthermore, as a finite-memory model, it cannot capture recursive linguistic structures. Nevertheless, the VMM provides a highly efficient framework for "pruning" unlikely tag sequences, serving as a powerful component for more complex hybrid tagging systems.

Summary updated

Abstract

We present a new approach to disambiguating syntactically ambiguous words in context, based on Variable Memory Markov (VMM) models. In contrast to fixed-length Markov models, which predict based on fixed-lenth histories, variable memory Markov models dynamically adapt their history length based on the training data, and hence may use fewer parameters. In a test of a VMM based tagger on the Brown corpus, 95.81% of tokens are correctly classified.
BibTeX
@inproceedings{schutze1994part,
  author = {Hinrich Schütze and Yoram Singer},
  title = {{Part-of-Speech Tagging using a Variable Memory Markov Model}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {1994},
  url = {https://openreview.net/forum?id=SyEO2heOZH},
}
Figure