A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 470–480, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics A Comparison of Loopy Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing 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 Via an oracle experiment, we show that the upper bound on accuracy of a CCG parser is significantly lowered when its search space is pruned using a supertagger, though the su- pertagger also prunes many bad parses. In- spired by this analysis, we design a single model with both supertagging and parsing fea- tures, rather than separating them into dis- tinct models chained together in a pipeline. To overcome the resulting increase in com- plexity, we experiment with both belief prop- agation and dual decomposition approaches to inference, the first empirical comparison of these algorithms that we are aware of on a structured natural language processing prob- lem. On CCGbank we achieve a labelled de- pendency F-measure of 88.8% on gold POS tags, and 86.7% on automatic part-of-speeoch tags, the best reported results for this task. 1 Introduction Accurate and efficient parsing of Combinatorial Cat- egorial Grammar (CCG; Steedman, 2000) is a long- standing problem in computational linguistics, due to the complexities associated its mild context sen- sitivity. Even for practical CCG that are strongly context-free (Fowler and Penn, 2010), parsing is much harder than with Penn Treebank-style context- free grammars, with vast numbers of nonterminal categories leading to increased grammar constants. Where a typical Penn Treebank grammar may have fewer than 100 nonterminals (Hockenmaier and Steedman, 2002), we found that a CCG grammar derived from CCGbank contained over 1500. The same grammar assigns an average of 22 lexical cate- gories per word (Clark and Curran, 2004a), resulting in an enormous space of possible derivations. The most successful approach to CCG parsing is based on a pipeline strategy (§2). First, we tag (or multitag) each word of the sentence with a lexical category using a supertagger, a sequence model over these categories (Bangalore and Joshi, 1999; Clark, 2002). Second, we parse the sentence under the requirement that the lexical categories are fixed to those preferred by the supertagger. Variations on this approach drive the widely-used, broad coverage C&C parser (Clark and Curran, 2004a; Clark and Curran, 2007; Kummerfeld et al., 2010). However, it fails when the supertagger makes errors. We show experimentally that this pipeline significantly lowers the upper bound on parsing accuracy (§3). The same experiment shows that the supertag- ger prunes many bad parses. So, while we want to avoid the error propagation inherent to a pipeline, ideally we still want to benefit from the key insight of supertagging: that a sequence model over lexi- cal categories can be quite accurate. Our solution is to combine the features of both the supertagger and the parser into a single, less aggressively pruned model. The challenge with this model is its pro- hibitive complexity, …

Content truncated to 500 words