Investigations in Exact Inference for Hierarchical Translation

Proceedings of the Eighth Workshop on Statistical Machine Translation, pages 472–483, Sofia, Bulgaria, August 8-9, 2013 c⃝2013 Association for Computational Linguistics Investigations in Exact Inference for Hierarchical Translation Wilker Aziz†, Marc Dymetman‡, Sriram Venkatapathy‡ †University of Wolverhampton, Wolverhampton, UK ‡Xerox Research Centre Europe, Grenoble, France †w.aziz@wlv.ac.uk, ‡{first.last}@xrce.xerox.com Abstract We present a method for inference in hi- erarchical phrase-based translation, where both optimisation and sampling are per- formed in a common exact inference framework related to adaptive rejection sampling. We also present a first imple- mentation of that method along with ex- perimental results shedding light on some fundamental issues. In hierarchical transla- tion, inference needs to be performed over a high-complexity distribution defined by the intersection of a translation hypergraph and a target language model. We replace this intractable distribution by a sequence of tractable upper-bounds for which exact optimisers and samplers are easy to obtain. Our experiments show that exact inference is then feasible using only a fraction of the time and space that would be required by the full intersection, without recourse to pruning techniques that only provide ap- proximate solutions. While the current im- plementation is limited in the size of inputs it can handle in reasonable time, our exper- iments provide insights towards obtaining future speedups, while staying in the same general framework. 1 Introduction In statistical machine translation (SMT), optimi- sation — the task of searching for an optimum translation — is performed over a high-complexity distribution defined by the intersection between a translation hypergraph and a target language model (LM). This distribution is too complex to be repre- sented exactly and one typically resorts to approx- imation techniques such as beam-search (Koehn et al., 2003) and cube-pruning (Chiang, 2007), where maximisation is performed over a pruned represen- tation of the full distribution. Often, rather than finding a single optimum, one is really interested in obtaining a set of proba- bilistic samples from the distribution. This is the case for minimum error rate training (Och, 2003; Watanabe et al., 2007), minimum risk training (Smith and Eisner, 2006) and minimum risk de- coding (Kumar and Byrne, 2004). Due to the ad- ditional computational challenges posed by sam- pling, n-best lists, a by-product of optimisation, are typically used as approximation to true probabilis- tic samples. A known issue with n-best lists is that they tend to be clustered around only one mode of the distribution. A more direct procedure is to at- tempt to directly draw samples from the underlying distribution rather than rely on n-best list approxi- mations (Arun et al., 2009; Blunsom and Osborne, 2008). OS∗ (Dymetman et al., 2012a) is a recent ap- proach that stresses a unified view between the two types of inference, optimisation and sampling. In this view, rather than resorting to pruning in or- der to cope with the tractability issues, one upper- bounds the complex goal distribution with a sim- pler “proposal” distribution for which dynamic programming is feasible. This proposal is incre- mentally refined to be closer to …

Content truncated to 500 words