Elamur Research⌕
☰
home / papers / 2013 / Divisible Transition Systems and Multiplanar Dependency Parsing

Divisible Transition Systems and Multiplanar Dependency Parsing

Paper · 2013 · Carlos Gómez-Rodríguez and Joakim Nivre

Summary

Transition-based dependency parsers are fast, but the many existing transition systems were described in different formalisms, and efficient handling of non-projective structure remained difficult. Gómez-Rodríguez and Nivre introduce divisible transition systems, a shared stack-based framework in which known projective parsers are built by combining and constraining five basic operations. Within this framework they prove general results on expressivity and complexity. They also identify a subclass, efficient divisible transition systems, that processes planar graphs in linear time, and they design a new parser that covers exactly the planar trees. They then study multiplanarity, Yli-Jyrä's idea of a tree that can be split into k planar subgraphs. They give the first efficient k-planarity test by recasting it as graph coloring and use it to measure coverage across many dependency treebanks, where 2-planar trees fit the data very well. Adding a second stack yields a linear-time 2-planar parser with a correctness proof. It outperforms 1-planar and projective baselines on non-projective data and matches the arc-eager pseudo-projective parser. The work unifies the theory and offers a principled route to mildly non-projective parsing.

Key points

  • The framework rests on five elementary transitions: SHIFT, UNSHIFT, REDUCE, LEFT-ARC and RIGHT-ARC. Several well-known projective parsers turn out to be compositions or restrictions of these.
  • Every divisible system is sound for planar dependency graphs. The "efficient" subclass runs in linear time with greedy inference or beam search.
  • Finding the minimal k for k-planarity reduces to k-coloring an undirected graph. This is tractable for k ≤ 2 and, because non-projective arcs are sparse, also workable in practice for larger k.
  • On available treebanks, 2-planar coverage is at least as good as other mildly non-projective classes, such as bounded gap degree or bounded arc degree. Plain 1-planarity is clearly too restrictive.
  • The two-stack 2-planar parser was evaluated with MaltParser. It gave significant accuracy gains over projective and 1-planar parsers on data with a notable share of non-projective trees. The 1-planar and 2-planar parsers and the multiplanarity test first appeared in Gómez-Rodríguez and Nivre (2010).

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

🎓Uppsala UniversityUppsala · Sweden64 works · 13,164 citations🎓Universidade da CoruñaA Coruña · Spain14 works · 328 citations

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputational Theory and Mathematics · 252 works

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

Cite

Cite as Carlos Gómez-Rodríguez and Joakim Nivre. 2013. Divisible Transition Systems and Multiplanar Dependency Parsing. Computational Linguistics.

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

@article{gomezrodriguez2013divisible,
  title = {{Divisible Transition Systems and Multiplanar Dependency Parsing}},
  author = {Carlos Gómez-Rodríguez and Joakim Nivre},
  journal = {Computational Linguistics},
  year = {2013},
  doi = {10.1162/coli\_a\_00150},
  url = {https://doi.org/10.1162/coli_a_00150}
}

References

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

  1. Afonso, Susana, Eckhard Bick, Renato Haber, and Diana Santos. 2002. “Floresta sintá(c)tica”: A treebank for Portuguese. In Proceedings of the 3rd International Conference on Language Resources and Evaluation (LREC 2002), pages 1,968–1,703, Paris.
  2. Atalay, Nart B., Kemal Oflazer, and Bilge Say. 2003. The annotation process in the Turkish treebank. In Proceedings of EACL Workshop on Linguistically Interpreted Corpora (LINC-03), pages 243–246, Morristown, NJ.
  3. 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.
  4. Bikel, Daniel M. and Vittorio Castelli. 2008. Event matching using the transitive closure of dependency relations. In Proceedings of ACL-08: HLT, Short Papers, pages 145–148, Columbus, OH. find
  5. Bodirsky, Manuel, Marco Kuhlmann, and Mattias Möhl. 2005. Well-nested drawings as models of syntactic structure. In Proceedings of FG-MoL 2005: The 10th Conference on Formal Grammar, pages 195–203, Edinburgh. find
  6. Böhmová, Alena, Jan Hajič, Eva Hajičová, and Barbora Hladká. 2003. The Prague Dependency Treebank: A three-level annotation scenario. In Anne Abeillé, editor, Treebanks: Building and Using Parsed Corpora. Kluwer, pages 103–127. find
  7. Brants, Sabine, Stefanie Dipper, Silvia Hansen, Wolfgang Lezius, and George Smith. 2002. TIGER treebank. In Proceedings of the 1st Workshop on Treebanks and Linguistic Theories (TLT), pages 24–42, Sozopol. find
  8. 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.
  9. Buyko, Ekaterina and Udo Hahn. 2010. Evaluating the impact of alternative dependency graph encodings on solving event extraction tasks. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 982–992, Cambridge, MA. find
  10. 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.
  11. Cohen, Shay B., Carlos Gómez-Rodrı́guez, and Giorgio Satta. 2011. Exact inference for generative probabilistic non-projective dependency parsing. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing (EMNLP 2011), pages 1,234–1,245, Edinburgh. find
  12. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press. find
  13. Covington, Michael A. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the 39th Annual ACM Southeast Conference, pages 95–102, Athens, GA. find
  14. Culotta, Aron and Jeffery Sorensen. 2004. Dependency tree kernels for relation extraction. In Proceedings of the 42nd Annual Meeting of the Association for Computational Linguistics (ACL), pages 423–429, Barcelona.
  15. 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.
  16. Goldberg, Yoav and Michael Elhadad. 2010. An efficient algorithm for easy-first non-directional dependency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL HLT), pages 742–750, Los Angeles, CA. find
  17. Gómez-Rodrı́guez, Carlos, John Carroll, and David Weir. 2011. Dependency parsing schemata and mildly non-projective dependency parsing. Computational Linguistics, 37(3):541–586. find
  18. Gómez-Rodrı́guez, Carlos and Joakim Nivre. 2010. A transition-based parser for 2-planar dependency structures. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1,492–1,501, Uppsala. find
  19. Gómez-Rodrı́guez, Carlos, David Weir, and John Carroll. 2009. Parsing mildly non-projective dependency structures. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 291–299, Athens. find
  20. Hajič, Jan, Jarmila Panevová, Eva Hajičová, Jarmila Panevová, Petr Sgall, Petr Pajas, Jan Štěpánek, Jiřı́ Havelka, and Marie Mikulová. 2006. Prague Dependency Treebank 2.0. CDROM CAT: LDC2006T01, ISBN 1-58563-370-4. Linguistic Data Consortium. find
  21. Hajič, Jan, Otakar Smrž, Petr Zemánek, Jan Šnaidauf, and Emanuel Beška. 2004. Prague Arabic Dependency Treebank: Development in data and tools. In Proceedings of the NEMLAR International Conference on Arabic Language Resources and Tools, pages 110–117, Cairo. find
  22. Hajič, Jan, Barbora Vidova Hladka, Jarmila Panevová, Eva Hajičová, Petr Sgall, and Petr Pajas. 2001. Prague Dependency Treebank 1.0. LDC, 2001T10. find
  23. Havelka, Jiri. 2007. Beyond projectivity: Multilingual evaluation of constraints and measures on non-projective structures. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 608–615, Prague. find
  24. Huang, Liang, Wenbin Jiang, and Qun Liu. 2009. Bilingually-constrained (monolingual) shift-reduce parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1,222–1,231, Suntec. find
  25. Huang, Liang and Kenji Sagae. 2010. Dynamic programming for linear-time incremental parsing. In Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics (ACL), pages 1,077–1,086, Uppsala. find
  26. Hudson, Richard A. 1990. English Word Grammar. Blackwell. find
  27. Johansson, Richard and Pierre Nugues. 2006. Investigating multilingual dependency parsing. In Proceedings of the 10th Conference on Computational Natural Language Learning (CoNLL), pages 206–210, New York, NY. find
  28. Kahane, Sylvain, Alexis Nasr, and Owen Rambow. 1998. Pseudo-projectivity: A polynomially parsable non-projective dependency grammar. In Proceedings of the 36th Annual Meeting of the Association for Computational Linguistics (ACL) and the 17th International Conference on Computational Linguistics (CO… find
  29. Karp, Richard M. 1972. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Complexity of Computer Computations. Plenum Press, pages 85–103. find
  30. Koo, Terry 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
  31. Koo, Terry, Alexander M. Rush, Michael Collins, Tommi Jaakkola, and David Sontag. 2010. Dual decomposition for parsing with non-projective head automata. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 1,288–1,298, Cambridge, MA.
  32. Kromann, Matthias Trautner. 2003. The Danish Dependency Treebank and the DTAG treebank tool. In Proceedings of the 2nd Workshop on Treebanks and Linguistic Theories (TLT), pages 217–220, Växjö. find
  33. Kuhlmann, Marco. 2010. Dependency Structures and Lexicalized Grammars: An Algebraic Approach, volume 6270 of Lecture Notes in Computer Science. Springer. find
  34. Kuhlmann, Marco, 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 (ACL), pages 673–682, Portland, OR. find
  35. Kuhlmann, Marco and Mathias Möhl. 2007. Mildly context-sensitive dependency languages. In Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics, pages 160–167, Prague. find
  36. Kuhlmann, Marco and Joakim Nivre. 2006. Mildly non-projective dependency structures. In Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions, pages 507–514, Sydney. find
  37. Kuhlmann, Marco and Giorgio Satta. 2009. Treebank grammar techniques for non-projective dependency parsing. In Proceedings of the 12th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 478–486, Athens. find
  38. Maier, Wolfgang and Timm Lichte. 2009. Characterizing discontinuity in constituent treebanks. In Proceedings of the 14th Conference on Formal Grammar, pages 164–179, Opole. find
  39. 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.
  40. Marcus, Mitchell P., Beatrice Santorini, Mary Ann Marcinkiewicz, Robert MacIntyre, Ann Bies, Mark Ferguson, Karen Katz, and Britta Schasberger. 1994. The Penn Treebank: Annotating predicate-argument structure. In Proceedings of the ARPA Human Language Technology Workshop, pages 114–119, Plainsboro,…
  41. Martins, Andre, Noah Smith, and Eric 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 (ACL-IJCNLP), p… find
  42. Martins, Andre, Noah Smith, Eric Xing, Pedro Aguiar, and Mario Figueiredo. 2010. Turbo parsers: Dependency parsing by approximate variational inference. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 34–44, Cambridge, MA.
  43. 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.
  44. 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.
  45. 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.
  46. 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
  47. Mel’čuk, Igor. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. find
  48. 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
  49. Nilsson, Jens, Johan Hall, and Joakim Nivre. 2005. MAMBA meets TIGER: Reconstructing a Swedish treebank from Antiquity. In Proceedings of the NODALIDA Special Session on Treebanks, pages 121–132, Joensuu. find
  50. 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.
  51. Nivre, Joakim. 2004. Incrementality in deterministic dependency parsing. In Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together (ACL), pages 50–57, Barcelona.
  52. Nivre, Joakim. 2006a. Constraints on non-projective dependency graphs. In Proceedings of the 11th Conference of the European Chapter of the Association for Computational Linguistics (EACL), pages 73–80, Trento. find
  53. Nivre, Joakim. 2006b. Inductive Dependency Parsing. Springer. find
  54. 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
  55. Nivre, Joakim. 2008. Algorithms for deterministic incremental dependency parsing. Computational Linguistics, 34:513–553.
  56. 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, Suntec.
  57. Nivre, Joakim, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Proceedings of the 8th Conference on Computational Natural Language Learning (CoNLL), pages 49–56, Boston, MA.
  58. Nivre, Joakim, Johan Hall, and Jens Nilsson. 2006. Maltparser: A data-driven parser-generator for dependency parsing. In Proceedings of the 5th International Conference on Language Resources and Evaluation (LREC), pages 2,216–2,219, Genoa.
  59. 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.
  60. 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.
  61. Oflazer, Kemal, Bilge Say, Dilek Zeynep Hakkani-Tür, and Gökhan Tür. 2003. Building a Turkish treebank. In Anne Abeillé, editor, Treebanks: Building and Using Parsed Corpora. Kluwer, pages 261–277. find
  62. Quirk, Chris, Arul Menezes, and Colin Cherry. 2005. Dependency treelet translation: Syntactically informed phrasal SMT. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL), pages 271–279, Ann Arbor, MI.
  63. 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
  64. Sagae, Kenji and Jun’ichi Tsujii. 2008. Shift-reduce dependency DAG parsing. In Proceedings of the 22nd International Conference on Computational Linguistics (COLING), pages 753–760, Manchester.
  65. Sgall, Petr, Eva Hajičová, and Jarmila Panevová. 1986. The Meaning of the Sentence in Its Pragmatic Aspects. Reidel. find
  66. Shen, Dan and Dietrich Klakow. 2006. Exploring correlation of dependency relation paths for answer extraction. In Proceedings of the 21st International Conference on Computational Linguistics and the 44th Annual Meeting of the Association for Computational Linguistics, pages 889–896, Sydney. find
  67. Shieber, Stuart M., Yves Schabes, and Fernando C. N. Pereira. 1995. Principles and implementation of deductive parsing. Journal of Logic Programming, 24:3–36. find
  68. Smith, David and Jason Eisner. 2008. Dependency parsing by belief propagation. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 145–156, Waikiki, HI.
  69. Stevenson, Mark and Mark A. Greenwood. 2006. Comparing information extraction pattern models. In Proceedings of the Workshop on Information Extraction Beyond The Document, pages 12–19, Sydney. find
  70. Tesnière, Lucien. 1959. Éléments de syntaxe structurale. Editions Klincksieck. find
  71. Titov, Ivan and James Henderson. 2007. A latent variable model for generative dependency parsing. In Proceedings of the 10th International Conference on Parsing Technologies (IWPT), pages 144–155, Prague. find
  72. Tratz, Stephen and Eduard Hovy. 2011. A fast, accurate, non-projective, semantically-enriched parser. In Proceedings of the 2011 Conference on Empirical Methods in Natural Language Processing, pages 1,257–1,268, Edinburgh. find
  73. Van der Beek, Leonoor, Gosse Bouma, Robert Malouf, and Gertjan Van Noord. 2002. The Alpino dependency treebank. In Mariet Theune, Anton Nijholt, and Hendri Hondorp, editors, Language and Computers, Computational Linguistics in the Netherlands 2001. Selected Papers from the Twelfth CLIN Meeting, page… find
  74. Xu, Peng, Jaeho Kang, Michael Ringgaard, and Franz Och. 2009. Using a dependency parser to improve SMT for subject-object-verb languages. In Proceedings of Human Language Technologies: The 2009 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL HL…
  75. 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.
  76. Yli-Jyrä, Anssi. 2003. Multiplanarity— a model for dependency structures in treebanks. In Proceedings of the 2nd Workshop on Treebanks and Linguistic Theories (TLT), pages 189–200, Växjö. find
  77. Zhang, Yue and Stephen Clark. 2008. A tale of two parsers: Investigating and combining graph-based and transition-based dependency parsing. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 562–571, Waikiki, HI.
  78. Zhang, Yue and Joakim Nivre. 2011. Transition-based parsing with rich non-local features. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL), pages 188–193, Portland, OR. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/rodriguez-2013-divisible-transition-systems-multiplanar-dependency/