Why Synchronous Tree Substitution Grammars?

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 876–884, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Why Synchronous Tree Substitution Grammars? Andreas Maletti Universitat Rovira i Virgili, Departament de Filologies Rom`aniques Avinguda de Catalunya 35, 43002 Tarragona, Spain andreas.maletti@urv.cat Abstract Synchronous tree substitution grammars are a translation model that is used in syntax-based machine translation. They are investigated in a formal setting and compared to a competi- tor that is at least as expressive. The competi- tor is the extended multi bottom-up tree trans- ducer, which is the bottom-up analogue with one essential additional feature. This model has been investigated in theoretical computer science, but seems widely unknown in natu- ral language processing. The two models are compared with respect to standard algorithms (binarization, regular restriction, composition, application). Particular attention is paid to the complexity of the algorithms. 1 Introduction Every machine translation system uses a transla- tion model, which is a formal model that describes the translation process. Either this system is hand- crafted (in rule-based translation systems) or it is trained with the help of statistical processes. Brown et al. (1990) discuss automatically trainable transla- tion models in their seminal paper on the latter ap- proach. The IBM models of Brown et al. (1993) are string-based in the sense that they base the transla- tion decision on the words and the surrounding con- text. In the field of syntax-based machine transla- tion, the translation models have access to the syntax (in the form of parse trees) of the sentences. Knight (2007) presents a good exposition to both fields. In this paper, we focus on syntax-based transla- tion models, and in particular, synchronous tree sub- stitution grammars (STSGs), or the equally pow- erful (linear and nondeleting) extended (top-down) tree transducers of Graehl et al. (2008). Chiang and Knight (2006) gives a good introduction to STSGs, which originate from the syntax-directed transla- tion schemes of Aho and Ullman (1972) [nowadays more commonly known as synchronous context-free grammars]. Roughly speaking, an STSG has rules in which a nonterminal is replaced by two trees con- taining terminal and nonterminal symbols. In addi- tion, the nonterminals in the two trees are linked and a rule is only applied to linked nonterminals. Several algorithms for STSGs have been dis- cussed in the literature. For example, we can • train them [see Graehl et al. (2008)], • attempt to binarize them using the methods of (Zhang et al., 2006; Huang et al., 2009; DeNero et al., 2009b), • parse them [see DeNero et al. (2009a)], or • attempt to compose them. However, some important algorithms are partial be- cause it is known that the construction might not be possible in general. This is the case, for example, for binarization and composition. In the theoretical computer science community, alternative models have been explored. Such a model is the multi bottom-up tree transducer (MBOT) of Arnold and Dauchet (1982) and Lilin (1981), which essentially is the …

Content truncated to 500 words