A Bayesian Model for Learning SCFGs with Discontiguous Rules

Proceedings of the 2012 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pages 223–232, Jeju Island, Korea, 12–14 July 2012. c⃝2012 Association for Computational Linguistics A Bayesian Model for Learning SCFGs with Discontiguous Rules Abby Levenberg Dept. of Computer Science University of Oxford ablev@cs.ox.ac.uk Chris Dyer School of Computer Science Carnegie Mellon Univeristy cdyer@cs.cmu.edu Phil Blunsom Dept. of Computer Science University of Oxford pblunsom@cs.ox.ac.uk Abstract We describe a nonparametric model and corresponding inference algorithm for learning Synchronous Context Grammar derivations for parallel text.Free The model employs a Pitman-Yor Process prior which uses a novel base distribution over synchronous grammar rules. Through both synthetic grammar induction and statistical machine translation experiments, we show that our model learns complex translational correspondences— including discontiguous, many-to-many alignments—and produces competitive translation results. Further, inference is efficient and we present results on significantly larger corpora than prior work. 1 Introduction In the twenty years since Brown et al. (1992) pio- neered the first word-based statistical machine trans- lation (SMT) models substantially more expressive models of translational equivalence have been devel- oped. The prevalence of complex phrasal, discon- tiguous, and non-monotonic translation phenomena in real-world applications of machine translation has driven the development of hierarchical and syntac- tic models based on synchronous context-free gram- mars (SCFGs). Such models are now widely used in translation and represent the state-of-the-art in most language pairs (Galley et al., 2004; Chiang, 2007). However, while the models used for translation have evolved, the way in which they are learnt has not: na¨ıve word-based models are still used to infer trans- lational correspondences from parallel corpora. In this work we bring the learning of the minimal units of translation in step with the representational power of modern translation models. We present a nonparametric Bayesian model of translation based on SCFGs, and we use its posterior distribution to infer synchronous derivations for a parallel corpus using a novel Gibbs sampler. Our model is able to: 1) directly model many-to-many alignments, thereby capturing non-compositional and idiomatic translations; 2) align discontiguous phrases in both the source and target languages; 3) have no restric- tions on the length of a rule, the number of nonter- minal symbols per rule, or their configuration. Learning synchronous grammars is hard due to the high polynomial complexity of dynamic pro- gramming and the exponential space of possible rules. As such most prior work for learning SCFGs has relied on inference algorithms that were heuristi- cally constrained or biased by word-based alignment models and small experiments (Wu, 1997; Zhang et al., 2008; Blunsom et al., 2009; Neubig et al., 2011). In contrast to these previous attempts, our SCFG model scales to large datasets (over 1.3M sentence pairs) without imposing restrictions on the form of the grammar rules or otherwise constraining the set of learnable rules (e.g., with a word alignment). We validate our sampler by demonstrating its ability to recover grammars used to generate synthetic datasets. We then evaluate our model by inducing word alignments for …

Content truncated to 500 words