Training with Exploration Improves a Greedy Stack LSTM Parser

Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 2005–2010, Austin, Texas, November 1-5, 2016. c⃝2016 Association for Computational Linguistics Training with Exploration Improves a Greedy Stack LSTM Parser Miguel Ballesteros♦ Yoav Goldberg♣ Chris Dyer♠ Noah A. Smith♥ ♦NLP Group, Pompeu Fabra University, Barcelona, Spain ♣Computer Science Department, Bar-Ilan University, Ramat Gan, Israel ♠Google DeepMind, London, UK ♥Computer Science & Engineering, University of Washington, Seattle, WA, USA miguel.ballesteros@upf.edu, yoav.goldberg@gmail.com, cdyer@google.com, nasmith@cs.washington.edu Abstract We adapt the greedy stack LSTM dependency parser of Dyer et al. (2015) to support a training-with-exploration procedure using dy- namic oracles (Goldberg and Nivre, 2013) in- stead of assuming an error-free action his- tory. This form of training, which accounts for model predictions at training time, improves parsing accuracies. We discuss some modifi- cations needed in order to get training with ex- ploration to work well for a probabilistic neu- ral network dependency parser. 1 Introduction Natural language parsing can be formulated as a se- ries of decisions that read words in sequence and in- crementally combine them to form syntactic struc- tures; this formalization is known as transition- based parsing, and is often coupled with a greedy search procedure (Yamada and Matsumoto, 2003; Nivre, 2003; Nivre, 2004; Nivre, 2008). The lit- erature on transition-based parsing is vast, but all works share in common a classification component that takes into account features of the current parser state1 and predicts the next action to take condi- tioned on the state. The state is of unbounded size. Dyer et al. (2015) presented a parser in which the parser’s unbounded state is embedded in a fixed- dimensional continuous space using recurrent neu- ral networks. Coupled with a recursive tree com- position function, the feature representation is able 1The term “state” refers to the collection of previous de- cisions (sometimes called the history), resulting partial struc- tures, which are typically stored in a stack data structure, and the words remaining to be processed. to capture information from the entirety of the state, without resorting to locality assumptions that were common in most other transition-based parsers. The use of a novel stack LSTM data structure allows the parser to maintain a constant time per-state update, and retain an overall linear parsing time. The Dyer et al. parser was trained to maximize the likelihood of gold-standard transition sequences, given words. At test time, the parser makes greedy decisions according to the learned model. Although this setup obtains very good performance, the train- ing and testing conditions are mismatched in the fol- lowing way: at training time the historical context of an action is always derived from the gold standard (i.e., perfectly correct past actions), but at test time, it will be a model prediction. In this work, we adapt the training criterion so as to explore parser states drawn not only from the training data, but also from the model as it is be- ing learned. To do so, we use the method of Gold- berg and Nivre (2012; …

Content truncated to 500 words