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.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/v1/d14-1082

@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

29 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Bernd Bohnet. 2010. Very high accuracy and fast dependency parsing is not a contradiction. In Coling. find
2. 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
3. Ronan Collobert. 2011. Deep learning for efficient discriminative parsing. In AISTATS. find
4. Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In LREC. find our card
5. 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
6. John Duchi, Elad Hazan, and Yoram Singer. 2011. Adaptive subgradient methods for online learning and stochastic optimization. The Journal of Machine Learning Research. find
7. 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
8. Nikhil Garg and James Henderson. 2011. Temporal restricted boltzmann machines for dependency parsing. In ACL-HLT. find
9. He He, Hal Daumé III, and Jason Eisner. 2013. Dynamic feature selection for dependency parsing. In EMNLP. find
10. James Henderson. 2004. Discriminative training of a neural network statistical parser. In ACL. find
11. 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
12. Liang Huang, Wenbin Jiang, and Qun Liu. 2009. Bilingually-constrained (monolingual) shift-reduce parsing. In EMNLP. find
13. Richard Johansson and Pierre Nugues. 2007. Extended constituent-to-dependency conversion for english. In Proceedings of NODALIDA, Tartu, Estonia. find our card
14. Lingpeng Kong and Noah A. Smith. 2014. An empirical comparison of parsing methods for Stanford dependencies. CoRR, abs/1404.4314. find our card
15. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In ACL. find
16. Sandra Kübler, Ryan McDonald, and Joakim Nivre. 2009. Dependency Parsing. Synthesis Lectures on Human Language Technologies. Morgan & Claypool. find
17. Marshall R. Mayberry III and Risto Miikkulainen. 1999. Sardsrn: A neural network shift-reduce parser. In IJCAI. find
18. Marshall R. Mayberry III and Risto Miikkulainen. 2005. Broad-coverage parsing with neural networks. Neural Processing Letters. find
19. Ryan McDonald and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In EACL. find our card
20. 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
21. Joakim Nivre, Johan Hall, and Jens Nilsson. 2006. Maltparser: A data-driven parser-generator for dependency parsing. In LREC. find
22. Richard Socher, John Bauer, Christopher D Manning, and Andrew Y Ng. 2013. Parsing with compositional vector grammars. In ACL. find
23. 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
24. Pontus Stenetorp. 2013. Transition-based dependency parsing using recursive neural networks. In NIPS Workshop on Deep Learning. find
25. Ivan Titov and James Henderson. 2007. Fast and robust multilingual dependency parsing with a generative latent variable model. In EMNLP-CoNLL. find
26. 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
27. Laurens van der Maaten and Geoffrey Hinton. 2008. Visualizing data using t-SNE. The Journal of Machine Learning Research. find
28. 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
29. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In ACL. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/missing-2014-chen-fast-accurate-dependency-parser-neural/