Transition-Based Dependency Parsing with Stack Long Short-Term Memory

Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing, pages 334–343, Beijing, China, July 26-31, 2015. c⃝2015 Association for Computational Linguistics Transition-Based Dependency Parsing with Stack Long Short-Term Memory Chris Dyer♣♠ Miguel Ballesteros♦♠ Wang Ling♠ Austin Matthews♠ Noah A. Smith♠ ♣Marianas Labs ♦NLP Group, Pompeu Fabra University ♠Carnegie Mellon University chris@marianaslabs.com, miguel.ballesteros@upf.edu, {lingwang,austinma,nasmith}@cs.cmu.edu Abstract We propose a technique for learning rep- resentations of parser states in transition- based dependency parsers. Our primary innovation is a new control structure for sequence-to-sequence neural networks— the stack LSTM. Like the conventional stack data structures used in transition- based parsing, elements can be pushed to or popped from the top of the stack in constant time, but, in addition, an LSTM maintains a continuous space embedding of the stack contents. This lets us formu- late an efficient parsing model that cap- tures three facets of a parser’s state: (i) unbounded look-ahead into the buffer of incoming words, (ii) the complete history of actions taken by the parser, and (iii) the complete contents of the stack of partially built tree fragments, including their inter- nal structures. Standard backpropagation techniques are used for training and yield state-of-the-art parsing performance. 1 Introduction Transition-based dependency parsing formalizes the parsing problem as a series of decisions that read words sequentially from a buffer and combine them incrementally into syntactic structures (Ya- mada and Matsumoto, 2003; Nivre, 2003; Nivre, 2004). This formalization is attractive since the number of operations required to build any projec- tive parse tree is linear in the length of the sen- tence, making transition-based parsing computa- tionally efficient relative to graph- and grammar- based formalisms. The challenge in transition- based parsing is modeling which action should be taken in each of the unboundedly many states en- countered as the parser progresses. This challenge has been addressed by develop- ment of alternative transition sets that simplify the modeling problem by making better attachment decisions (Nivre, 2007; Nivre, 2008; Nivre, 2009; Choi and McCallum, 2013; Bohnet and Nivre, 2012), through feature engineering (Zhang and Nivre, 2011; Ballesteros and Nivre, 2014; Chen et al., 2014; Ballesteros and Bohnet, 2014) and more recently using neural networks (Chen and Man- ning, 2014; Stenetorp, 2013). We extend this last line of work by learning representations of the parser state that are sensi- tive to the complete contents of the parser’s state: that is, the complete input buffer, the complete history of parser actions, and the complete con- tents of the stack of partially constructed syn- tactic structures. This “global” sensitivity to the state contrasts with previous work in transition- based dependency parsing that uses only a nar- row view of the parsing state when constructing representations (e.g., just the next few incoming words, the head words of the top few positions in the stack, etc.). Although our parser integrates large amounts of information, the representation used for prediction at each time step is constructed incrementally, and therefore parsing and …

Content truncated to 500 words