Every sensible extended top-down tree transducer is a multi bottom-up tree transducer

2012 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 263–273, Montr´eal, Canada, June 3-8, 2012. c⃝2012 Association for Computational Linguistics Every sensible extended top-down tree transducer is a multi bottom-up tree transducer Andreas Maletti∗ Institute for Natural Language Processing, Universität Stuttgart Pfaffenwaldring 5b, 70569 Stuttgart, Germany andreas.maletti@ims.uni-stuttgart.de Abstract A tree transformation is sensible if the size of each output tree is uniformly bounded by a linear function in the size of the correspond- ing input tree. Every sensible tree transfor- mation computed by an arbitrary weighted ex- tended top-down tree transducer can also be computed by a weighted multi bottom-up tree transducer. This further motivates weighted multi bottom-up tree transducers as suitable translation models for syntax-based machine translation. 1 Introduction Several different translation models are used in syntax-based statistical machine translation. Koehn (2010) presents an introduction to statistical ma- chine translation, and Knight (2007) presents an overview of syntax-based statistical machine trans- lation. The oldest and best-studied tree transfor- mation device is the top-down tree transducer of Rounds (1970) and Thatcher (1970). Gécseg and Steinby (1984) and Fülöp and Vogler (2009) present the existing results on the unweighted and weighted model, respectively. Knight (2007) promotes the use of weighted extended top-down tree transduc- ers (XTOP), which have also been implemented in the toolkit TIBURON by May and Knight (2006) [more detail is reported by May (2010)]. In the con- text of bimorphisms, Arnold and Dauchet (1976) in- vestigated XTOP, and Lilin (1978) and Arnold and Dauchet (1982) investigated multi bottom-up tree ∗The author was supported by the German Research Foun- dation (DFG) grant MA 4959/1-1. transducers (MBOT) [as k-morphisms]. Recently, weighted XTOP and MBOT, which are the cen- tral devices in this contribution, were investigated by Maletti (2011a) in the context of statistical ma- chine translation. Several tree transformation devices are used as translation models in statistical machine translation. Chiang (2007) uses synchronous context-free gram- mars, which force translations to be very similar as observed by Eisner (2003) and Shieber (2004). This deficiency is overcome by synchronous tree substitution grammars, which are state-less linear and nondeleting XTOP. Recently, Maletti (2010b) proposed MBOT, and Zhang et al. (2008b) and Sun et al. (2009) proposed the even more powerful synchronous tree-sequence substitution grammars. Those two models allow certain translation discon- tinuities, and the former device also offers computa- tional benefits over linear and nondeleting XTOP as argued by Maletti (2010b). The simplicity of XTOP makes them very appeal- ing as translation models. In 2010 the ATANLP par- ticipants [workshop at ACL] identified ‘copying’ as the most exciting and promising feature of XTOP, but unrestricted copying can lead to an undesirable explosion of the size of the translation. According to Engelfriet and Maneth (2003) a tree transforma- tion has linear size-increase if the size of each output tree is linearly bounded by the size of its correspond- ing input tree. The author believes that this is a very sensible restriction that intuitively makes sense and …

Content truncated to 500 words