Hierarchical Phrase-based Translation Representations

Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1373–1383, Edinburgh, Scotland, UK, July 27–31, 2011. c⃝2011 Association for Computational Linguistics Hierarchical Phrase-Based Translation Representations Gonzalo Iglesias⋆ Cyril Allauzen‡ William Byrne⋆ Adri`a de Gispert⋆ Michael Riley‡ ⋆Department of Engineering, University of Cambridge, Cambridge, CB2 1PZ, U.K. {gi212,wjb31,ad465}@eng.cam.ac.uk ‡ Google Research, 76 Ninth Avenue, New York, NY 10011 {allauzen,riley}@google.com Abstract This paper compares several translation rep- resentations for a synchronous context-free grammar parse including CFGs/hypergraphs, finite-state automata (FSA), and pushdown automata (PDA). The representation choice is shown to determine the form and complex- ity of target LM intersection and shortest-path algorithms that follow. Intersection, shortest path, FSA expansion and RTN replacement al- gorithms are presented for PDAs. Chinese-to- English translation experiments using HiFST and HiPDT, FSA and PDA-based decoders, are presented using admissible (or exact) search, possible for HiFST with compact SCFG rulesets and HiPDT with compact LMs. For large rulesets with large LMs, we intro- duce a two-pass search strategy which we then analyze in terms of search errors and transla- tion performance. 1 Introduction Hierarchical phrase-based translation, using a syn- chronous context-free translation grammar (SCFG) together with an n-gram target language model (LM), is a popular approach in machine transla- tion (Chiang, 2007). Given a SCFG G and an n- gram language model M, this paper focuses on how to decode with them, i.e. how to apply them to the source text to generate a target translation. Decod- ing has three basic steps, which we first describe in terms of the formal languages and relations in- volved, with data representations and algorithms to follow. 1. Translating the source sentence s with G to give target translations: T = {s} ◦ G, a (weighted) context-free language resulting from the composition of a finite language and the algebraic relation G for SCFG G. 2. Applying the language model to these target translations: L=T ∩M, a (weighted) context- free language resulting from the intersection of a context-free language and the regular lan- guage M for M. 3. Searching for the translation and language model combination with the highest-probablity path: ˆL=argmaxl∈LL Of course, decoding requires explicit data represen- tations and algorithms for combining and searching them. In common to the approaches we will con- sider here, s is applied to G by using the CYK algo- rithm in Step 1 and M is represented by a finite au- tomaton in Step 2. The choice of the representation of T in many ways determines the remaining de- coder representations and algorithms needed. Since {s} is a finite language and we assume through- out that G does not allow unbounded insertions, T and L are, in fact, regular languages. As such, T and L have finite automaton representations Tf and Lf. In this case, weighted finite-state intersec- tion and single-source shortest path algorithms (us- ing negative log probabilities) can be used to solve Steps 2 and 3 (Mohri, 2009). This is the approach taken in (Iglesias et al., 2009a; de Gispert …

Content truncated to 500 words