SCFG Decoding Without Binarization

Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 646–655, MIT, Massachusetts, USA, 9-11 October 2010. c⃝2010 Association for Computational Linguistics SCFG Decoding Without Binarization Mark Hopkins and Greg Langmead SDL Language Weaver, Inc. 6060 Center Drive, Suite 150 Los Angeles, CA 90045 {mhopkins,glangmead}@languageweaver.com Abstract Conventional wisdom dictates that syn- chronous context-free grammars (SCFGs) must be converted to Chomsky Normal Form (CNF) to ensure cubic time decoding. For ar- bitrary SCFGs, this is typically accomplished via the synchronous binarization technique of (Zhang et al., 2006). A drawback to this ap- proach is that it inflates the constant factors as- sociated with decoding, and thus the practical running time. (DeNero et al., 2009) tackle this problem by defining a superset of CNF called Lexical Normal Form (LNF), which also sup- ports cubic time decoding under certain im- plicit assumptions. In this paper, we make these assumptions explicit, and in doing so, show that LNF can be further expanded to a broader class of grammars (called “scope- 3”) that also supports cubic-time decoding. By simply pruning non-scope-3 rules from a GHKM-extracted grammar, we obtain better translation performance than synchronous bi- narization. 1 Introduction At the heart of bottom-up chart parsing (Younger, 1967) is the following combinatorial problem. We have a context-free grammar (CFG) rule (for in- stance, S → NP VP PP) and an input sentence of length n (for instance, “on the fast jet ski of mr smith”). During chart parsing, we need to apply the rule to all relevant subspans of the input sentence. See Figure 1. For this particular rule, there are �n+1 4 � application contexts, i.e. ways to choose the sub- spans. Since the asymptotic running time of chart parsing is at least linear in this quantity, it will take on the fast jet ski of mr smith NP VP PP NP VP PP NP VP PP NP VP PP NP VP PP choice point choice point choice point choice point … … Figure 1: A demonstration of application contexts. There are �n+1 4 � application contexts for the CFG rule “S → NP VP PP”, where n is the length of the input sentence. at least O( �n+1 4 � ) = O(n4) time if we include this rule in our grammar. Fortunately, we can take advantage of the fact that any CFG has an equivalent representation in Chom- sky Normal Form (CNF). In CNF, all rules have the form X → Y Z or X → x, where x is a termi- nal and X, Y, Z are nonterminals. If a rule has the form X → Y Z, then there are only �n+1 3 � applica- tion contexts, thus the running time of chart parsing is O( �n+1 3 � ) = O(n3) when applied to CNF gram- mars. A disadvantage to CNF conversion is that it in- creases both the overall number of rules and the overall number of nonterminals. This inflation of the “grammar constant” does not affect …

Content truncated to 500 words