Mova0.5 pre-release⌕
☰
home / docs / papers / English / Integrating Graph-Based and Transition-Based Dependency Parsers in the Deep Contextualized Era

Integrating Graph-Based and Transition-Based Dependency Parsers in the Deep Contextualized Era

What it is about

The paper asks whether combining a graph-based and a transition-based parser still helps once the parsers use BiLSTM encoders and ELMo embeddings. The authors re-implement the Kiperwasser and Goldberg architectures and test two combination methods, blending (arc voting followed by a maximum spanning tree) and feature-based stacking, on several UD treebanks, with LAS on the test sets averaged over six seeds. Their finding is that the remaining diversity between the two models is below the level of two models trained with different seeds, so integration no longer raises accuracy. When both parsers use BiLSTMs, the graph-based one is consistently better, because its globally trained BiLSTM states carry more look-ahead syntactic information. Multi-task learning from the graph-based parser helps the transition-based parser, most of all on treebanks with many right-headed dependencies.

Ideas

For Mova

The parsers are en/src/parse.rs (transition, perceptron) and gparse/src/eisner.rs with the biaffine model (graph). The chapter is 20. Syntax: the Universal Dependencies frame. Measure first the seed spread on EWT test, once per release, since without it no ensemble gain can be claimed.

Topics: Dependency parsing · Treebanks

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.18653/v1/2020.iwpt-1.4

@inproceedings{falenska2020integrating,
  title = {{Integrating Graph-Based and Transition-Based Dependency Parsers in the Deep Contextualized Era}},
  author = {Falenska, Agnieszka and Björkelund, Anders and Kuhn, Jonas},
  booktitle = {Proceedings of the 16th International Conference on Parsing Technologies and the IWPT 2020 Shared Task on Parsing into Enhanced Universal Dependencies},
  year = {2020},
  doi = {10.18653/v1/2020.iwpt-1.4},
  url = {https://doi.org/10.18653/v1/2020.iwpt-1.4}
}

References

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

  1. Giuseppe Attardi and Felice Dell’Orletta. 2009. Reverse Revision and Linear Tree Combination for Dependency Parsing. In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics, Companion Volume: Short Paper… find
  2. Timothy Dozat and Christopher D. Manning. 2016. Deep Biaffine Attention for Neural Dependency Parsing. CoRR, abs/1611.01734. find our card
  3. Anders Björkelund, Agnieszka Falenska, Xiang Yu, and Jonas Kuhn. 2017. IMS at the CoNLL 2017 UD Shared Task: CRFs and Perceptrons Meet Neural Networks. In Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 40–51, Vancouver, Canada. Associa… find our card
  4. Jack Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards B, 71(4):233–240. find
  5. Jason M. Eisner. 1996. Three New Probabilistic Models for Dependency Parsing: An Exploration. In COLING 1996 Volume 1: The 16th International Conference on Computational Linguistics. find our card
  6. Bernd Bohnet and Jonas Kuhn. 2012. The Best of Both Worlds – A Graph-based Completion Model for Transition-based Parsers. In Proceedings of the 13th Conference of the European Chapter of the Association for Computational Linguistics, pages 77– 87, Avignon, France. Association for Computational Lingu… find
  7. Agnieszka Faleńska, Anders Björkelund, Özlem Çetinoğlu, and Wolfgang Seeker. 2015. Stacking or Supertagging for Dependency Parsing – What’s the Difference? In Proceedings of the 14th International Conference on Parsing Technologies, pages 118–129, Bilbao, Spain. Association for Computational Li… find
  8. Richard Caruana. 1993. Multitask Learning: A Knowledge-Based Source of Inductive Bias. In Proceedings of the Tenth International Conference on Machine Learning, pages 41–48. Morgan Kaufmann. find
  9. Agnieszka Falenska and Jonas Kuhn. 2019. The (Non-)Utility of Structural Features in BiLSTM-based Dependency Parsers. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 117–128, Florence, Italy. Association for Computational Linguistics. find
  10. Wanxiang Che, Jiang Guo, Yuxuan Wang, Bo Zheng, Huaipeng Zhao, Yang Liu, Dechuan Teng, and Ting Liu. 2017. The HIT-SCIR System for End-to-End Parsing of Universal Dependencies. In Proceedings of the CoNLL 2017 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 52–62, Va… find
  11. David Gaddy, Mitchell Stern, and Dan Klein. 2018. What’s Going On in Neural Constituency Parsers? An Analysis. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 999–1010. As… find
  12. Wanxiang Che, Yijia Liu, Yuxuan Wang, Bo Zheng, and Ting Liu. 2018. Towards Better UD Parsing: Deep Contextualized Word Embeddings, Ensemble, and Treebank Concatenation. In Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 55–64, Brussels,… find
  13. Yoav Goldberg and Joakim Nivre. 2012. A Dynamic Oracle for Arc-Eager Dependency Parsing. In Proceedings of COLING 2012, pages 959–976, Mumbai, India. find
  14. The COLING 2012 Organizing Committee. find
  15. Yoav Goldberg and Joakim Nivre. 2013. Training Deterministic Parsers with Non-Deterministic Oracles. Transactions of the Association for Computational Linguistics, 1:403–414. find
  16. Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 2779–2795, Hong Kong, China. Association for Computational Linguistics. Carlos Gómez-Rodrı́guez, Iago Alonso-Alonso, and David Vilares. 2017. How Important is Syntactic Parsing Accuracy? An Em… find
  17. Marco Kuhlmann, Carlos Gómez-Rodrı́guez, and Giorgio Satta. 2011. Dynamic programming algorithms for transition-based dependency parsers. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pages 673–682, Portland, Oregon, USA. As… find
  18. Carlos Gómez-Rodrı́guez, Tianze Shi, and Lillian Lee. 2018. Global Transition-based Non-projective Dependency Parsing. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 2664– 2675, Melbourne, Australia. Association for Computat… find
  19. Artur Kulmizev, Miryam de Lhoneux, Johannes Gontrum, Elena Fano, and Joakim Nivre. 2019. Deep Contextualized Word Embeddings in Transition-Based and Graph-Based Dependency Parsing - A Tale of Two Parsers Revisited. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Proces… find
  20. Edouard Grave, Piotr Bojanowski, Prakhar Gupta, Armand Joulin, and Tomas Mikolov. 2018. Learning Word Vectors for 157 Languages. In Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018), Miyazaki, Japan. European Language Resources Association (ELRA). find
  21. Adhiguna Kuncoro, Miguel Ballesteros, Lingpeng Kong, Chris Dyer, and Noah A. Smith. 2016. Distilling an Ensemble of Greedy Dependency Parsers into One MST Parser. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing, pages 1744–1753, Austin, Texas. Association fo… find
  22. Alex Graves and Jürgen Schmidhuber. 2005. Frame-wise Phoneme Classification with Bidirectional LSTM and Other Neural Network Architectures. Neural Networks, 18(5):602–610. find
  23. Johan Hall, Jens Nilsson, Joakim Nivre, Gülsen Eryigit, Beáta Megyesi, Mattias Nilsson, and Markus Saers. 2007. Single Malt or Blended? A Study in Multilingual Parser Optimization. In Proceedings of the CoNLL Shared Task Session of EMNLP-C oNLL 2007, pages 933–939, Prague, Czech Republic. Associat… find
  24. Miryam de Lhoneux, Miguel Ballesteros, and Joakim Nivre. 2019. ”Recursive Subtree Composition in LSTM-Based Dependency Parsing”. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short… find
  25. Sepp Hochreiter and Jürgen Schmidhuber. 1997. Long short-term memory. Neural computation, 9(8):1735–1780. find
  26. KyungTae Lim, Cheoneum Park, Changki Lee, and Thierry Poibeau. 2018. SEx BiST: A Multi-Source Trainable Parser with Deep Contextualized Lexical Representations. In Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 143–152, Brussels, Belgiu… find
  27. Ganesh Jawahar, Benjamin Muller, Amal Fethi, Louis Martin, Éric Villemonte de la Clergerie, Benoı̂t Sagot, and Djamé Seddah. 2018. ELMoLex: Connecting ELMo and Lexicon Features for Dependency Parsing. In Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dep… find
  28. André Filipe Torres Martins, Dipanjan Das, Noah A. Smith, and Eric P. Xing. 2008. Stacking Dependency Parsers. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 157–166, Honolulu, Hawaii. Association for Computational Linguistics. find
  29. 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. find our card
  30. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online Large-Margin Training of Dependency Parsers. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), pages 91–98. Association for Computational Linguistics. find our card
  31. Dan Kondratyuk and Milan Straka. 2019. 75 Languages, 1 Model: Parsing Universal Dependencies Universally. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Linguistics, volume 2: Short Papers, pages 154– 158, Gothenburg, Sweden. Association for Computational Linguistics. find our card
  32. Ryan McDonald and Joakim Nivre. 2007. Characterizing the Errors of Data-Driven Dependency Parsing Models. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 122–131, Prague, Czech Republic.… find our card
  33. Matthew Peters, Mark Neumann, Mohit Iyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. 2018. Deep Contextualized Word Representations. In Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technolog… find
  34. Thomas Mueller, Helmut Schmid, and Hinrich Schütze. 2013. Efficient Higher-Order CRFs for Morphological Tagging. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, pages 322–332. Association for Computational Linguistics. find
  35. Nils Reimers and Iryna Gurevych. 2017. Reporting Score Distributions Makes a Difference: Performance Study of LSTM-networks for Sequence Tagging. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 338–348, Copenhagen, Denmark. Association for Computation… find
  36. Graham Neubig, Chris Dyer, Yoav Goldberg, Austin Matthews, Waleed Ammar, Antonios Anastasopoulos, Miguel Ballesteros, David Chiang, Daniel Clothiaux, Trevor Cohn, Kevin Duh, Manaal Faruqui, Cynthia Gan, Dan Garrette, Yangfeng Ji, Lingpeng Kong, Adhiguna Kuncoro, Gaurav Kumar, Chaitanya Malaviya, Pau… find
  37. Nils Reimers and Iryna Gurevych. 2018. Why Comparing Single Performance Scores Does Not Allow to Draw Conclusions About Machine Learning Approaches. CoRR, abs/1803.09578. — [arXiv:1803.09578](https://arxiv.org/abs/1803.09578) find
  38. Kenji Sagae and Alon Lavie. 2006. Parser Combination by Reparsing. In Proceedings of the Human Language Technology Conference of the NAACL, Companion Volume: Short Papers, pages 129–132, New York City, USA. Association for Computational Linguistics. find
  39. Joakim Nivre. 2003. An Efficient Algorithm for Projective Dependency Parsing. In Proceedings of the Eighth International Workshop on Parsing Technologies (IWPT, pages 149–160, Nancy, France. find our card
  40. Tal Schuster, Ori Ram, Regina Barzilay, and Amir Globerson. 2019. Cross-Lingual Alignment of Contextual Word Embeddings, with Applications to Zero-shot Dependency Parsing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Lang… find
  41. Joakim Nivre. 2009. Non-Projective Dependency Parsing in Expected Linear Time. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP, pages 351–359. Association for Computational Linguistics… find
  42. Joakim Nivre, Mitchell Abrams, Željko Agić, et al. 2019. Universal Dependencies 2.4. LIN-DAT/CLARIN digital library at the Institute of Formal and Applied Linguistics (ÚFAL), Faculty of Mathematics and Physics, Charles University. find
  43. Katrin Schweitzer, Kerstin Eckart, Markus Gärtner, Agnieszka Falenska, Arndt Riester, Ina Rösiger, Antje Schweitzer, Sabrina Stehwien, and Jonas Kuhn. 2018. German Radio Interviews: The GRAIN Release of the SFB732 Silver Standard Collection. In Proceedings of the Eleventh International Conference… find
  44. Joakim Nivre, Marco Kuhlmann, and Johan Hall. 2009. An Improved Oracle for Dependency Parsing with Online Reordering. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT’09), pages 73–76. Association for Computational Linguistics. find
  45. Tianze Shi, Liang Huang, and Lillian Lee. 2017a. Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Set. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 12–23. Association for Computational Lingui… find
  46. Joakim Nivre and Ryan McDonald. 2008. Integrating Graph-Based and Transition-Based Dependency Parsers. In Proceedings of ACL-08: HLT, pages 950–958, Columbus, Ohio. Association for Computational Linguistics. find
  47. Hiroki Ouchi, Kevin Duh, and Yuji Matsumoto. 2014. Improving Dependency Parsers with Supertags. In Proceedings of the 14th Conference of the European Chapter of the Association for Computational Tianze Shi, Felix G. Wu, Xilun Chen, and Yao Cheng. 2017b. Combining Global Models for Parsing Universal… find
  48. Anders Søgaard and Yoav Goldberg. 2016. Deep multi-task learning with low level tasks supervised at lower layers. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pages 231– 235, Berlin, Germany. Association for Computational Lingui… find
  49. Michalina Strzyz, David Vilares, and Carlos Gómez-Rodrı́guez. 2019. Viable Dependency Parsing as Sequence Labeling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pa… find
  50. Mihai Surdeanu and Christopher D. Manning. 2010. Ensemble Models for Dependency Parsing: Cheap and Good? In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pages 649–652, Los Angeles, California. Association for… find
  51. Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical Dependency Analysis with Support Vector Machines. In Proceedings of the Eighth International Conference on Parsing Technologies, pages 195–206, Nancy, France. find our card
  52. Daniel Zeman, Jan Hajič, Martin Popel, Martin Potthast, Milan Straka, Filip Ginter, Joakim Nivre, and Slav Petrov. 2018. find
  53. CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies. In Proceedings of the CoNLL 2018 Shared Task: Multilingual Parsing from Raw Text to Universal Dependencies, pages 1–21, Brussels, Belgium. Association for Computational Linguistics. find our card
  54. Yuan Zhang and David Weiss. 2016. Stack-propagation: Improved Representation Learning for Syntax. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1557–1566, Berlin, Germany. Association for Computational Linguistics. find
  55. Yue Zhang and Stephen Clark. 2008. A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pages 562– 571, Honolulu, Hawaii. Association for Computational Lingui… find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/ud-2020-falenska-integrating-graph-based-transition-based/