A Fast and Accurate Dependency Parser using Neural Networks

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 740–750, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics A Fast and Accurate Dependency Parser using Neural Networks Danqi Chen Computer Science Department Stanford University danqi@cs.stanford.edu Christopher D. Manning Computer Science Department Stanford University manning@stanford.edu Abstract Almost all current dependency parsers classify based on millions of sparse indi- cator features. Not only do these features generalize poorly, but the cost of feature computation restricts parsing speed signif- icantly. In this work, we propose a novel way of learning a neural network classifier for use in a greedy, transition-based depen- dency parser. Because this classifier learns and uses just a small number of dense fea- tures, it can work very fast, while achiev- ing an about 2% improvement in unla- beled and labeled attachment scores on both English and Chinese datasets. Con- cretely, our parser is able to parse more than 1000 sentences per second at 92.2% unlabeled attachment score on the English Penn Treebank. 1 Introduction In recent years, enormous parsing success has been achieved by the use of feature-based discrim- inative dependency parsers (K¨ubler et al., 2009). In particular, for practical applications, the speed of the subclass of transition-based dependency parsers has been very appealing. However, these parsers are not perfect. First, from a statistical perspective, these parsers suffer from the use of millions of mainly poorly esti- mated feature weights. While in aggregate both lexicalized features and higher-order interaction term features are very important in improving the performance of these systems, nevertheless, there is insufficient data to correctly weight most such features. For this reason, techniques for introduc- ing higher-support features such as word class fea- tures have also been very successful in improving parsing performance (Koo et al., 2008). Second, almost all existing parsers rely on a manually de- signed set of feature templates, which require a lot of expertise and are usually incomplete. Third, the use of many feature templates cause a less stud- ied problem: in modern dependency parsers, most of the runtime is consumed not by the core pars- ing algorithm but in the feature extraction step (He et al., 2013). For instance, Bohnet (2010) reports that his baseline parser spends 99% of its time do- ing feature extraction, despite that being done in standard efficient ways. In this work, we address all of these problems by using dense features in place of the sparse indi- cator features. This is inspired by the recent suc- cess of distributed word representations in many NLP tasks, e.g., POS tagging (Collobert et al., 2011), machine translation (Devlin et al., 2014), and constituency parsing (Socher et al., 2013). Low-dimensional, dense word embeddings can ef- fectively alleviate sparsity by sharing statistical strength between similar words, and can provide us a good starting point to construct features of words and their interactions. Nevertheless, there remain challenging prob- lems of how to encode all the available infor- mation from the configuration and how to model …

Content truncated to 500 words