Efficient Parsing for Transducer Grammars

Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the ACL, pages 227–235, Boulder, Colorado, June 2009. c⃝2009 Association for Computational Linguistics Efficient Parsing for Transducer Grammars John DeNero, Mohit Bansal, Adam Pauls, and Dan Klein Computer Science Division University of California, Berkeley {denero, mbansal, adpauls, klein}@cs.berkeley.edu Abstract The tree-transducer grammars that arise in current syntactic machine translation systems are large, flat, and highly lexicalized. We ad- dress the problem of parsing efficiently with such grammars in three ways. First, we present a pair of grammar transformations that admit an efficient cubic-time CKY-style parsing algorithm despite leaving most of the grammar in n-ary form. Second, we show how the number of intermediate symbols gen- erated by this transformation can be substan- tially reduced through binarization choices. Finally, we describe a two-pass coarse-to-fine parsing approach that prunes the search space using predictions from a subset of the origi- nal grammar. In all, parsing time reduces by 81%. We also describe a coarse-to-fine prun- ing scheme for forest-based language model reranking that allows a 100-fold increase in beam size while reducing decoding time. The resulting translations improve by 1.3 BLEU. 1 Introduction Current approaches to syntactic machine translation typically include two statistical models: a syntac- tic transfer model and an n-gram language model. Recent innovations have greatly improved the effi- ciency of language model integration through multi- pass techniques, such as forest reranking (Huang and Chiang, 2007), local search (Venugopal et al., 2007), and coarse-to-fine pruning (Petrov et al., 2008; Zhang and Gildea, 2008). Meanwhile, trans- lation grammars have grown in complexity from simple inversion transduction grammars (Wu, 1997) to general tree-to-string transducers (Galley et al., 2004) and have increased in size by including more synchronous tree fragments (Galley et al., 2006; Marcu et al., 2006; DeNeefe et al., 2007). As a result of these trends, the syntactic component of machine translation decoding can now account for a substan- tial portion of total decoding time. In this paper, we focus on efficient methods for parsing with very large tree-to-string grammars, which have flat n-ary rules with many adjacent non-terminals, as in Fig- ure 1. These grammars are sufficiently complex that the purely syntactic pass of our multi-pass decoder is the compute-time bottleneck under some conditions. Given that parsing is well-studied in the mono- lingual case, it is worth asking why MT grammars are not simply like those used for syntactic analy- sis. There are several good reasons. The most im- portant is that MT grammars must do both analysis and generation. To generate, it is natural to mem- orize larger lexical chunks, and so rules are highly lexicalized. Second, syntax diverges between lan- guages, and each divergence expands the minimal domain of translation rules, so rules are large and flat. Finally, we see most rules very few times, so it is challenging to subcategorize non-terminals to the degree done in analytic parsing. This paper de- velops encodings, algorithms, and pruning strategies for such grammars. We first investigate the …

Content truncated to 500 words