Variational Decoding for Statistical Machine Translation

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 593–601, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Variational Decoding for Statistical Machine Translation Zhifei Li and Jason Eisner and Sanjeev Khudanpur Department of Computer Science and Center for Language and Speech Processing Johns Hopkins University, Baltimore, MD 21218, USA zhifei.work@gmail.com, jason@cs.jhu.edu, khudanpur@jhu.edu Abstract Statistical models in machine translation exhibit spurious ambiguity. That is, the probability of an output string is split among many distinct derivations (e.g., trees or segmentations). In principle, the goodness of a string is measured by the total probability of its many derivations. However, finding the best string (e.g., dur- ing decoding) is then computationally in- tractable. Therefore, most systems use a simple Viterbi approximation that mea- sures the goodness of a string using only its most probable derivation. Instead, we develop a variational approximation, which considers all the derivations but still allows tractable decoding. Our particular variational distributions are parameterized as n-gram models. We also analytically show that interpolating these n-gram mod- els for different n is similar to minimum- risk decoding for BLEU (Tromble et al., 2008). Experiments show that our ap- proach improves the state of the art. 1 Introduction Ambiguity is a central issue in natural language processing. Many systems try to resolve ambigu- ities in the input, for example by tagging words with their senses or choosing a particular syntax tree for a sentence. These systems are designed to recover the values of interesting latent variables, such as word senses, syntax trees, or translations, given the observed input. However, some systems resolve too many ambi- guities. They recover additional latent variables— so-called nuisance variables—that are not of in- terest to the user.1 For example, though machine translation (MT) seeks to output a string, typical MT systems (Koehn et al., 2003; Chiang, 2007) 1These nuisance variables may be annotated in training data, but it is more common for them to be latent even there, i.e., there is no supervision as to their “correct” values. will also recover a particular derivation of that out- put string, which specifies a tree or segmentation and its alignment to the input string. The compet- ing derivations of a string are interchangeable for a user who is only interested in the string itself, so a system that unnecessarily tries to choose among them is said to be resolving spurious ambiguity. Of course, the nuisance variables are important components of the system’s model. For example, the translation process from one language to an- other language may follow some hidden tree trans- formation process, in a recursive fashion. Many features of the model will crucially make reference to such hidden structures or alignments. However, collapsing the resulting spurious ambiguity—i.e., marginalizing out the nuisance variables—causes significant computational dif- ficulties. The goodness of a possible MT out- put string should be measured by summing up the probabilities of all its derivations. Unfortu- nately, finding the best string is then computation- ally intractable …

Content truncated to 500 words