Trevor Cohn, Sharon Goldwater, Phil Blunsom Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics.
Abstract
This paper introduces a Bayesian non-parametric approach to learning Tree Substitution Grammars (TSGs) that automatically balances model complexity and accuracy. By using a Dirichlet Process prior, the model induces compact grammars that capture non-local linguistic structures—like verb subcategorization—while significantly outperforming standard context-free grammars.
Introduction
Most successful syntactic models are based on Probabilistic Context-Free Grammars (PCFGs). However, PCFGs make a massive, unrealistic assumption: that a phrase's internal structure is independent of its outside context. To make PCFGs work well, researchers usually have to spend years "hand-coding" features or engineering complex smoothing techniques.
Tree Substitution Grammars (TSGs) offer a solution by allowing "rules" to be entire tree fragments (elementary trees) rather than just a single parent and its immediate children. This lets the model capture non-local context, such as how a specific verb prefers certain types of objects. The challenge lies in induction: deciding which fragments to use without over-fitting. Previous methods, like Data Oriented Parsing (DOP), often used every possible subtree, leading to massive, computationally expensive grammars.
Methodology
The authors treat grammar induction as a segmentation problem. Given a treebank, the model must decide where to "cut" the trees into elementary fragments.
Bayesian Non-parametric Prior
The model utilizes a Dirichlet Process (DP) prior for each non-terminal symbol. This creates a "rich-get-richer" dynamic, where the model prefers to reuse a small set of fragments it has seen before rather than constantly inventing new ones. This bias toward sparsity ensures the resulting grammar remains compact.
Inference and Parsing
To train the model, a Gibbs sampling method is employed. The sampler iterates through the trees, deciding at each node whether it is a "substitution point" (a boundary between fragments) or an internal node. Because finding the exact maximum probability parse is NP-hard for TSGs, the authors use Monte Carlo sampling to approximate the best tree, specifically focusing on a Maximum Expected Rule (MER) approach.
Key Insights
A key insight of this work is that while a syntax tree is fixed, there are many ways (derivations) to build it. By penalizing the "cost" of large rules through the DP prior, the model only learns complex fragments when standard context-free assumptions fail. This results in a grammar that is only about twice the size of a standard PCFG, yet far more accurate. The model automatically uncovers structures like multi-word expressions and verb subcategorization frames without explicit supervision.
Results and Discussion
The model was evaluated on the Penn Treebank (Wall Street Journal) corpus. On a small data sample (Section 2), the TSG model achieved an F1 score of 76.89%, compared to just 60.20% for a standard PCFG. On the full Penn Treebank, the model achieved an F1 of 84.0%.
As shown in Figure 2, the induced grammar is remarkably compact. It used only ~15,000 rules to achieve its results, whereas a DOP model on the same data would typically use over 700,000 rules. Most induced rules are relatively shallow (depth 2-4), confirming the model's preference for simplicity while still capturing essential non-local dependencies.
Conclusion
This research demonstrates that Bayesian non-parametric induction can produce TSGs that are both accurate and computationally manageable. While the model does not yet reach the performance of highly-tuned, category-refined parsers on very large datasets, it offers a theoretically consistent and automated way to capture linguistic structure that PCFGs miss. Future work may combine these TSG fragments with refined non-terminal categories for further performance gains.
Summary updated