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.
- The Adaptor: An adaptor is a function attached to a nonterminal symbol (like
WordorStem). Instead of always expanding that symbol using standard rules, the adaptor maintains a cache of previously generated subtrees. - 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.
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