Abstract: Inducing a grammar directly from text is one of the oldest and most challenging tasks in Computational Linguistics. Significant progress has been made for inducing dependency grammars, however the models employed are overly simplistic, particularly in comparison to supervised parsing models. In this paper we present an approach to dependency grammar induction using tree substitution grammar which is capable of learning large dependency fragments and thereby better modelling the text. We define a hierarchical non-parametric Pitman-Yor Process prior which biases towards a small grammar with simple productions. This approach significantly improves the state-of-the-art, when measured by head attachment accuracy.
TL;DR
This paper introduces a powerful new method for unsupervised grammar induction—learning the structure of a language without any labeled examples. By using Tree Substitution Grammars (TSG) combined with a hierarchical Pitman-Yor Process prior, the authors allow their model to learn complex, multi-word linguistic fragments while naturally biasing toward simpler structures to avoid overfitting. The result is a significant leap in dependency parsing accuracy, outperforming previous state-of-the-art models by over 5% on standard benchmarks.
What Problem Does This Paper Address?
Grammar induction is a fundamental challenge in computational linguistics: can a machine learn the rules of a language just by reading raw text? Most successful attempts focus on dependency parsing, which involves determining the head-modifier relationships between words in a sentence.
Existing models like the Dependency Model with Valence (DMV) are often too simplistic to capture complex linguistic phenomena like idioms or specific verb-argument structures. Conversely, complex models standard in supervised learning tend to overfit in an unsupervised setting, memorizing noise rather than learning grammar. Blunsom and Cohn address this trade-off by using a more expressive Tree Substitution Grammar (TSG) while employing Bayesian non-parametrics to regulate model complexity.
Methods
The authors build upon the Tree Substitution Grammar (TSG). Unlike standard Context-Free Grammars (CFG) that expand one symbol into a single layer of children, TSGs use "elementary trees"—fragments of arbitrary height. This allows the model to learn that certain groups of words often function as a single structural unit.
To make this work without labels, they employ several key techniques:
- Split-Head Construction: They use a clever mapping to turn dependency trees into a CFG-like format ($P^{sh}$), making it computationally feasible to process using standard parsing algorithms.
- Hierarchical Pitman-Yor Process (PYP): This Bayesian prior creates a multi-level "backoff" path. If the model encounters a complex, lexicalized rule, it can back off to a simpler unlexicalized rule, and eventually to a basic CFG rule. This encourages the reuse of common patterns while penalizing unnecessary complexity.
- Lexicalization: The 100 most frequent words are treated as distinct entities, while less frequent words are represented by their part-of-speech tags.
- Inference via Sampling: They use a blocked Metropolis-Hastings sampler to explore the space of possible grammars and trees, effectively "hallucinating" structures and retaining those that best explain the data.
Datasets and Evaluation
The model was evaluated using the Wall Street Journal (WSJ) section of the Penn Treebank. Training was conducted on Sections 2-21 (sentences $\le 10$ words), and evaluation was performed on Section 23. Punctuation was removed, and gold-standard part-of-speech tags were used as input.
Key Insights and Results
- Fragments are Functional: The ability to learn elementary trees allows the model to capture "look-ahead" capabilities, such as identifying that the verb "has" often expects a past participle.
- The Power of the Prior: The Pitman-Yor Process acts as a sophisticated version of Occam's Razor, allowing complexity only where it is justified by the data.
- State-of-the-Art Performance: The best model, LexTSG-DMV, achieved 55.7% head-attachment accuracy on the full Section 23. This is a massive improvement over the standard Expectation-Maximization (EM) baseline of 35.9% and significantly outperforms previous state-of-the-art smoothed models.
Limitations and Future Work
While successful, the sampling-based inference is computationally expensive. Future work may explore variational inference for speed. Additionally, the model still struggles with complex structures like conjunctions (39% accuracy), and the authors suggest applying this hierarchical Bayesian approach to even more complex formalisms like Tree Adjoining Grammars (TAG).
Summary updated