Mova0.5 pre-release⌕
☰
home / docs / papers / English / Algorithms for Deterministic Incremental Dependency Parsing

Algorithms for Deterministic Incremental Dependency Parsing

What it is about

The paper sets out deterministic incremental dependency parsing as transition systems and analyses four algorithms: two stack-based projective ones (arc-eager and arc-standard) and two list-based ones (a projective and a non-projective variant). For each it gives correctness and complexity proofs. In experiments with SVM classifiers on 13 languages from CoNLL-X, all four give competitive accuracy. The non-projective list-based parser is the most accurate on languages with many non-projective arcs, while pseudo-projective parsing brings the projective algorithms close to it. The average LAS across the algorithms differs by only 0.58 points, and the stack-based ones run in linear time, though the projective list-based one is about as fast in practice.

Ideas

For Mova

The ideas touch en/src/parse.rs, the converters in en/src/convert.rs, and the report of en parse-eval. The chapters are languages/en/20-syntax-overview and languages/en/29-ellipsis-word-order-information-structure, where word order and non-projective arcs matter. Measure first I3, which is a reporting change, and then I2, which tests whether the projective parser can absorb the few non-projective English arcs.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 10.1162/coli.07-056-r1-07-027

@article{nivre2008algorithms,
  title = {{Algorithms for Deterministic Incremental Dependency Parsing}},
  author = {Nivre, Joakim},
  journal = {Computational Linguistics},
  year = {2008},
  doi = {10.1162/coli.07-056-r1-07-027},
  url = {https://doi.org/10.1162/coli.07-056-r1-07-027}
}

References

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

  1. Abney, Steven and Mark Johnson. 1991. Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20:233–250. find
  2. Aho, Alfred V., Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA. find
  3. Attardi, Giuseppe. 2006. Experiments with a multilanguage non-projective dependency parser. In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X), pages 166–170, New York. find
  4. 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 Academic Publishers, Dordrecht, pages 103–127. find
  5. Buchholz, Sabine and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of the Tenth Conference on Computational Natural Language Learning, pages 149–164, New York. find our card
  6. Chang, Chih-Chung and Chih-Jen Lin, 2001. LIBSVM: A Library for Support Vector Machines. Software available at http://www.csie.ntu.edu.tw/∼ cjlin/libsvm. ↗
  7. Cheng, Yuchang, Masayuki Asahara, and Yuji Matsumoto. 2005. Machine learning-based dependency analyzer for Chinese. In Proceedings of International Conference on Chinese Computing (ICCC), pages 66–73, Singapore. find
  8. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA. find
  9. 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
  10. 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. find our card
  11. Hajič, Jan, Barbora Vidova Hladka, Jarmila Panevová, Eva Hajičová, Petr Sgall, and Petr Pajas. 2001. Prague Dependency Treebank 1.0. LDC, 2001T10. find
  12. Hall, J., J. Nilsson, J. Nivre, G. Eryiğit, B. Megyesi, M. Nilsson, and M. 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
  13. Hall, Johan, Joakim Nivre, and Jens Nilsson. 2006. Discriminative classifiers for deterministic dependency parsing. In Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions, pages 316–323, Sydney. find
  14. Hudson, Richard A. 1990. English Word Grammar. Blackwell, Oxford. find
  15. Johansson, Richard and Pierre Nugues. 2006. Investigating multilingual dependency parsing. In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X), pages 206–210, New York. find
  16. Kalt, Tom. 2004. Induction of greedy controllers for deterministic treebank parsers. In Proceedings of the Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 17–24, Barcelona. find
  17. 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, Taipei. find
  18. Marcus, Mitchell P. 1980. A Theory of Syntactic Recognition for Natural Language. MIT Press, Cambridge, MA. find
  19. 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. find our card
  20. 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,… find our card
  21. Marinov, S. 2007. Covington variations. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 1144–1148, Prague. find
  22. 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. find our card
  23. McDonald, Ryan, Kevin Lerman, and Fernando Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL), pages 216–220. find
  24. 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. find our card
  25. 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. find our card
  26. 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… find our card
  27. Mel’čuk, Igor. 1988. Dependency Syntax: Theory and Practice. State University of New York Press, New York. find
  28. Nilsson, Jens, Joakim Nivre, and Johan Hall. 2007. Generalizing tree transformations for inductive dependency parsing. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics (ACL), pages 968–975, Prague. find
  29. 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. find our card
  30. 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. find our card
  31. 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
  32. Nivre, Joakim. 2006b. Inductive Dependency Parsing. Springer, Dordrecht. find
  33. 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
  34. 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. find
  35. Nivre, Joakim, Johan Hall, Jens Nilsson, Atanas Chanev, Gülşen Eryiǧit, Sandra Kübler, Svetoslav Marinov, and Erwin Marsi. 2007. MaltParser: A language-independent system for data-driven dependency parsing. Natural Language Engineering, 13:95–135. find
  36. 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 Tenth Conference on Computational Natural Language Learning (CoNLL), pages 221–225, New York, NY. find
  37. 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. find
  38. Nivre, Joakim and Mario Scholz. 2004. Deterministic dependency parsing of English text. In Proceedings of the 20th International Conference on Computational Linguistics (COLING), pages 64–70, Geneva. find our card
  39. Ratnaparkhi, Adwait. 1997. A linear observed time statistical parser based on maximum entropy models. In Proceedings of the Second Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1–10, Providence, RI. find
  40. Ratnaparkhi, Adwait. 1999. Learning to parse natural language with maximum entropy models. Machine Learning, 34:151–175. find
  41. Sagae, Kenji and Alon Lavie. 2005. A classifier-based parser with linear run-time complexity. In Proceedings of the 9th International Workshop on Parsing Technologies (IWPT), pages 125–132, Vancouver. find
  42. Sagae, Kenji and Alon Lavie. 2006. A best-first probabilistic shift-reduce parser. In Proceedings of the COLING/ACL 2006 Main Conference Poster Sessions, pages 691–698, Sydney. find
  43. Sgall, Petr, Eva Hajičová, and Jarmila Panevová. 1986. The Meaning of the Sentence in Its Pragmatic Aspects. Reidel, Dordrecht. find
  44. Shieber, Stuart M. 1983. Sentence disambiguation by a shift-reduce parsing technique. In Proceedings of the 21st Conference on Association for Computational Linguistics (ACL), pages 113–118, Cambridge, MA. find
  45. 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
  46. Tesnière, Lucien. 1959. Éléments de syntaxe structurale. Editions Klincksieck, Paris. find
  47. 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. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/narrative-2008-nivre-algorithms-deterministic-incremental-dependency-parsing/