Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Set

Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 12–23 Copenhagen, Denmark, September 7–11, 2017. c⃝2017 Association for Computational Linguistics Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Set Tianze Shi Cornell University tianze@cs.cornell.edu Liang Huang Oregon State University liang.huang.sh@gmail.com Lillian Lee Cornell University llee@cs.cornell.edu Abstract We first present a minimal feature set for transition-based dependency parsing, con- tinuing a recent trend started by Kiper- wasser and Goldberg (2016a) and Cross and Huang (2016a) of using bi-directional LSTM features. We plug our minimal feature set into the dynamic-programming framework of Huang and Sagae (2010) and Kuhlmann et al. (2011) to produce the first implementation of worst-case Opn3q exact decoders for arc-hybrid and arc- eager transition systems. With our mini- mal features, we also present Opn3q global training methods. Finally, using ensem- bles including our new parsers, we achieve the best unlabeled attachment score re- ported (to our knowledge) on the Chinese Treebank and the “second-best-in-class” result on the English Penn Treebank. 1 Introduction It used to be the case that the most accurate de- pendency parsers made global decisions and em- ployed exact decoding. But transition-based de- pendency parsers (TBDPs) have recently achieved state-of-the-art performance, despite the fact that for efficiency reasons, they are usually trained to make local, rather than global, decisions and the decoding process is done approximately, rather than exactly (Weiss et al., 2015; Dyer et al., 2015; Andor et al., 2016). The key efficiency issue for decoding is as follows. In order to make accurate (local) attachment decisions, historically, TBDPs have required a large set of features in order to ac- cess rich information about particular positions in the stack and buffer of the current parser configu- ration. But consulting many positions means that although polynomial-time exact-decoding algo- rithms do exist, having been introduced by Huang and Sagae (2010) and Kuhlmann et al. (2011), un- fortunately, they are prohibitively costly in prac- tice, since the number of positions considered can factor into the exponent of the running time. For instance, Huang and Sagae employ a fairly re- duced set of nine positions, but the worst-case run- ning time for the exact-decoding version of their algorithm is Opn6q (originally reported as Opn7q) for a length-n sentence. As an extreme case, Dyer et al. (2015) use an LSTM to summarize arbitrary information on the stack, which completely rules out dynamic programming. andRecently, Kiperwasser and Goldberg (2016a) Cross and Huang (2016a) applied bi- directional long short-term memory networks (Graves and Schmidhuber, 2005, bi-LSTMs) to derive feature representations for parsing, because these networks capture wide-window contextual information well. Collectively, these two sets of authors demonstrated that with bi-LSTMs, four positional features suffice for the arc-hybrid pars- ing system (K&G), and three suffice for arc- standard (C&H).1 Inspired by their work, we arrive at a minimal feature set for arc-hybrid and arc-eager: it con- tains only two positional bi-LSTM vectors, suf- fers almost no loss in performance in comparison to larger …

Content truncated to 500 words