Linear Inversion Transduction Grammar Alignments as a Second Translation Path

Proceedings of the Joint 5th Workshop on Statistical Machine Translation and MetricsMATR, pages 167–171, Uppsala, Sweden, 15-16 July 2010. c⃝2010 Association for Computational Linguistics Linear Inversion Transduction Grammar Alignments as a Second Translation Path Markus SAERS and Joakim NIVRE Computational Linguistics Group Dept. of Linguistics and Philology Uppsala University Sweden first.last@lingfil.uu.se Dekai WU Human Language Technology Center Dept. of Computer Science and Engineering HKUST Hong Kong dekai@cs.ust.hk Abstract We explore the possibility of using Stochastic Bracketing Linear Inversion Transduction Grammars for a full-scale German–English translation task, both on their own and in conjunction with align- ments induced with GIZA++. The ratio- nale for transduction grammars, the details of the system and some results are pre- sented. 1 Introduction Lately, there has been some interest in using In- version Transduction Grammars (ITGs) for align- ment purposes. The main problem with ITGs is the time complexity, O(Gn6) doesn’t scale well. By limiting the grammar to a bracketing ITG (BITG), the grammar constant (G) can be eliminated, but O(n6) is still prohibitive for large data sets. There has been some work on approximate in- ference of ITGs. Zhang et al. (2008) present a method for evaluating spans in the sentence pair to determine whether they should be excluded or not. The algorithm has a best case time com- plexity of O(n3). Saers, Nivre & Wu (2009) in- troduce a beam pruning scheme, which reduces time complexity to O(bn3). They also show that severe pruning is possible without significant deterioration in alignment quality (as measured by downstream translation quality). Haghighi et al. (2009) use a simpler aligner as guidance for pruning, which reduces the time complexity by two orders of magnitude. Their work also par- tially implements the phrasal ITGs for translation- driven segmentation introduced in Wu (1997), al- though they only allow for one-to-many align- ments, rather than many-to-many alignments. A more extreme approach is taken in Saers, Nivre & Wu (2010). Not only is the search severely pruned, but the grammar itself is limited to a lin- earized form, getting rid of branching within a sin- gle parse. Although a small deterioration in down- stream translation quality is noted (compared to harshly pruned SBITGs), the grammar can be in- duced in linear time. In this paper we apply SBLITGs to a full size German–English WMT’10 translation task. We also use differentiated translation paths to com- bine SBLITG translation models with a standard GIZA++ translation model. 2 Background A transduction grammar is a grammar that gener- ates a pair of languages. In a transduction gram- mar, the terminal symbols consist of pairs of to- kens where the first is taken from the vocabulary of one of the languages, and the second from the vocabulary of the other. Transduction grammars have to our knowledge been restricted to trans- duce between languages no more complex than context-free languages (CFLs). Transduction be- tween CFLs was first described in Lewis & Stearns (1968), and then further explored in Aho & Ull- man (1972). The main motivation for …

Content truncated to 500 words