Algorithms for deterministic incremental dependency parsing

Abstract

Parsing algorithms that process the input from left to right and construct a single derivation have often been considered inadequate for natural language parsing because of the massive ambiguity typically found in natural language grammars. Nevertheless, it has been shown that such algorithms, combined with treebank-induced classifiers, can be used to build highly accurate disambiguating parsers, in particular for dependency-based syntactic representations. In this article, we first present a general framework for describing and analyzing algorithms for deterministic incremental dependency parsing, formalized as transition systems. We then describe and analyze two families of such algorithms: stack-based and list-based algorithms. In the former family, which is restricted to projective dependency structures, we describe an arc-eager and an arc-standard variant; in the latter family, we present a projective and a non-projective variant. For each of the four algorithms, we give proofs of correctness and complexity. In addition, we perform an experimental evaluation of all algorithms in combination with SVM classifiers for predicting the next parsing action, using data from thirteen languages. We show that all four algorithms give competitive accuracy, although the non-projective list-based algorithm generally outperforms the projective algorithms for languages with a non-negligible proportion of non-projective constructions. However, the projective algorithms often produce comparable results when combined with the technique known as pseudo-projective parsing. The linear time complexity of the stack-based algorithms gives them an advantage with respect to efficiency both in learning and in parsing, but the projective list-based algorithm turns out to be equally efficient in practice. Moreover, when the projective algorithms are used to implement pseudo-projective parsing, they sometimes become less efficient in parsing (but not in learning) than the non-projective list-based algorithm. Although most of the algorithms have been partially described in the literature before, this is the first comprehensive analysis and evaluation of the algorithms within a unified framework.

References

1. Abney, Steven and Mark Johnson. 1991. Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20:233-250.
2. Aho, Alfred V., Ravi Sethi, and Jeffrey D. Ullman. 1986. Compilers: Principles, Techniques, and Tools. Addison-Wesley, Reading, MA.
3. Attardi, Giuseppe. 2006. Experiments with a multilanguage nonprojective dependency parser. In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL-X), pages 166-170, New York.
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.
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.
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.
8. Cormen, Thomas H., Charles E. Leiserson, and Ronald L. Rivest. 1990. Introduction to Algorithms. MIT Press, Cambridge, MA.
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.
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.
11. Haji¿, Jan, Barbora Vidova Hladka, Jarmila Panevová, Eva Haji¿ová, Petr Sgall, and Petr Pajas. 2001. Prague Dependency Treebank 1.0. LDC, 2001T10.
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.
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.
14. Hudson, Richard A. 1990. English Word Grammar. Blackwell, Oxford.
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.
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.
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.
18. Marcus, Mitchell P. 1980. A Theory of Syntactic Recognition for Natural Language. MIT Press, Cambridge, MA.
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.
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, NJ.
21. Marinov, S. 2007. Covington variations. In Proceedings of the CoNLL Shared Task of EMNLP-CoNLL 2007, pages 1144-1148, Prague.
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.
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.
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.
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.
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, Vancouver.
27. Mel'¿uk, Igor. 1988. Dependency Syntax: Theory and Practice. State University of NewYork Press, New York.
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.
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.
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.
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.
32. Nivre, Joakim. 2006b. Inductive Dependency Parsing. Springer, Dordrecht.
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.
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.
35. Nivre, Joakim, Johan Hall, Jens Nilsson, Atanas Chanev, Gülsen 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.
36. Nivre, Joakim, Johan Hall, Jens Nilsson, Gülsen Eryi¿it, and Svetoslav Marinov. 2006. Labeled pseudoprojective dependency parsing with support vector machines. In Proceedings of the Tenth Conference on Computational Natural Language Learning (CoNLL), pages 221-225, New York, NY.
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.
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.
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.
40. Ratnaparkhi, Adwait. 1999. Learning to parse natural language with maximum entropy models. Machine Learning, 34:151-175.
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.
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.
43. Sgall, Petr, Eva Haji¿ová, and Jarmila Panevová. 1986. The Meaning of the Sentence in Its Pragmatic Aspects. Reidel, Dordrecht.
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.
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.
46. Tesnière, Lucien. 1959. Éléments de syntaxe structurale. Editions Klincksieck, Paris.
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.

Index Terms

• Applied computing

  • Arts and humanities

    • Language translation

• Computing methodologies

  • Artificial intelligence

    • Natural language processing

• Theory of computation

  • Semantics and reasoning

    • Program reasoning

      • Parsing