A Gibbs Sampler for Phrasal Synchronous Grammar Induction

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 782–790, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP A Gibbs Sampler for Phrasal Synchronous Grammar Induction Phil Blunsom∗ pblunsom@inf.ed.ac.uk Chris Dyer† redpony@umd.edu Trevor Cohn∗ tcohn@inf.ed.ac.uk Miles Osborne∗ miles@inf.ed.ac.uk ∗Department of Informatics University of Edinburgh Edinburgh, EH8 9AB, UK †Department of Linguistics University of Maryland College Park, MD 20742, USA Abstract We present a phrasal synchronous gram- mar model of translational equivalence. Unlike previous approaches, we do not aresort to heuristics or constraints from word-alignment model, but instead directly induce a synchronous grammar from parallel sentence-aligned corpora. We use a hierarchical Bayesian prior to bias towards compact grammars with small translation units. Inference is per- formed using a novel Gibbs sampler over synchronous derivations. This sam- pler side-steps the intractability issues of previous models which required inference over derivation forests. Instead each sam- pling iteration is highly efficient, allowing the model to be applied to larger transla- tion corpora than previous approaches. 1 Introduction The field of machine translation has seen many advances in recent years, most notably the shift from word-based (Brown et al., 1993) to phrase- based models which use token n-grams as trans- lation units (Koehn et al., 2003). Although very few researchers use word-based models for trans- lation per se, such models are still widely used in the training of phrase-based models. These word- based models are used to find the latent word- alignments between bilingual sentence pairs, from which a weighted string transducer can be induced (either finite state (Koehn et al., 2003) or syn- chronous context free grammar (Chiang, 2007)). Although wide-spread, the disconnect between the translation model and the alignment model is arti- ficial and clearly undesirable. Word-based mod- els are incapable of learning translational equiv- alences between non-compositional phrasal units, while the algorithms used for inducing weighted transducers from word-alignments are based on heuristics with little theoretical justification. A model which can fulfil both roles would address both the practical and theoretical short-comings of the machine translation pipeline. The machine translation literature is littered with various attempts to learn a phrase-based string transducer directly from aligned sentence pairs, doing away with the separate word align- ment step (Marcu and Wong, 2002; Cherry and Lin, 2007; Zhang et al., 2008b; Blunsom et al., 2008). Unfortunately none of these approaches resulted in an unqualified success, due largely to intractable estimation. Large training sets with hundreds of thousands of sentence pairs are com- mon in machine translation, leading to a parameter space of billions or even trillions of possible bilin- gual phrase-pairs. Moreover, the inference proce- dure for each sentence pair is non-trivial, prov- ing NP-complete for learning phrase based models (DeNero and Klein, 2008) or a high order poly- nomial (O(|f|3|e|3))1 for a sub-class of weighted synchronous context free grammars (Wu, 1997). Consequently, for such models both the param- eterisation and approximate inference techniques are fundamental to their success. In this paper we present a novel …

Content truncated to 500 words