How to train your multi bottom-up tree transducer

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 825–834, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics How to train your multi bottom-up tree transducer Andreas Maletti Universit¨at Stuttgart, Institute for Natural Language Processing Azenbergstraße 12, 70174 Stuttgart, Germany andreas.maletti@ims.uni-stuttgart.de Abstract The local multi bottom-up tree transducer is introduced and related to the (non-contiguous) synchronous tree sequence substitution gram- mar. It is then shown how to obtain a weighted local multi bottom-up tree transducer from a bilingual and biparsed corpus. Finally, the problem of non-preservation of regular- ity is addressed. Three properties that ensure preservation are introduced, and it is discussed how to adjust the rule extraction process such that they are automatically fulfilled. 1 Introduction A (formal) translation model is at the core of ev- ery machine translation system. Predominantly, sta- tistical processes are used to instantiate the for- mal model and derive a specific translation device. Brown et al. (1990) discuss automatically trainable translation models in their seminal paper. However, the IBM models of Brown et al. (1993) are string- based in the sense that they base the translation de- cision on the words and their surrounding context. Contrary, in the field of syntax-based machine trans- lation, the translation models have full access to the syntax of the sentences and can base their decision on it. A good exposition to both fields is presented in (Knight, 2007). In this paper, we deal exclusively with syntax- based translation models such as synchronous tree substitution grammars (STSG), multi bottom-up tree transducers (MBOT), and synchronous tree-sequence substitution grammars (STSSG). Chiang (2006) gives a good introduction to STSG, which originate from the syntax-directed translation schemes of Aho and Ullman (1972). Roughly speaking, an STSG has rules in which two linked nonterminals are re- placed (at the same time) by two corresponding trees containing terminal and nonterminal symbols. In addition, the nonterminals in the two replacement trees are linked, which creates new linked nontermi- nals to which further rules can be applied. Hence- forth, we refer to these two trees as input and output tree. MBOT have been introduced in (Arnold and Dauchet, 1982; Lilin, 1981) and are slightly more expressive than STSG. Roughly speaking, they al- low one replacement input tree and several output trees in a single rule. This change and the pres- ence of states yields many algorithmically advanta- geous properties such as closure under composition, efficient binarization, and efficient input and output restriction [see (Maletti, 2010)]. Finally, STSSG, which have been derived from rational tree rela- tions (Raoult, 1997), have been discussed by Zhang et al. (2008a), Zhang et al. (2008b), and Sun et al. (2009). They are even more expressive than the lo- cal variant of the multi bottom-up tree transducer (LMBOT) that we introduce here and can have sev- eral input and output trees in a single rule. In this contribution, we restrict MBOT to a form that is particularly relevant in machine translation. We drop the general state behavior …

Content truncated to 500 words