General binarization for parsing and translation

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 145–154, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics Generic binarization for parsing and translation Matthias B¨uchse Technische Universit¨at Dresden matthias.buechse@tu-dresden.de Alexander Koller University of Potsdam koller@ling.uni-potsdam.de Heiko Vogler Technische Universit¨at Dresden heiko.vogler@tu-dresden.de Abstract Binarization of grammars is crucial for im- proving the complexity and performance of parsing and translation. We present a versatile binarization algorithm that can be tailored to a number of grammar for- malisms by simply varying a formal pa- rameter. We apply our algorithm to bi- narizing tree-to-string transducers used in syntax-based machine translation. 1 Introduction Binarization amounts to transforming a given grammar into an equivalent grammar of rank 2, i.e., with at most two nonterminals on any right- hand side. The ability to binarize grammars is crucial for efficient parsing, because for many grammar formalisms the parsing complexity de- pends exponentially on the rank of the gram- mar. It is also critically important for tractable statistical machine translation (SMT). Syntax- based SMT systems (Chiang, 2007; Graehl et al., 2008) typically use some type of synchronous grammar describing a binary translation rela- tion between strings and/or trees, such as syn- chronous context-free grammars (SCFGs) (Lewis and Stearns, 1966; Chiang, 2007), synchronous tree-substitution grammars (Eisner, 2003), syn- chronous tree-adjoining grammars (Nesson et al., 2006; DeNeefe and Knight, 2009), and tree-to- string transducers (Yamada and Knight, 2001; Graehl et al., 2008). These grammars typically have a large number of rules, many of which have rank greater than two. The classical approach to binarization, as known from the Chomsky normal form transfor- mation for context-free grammars (CFGs), pro- ceeds rule by rule. It replaces each rule of rank greater than 2 by an equivalent collection of rules of rank 2. All CFGs can be binarized in this way, which is why their recognition problem is cubic. In the case of linear context-free rewriting systems (LCFRSs, (Weir, 1988)) the rule-by-rule technique also applies to every grammar, as long as an increased fanout it permitted (Rambow and Satta, 1999). There are also grammar formalisms for which the rule-by-rule technique is not complete. In the case of SCFGs, not every grammar has an equiva- lent representation of rank 2 in the first place (Aho and Ullman, 1969). Even when such a represen- tation exists, it is not always possible to compute it rule by rule. Nevertheless, the rule-by-rule bi- narization algorithm of Huang et al. (2009) is very useful in practice. In this paper, we offer a generic approach for transferring the rule-by-rule binarization tech- nique to new grammar formalisms. At the core of our approach is a binarization algorithm that can be adapted to a new formalism by changing a pa- rameter at runtime. Thus it only needs to be im- plemented once, and can then be reused for a va- riety of formalisms. More specifically, our algo- rithm requires the user to (i) encode the grammar formalism as a subclass of interpreted regular tree grammars …

Content truncated to 500 words