Incremental Recurrent Neural Network Dependency Parser with Search-based Discriminative Training

Proceedings of the 19th Conference on Computational Language Learning, pages 142–152, Beijing, China, July 30-31, 2015. c⃝2015 Association for Computational Linguistics Incremental Recurrent Neural Network Dependency Parser with Search-based Discriminative Training Majid Yazdani Computer Science Department University of Geneva majid.yazdani@unige.ch James Henderson Xerox Research Center Europe james.henderson@xrce.xerox.com Abstract We propose a discriminatively trained re- current neural network (RNN) that pre- dicts the actions for a fast and accurate shift-reduce dependency parser. The RNN uses its output-dependent model struc- ture to compute hidden vectors that en- code the preceding partial parse, and uses them to estimate probabilities of parser ac- tions. Unlike a similar previous generative model (Henderson and Titov, 2010), the RNN is trained discriminatively to opti- mize a fast beam search. This beam search prunes after each shift action, so we add a correctness probability to each shift ac- tion and train this score to discriminate be- tween correct and incorrect sequences of parser actions. We also speed up pars- ing time by caching computations for fre- quent feature combinations, including dur- ing training, giving us both faster training and a form of backoff smoothing. The re- sulting parser is over 35 times faster than its generative counterpart with nearly the same accuracy, producing state-of-art de- pendency parsing results while requiring minimal feature engineering. 1 Introduction and Motivation There has been significant interest recently in ma- chine learning and natural language processing community in models that learn hidden multi- layer representations to solve various tasks. Neu- ral networks have been popular in this area as a powerful and yet efficient models. For example, feed forward neural networks were used in lan- guage modeling (Bengio et al., 2003; Collobert and Weston, 2008), and recurrent neural networks (RNNs) have yielded state-of-art results in lan- guage modeling (Mikolov et al., 2010), language generation (Sutskever et al., 2011) and language understanding (Yao et al., 2013). 1.1 Neural Network Parsing Neural networks have also been popular in pars- ing. These models can be divided into those whose design are motivated mostly by inducing useful vector representations (e.g. (Socher et al., 2011; Socher et al., 2013; Collobert, 2011)), and those whose design are motivated mostly by ef- ficient inference and decoding (e.g. (Henderson, 2003; Henderson and Titov, 2010; Henderson et al., 2013; Chen and Manning, 2014)). The first group of neural network parsers are all deep models, such as RNNs, which gives them the power to induce vector representations for com- plex linguistic structures without extensive feature engineering. However, decoding in these models can only be done accurately if they are used to re- rank the best parse trees of another parser (Socher et al., 2013). The second group of parsers use a shift-reduce parsing architecture so that they can use search based decoding algorithms with effective pruning strategies. The more accurate parsers also use a RNN architecture (see Section 6), and use gener- ative models to allow beam search. These mod- els are accurate but are relatively slow, and accu- racy degrades when you …

Content truncated to 500 words