Elamur Research⌕
☰
home / papers / 2018 / Seq2seq Dependency Parsing

Seq2seq Dependency Parsing

Paper · 2018 · Zuchao Li, Jiaxun Cai, Shexia He et al.

Summary

Earlier seq2seq dependency parsers did not output trees directly. They generated sequences of transition actions, so a transition algorithm was still needed to build the final structure. Li et al. remove this dependence. Their encoder–decoder model has a BiLSTM encoder and an LSTM decoder with attention. For every token, it outputs the relative offset of that token's head, which keeps every prediction inside the sentence. A separate BiLSTM-CRF tagger then assigns the arc labels. Each token is represented by concatenating:

  • GloVe vectors;
  • Node2Vec vectors pre-trained on the training-set trees;
  • BPE subword embeddings;
  • character embeddings;
  • POS embeddings.

Two decoding aids complete the system. A constrained beam search guarantees a well-formed tree, and a sub-root decomposition splits long sentences into shorter segments to ease long-distance dependencies. On English PTB and Chinese CTB, the parser achieves the best reported results among seq2seq parsers. It also comes close to leading graph- and transition-based systems. The work shows that dependency parsing can be treated as ordinary sequence generation, with no transition system behind it.

Key points

  • Test scores: PTB-SD reaches 94.11% UAS and 92.08% LAS; CTB reaches 88.78% UAS and 86.23% LAS.
  • Target encodings were compared in a basic model without decomposition. Relative head positions reached 89.32% test UAS, compared with 87.49% for transition sequences. A BiLSTM-CRF sequence tagger using the same relative-position targets scored 87.60%.
  • The sub-root tagger scores 96.73% F1 on dev and 96.01% on test. A sentence-length threshold of 40 for decomposition gave the best PTB results.
  • Ablation on PTB-SD shows that removing the tree-constrained beam search hurts most, cutting test LAS from 92.08 to 90.75 and UAS from 94.11 to 93.60. Removing the subword or Node2Vec embeddings causes smaller drops.
  • The authors describe Node2Vec and BPE subword embeddings as additions not previously used in this setting. They also present the parser as the first truly end-to-end seq2seq dependency parser that predicts heads directly.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓Shanghai Jiao Tong UniversityShanghai · China63 works · 15,047 citations

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 9,086 worksArtificial Intelligence · 8,889 worksArts and Humanities · 9,296 worksLanguage and Linguistics · 9,206 works

🧭 Topics 1Research subjects and languages the work is about.Dependency parsing · 120 works

Cite

Cite as Zuchao Li, Jiaxun Cai, Shexia He and Hai Zhao. 2018. Seq2seq Dependency Parsing. Proceedings of the 27th International Conference on Computational Linguistics.

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{li2018seq2seq,
  title = {{Seq2seq Dependency Parsing}},
  author = {Zuchao Li, Jiaxun Cai, Shexia He and Hai Zhao},
  booktitle = {Proceedings of the 27th International Conference on Computational Linguistics},
  year = {2018},
  url = {https://aclanthology.org/C18-1271/}
}

References

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

  1. Daniel Andor, Chris Alberti, David Weiss, Aliaksei Severyn, Alessandro Presta, Kuzman Ganchev, Slav Petrov, and Michael Collins. 2016. Globally normalized transition-based neural networks. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Pape…
  2. Hongxiao Bai and Hai Zhao. 2018. Deep enhanced representation for implicit discourse relation recognition. In Proceedings of the 27th International Conference on Computational Linguistics (COLING 2018).
  3. Deng Cai and Hai Zhao. 2017. Pair-Aware Neural Sentence Modeling for Implicit Discourse Relation Classification. IEA/AIE 2017, Part II, LNAI 10351. find
  4. Jiaxun Cai, Shexia He, Zuchao Li, and Hai Zhao. 2018. A full end-to-end semantic role labeler, syntactic-agnostic or syntactic-aware? In Proceedings of the 27th International Conference on Computational Linguistics (COLING 2018). find
  5. Danqi Chen and Christopher Manning. 2014. A fast and accurate dependency parser using neural networks. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 740–750.
  6. Marie-Catherine De Marneffe, Bill MacCartney, Christopher D Manning, et al. 2006. Generating typed dependency parses from phrase structure parses. In Proceedings of LREC, volume 6, pages 449–454. Genoa Italy.
  7. Timothy Dozat and Christopher D Manning. 2016. Deep biaffine attention for neural dependency parsing. Advances in Neural Information Processing Systems.
  8. Chris Dyer, Miguel Ballesteros, Wang Ling, Austin Matthews, and Noah A. Smith. 2015. Transition-based dependency parsing with stack long short-term memory. pages 334–343.
  9. Jason Eisner. 1996. Efficient normal-form parsing for combinatory categorial grammar. In Proceedings of the 34th annual meeting on Association for Computational Linguistics, pages 79–86. find
  10. Jeffrey L. Elman. 1990. Finding structure in time. Cognitive Science, (2):179–211. find
  11. Matt Gardner, Joel Grus, Mark Neumann, Oyvind Tafjord, Pradeep Dasigi, Nelson F. Liu, Matthew Peters, Michael Schmitz, and Luke S. Zettlemoyer. 2017. Allennlp: A deep semantic natural language processing platform.
  12. Aditya Grover and Jure Leskovec. 2016. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pages 855–864. find
  13. Shexia He, Zuchao Li, Hai Zhao, Hongxiao Bai, and Gongshen Liu. 2018. Syntax for semantic role labeling, to be, or not to be. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL 2018).
  14. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find
  15. Zhiheng Huang, Wei Xu, and Kai Yu. 2015. Bidirectional lstm-crf models for sequence tagging. Computer Science.
  16. Yafang Huang, Zuchao Li, Zhuosheng Zhang, and Hai Zhao. 2018. Moon IME: neural-based chinese pinyin aided input method with customizable association. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (ACL 2018), System Demonstration. find
  17. Eliyahu Kiperwasser and Yoav Goldberg. 2016. Simple and accurate dependency parsing using bidirectional lstm feature representations. Transactions of the Association for Computational Linguistics, 4:313–327.
  18. Guillaume Klein, Yoon Kim, Yuntian Deng, Jean Senellart, and Alexander M. Rush. 2017. Opennmt: Open-source toolkit for neural machine translation. In Proc. ACL.
  19. Adhiguna Kuncoro, Miguel Ballesteros, Lingpeng Kong, Chris Dyer, Graham Neubig, and Noah A Smith. 2016. What do recurrent neural network grammars learn about syntax? arXiv preprint arXiv:1611.05774. find
  20. Haonan Li, Zhisong Zhang, Yuqi Ju, and Hai Zhao. 2018. Neural character-level dependency parsing for Chinese. In The Thirty-Second AAAI Conference on Artificial Intelligence (AAAI-18). find
  21. Thang Luong, Hieu Pham, and Christopher D. Manning. 2015. Effective approaches to attention-based neural machine translation. pages 1412–1421, September.
  22. Xuezhe Ma and Hai Zhao. 2012. Fourth-order dependency parsing. Proceedings of COLING 2012: posters, pages 785–796. find
  23. André FT Martins, Miguel B Almeida, and Noah A Smith. 2013. Turning on the turbo: Fast third-order non-projective turbo parsers.
  24. Ryan Mcdonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Meeting on Association for Computational Linguistics, pages 91–98.
  25. Joakim Nivre and Ryan T. Mcdonald. 2008. Integrating graph-based and transition-based dependency parsers. In ACL 2008, Proceedings of the Meeting of the Association for Computational Linguistics, June 15-20, 2008, Columbus, Ohio, Usa, pages 950–958.
  26. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT).
  27. Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014. Glove: Global vectors for word representation. In Empirical Methods in Natural Language Processing (EMNLP), pages 1532–1543.
  28. Matthew E Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep contextualized word representations. arXiv preprint arXiv:1802.05365.
  29. Lianhui Qin, Zhisong Zhang, Hai Zhao, Zhiting Hu, and Eric P. Xing. 2017. Adversarial connective-exploiting networks for implicit discourse relation classification. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (ACL 2017), pages 1006–1017.
  30. Rico Sennrich, Barry Haddow, and Alexandra Birch. 2015. Neural machine translation of rare words with subword units. Computer Science.
  31. Ilya Sutskever, Oriol Vinyals, and Quoc V Le. 2014. Sequence to sequence learning with neural networks. In Advances in neural information processing systems, pages 3104–3112. find
  32. Kristina Toutanova, Dan Klein, Christopher D Manning, and Yoram Singer. 2003. Feature-rich part-of-speech tagging with a cyclic dependency network. In Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology-Volume…
  33. Wenhui Wang and Baobao Chang. 2016. Graph-based dependency parsing with bidirectional lstm. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), volume 1, pages 2306–2315. find
  34. Hao Wang, Hai Zhao, and Zhisong Zhang. 2017. A transition-based system for universal dependency parsing. In CONLL 2017 Shared Task: Multilingual Parsing From Raw Text To Universal Dependencies (CONLL 2017), pages 191–197. find
  35. David Weiss, Chris Alberti, Michael Collins, and Slav Petrov. 2015. Structured training for neural network transition-based parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (V… find
  36. Sam Wiseman and Alexander M. Rush. 2016. Sequence-to-sequence learning as beam-search optimization. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1296–1306, Austin, Texas, November. find
  37. 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 Proceedings of the Conference on Empirical Methods in Natural Language Processing, pages 562–571. Association for Computational Linguistics.
  38. Hao Zhang and Ryan McDonald. 2012. Generalized higher-order dependency parsing with cube pruning. In Proceedings of the 2012 joint conference on empirical methods in natural language processing and computational natural language learning, pages 320–331. Association for Computational Linguistics. find
  39. Hao Zhang and Ryan McDonald. 2014. Enforcing structural diversity in cube-pruned dependency parsing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), volume 2, pages 656–661. find
  40. Zhisong Zhang, Hai Zhao, and Lianhui Qin. 2016. Probabilistic graph-based dependency parsing with convolutional neural network. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (ACL 2016), pages 1382–1392. find
  41. Xingxing Zhang, Jianpeng Cheng, and Mirella Lapata. 2017a. Dependency parsing as head selection. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers, pages 665–676, Valencia, Spain, April. find
  42. Zhirui Zhang, Shujie Liu, Mu Li, Ming Zhou, and Enhong Chen. 2017b. Stack-based multi-layer attention for transition-based dependency parsing. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 1677–1682, Copenhagen, Denmark, September. find
  43. Zhuosheng Zhang, Jiangtong Li, Pengfei Zhu, and Hai Zhao. 2018. Modeling multi-turn conversation with deep utterance aggregation. In Proceedings of the 27th International Conference on Computational Linguistics (COLING 2018).
  44. Hao Zhou, Yue Zhang, Shujian Huang, and Jiajun Chen. 2015. A neural probabilistic structured-prediction model for transition-based dependency parsing. In Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Lang… find
  45. Chenxi Zhu, Xipeng Qiu, Xinchi Chen, and Xuanjing Huang. 2015. A re-ranking model for dependency parser with recursive convolutional neural network. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/li-2018-seq2seq-dependency-parsing/