Translation as Weighted Deduction

Translation as Weighted Deduction Adam Lopez University of Edinburgh 10 Crichton Street Edinburgh, EH8 9AB United Kingdom alopez@inf.ed.ac.uk Abstract We present a unified view of many trans- lation algorithms that synthesizes work on deductive parsing, semiring parsing, and efficient approximate search algorithms. This gives rise to clean analyses and com- pact descriptions that can serve as the ba- sis for modular implementations. We illus- trate this with several examples, showing how to build search spaces for several dis- parate phrase-based search strategies, inte- grate non-local features, and devise novel models. Although the framework is drawn from parsing and applied to translation, it is applicable to many dynamic program- ming problems arising in natural language processing and other areas. 1 Introduction Implementing a large-scale translation system is a major engineering effort requiring substantial time and resources, and understanding the trade- offs involved in model and algorithm design de- cisions is important for success. As the space of systems described in the literature becomes more crowded, identifying their common elements and isolating their differences becomes crucial to this understanding. In this work, we present a com- mon framework for model manipulation and anal- ysis that accomplishes this, and use it to derive sur- prising conclusions about phrase-based models. Most translation algorithms do the same thing: dynamic programming search over a space of weighted rules (§2). Fortunately, we need not search far for modular descriptions of dy- namic programming algorithms. Deductive logic (Pereira and Warren, 1983), extended with semir- ings (Goodman, 1999), is an established formal- ism used in parsing. It is occasionally used to describe formally syntactic translation mod- els, but these treatments tend to be brief (Chiang, 2007; Venugopal et al., 2007; Dyer et al., 2008; Melamed, 2004). We apply weighted deduction much more thoroughly, first extending it to phrase- based models and showing that the set of search strategies used by these models have surprisingly different implications for model and search error (§3, §4). We then show how it can be used to an- alyze common translation problems such as non- local parameterizations (§5), alignment, and novel model design (§6). Finally, we show that it leads to a simple analysis of cube pruning (Chiang, 2007), an important approximate search algorithm (§7). 2 Translation Models A translation model consists of two distinct ele- ments: an unweighted ruleset, and a parameteriza- tion (Lopez, 2008). A ruleset licenses the steps by which a source string f1...fI may be rewritten as a target string e1...eJ, thereby defining the finite set of all possible rewritings of a source string. A parameterization defines a weight function over every sequence of rule applications. In a phrase-based model, the ruleset is simply the unweighted phrase table, where each phrase pair fi...fi′/ej...ej′ states that phrase fi...fi′ in the source is rewritten as ej...ej′ in the the target. The model operates by iteratively applying rewrites to the source sentence until each source word has been consumed by exactly one rule. We call a sequence of rule applications a derivation. A …

Content truncated to 500 words