Frontier Pruning for Shift-Reduce CCG Parsing

Frontier Pruning for Shift-Reduce CCG Parsing Stephen Merity and James R. Curran School of Information Technologies University of Sydney NSW 2006, Australia {smerity, james}@it.usyd.edu.au Abstract We apply the graph-structured stack (GSS) to shift-reduce parsing in a Combinatory Cate- gorial Grammar (CCG) parser. This allows the shift-reduce parser to explore all possible parses in polynomial time without resorting to heuristics, such as beam search. The GSS- based shift-reduce parser is 34% slower than CKY in the finely-tuned C&C parser. We per- form frontier pruning on the GSS, increasing the parsing speed to be competitive with the C&C parser with a small accuracy penalty. 1 Introduction Parsing is a vital component of sophisticated natu- ral language processing (NLP) systems that require deep and accurate semantic interpretation, including question answering and summarisation. Unfortu- nately, the complexity of natural languages results in substantial ambiguity. For even a typical sentence, thousands of potential analyses may be considered by a wide-coverage parser, making parsing imprac- tical for large-scale applications. Several methods have been proposed to improve parsing speed, including supertagging (Bangalore and Joshi, 1999; Clark and Curran, 2004; Kummer- feld et al., 2010), coarse-to-fine parsing (Charniak and Johnson, 2005; Pauls and Klein, 2009), chart repair (Djordjevic, 2006), chart constraints (Roark and Hollingshead, 2009), structure caching (Daw- born and Curran, 2009) and chart pruning (Zhang et al., 2010). These heuristic methods offer a trade- off between accuracy and speed. A* parsing (Klein and Manning, 2003) offers speed increases with no reduction in accuracy. For parsers optimised for speed, the overhead required by additional efficiency techniques can exceed the speed gains they provide (Dawborn and Curran, 2009). As mistakes made in the parsing phase propagate to later stages, high speed but low accuracy parsers may not be useful in NLP systems (Chang et al., 2006). In this paper, we modify the C&C (Clark and Cur- ran, 2007) Combinatory Categorial Grammar (CCG) parser to enable shift-reduce (SR) parsing. The Cocke-Kasami-Younger (CKY) algorithm (Kasami, 1965; Younger, 1967) is replaced with the shift- reduce algorithm (Aho and Ullman, 1972). How- ever, back-tracking in shift-reduce parsers make them exponential in the worst case. To eliminate this duplication of work, a graph- structured stack (GSS; Tomita, 1988) is employed. This is the equivalent, for shift-reduce parsing, of the chart in CKY parsing, which stores all possible parse states compactly and enables polynomial time worst-case complexity. Due to the incremental na- ture of shift-reduce parsing, we can perform prun- ing of the parse state in the process of considering the next word (the frontier). Our frontier pruning model is an averaged perceptron trained to recognise the highest-scoring derivation that the C&C parser would have selected. By eliminating unlikely derivations , we substantially decrease the amount of ambiguity that the parser is required to handle. The GSS SR parser considers all the derivations that the C&C parser would consider, but is 34% slower. When frontier pruning is applied, incremen- tal parsing speed is improved by 39% relative to the GSS parser with a negligible impact …

Content truncated to 500 words