Rule Markov Models for Fast Tree-to-String Translation

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 856–864, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Rule Markov Models for Fast Tree-to-String Translation Ashish Vaswani Information Sciences Institute University of Southern California avaswani@isi.edu Haitao Mi Institute of Computing Technology Chinese Academy of Sciences htmi@ict.ac.cn Liang Huang and David Chiang Information Sciences Institute University of Southern California {lhuang,chiang}@isi.edu Abstract Most statistical machine translation systems rely on composed rules (rules that can be formed out of smaller rules in the grammar). Though this practice improves translation by weakening independence assumptions in the translation model, it nevertheless results in huge, redundant grammars, making both train- ing and decoding inefficient. Here, we take the opposite approach, where we only use min- imal rules (those that cannot be formed out of other rules), and instead rely on a rule Markov model of the derivation history to capture dependencies between minimal rules. Large-scale experiments on a state-of-the-art tree-to-string translation system show that our approach leads to a slimmer model, a faster decoder, yet the same translation quality (mea- sured using Bleu) as composed rules. 1 Introduction Statistical machine translation systems typically model the translation process as a sequence of trans- lation steps, each of which uses a translation rule, for example, a phrase pair in phrase-based transla- tion or a tree-to-string rule in tree-to-string transla- tion. These rules are usually applied independently of each other, which violates the conventional wis- dom that translation should be done in context. To alleviate this problem, most state-of-the-art sys- tems rely on composed rules, which are larger rules that can be formed out of smaller rules (includ- ing larger phrase pairs that can be formerd out of smaller phrase pairs), as opposed to minimal rules, which are rules that cannot be formed out of other rules. Although this approach does improve trans- lation quality dramatically by weakening the inde- pendence assumptions in the translation model, they suffer from two main problems. First, composition can cause a combinatorial explosion in the number of rules. To avoid this, ad-hoc limits are placed dur- ing composition, like upper bounds on the number of nodes in the composed rule, or the height of the rule. Under such limits, the grammar size is man- ageable, but still much larger than the minimal-rule grammar. Second, due to large grammars, the de- coder has to consider many more hypothesis transla- tions, which slows it down. Nevertheless, the advan- tages outweigh the disadvantages, and to our knowl- edge, all top-performing systems, both phrase-based and syntax-based, use composed rules. For exam- ple, Galley et al. (2004) initially built a syntax-based system using only minimal rules, and subsequently reported (Galley et al., 2006) that composing rules improves Bleuby 3.6 points, while increasing gram- mar size 60-fold and decoding time 15-fold. The alternative we propose is to replace composed rules with a rule Markov model that generates rules conditioned on their context. In this work, we re- strict a rule’s context to the …

Content truncated to 500 words