Blocked Inference in Bayesian Tree Substitution Grammars

Trevor Cohn, Phil BlunsomACL 2010 · OpenReview

Abstract

Learning a tree substitution grammar is very challenging due to derivational ambiguity. Our recent approach used a Bayesian non-parametric model to induce good derivations from treebanked input (Cohn et al., 2009), biasing towards small grammars composed of small generalisable productions. In this paper we present a novel training method for the model using a blocked Metropolis-Hastings sampler in place of the previous method's local Gibbs sampler. The blocked sampler makes considerably larger moves than the local sampler and consequently converges in less time. A core component of the algorithm is a grammar transformation which represents an infinite tree substitution grammar in a finite context free grammar. This enables efficient blocked inference for training and also improves the parsing algorithm. Both algorithms are shown to improve parsing accuracy.

Introduction: The Challenge of Derivational Ambiguity

Tree Substitution Grammars (TSGs) offer a powerful framework for natural language processing by allowing "elementary trees"—fragments of syntax larger than a single rule—to serve as the building blocks of language. This capability is essential for modeling complex phenomena like idioms (e.g., "kick the bucket") or specific verb-argument structures that standard Context-Free Grammars (CFGs) struggle to capture.

However, TSGs suffer from significant derivational ambiguity. Given a full parse tree in a treebank, the specific elementary fragments used to construct it are hidden. To learn the grammar, researchers typically use Bayesian models to infer these latent fragments. Previous state-of-the-art methods relied on "local" Gibbs samplers that made incremental changes, such as deciding if a single node is a "cut" point. These samplers are notoriously "sticky," often getting trapped in local optima because escaping requires multiple improbable local steps to occur simultaneously.

Methodology: Blocked Metropolis-Hastings Inference

To overcome the limitations of local sampling, this paper proposes a blocked Metropolis-Hastings (MH) sampler. Instead of updating one node at a time, the blocked sampler jointly updates all substitution variables within a tree. This allows for much larger moves in the state space, leading to faster convergence.

The Key Innovation: Grammar Transformation

The primary technical challenge in implementing a blocked sampler is creating an effective proposal distribution. A good proposal should approximate the true model while remaining easy to sample from. The authors aim to use a Maximum A Posteriori (MAP) estimate; however, because the Bayesian prior allows for an infinite number of possible tree fragments, the MAP grammar is technically infinite.

To solve this, the authors developed a grammar transformation that represents an infinite TSG as an equivalent finite CFG.

The formal rules for transforming an infinite TSG into a finite CFG.

As shown in the transformation rules above, the grammar uses "signed" or "primed" nonterminals to distinguish between fragments already observed in the training data and new fragments generated by the base distribution (the "backoff" model). This allows the model to perform exact inference on an infinite space without enumerating it.

An example of the grammar transformation applied to a simple sentence, showing the mapping between elementary trees and primed nonterminals.

By structuring the CFG to represent the process of either selecting a known fragment or generating a new one, the authors can utilize standard, efficient dynamic programming—specifically the Inside algorithm—to calculate probabilities and sample entire derivations in polynomial time.

Experimental Setup and Results

The model was evaluated using the Penn Treebank (WSJ), with training conducted on Sections 02–21, development on Section 22, and testing on Section 23.

Convergence and Efficiency

The blocked sampler demonstrated superior "mixing," a term in MCMC methods referring to how well the sampler explores the distribution. By grouping variables together, the sampler breaks the high interdependencies found in tree structures. While the blocked sampler is approximately 50% slower per iteration due to the overhead of dynamic programming, it reaches higher log-likelihood states in significantly fewer iterations, resulting in a net reduction in total training time. The MH sampler also showed acceptance rates exceeding 99%, confirming that the transformed grammar serves as an exceptional proposal distribution.

Parsing Accuracy

The transformation also benefits the parsing stage. By sampling derivations from the transformed grammar and employing a Maximum Expected Recall (MER) objective, the authors achieved more robust results than previous approaches. On the full Penn Treebank (Section 23), the model achieved an F1 score of 85.3, a notable improvement over the previous best of 84.0.

Conclusion and Future Directions

This work demonstrates that blocked inference, enabled by a clever grammar transformation, significantly improves both the efficiency and accuracy of Bayesian TSG induction. While the current performance still lags slightly behind specialized state-of-the-art parsers due to simplistic handling of unknown words, the approach opens new doors for unsupervised grammar induction. Future work may explore "split-merge" moves or variational approximations to further scale the model to massive datasets where distribution modes are even more pronounced.

Summary updated

Abstract

Learning a tree substitution grammar is very challenging due to derivational ambiguity. Our recent approach used a Bayesian non-parametric model to induce good derivations from treebanked input (Cohn et al., 2009), biasing towards small grammars composed of small generalisable productions. In this paper we present a novel training method for the model using a blocked Metropolis-Hastings sampler in place of the previous method's local Gibbs sampler. The blocked sampler makes considerably larger moves than the local sampler and consequently converges in less time. A core component of the algorithm is a grammar transformation which represents an infinite tree substitution grammar in a finite context free grammar. This enables efficient blocked inference for training and also improves the parsing algorithm. Both algorithms are shown to improve parsing accuracy.
BibTeX
@inproceedings{cohn2010blocked,
  author = {Trevor Cohn and Phil Blunsom},
  title = {{Blocked Inference in Bayesian Tree Substitution Grammars}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=Sy4fjhxu-H},
}
Figure