A Transition-Based Dependency Parser Using a Dynamic Parsing Strategy

Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, pages 135–144, Sofia, Bulgaria, August 4-9 2013. c⃝2013 Association for Computational Linguistics A Transition-Based Dependency Parser Using a Dynamic Parsing Strategy Francesco Sartorio Department of Information Engineering University of Padua, Italy sartorio@dei.unipd.it Giorgio Satta Department of Information Engineering University of Padua, Italy satta@dei.unipd.it Joakim Nivre Department of Linguistics and Philology Uppsala University, Sweden joakim.nivre@lingfil.uu.se Abstract We present a novel transition-based, greedy dependency parser which implements a flexible mix of bottom-up and top-down strategies. The new strategy allows the parser to postpone difficult decisions until the relevant information becomes available. The novel parser has a ∼12% error reduc- tion in unlabeled attachment score over an arc-eager parser, with a slow-down factor of 2.8. 1 Introduction Dependency-based methods for syntactic parsing have become increasingly popular during the last decade or so. This development is probably due to many factors, such as the increased availability of dependency treebanks and the perceived use- fulness of dependency structures as an interface to downstream applications, but a very important reason is also the high efficiency offered by de- pendency parsers, enabling web-scale parsing with high throughput. The most efficient parsers are greedy transition-based parsers, which only explore a single derivation for each input and relies on a locally trained classifier for predicting the next parser action given a compact representation of the derivation history, as pioneered by Yamada and Matsumoto (2003), Nivre (2003), Attardi (2006), and others. However, while these parsers are cap- able of processing tens of thousands of tokens per second with the right choice of classifiers, they are also known to perform slightly below the state-of- the-art because of search errors and subsequent error propagation (McDonald and Nivre, 2007), and recent research on transition-based depend- ency parsing has therefore explored different ways of improving their accuracy. The most common approach is to use beam search instead of greedy decoding, in combination with a globally trained model that tries to minim- ize the loss over the entire sentence instead of a locally trained classifier that tries to maximize the accuracy of single decisions (given no previous er- rors), as first proposed by Zhang and Clark (2008). With these methods, transition-based parsers have reached state-of-the-art accuracy for a number of languages (Zhang and Nivre, 2011; Bohnet and Nivre, 2012). However, the drawback with this ap- proach is that parsing speed is proportional to the size of the beam, which means that the most accur- ate transition-based parsers are not nearly as fast as the original greedy transition-based parsers. An- other line of research tries to retain the efficiency of greedy classifier-based parsing by instead improv- ing the way in which classifiers are learned from data. While the classical approach limits training data to parser states that result from oracle predic- tions (derived from a treebank), these novel ap- proaches allow the classifier to explore states that result from its own (sometimes erroneous) predic- tions (Choi and Palmer, 2011; Goldberg and Nivre, 2012). In …

Content truncated to 500 words