Adaptor Grammars: A Framework for Specifying Compositional Nonparametric Bayesian Models

Mark Johnson, Thomas L. Griffiths, Sharon GoldwaterNeurIPS 2006 · OpenReview

Introduction

In computational linguistics, researchers frequently face a trade-off between structure and statistics. Probabilistic Context-Free Grammars (PCFGs) excel at defining hierarchical structures, such as how a sentence is composed of phrases. However, they suffer from a "memoryless" property: every time a rule is applied, it is treated as an independent event. Real language, conversely, is highly repetitive. If a speaker uses the word "jumping" once, they are much more likely to use it again.

Nonparametric Bayesian models, like Dirichlet Processes, are excellent at capturing these "rich-get-richer" frequency distributions but are notoriously difficult to compose into complex hierarchies. Historically, researchers had to derive and implement custom, complex inference algorithms for every new linguistic model. Adaptor Grammars provide a powerful solution, combining the structural elegance of formal grammars with the flexibility of nonparametric Bayesian statistics. By adding "caching" mechanisms to standard probabilistic grammars, complex tasks like word segmentation and morphological analysis can be defined simply by writing a few lines of grammar rules.

Methods: Caching with Adaptors

The authors introduce Adaptor Grammars, which extend PCFGs by inserting "adaptors" into the recursion process.

  1. The Adaptor: An adaptor is a function attached to a nonterminal symbol (like Word or Stem). Instead of always expanding that symbol using standard rules, the adaptor maintains a cache of previously generated subtrees.
  2. Pitman-Yor Process (PYP): The specific adaptor used in this framework is based on the Pitman-Yor process. It provides a "rich-get-richer" dynamic: the more often a specific tree (e.g., a specific word structure) is generated, the higher the probability it will be retrieved from the cache again rather than generated from scratch.
A visual representation of an adaptor grammar for morphological analysis, showing how Word, Stem, and Suffix subtrees are cached and reused.

To learn from data, the authors developed a general-purpose Markov chain Monte Carlo (MCMC) algorithm. The breakthrough in their implementation is a PCFG approximation: they temporarily convert the complex adaptor state into a standard, static PCFG. This allows them to use efficient, well-known parsing algorithms to propose new structures during the sampling process.

Key Insights

The most significant insight of this work is the concept of Grammar as Specification. Complex Bayesian models can be treated as "software" written in the language of grammars. To build a morphology model, one does not need to write a new sampler; they simply write a rule like Word -> Stem Suffix.

Because the adaptors cache entire subtrees, the model naturally learns to identify "units" of language (like words or morphemes) that aren't explicitly defined in the input string. It effectively "adapts" the grammar to the specific vocabulary of the dataset. Furthermore, the authors demonstrate that many existing, specialized models—such as Hierarchical Dirichlet Processes (HDPs)—are actually just specific configurations of Adaptor Grammars.

Experimental Results

The paper evaluates the framework on two classic unsupervised learning tasks:

  • Word Segmentation: Using a corpus of unsegmented child-directed speech (phoneme sequences) originally compiled by Brent (1999), the model achieved a precision of 0.64 and an F-score of 0.56. While modest by modern deep learning standards, these numbers were entirely consistent with the state-of-the-art unigram Bayesian models of the time, validating the framework.
  • Morphological Analysis: Using 170,015 orthographic verb tokens extracted from the Penn Wall Street Journal (WSJ) corpus, the model correctly segmented 70% of tokens and 66% of unique verb types.

Notably, the errors made by the model were often linguistically sensible. For example, it might analyze eased as eas + ed. While "eas" isn't a standard stem, the model correctly identified the suffix pattern and the relationship between eased and easing.

Limitations and Future Directions

While powerful, the framework has limitations. MCMC sampling is inherently slow and computationally expensive compared to modern neural approaches. Additionally, the current inference algorithm requires that "adapted" nonterminals (those with caches) cannot be self-recursive (e.g., $X \to X Y$), which limits the types of structures the model can represent. Finally, the Metropolis-Hastings proposal assumes the adaptor state doesn't change within a single string. While this had a negligible effect on accuracy (less than 1% rejection rate), it remains a theoretical approximation.

Ultimately, the authors suggest that the real power of this framework lies in building more sophisticated models by layering these simple grammar components, serving as a precursor to the more complex hierarchical Bayesian models used in subsequent years.

Summary updated

Abstract

This paper introduces adaptor grammars, a class of probabilistic models of lan- guage that generalize probabilistic context-free grammars (PCFGs). Adaptor grammars augment the probabilistic rules of PCFGs with “adaptors” that can in- duce dependencies among successive uses. With a particular choice of adaptor, based on the Pitman-Yor process, nonparametric Bayesian models of language using Dirichlet processes and hierarchical Dirichlet processes can be written as simple grammars. We present a general-purpose inference algorithm for adaptor grammars, making it easy to define and use such models, and illustrate how several existing nonparametric Bayesian models can be expressed within this framework.
BibTeX
@inproceedings{johnson2006adaptor,
  author = {Mark Johnson and Thomas L. Griffiths and Sharon Goldwater},
  title = {{Adaptor Grammars: A Framework for Specifying Compositional Nonparametric Bayesian Models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2006},
  url = {https://openreview.net/forum?id=r1bGN_ZdZH},
}
Figure