Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 539–547, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Optimal Reduction of Rule Length in Linear Context-Free Rewriting Systems Carlos G´omez-Rodr´ıguez1, Marco Kuhlmann2, Giorgio Satta3 and David Weir4 1 Departamento de Computaci´on, Universidade da Coru˜na, Spain (cgomezr@udc.es) 2 Department of Linguistics and Philology, Uppsala University, Sweden (marco.kuhlmann@lingfil.uu.se) 3 Department of Information Engineering, University of Padua, Italy (satta@dei.unipd.it) 4 Department of Informatics, University of Sussex, United Kingdom (davidw@sussex.ac.uk) Abstract Linear Context-free Rewriting Systems (LCFRS) is an expressive grammar formalism with applications in syntax-based machine translation. The parsing complexity of an LCFRS is exponential in both the rank of a production, defined as the number of nonterminals on its right-hand side, and a measure for the discontinuity of a phrase, called fan-out. In this paper, we present an algorithm that transforms an LCFRS into a strongly equivalent form in which all productions have rank at most 2, and has minimal fan-out. Our results generalize previous work on Synchronous Context-Free Grammar, and are particularly relevant for machine translation from or to languages that require syntactic analyses with discontinuous constituents. 1 Introduction There is currently considerable interest in syntax- based models for statistical machine translation that are based on the extraction of a synchronous gram- mar from a corpus of word-aligned parallel texts; see for instance Chiang (2007) and the references therein. One practical problem with this approach, apart from the sheer number of the rules that result from the extraction procedure, is that the parsing complexity of all synchronous formalisms that we are aware of is exponential in the rank of a rule, defined as the number of nonterminals on the right- hand side. Therefore, it is important that the rules of the extracted grammar are transformed so as to minimise this quantity. Not only is this beneficial in terms of parsing complexity, but smaller rules can also improve a translation model’s ability to gener- alize to new data (Zhang et al., 2006). Optimal algorithms exist for minimising the size of rules in a Synchronous Context-Free Gram- mar (SCFG) (Uno and Yagiura, 2000; Zhang et al., 2008). However, the SCFG formalism is limited to modelling word-to-word alignments in which a single continuous phrase in the source language is aligned with a single continuous phrase in the tar- get language; as defined below, this amounts to saying that SCFG have a fan-out of 2. This re- striction appears to render SCFG empirically inad- equate. In particular, Wellington et al. (2006) find that the coverage of a translation model can increase dramatically when one allows a bilingual phrase to stretch out over three rather than two continuous substrings. This observation is in line with empir- ical studies in the context of dependency parsing, where the need for formalisms with higher fan-out has been observed even in standard, single language texts (Kuhlmann and Nivre, 2006). In this paper, we present an algorithm that com- putes optimal decompositions of rules …

Content truncated to 500 words