LSTM Shift-Reduce CCG Parsing

LSTM Shift-Reduce CCG Parsing Wenduan Xu Computer Laboratory University of Cambridge wx217@cam.ac.uk Abstract We describe a neural shift-reduce parsing model for CCG, factored into four unidirec- tional LSTMs and one bidirectional LSTM. This factorization allows the linearization of the complete parsing history, and results in a highly accurate greedy parser that outper- forms all previous beam-search shift-reduce parsers for CCG. By further deriving a glob- ally optimized model using a task-based loss, we improve over the state of the art by up to 2.67% labeled F1. 1 Introduction Combinatory Categorial Grammar (CCG; Steedman, 2000) parsing is challenging due to its so-called “spurious” ambiguity that permits a large num- ber of non-standard derivations (Vijay-Shanker and Weir, 1993; Kuhlmann and Satta, 2014). To ad- dress this, the de facto models resort to chart-based CKY (Hockenmaier, 2003; Clark and Curran, 2007), despite CCG being naturally compatible with shift- reduce parsing (Ades and Steedman, 1982). More recently, Zhang and Clark (2011) introduced the first shift-reduce model for CCG, which also showed substantial improvements over the long-established state of the art (Clark and Curran, 2007). The success of the shift-reduce model (Zhang and Clark, 2011) can be tied to two main contributing factors. First, without any feature locality restric- tions, it is able to use a much richer feature set; while intensive feature engineering is inevitable, it has nevertheless delivered an effective and concep- tually simpler alternative for both parameter estima- tion and inference. Second, it couples beam search with global optimization (Collins, 2002; Collins and Roark, 2004; Zhang and Clark, 2008), which makes it less prone to search errors than fully greedy mod- els (Huang et al., 2012). In this paper, we present a neural architecture for shift-reduce CCG parsing based on long short-term memories (LSTMs; Hochreiter and Schmidhuber, 1997). Our model is inspired by Dyer et al. (2015), in which we explicitly linearize the complete history of parser states in an incremental fashion by requir- ing no feature engineering (Zhang and Clark, 2011; Xu et al., 2014), and no atomic feature sets (Chen and Manning, 2014). However, a key difference is that we achieve this linearization without relying on any additional control operations or compositional tree structures (Socher et al., 2010; Socher et al., 2011; Socher et al., 2013), both of which are vital in the architecture of Dyer et al. (2015). Crucially, unlike the sequence-to-sequence transduction model of Vinyals et al. (2015), which primarily conditions on the input words, our model is sensitive to all as- pects of the parsing history, including arbitrary po- sitions in the input. As another contribution, we present a global LSTM parsing model by adapting an expected F- measure loss (Xu et al., 2016). As well as natu- rally incorporating beam search during training, this loss optimizes the model towards the final evaluation metric (Goodman, 1996; Smith and Eisner, 2006; Auli and Lopez, 2011b), allowing it to learn shift- reduce action sequences that lead to parses with high expected F-scores. We further show the globally op- timized …

Content truncated to 500 words