Monte Carlo inference and maximization for phrase-based translation

Proceedings of the Thirteenth Conference on Computational Natural Language Learning (CoNLL), pages 102–110, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Monte Carlo inference and maximization for phrase-based translation Abhishek Arun∗ a.arun@sms.ed.ac.uk Phil Blunsom∗ pblunsom@inf.ed.ac.uk Chris Dyer† redpony@umd.edu Adam Lopez∗ alopez@inf.ed.ac.uk Barry Haddow∗ bhaddow@inf.ed.ac.uk Philipp Koehn∗ pkoehn@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 Recent advances in statistical machine translation have used beam search for approximate NP-complete inference within probabilistic translation models. We present an alternative approach of sampling from the posterior distribution defined by a translation model. We define a novel Gibbs sampler for sampling translations given a source sentence and show that it effectively explores this posterior distribution. In doing so we overcome the limitations of heuristic beam search and obtain theoretically sound solutions to inference problems such as finding the maximum probability translation and minimum expected risk training and decoding. 1 Introduction Statistical machine translation (SMT) poses the problem: translationgiven a foreign sentence f, find the e∗ that maximises the conditional posterior probability p(e|f). This probabilistic formulation of translation has driven development of state-of-the-art systems which are able to learn from parallel corpora which were generated for other purposes — a direct result of employing a mathematical framework that we can reason about independently of any particular model. For example, we can train SMT models using maximum likelihood estimation (Brown et al., 1993; Och and Ney, 2000; Marcu and Wong, 2002). Alter- natively, we can train to minimise probabilistic con- ceptions of risk (expected loss) with respect to trans- lation metrics, thereby obtaining better results for those metrics (Kumar and Byrne, 2004; Smith and Eisner, 2006; Zens and Ney, 2007). We can also use Bayesian inference techniques to avoid resorting to heuristics that damage the probabilistic interpreta- tion of the models (Zhang et al., 2008; DeNero et al., 2008; Blunsom et al., 2009). Most models define multiple derivations for each translation; the probability of a translation is thus the sum over all of its derivations. Unfortunately, finding the maximum probability translation is NP- hard for all but the most trivial of models in this setting (Sima’an, 1996). It is thus necessary to resort to approximations for this sum and the search for its maximum e∗. The most common of these approximations is the max-derivation approximation, which for many models can be computed in polynomial time via dynamic programming (DP). Though effective for some problems, it has many serious drawbacks for probabilistic inference: 1. It typically differs from the true model maxi- mum. 2. It often requires additional approximations in search, leading to further error. 3. It introduces restrictions on models, such as use of only local features. 4. It provides no good solution to compute the normalization factor Z(f) required by many prob- abilistic algorithms. In this work, we solve these problems using a Monte Carlo technique with none of the above draw- backs. Our technique is based on a novel …

Content truncated to 500 words