A Bayesian Model of Syntax-Directed Tree to String Grammar Induction

Trevor Cohn, Phil BlunsomEMNLP 2009 · OpenReview

Abstract

Tree-based translation models are a compelling means of integrating linguistic information into machine translation. Syntax can inform lexical selection and reordering choices and thereby improve translation quality. Research to date has focussed primarily on decoding with such models, but less on the difficult problem of inducing the bilingual grammar from data. We propose a generative Bayesian model of tree-to-string translation which induces grammars that are both smaller and produce better translations than the previous heuristic two-stage approach which employs a separate word alignment step.

Introduction

In syntax-based statistical machine translation (SMT), models typically translate by mapping source strings to target syntax trees. A critical component of this process is the bilingual grammar. Historically, extracting this grammar has relied on a two-stage heuristic process: first, using a word-based model to align words between languages, and second, extracting translation rules consistent with those alignments.

However, this approach is fundamentally flawed because word alignment models often ignore syntax. Consequently, word alignments rarely align cleanly with constituent parse trees. This mismatch forces extraction algorithms to create massive, implausible rules that memorize training data but fail to generalize. Furthermore, standard Expectation-Maximization (EM) fails in this context due to "degeneracy"—it tends to create one giant rule per sentence to maximize likelihood. This paper proposes a principled, single-step Bayesian model to infer the grammar directly from parsed parallel corpora.

The Generative Model

The authors utilize a Synchronous Tree Substitution Grammar (STSG) to model the translation process. Unlike heuristic methods, they treat grammar induction as a Bayesian inference problem, employing a Non-Parametric Bayesian Prior. Specifically, a Dirichlet Process (DP) prior is placed over the grammar rules.

A sample tree-to-string alignment where English syntax nodes map to spans in the Chinese target sentence.

The base distribution of this prior is designed to exponentially penalize large rules (those with many internal nodes or long terminal strings). This sparsity-inducing bias solves the EM degeneracy problem, encouraging the model to learn small, reusable translation rules unless the data strongly supports a more complex structure. In this framework, the alignment model is the translation model, ensuring that syntax directly informs alignments during training.

Inference via Gibbs Sampling

Given the vast space of possible grammars, the authors use Markov chain Monte Carlo (MCMC) inference, specifically a Gibbs sampler. To navigate the search space effectively, they introduce two primary operators:

  • EXPAND: Samples a new alignment span for a single node in the tree, conditioned on the rest of the tree's state.
  • SWAP: Swaps the alignment values of two sibling nodes to improve mixing and help the sampler escape local optima.
The EXPAND operator samples from various possible alignment spans for a node (e.g., 'corner/NN'), allowing the model to explore the grammar space.

Results and Insights

The model was evaluated on the NIST Chinese-English translation task. Key findings include:

  • Compact Grammars: The Bayesian model induced a grammar of 1.62M rules, nearly identical in size to the heuristic GHKM baseline (1.63M) but structurally more principled.
  • Improved Translation: Using a synchronous beam search decoder, the Bayesian grammar achieved a BLEU score of 26.6, outperforming the heuristic baseline's 26.0 on the MT03 test set (for sentences ≤ 20 words).
  • Linguistic Plausibility: The model naturally learned moderately lexicalized rules that capture systematic reorderings, such as Chinese prepositional modifiers preceding the nouns they modify.

Conclusion and Future Work

While the Bayesian approach shows clear advantages in grammar induction, absolute BLEU scores were limited by the custom decoder's lack of advanced features like synchronous rule binarization. Future work includes developing more sophisticated linguistic priors and improving inference algorithms for faster mixing. Ultimately, the goal is to move toward full Bayesian decoding rather than extracting a single point-estimate grammar.

Summary updated

Abstract

Tree based translation models are a compelling means of integrating linguistic information into machine translation. Syntax can inform lexical selection and reordering choices and thereby improve translation quality. Research to date has focussed primarily on decoding with such models, but less on the difficult problem of inducing the bilingual grammar from data. We propose a generative Bayesian model of tree-to-string translation which induces grammars that are both smaller and produce better translations than the previous heuristic two-stage approach which employs a separate word alignment step.
BibTeX
@inproceedings{cohn2009bayesian,
  author = {Trevor Cohn and Phil Blunsom},
  title = {{A Bayesian Model of Syntax-Directed Tree to String Grammar Induction}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=r1ZF8fzObH},
}
Figure