A Fast and Accurate Dependency Parser using Neural Networks
What it is about
Almost all parsers of the time used millions of sparse indicator features built from hand-made templates, which generalise poorly and make feature extraction the main cost. This paper proposes a greedy arc-standard parser whose decisions come from a small feedforward network over dense, learned embeddings of words, POS tags and arc labels taken from the stack top, the buffer front and their children. The network uses only about 200 learned dense features, and a cube activation to capture interactions between them. It parses over 1000 sentences per second and reaches 92.2% UAS on the English Penn Treebank, with gains on Chinese too. The ablation study shows that lexicalised features and word-pair features of the top stack items carry most of the signal in the old sparse set.
Ideas
- I1. en/src/parse.rs: add a from-scratch dense scorer (embeddings for the same stack and buffer slots, a small MLP with cube activation, trained inside the parser) as an extra score beside the perceptron, and measure LAS on EWT dev and sentences per second on CPU through
en parse-eval. - I2. en/src/parse.rs: ablate the stack and buffer slots one class at a time (words, tags, labels, children) and measure the LAS loss on EWT dev, to find which of the feature classes the perceptron actually needs.
- I3. en/src/parse.rs: compare the cube activation with tanh in the dense scorer of I1 on EWT dev, twice, to check that the choice of activation, not the size, makes the difference.
For Mova
The ideas touch the scorer in en/src/parse.rs and its feature slots, and they respect the rule that the weights come from scratch on training data only. The chapters are languages/en/10-word-classes (the POS features) and languages/en/20-syntax-overview. Measure first I2, which uses only the current feature templates, and then I1 under the speed budget that this paper sets.
Library summary
Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/D14-1082.pdf
Summary
Greedy transition-based dependency parsers are fast, but their classifiers usually rely on millions of hand-designed sparse indicator features. These features are poorly estimated because of data sparsity, never cover every useful combination, and are expensive to compute. In the authors' measurements, building features consumed over 95% of parsing time. Chen and Manning replace this machinery with a small feed-forward neural network that selects transitions in the arc-standard system. Words, POS tags and arc labels from selected stack and buffer positions are each mapped to learned dense embeddings and concatenated. They then pass through one hidden layer with a new cube activation, g(x)=x³, which directly captures products of three input elements, followed by a softmax over transitions. The parser was evaluated on English (Penn Treebank, with CoNLL and Stanford dependencies) and Chinese (CTB). It raised unlabeled and labeled attachment scores by roughly 2% over sparse-feature greedy baselines while also running faster. The work shows that compact representations learned inside the parsing task can outperform manual feature engineering. It became an influential blueprint for later neural parsers.
Key points
- Reaches 92.2% UAS on the English Penn Treebank while processing more than 1000 sentences per second.
- Uses only 200 hidden units ("dense features"), compared with millions of sparse features in conventional parsers. Inspection of the weights shows these units learn plausible feature conjunctions, some involving more than three elements.
- Introduces embeddings for POS tags and arc labels in addition to word embeddings. The authors present this as the first such attempt, and t-SNE plots show linguistically similar tags and labels clustering together.
- The cube activation outperformed tanh, sigmoid and identity in the reported ablations. Pre-trained word vectors also helped compared with random initialization.
- A motivating analysis on PTB (CoNLL representation) shows the cost of dropping lexicalized features from a sparse model: UAS falls from 88.0 to 81.5. Bohnet (2010) is cited as reporting that 99% of his baseline parser's runtime went to feature extraction.
Cite
@inproceedings{chen2014fast,
title = {{A Fast and Accurate Dependency Parser using Neural Networks}},
author = {Chen, Danqi and Manning, Christopher},
booktitle = {Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP)},
year = {2014},
doi = {10.3115/v1/d14-1082},
url = {https://doi.org/10.3115/v1/d14-1082}
}References
- Bernd Bohnet. 2010. Very high accuracy and fast dependency parsing is not a contradiction. In Coling. find our card
- Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa. 2011. Natural language processing (almost) from scratch. Journal of Machine Learning Research. find our card
- Ronan Collobert. 2011. Deep learning for efficient discriminative parsing. In AISTATS. find
- Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In LREC. find our card
- Jacob Devlin, Rabih Zbib, Zhongqiang Huang, Thomas Lamar, Richard Schwartz, and John Makhoul. 2014. Fast and robust neural network joint models for statistical machine translation. In ACL. find
- John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research. find
- Rong-En Fan, Kai-Wei Chang, Cho-Jui Hsieh, Xiang-Rui Wang, and Chih-Jen Lin. 2008. Liblinear: A library for large linear classification. The Journal of Machine Learning Research. find
- Nikhil Garg and James Henderson. 2011. Temporal restricted boltzmann machines for dependency parsing. In ACL-HLT. find
- He He, Hal Daumé III, and Jason Eisner. 2013. Dynamic feature selection for dependency parsing. In EMNLP. find
- James Henderson. 2004. Discriminative training of a neural network statistical parser. In ACL. find
- Geoffrey E. Hinton, Nitish Srivastava, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. 2012. Improving neural networks by preventing co-adaptation of feature detectors. CoRR, abs/1207.0580. find
- Liang Huang, Wenbin Jiang, and Qun Liu. 2009. Bilingually-constrained (monolingual) shift-reduce parsing. In EMNLP. find
- Richard Johansson and Pierre Nugues. 2007. Extended constituent-to-dependency conversion for english. In Proceedings of NODALIDA, Tartu, Estonia. find our card
- Lingpeng Kong and Noah A. Smith. 2014. An empirical comparison of parsing methods for Stanford dependencies. CoRR, abs/1404.4314. find our card
- Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In ACL. find our card
- Sandra Kübler, Ryan McDonald, and Joakim Nivre. 2009. Dependency Parsing. Synthesis Lectures on Human Language Technologies. Morgan & Claypool. find
- Marshall R. Mayberry III and Risto Miikkulainen. 1999. Sardsrn: A neural network shift-reduce parser. In IJCAI. find
- Marshall R. Mayberry III and Risto Miikkulainen. 2005. Broad-coverage parsing with neural networks. Neural Processing Letters. find
- Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In EACL. find our card
- Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In NIPS. find
- Joakim Nivre, Johan Hall, and Jens Nilsson. 2006. Maltparser: A data-driven parser-generator for dependency parsing. In LREC. find
- Richard Socher, John Bauer, Christopher D Manning, and Andrew Y Ng. 2013. Parsing with compositional vector grammars. In ACL. find
- Richard Socher, Andrej Karpathy, Quoc V. Le, Christopher D. Manning, and Andrew Y. Ng. 2014. Grounded compositional semantics for finding and describing images with sentences. TACL. find our card
- Pontus Stenetorp. 2013. Transition-based dependency parsing using recursive neural networks. In NIPS Workshop on Deep Learning. find
- Ivan Titov and James Henderson. 2007. Fast and robust multilingual dependency parsing with a generative latent variable model. In EMNLP-CoNLL. find
- Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In NAACL. find
- Laurens van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE. The Journal of Machine Learning Research. find
- Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing using beam-search. In EMNLP. find our card
- Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In ACL. find