Shift-Reduce CCG Parsing

Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics, pages 683–692, Portland, Oregon, June 19-24, 2011. c⃝2011 Association for Computational Linguistics Shift-Reduce CCG Parsing Yue Zhang University of Cambridge Computer Laboratory yue.zhang@cl.cam.ac.uk Stephen Clark University of Cambridge Computer Laboratory stephen.clark@cl.cam.ac.uk Abstract CCGs are directly compatible with binary- branching bottom-up parsing algorithms, in particular CKY and shift-reduce algorithms. While the chart-based approach has been the dominant approach for CCG, the shift-reduce method has been little explored. In this paper, we develop a shift-reduce CCG parser using a discriminative model and beam search, and compare its strengths and weaknesses with the chart-based C&C parser. We study different errors made by the two parsers, and show that the shift-reduce parser gives competitive accu- racies compared to C&C. Considering our use of a small beam, and given the high ambigu- ity levels in an automatically-extracted gram- mar and the amount of information in the CCG lexical categories which form the shift actions, this is a surprising result. 1 Introduction Combinatory Categorial Grammar (CCG; Steedman (2000)) is a lexicalised theory of grammar which has been successfully applied to a range of problems in NLP, including treebank creation (Hockenmaier and Steedman, 2007), syntactic parsing (Hockenmaier, 2003; Clark and Curran, 2007), logical form con- struction (Bos et al., 2004) and surface realization (White and Rajkumar, 2009). From a parsing per- spective, the C&C parser (Clark and Curran, 2007) has been shown to be competitive with state-of-the- art statistical parsers on a variety of test suites, in- cluding those consisting of grammatical relations (Clark and Curran, 2007), Penn Treebank phrase- structure trees (Clark and Curran, 2009), and un- bounded dependencies (Rimell et al., 2009). The binary branching nature of CCG means that it is naturally compatible with bottom-up parsing al- gorithms such as shift-reduce and CKY (Ades and Steedman, 1982; Steedman, 2000). However, the parsing work by Clark and Curran (2007), and also Hockenmaier (2003) and Fowler and Penn (2010), has only considered chart-parsing. In this paper we fill a gap in the CCG literature by developing a shift- reduce parser for CCG. Shift-reduce parsers have become popular for de- pendency parsing, building on the initial work of Ya- mada and Matsumoto (2003) and Nivre and Scholz (2004). One advantage of shift-reduce parsers is that the scoring model can be defined over actions, al- lowing highly efficient parsing by using a greedy algorithm in which the highest scoring action (or a small number of possible actions) is taken at each step. In addition, high accuracy can be maintained by using a model which utilises a rich set of features for making each local decision (Nivre et al., 2006). Following recent work applying global discrim- inative models to large-scale structured prediction problems (Collins and Roark, 2004; Miyao and Tsujii, 2005; Clark and Curran, 2007; Finkel et al., 2008), we build our shift-reduce parser using a global linear model, and compare it with the chart- based C&C parser. Using standard development and test sets from CCGbank, our …

Content truncated to 500 words