Efficient CCG Parsing: A* versus Adaptive Supertagging

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 1577–1585, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Efficient CCG Parsing: A* versus Adaptive Supertagging Michael Auli School of Informatics University of Edinburgh m.auli@sms.ed.ac.uk Adam Lopez HLTCOE Johns Hopkins University alopez@cs.jhu.edu Abstract We present a systematic comparison and com- bination of two orthogonal techniques for efficient parsing of Combinatory Categorial Grammar (CCG). First we consider adap- tive supertagging, a widely used approximate search technique that prunes most lexical cat- egories from the parser’s search space using a separate sequence model. Next we con- sider several variants on A*, a classic exact search technique which to our knowledge has not been applied to more expressive grammar formalisms like CCG. In addition to standard hardware-independent measures of parser ef- fort we also present what we believe is the first evaluation of A* parsing on the more realistic but more stringent metric of CPU time. By it- self, A* substantially reduces parser effort as measured by the number of edges considered during parsing, but we show that for CCG this does not always correspond to improvements in CPU time over a CKY baseline. Combining A* with adaptive supertagging decreases CPU time by 15% for our best model. 1 Introduction Efficient parsing of Combinatorial Categorial Gram- mar (CCG; Steedman, 2000) is a longstanding prob- lem in computational linguistics. Even with practi- cal CCG that are strongly context-free (Fowler and Penn, 2010), parsing can be much harder than with Penn Treebank-style context-free grammars, since the number of nonterminal categories is generally much larger, leading to increased grammar con- stants. Where a typical Penn Treebank grammar may have fewer than 100 nonterminals (Hocken- maier and Steedman, 2002), we found that a CCG grammar derived from CCGbank contained nearly 1600. The same grammar assigns an average of 26 lexical categories per word, resulting in a very large space of possible derivations. The most successful strategy to date for efficient parsing of CCG is to first prune the set of lexi- cal categories considered for each word, using the output of a supertagger, a sequence model over these categories (Bangalore and Joshi, 1999; Clark, 2002). Variations on this approach drive the widely- used, broad coverage C&C parser (Clark and Cur- ran, 2004; Clark and Curran, 2007). However, prun- ing means approximate search: if a lexical category used by the highest probability derivation is pruned, the parser will not find that derivation (§2). Since the supertagger enforces no grammaticality constraints it may even prefer a sequence of lexical categories that cannot be combined into any derivation (Fig- ure 1). Empirically, we show that supertagging im- proves efficiency by an order of magnitude, but the tradeoff is a significant loss in accuracy (§3). Can we improve on this tradeoff? The line of in- vestigation we pursue in this paper is to consider more efficient exact algorithms. In particular, we test different variants of the classical A* algorithm (Hart et al., 1968), which has met …

Content truncated to 500 words