Hierarchical Phrase-Based Translation with Weighted Finite State Transducers

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 433–441, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Hierarchical Phrase-Based Translation with Weighted Finite State Transducers Gonzalo Iglesias⋆ Adri`a de Gispert‡ ⋆ University of Vigo. Dept. of Signal Processing and Communications. Vigo, Spain {giglesia,erbanga}@gts.tsc.uvigo.es ‡ University of Cambridge. Dept. of Engineering. CB2 1PZ Cambridge, U.K. {ad465,wjb31}@eng.cam.ac.uk Eduardo R. Banga⋆ William Byrne‡ Abstract This paper describes a lattice-based decoder for hierarchical phrase-based translation. The decoder is implemented with standard WFST operations as an alternative to the well-known cube pruning procedure. We find that the use of WFSTs rather than k-best lists requires less pruning in translation search, resulting in fewer search errors, direct generation of translation lattices in the target language, better parameter optimization, and improved translation performance when rescoring with long-span language models and MBR decod- ing. We report translation experiments for the Arabic-to-English and Chinese-to-English NIST translation tasks and contrast the WFST- based hierarchical decoder with hierarchical translation under cube pruning. 1 Introduction Hierarchical phrase-based translation generates translation hypotheses via the application of hierar- chical rules in CYK parsing (Chiang, 2005). Cube pruning is used to apply language models at each cell of the CYK grid as part of the search for a k-best list of translation candidates (Chiang, 2005; Chiang, 2007). While this approach is very effective and has been shown to produce very good quality translation, the reliance on k-best lists is a limita- tion. We take an alternative approach and describe a lattice-based hierarchical decoder implemented with Weighted Finite State Transducers (WFSTs). In ev- ery CYK cell we build a single, minimal word lattice containing all possible translations of the source sen- tence span covered by that cell. When derivations contain non-terminals, we use pointers to lower- level lattices for memory efficiency. The pointers are only expanded to the actual translations if prun- ing is required during search; expansion is otherwise only carried out at the upper-most cell, after the full CYK grid has been traversed. We describe how this decoder can be easily im- plemented with WFSTs. For this we employ the OpenFST libraries (Allauzen et al., 2007). Using standard FST operations such as composition, ep- silon removal, determinization, minimization and shortest-path, we find this search procedure to be simpler to implement than cube pruning. The main modeling advantages are a significant reduction in search errors, a simpler implementation, direct gen- eration of target language word lattices, and better integration with other statistical MT procedures. We report translation results in Arabic-to-English and Chinese-to-English translation and contrast the per- formance of lattice-based and cube pruning hierar- chical decoding. 1.1 Related Work Hierarchical phrase-based translation has emerged as one of the dominant current approaches to statis- tical machine translation. Hiero translation systems incorporate many of the strengths of phrase-based translation systems, such as feature-based transla- tion and strong target language models, while also allowing flexible translation and movement based on hierarchical rules extracted from aligned paral- lel text. We …

Content truncated to 500 words