Elamur Research⌕
☰
home / papers / 2011 / Analyzing and Integrating Dependency Parsers

Analyzing and Integrating Dependency Parsers

Paper · 2011 · Ryan McDonald and Joakim Nivre

Summary

After the CoNLL shared tasks released treebanks for many languages, research on data-driven dependency parsing grew rapidly. Two families dominated it. Graph-based parsers use global training and exhaustive search over whole trees. Transition-based parsers use locally trained classifiers that greedily choose state-machine actions. Both reached almost the same overall accuracy, so McDonald and Nivre ask whether their errors are also alike. They compare the theoretical properties of each paradigm and run a fine-grained error analysis of MST (graph-based) and Malt (transition-based) on the CoNLL-X datasets. The two parsers turn out to make different, complementary mistakes, and theory predicts them well. Malt's greedy decisions lead to error propagation, which hurts long arcs and arcs near the root. MST is held back by a narrow feature scope. The authors then integrate the parsers through classifier stacking, where one parser's output becomes extra features for the other. Both guided parsers improve consistently, and a second error analysis shows each one absorbing the other's strengths. The work makes a strong case for error analysis grounded in theory.

Key points

  • The 13 CoNLL-X languages include Arabic, Czech, Japanese, Slovene and Turkish. On these, the top graph-based and transition-based systems averaged 80.83 vs. 80.75 labeled accuracy, with no statistically significant difference.
  • The authors explain the differing error profiles as a tradeoff between global learning/inference and rich feature representations.
  • Stacked variants (MST guided by Malt, Malt guided by MST) only require adding new features. MST_Malt was the strongest guided model.
  • MST trains online with MIRA and Malt trains in batch with SVM. This may explain why MST makes heavier use of the guide features.
  • Even MST_Malt falls short of the graph-selection and arc-selection oracles, so further gains remain possible.

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

🏢GoogleMountain View · United States353 works · 364,806 citations🎓Uppsala UniversityUppsala · Sweden56 works · 13,046 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 Ryan McDonald and Joakim Nivre. 2011. Analyzing and Integrating Dependency Parsers. Computational Linguistics.

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

@article{mcdonald2011analyzing,
  title = {{Analyzing and Integrating Dependency Parsers}},
  author = {Ryan McDonald and Joakim Nivre},
  journal = {Computational Linguistics},
  year = {2011},
  doi = {10.1162/coli\_a\_00039},
  url = {https://doi.org/10.1162/coli_a_00039}
}

References

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

  1. Attardi, Giuseppe. 2006. Experiments with a multilanguage non-projective dependency parser. In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL), pages 166–170, New York, NY.
  2. Attardi, Giuseppe and Massimiliano Ciaramita. 2007. Tree revision learning for dependency parsing. In Proceedings of Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL HLT), pages 388–395, Rochester, NY. find
  3. Berger, Adam L., Stephen A. Della Pietra, and Vincent J. Della Pietra. 1996. A maximum entropy approach to natural language processing. Computational Linguistics, 22:39–71.
  4. Buchholz, Sabine and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL), pages 149–164, New York, NY.
  5. Carreras, Xavier. 2007. Experiments with a higher-order projective dependency parser. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 957–961, Prague.
  6. Chang, Chih-Chung and Chih-Jen Lin. 2001. LIBSVM: A Library for Support Vector Machines. Software available at www.csie. ntu.edu.tw/ ∼ cjlin/libsvm. find
  7. Charniak, Eugene. 2000. A maximum-entropy-inspired parser. In Proceedings of the First Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL), pages 132–139, Seattle, WA.
  8. Cheng, Yuchang, Masayuki Asahara, and Yuji Matsumoto. 2006. Multi-lingual dependency parsing at NAIST. In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL), pages 191–195, New York, NY. find
  9. Chu, Yoeng-Jin and Tseng-Hong Liu. 1965. On the shortest arborescence of a directed graph. Scientia Sinica, 14:1396–1400. find
  10. Collins, Michael. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
  11. Collins, Michael. 2000. Discriminative reranking for natural language parsing. In Proceedings of the International Conference on Machine Learning (ICML), pages 175–182, Stanford, CA.
  12. Cortes, Corinna and Vladimir Vapnik. 1995. Support-vector networks. Machine Learning, 20(3):273–297. find
  13. Crammer, Koby, Ofer Dekel, Joseph Keshet, Shai Shalev-Shwartz, and Yoram Singer. 2006. Online passive-aggressive algorithms. The Journal of Machine Learning Research, 7:551–585. find
  14. Ding, Yuan and Martha Palmer. 2004. Synchronous dependency insertion grammars: A grammar formalism for syntax based statistical MT. In Workshop on Recent Advances in Dependency Grammars (COLING), pages 90–97, Geneva. find
  15. Duan, Xiangyu, Jun Zhao, and Bo Xu. 2007. Probabilistic parsing action models for multi-lingual dependency parsing. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 940–946, Prague. find
  16. Edmonds, Jack. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233–240. find
  17. Eisner, Jason M. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of the 16th International Conference on Computational Linguistics (COLING), pages 340–345, Copenhagen.
  18. Florian, Radu, Hany Hassan, Abraham Ittycheriah, Hongyan Jing, Nanda Kambhatla, Xiaoqiang Luo, Nicolas Nicolov, and Salim Roukos. 2004. A statistical model for multilingual entity detection and tracking. In Proceedings of Human Language Technology and the Conference of the North American Chapter of…
  19. Hall, Keith. 2007. K-best spanning tree parsing. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL), pages 392–399, Prague. find
  20. Hall, Johan, Jens Nilsson, Joakim Nivre, Gülsen Eryiğit, 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 of EMNLP-CoNLL 2007, pages 933–939, Prague. find
  21. Henderson, John C. and Eric Brill. 1999. Exploiting diversity in natural language processing: Combining parsers. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 188–194, College Park, MD. find
  22. Hollingshead, Kristy and Brian Roark. 2007. Pipeline iteration. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL), pages 952–959, Prague. find
  23. Huang, Liang and David Chiang. 2005. Better k-best parsing. In Proceedings of the 9th International Workshop on Parsing Technologies (IWPT), pages 53–64, Vancouver. find
  24. Huang, Liang and Kenjie Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1077–1086, Uppsala. find
  25. Hudson, Richard A. 1984. Word Grammar. Blackwell, Oxford. find
  26. Johansson, Richard and Pierre Nugues. 2007. Incremental dependency parsing using online learning. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 1134–1138, Prague. find
  27. Koo, Terry, Amir Globerson, Xavier Carreras, and Michael Collins. 2010. Efficient third-order dependency parsers. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1–11, Uppsala. find
  28. Koo, Terry, Amir Globerson, Xavier Carreras, and Michael Collins. 2007. Structured prediction models via the matrix-tree theorem. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 141–150,… find
  29. Kudo, Taku and Yuji Matsumoto. 2002. Japanese dependency analysis using cascaded chunking. In Proceedings of the Sixth Workshop on Computational Language Learning (CoNLL), pages 63–69, Edmonton. find
  30. Lafferty, John, Andrew McCallum, and Fernando Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedings of the International Conference on Machine Learning (ICML), pages 282–289, Williamstown, MA. find
  31. Marcus, Mitchell P., Beatrice Santorini, and Mary Ann Marcinkiewicz. 1993. Building a large annotated corpus of English: The Penn Treebank. Computational Linguistics, 19:313–330.
  32. Martins, Andre F. T., Dipanjan Das, Noah A. Smith, and Eric P. Xing. 2008. Stacking dependency parsers. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 157–166, Honolulu, HI. find
  33. Martins, Andre F. T., Noah A. Smith, and Eric P. Xing. 2009. Concise integer linear programming formulations for dependency parsing. 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 (AC… find
  34. Maruyama, Hiroshi. 1990. Structural disambiguation with constraint propagation. In Proceedings of the 28th Meeting of the Association for Computational Linguistics (ACL), pages 31–38, Pittsburgh, PA. find
  35. McDonald, Ryan. 2006. Discriminative Learning and Spanning Tree Algorithms for Dependency Parsing. Ph.D. thesis, University of Pennsylvania. find
  36. McDonald, Ryan, 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), pages 91–98, Ann Arbor, MI.
  37. McDonald, Ryan, Kevin Lerman, and Fernando Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL), pages 216–220, New York, NY.
  38. McDonald, Ryan 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.
  39. McDonald, Ryan and Fernando Pereira. 2006. Online learning of approximate dependency parsing algorithms. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 81–88, Trento.
  40. McDonald, Ryan, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of the Human Language Technology Conference and the Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 523–530, Vanco…
  41. McDonald, Ryan and Giorgio Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proceedings of the 10th International Conference on Parsing Technologies (IWPT), pages 122–131, Prague. find
  42. Mel’čuk, Igor. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. find
  43. Nakagawa, Tetsuji. 2007. Multilingual dependency parsing using global features. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 952–956, Prague. find
  44. Nivre, Joakim. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 149–160, Nancy.
  45. Nivre, Joakim. 2007. Incremental non-projective dependency parsing. In Proceedings of Human Language Technologies: The Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL HLT), pages 396–403, Rochester, NY. find
  46. Nivre, Joakim. 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 (ACL-IJCNLP), pages 351–359, Singapore.
  47. Nivre, Joakim, Johan Hall, Sandra Kübler, Ryan McDonald, Jens Nilsson, Sebastian Riedel, and Deniz Yuret. 2007. find
  48. The CoNLL 2007 shared task on dependency parsing. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 915–932, Prague.
  49. Nivre, Joakim, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Proceedings of the 8th Conference on Computational Natural Language Learning, pages 49–56, Boston, MA.
  50. Nivre, Joakim, Johan Hall, Jens Nilsson, Gülsen Eryiğit, and Svetoslav Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL), pages 221–225, New York, NY.
  51. Nivre, Joakim and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics (ACL), pages 950–958, Columbus, OH.
  52. Nivre, Joakim and Jens Nilsson. 2005. Pseudo-projective dependency parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL), pages 99–106, Ann Arbor, MI.
  53. Riedel, Sebastian and James Clarke. 2006. Incremental integer linear programming for non-projective dependency parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 129–137, Sydney. find
  54. Riedel, Sebastian, Ruket Çakıcı, and Ivan Meza-Ruiz. 2006. Multi-lingual dependency parsing with incremental integer linear programming. In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL), pages 226–230, New York, NY. find
  55. Sagae, Kenji and Alon Lavie. 2006. Parser combination by reparsing. In Proceedings of NAACL: Short Papers, pages 129–132, New York, NY.
  56. Sarkar, Anoop. 2001. Applying co-training methods to statistical parsing. In Proceedings of the Second Meeting of the North American Chapter of the Association for Computational Linguistics (NAACL), pages 175–182, Pittsburgh, PA. find
  57. Sgall, Petr, Eva Hajičová, and Jarmila Panevová. 1986. The Meaning of the Sentence in Its Pragmatic Aspects. Reidel, Dordrecht. find
  58. Smith, David A. and Jason Eisner. 2008. Dependency parsing by belief propagation. Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 145–156, Honolulu, HI.
  59. Smith, David A. and Noah A. Smith. 2007. Probabilistic models of nonprojective dependency trees. In Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning (EMNLP-CoNLL), pages 132–140, Prague. find
  60. Snow, Rion, Dan Jurafsky, and Andrew Y. Ng. 2005. Learning syntactic patterns for automatic hypernym discovery. In Advances in Neural Information Processing Systems (NIPS), pages 1297–1304, Vancouver. find
  61. Steedman, Mark, Rebecca Hwa, Miles Osborne, and Anoop Sarkar. 2003. Corrected co-training for statistical parsers. In Proceedings of the International Conference on Machine Learning (ICML), pages 95–102, Washington, DC. find
  62. Tarjan, Robert E. 1977. Finding optimum branchings. Networks, 7:25–35. find
  63. Taskar, Ben, Simon Lacoste-Julien, and Dan Klein. 2005. A discriminative matching approach to word alignment. In Proceedings of the Human Language Technology Conference and the Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP), pages 73–80, Vancouver.
  64. Titov, Ivan and James Henderson. 2007a. Fast and robust multilingual dependency parsing with a generative latent variable model. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 947–951, Prague. find
  65. Titov, Ivan and James Henderson. 2007b. A latent variable model for generative dependency parsing. In Proceedings of the 10th International Conference on Parsing Technologies (IWPT), pages 144–155, Prague. find
  66. Yamada, Hiroyasu and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 195–206, Nancy.
  67. Zeman, Daniel and Zdeněk Žabokrtskỳ. 2005. Improving parsing accuracy by combining diverse dependency parsers. Proceedings of the International Workshop on Parsing Technologies, pages 171–178, Vancouver. find
  68. Zhang, Yue and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing. Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 562–571, Honolulu, HI.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/mcdonald-2011-analyzing-integrating-dependency-parsers/