Mova0.5 pre-release⌕
☰
home / docs / papers / English / Transition-Based Dependency Parsing with Stack Long Short-Term Memory

Transition-Based Dependency Parsing with Stack Long Short-Term Memory

What it is about

The paper introduces the stack LSTM: an LSTM with a stack pointer, so that pushes and pops take constant time and the network keeps a vector summary of the current stack contents. The arc-standard parser keeps three such stacks, for the buffer, for the partial trees (which are composed by a recursive network) and for the action history, so the classifier sees the whole parser state rather than a few words near the top. The model is trained by backpropagation through the whole parse. On the English Penn Treebank with Stanford dependencies it reaches 93.1 UAS and 90.9 LAS on the test set, against 91.8 and 89.6 for the Chen and Manning parser. On Chinese (CTB5) it reaches 87.2 UAS and 85.7 LAS. Ablations show that predicted POS tags add little, and that composed representations of tree fragments beat representations of head words alone (92.2 UAS without composition, against 93.1 with it).

Ideas

For Mova

The ideas touch the feature templates of en/src/parse.rs and the tag input from en/src/ptag.rs. The chapters are languages/en/20-syntax-overview, languages/en/21-clause-structure and languages/en/24-coordination-subordination, where the parser state matters most. Measure first I3, a single run on the existing parser, which says whether tags are worth their cost before any new feature is added.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.3115/v1/p15-1033 · arXiv 1505.08075

@inproceedings{dyer2015transition,
  title = {{Transition-Based Dependency Parsing with Stack Long Short-Term Memory}},
  author = {Dyer, Chris and Ballesteros, Miguel and Ling, Wang and Matthews, Austin and Smith, Noah A.},
  booktitle = {Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)},
  year = {2015},
  doi = {10.3115/v1/p15-1033},
  eprint = {1505.08075},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.3115/v1/p15-1033}
}

References

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

  1. Miguel Ballesteros and Bernd Bohnet. 2014. Automatic feature selection for agenda-based dependency parsing. In Proc. COLING. find
  2. Miguel Ballesteros and Joakim Nivre. 2014. MaltOptimizer: Fast and effective parser optimization. Natural Language Engineering. find
  3. Mohit Bansal, Kevin Gimpel, and Karen Livescu. 2014. Tailoring continuous word representations for dependency parsing. In Proc. ACL. find
  4. Bernd Bohnet and Joakim Nivre. 2012. A transition-based system for joint part-of-speech tagging and labeled non-projective dependency parsing. In Proc. EMNLP. find
  5. Danqi Chen and Christopher D. Manning. 2014. A fast and accurate dependency parser using neural networks. In Proc. EMNLP. find our card
  6. Wenliang Chen, Yue Zhang, and Min Zhang. 2014. Feature embedding for dependency parsing. In Proc. COLING. find
  7. Jinho D. Choi and Andrew McCallum. Transition-based dependency parsing with selectional branching. In Proc. ACL. find
  8. Sreerupa Das, C. Lee Giles, and Guo-Zheng Sun. 1992. Learning context-free grammars: Capabilities and limitations of a recurrent neural network with an external stack memory. In Proc. Cognitive Science Society. find
  9. Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating typed dependency parses from phrase structure parses. In Proc. LREC. find our card
  10. Xavier Glorot and Yoshua Bengio. 2010. Understanding the difficulty of training deep feedforward neural networks. In Proc. ICML. find
  11. Xavier Glorot, Antoine Bordes, and Yoshua Bengio. 2011. Deep sparse rectifier neural networks. In Proc. AISTATS. find
  12. Yoav Goldberg, Kai Zhao, and Liang Huang. 2013. Efficient implementation of beam-search incremental parsers. In Proc. ACL. find
  13. Alex Graves and Jürgen Schmidhuber. 2005. Frame-wise phoneme classification with bidirectional LSTM networks. In Proc. IJCNN. find
  14. Alex Graves, Santiago Fernández, and Jürgen Schmidhuber. 2007. Multi-dimensional recurrent neural networks. In Proc. ICANN. find
  15. Alex Graves, Greg Wayne, and Ivo Danihelka. 2014. Neural Turing machines. CoRR, abs/1410.5401. find
  16. Alex Graves. 2013. Generating sequences with recurrent neural networks. CoRR, abs/1308.0850. find
  17. Edward Grefenstette, Karl Moritz Hermann, Georgiana Dinu, and Phil Blunsom. 2014. New directions in vector space models of meaning. ACL Tutorial. find
  18. James Henderson. 2004. Discriminative training of a neural network discriminative parser. In Proc. ACL. find
  19. Karl Moritz Hermann and Phil Blunsom. 2013. The role of syntax in vector space models of compositional semantics. In Proc. ACL. find
  20. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural Computation, 9(8):1735–1780. find
  21. Liang Huang and David Chiang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proc. ACL. find
  22. Phong Le and Willem Zuidema. 2014. Inside-outside recursive neural network model for dependency parsing. In Proc. EMNLP. find
  23. Wang Ling, Chris Dyer, Alan Black, and Isabel Trancoso. 2015. Two/too simple adaptations of word2vec for syntax problems. In Proc. NAACL. find
  24. André F. T. Martins, Noah A. Smith, Eric P. Xing, Pe-2013. dro M. Q. Aguiar, and Mário A. T. Figueiredo. 2010. Turboparsers: Dependency parsing by approximate variational inference. In Proc. EMNLP. find
  25. Marshall R. Mayberry and Risto Miikkulainen. 1999. S ARD S RN : A neural network shift-reduce parser. In Proc. IJCAI. find
  26. Risto Mikkulainen. 1996. Subsymbolic case-role analysis of sentences with embedded clauses. Cognitive Science, 20:47–73. find
  27. Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013. Distributed representations of words and phrases and their compositionality. In Proc. NIPS. find
  28. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proc. IWPT. find our card
  29. Joakim Nivre. 2004. Incrementality in deterministic dependency parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together. find our card
  30. Joakim Nivre. 2007. Incremental non-projective dependency parsing. In Proc. NAACL. find
  31. Joakim Nivre. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:4:513–553. MIT Press. find our card
  32. Joakim Nivre. 2009. Non-projective dependency parsing in expected linear time. In Proc. ACL. find
  33. Razvan Pascanu, Çaglar Gülçehre, Kyunghyun Cho, and Yoshua Bengio. 2014. How to construct deep recurrent neural networks. In Proc. ICLR. find
  34. Francesco Sartorio, Giorgio Satta, and Joakim Nivre. 2013. A transition-based dependency parser using a dynamic parsing strategy. In Proc. ACL. find
  35. Richard Socher, Eric H. Huang, Jeffrey Pennington, Andrew Y. Ng, and Christopher D. Manning. 2011. Dynamic pooling and unfolding recursive autoencoders for paraphrase detection. In Proc. NIPS. find
  36. Richard Socher, John Bauer, Christopher D. Manning, and Andrew Y. Ng. 2013a. Parsing with compositional vector grammars. In Proc. ACL. find
  37. Richard Socher, Andrej Karpathy, Quoc V. Le, Christopher D. Manning, and Andrew Y. Ng. 2013b. Grounded compositional semantics for finding and describing images with sentences. TACL. find
  38. Richard Socher, Alex Perelygin, Jean Y. Wu, Jason Chuang, Christopher D. Manning, Andrew Y. Ng, and Christopher Potts. 2013c. Recursive deep models for semantic compositionality over a sentiment treebank. In Proc. EMNLP. find
  39. Pontus Stenetorp. 2013. Transition-based dependency parsing using recursive neural networks. In Proc. NIPS Deep Learning Workshop. find
  40. Ilya Sutskever, Oriol Vinyals, and Quoc V. Le. 2014. Sequence to sequence learning with neural networks. In Proc. NIPS. find
  41. Ivan Titov and James Henderson. 2007. Constituent parsing with incremental sigmoid belief networks. In Proc. ACL. find
  42. Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proc. NAACL. find
  43. Huihsin Tseng, Pichuan Chang, Galen Andrew, Daniel Jurafsky, and Christopher Manning. 2005. A conditional random field word segmenter for SIGHAN bakeoff 2005. In Proc. Fourth SIGHAN Workshop on Chinese Language Processing. find
  44. Oriol Vinyals, Lukasz Kaiser, Terry Koo, Slav Petrov, Ilya Sutskever, and Geoffrey Hinton. 2015. Grammar as a foreign language. In Proc. ICLR. find
  45. David Weiss, Christopher Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Proc. ACL. find
  46. Jason Weston, Sumit Chopra, and Antoine Bordes. 2015. Memory networks. In Proc. ICLR. find
  47. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. IWPT. find our card
  48. Wojciech Zaremba and Ilya Sutskever. 2015. Reinforcement learning neural Turing machines. ArXiv e-prints, May. find
  49. Yue Zhang and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing. In Proc. EMNLP. find our card
  50. Yue Zhang and Joakim Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proc. ACL. find
  51. Yuan Zhang, Tao Lei, Regina Barzilay, and Tommi Jaakkola. 2014. Greed is good if randomized: New inference for dependency parsing. In Proc. EMNLP. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/missing-2015-dyer-transition-based-dependency-parsing-stack/