Inductive Dependency Parsing

Inductive Dependency Parsing (IDP) is a general framework for robust and efficient syntactic analysis of unrestricted natural language text, developed in the project Stochastic Dependency Grammars for Natural Language Parsing (VR 621-2002-4207). The purpose of this follow-up project is to further investigate the properties of this framework with respect to three dimensions:

Parsing methods: How can parsing algorithms of different complexity be incorporated in the framework and how do they affect performance in terms of accuracy, robustness and efficiency?
Feature models: How can different models of linguistic and contextual features be incorporated and combined with efficient parsing algorithms to achieve optimal disambiguation accuracy?
Learning methods: How can generative and discriminative methods for inductive machine learning be incorporated and combined with parsing algorithms and features models?

The project is funded by the Swedish Research Council (Vetenskapsrådet 2005-4123).

Participants

Joakim Nivre, project leader
Johan Hall, PhD student
Jens Nilsson, PhD student

Resources and Tools

MaltParser (Data-driven dependency parser)
Malt-XML and Malt-TAB (Representation formats for dependency treebanks)
MaltConverter (Conversion between different dependency treebank formats)
Penn2Malt (Conversion from Penn to Malt)
MaltEval (Evaluation and visualization tool for dependency parsing)
Proj (Pre- and post-processing tools for pseudo-projective parsing with MaltParser)
Talbanken05 (Swedish treebank)

Publications

Nivre, J. (2002) Two Models of Stochastic Dependency Grammar. MSI Report 02118. Växjö University: School of Mathematics and Systems Engineering.
Nivre, J. (2003) Optimizing a Deterministic Dependency Parser for Unrestricted Swedish Text. In Proceedings of Promote IT, Gotland University, 3-5 May 2003.
Nivre, J. (2003) An Efficient Algorithm for Projective Dependency Parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT 03), Nancy, France, 23-25 April 2003, pp. 149-160.
Nivre, J. (2004) Inductive Dependency Parsing. MSI Report 04070. Växjö University: School of Mathematics and Systems Engineering.
Nivre, J., Hall, J. and Nilsson, J. (2004) Memory-Based Dependency Parsing. In Ng, H. T. and Riloff, E. (eds.) Proceedings of the Eighth Conference on Computational Natural Language Learning (CoNLL), May 6-7, 2004, Boston, Massachusetts, pp. 49-56.
Nivre, J. and Nilsson, J. (2004) Multiword Units in Syntactic Parsing. In Dias, G., Lopes, J. G. P. and Vintar, S. (eds.) MEMURA 2004 - Methodologies and Evaluation of Multiword Units in Real-World Applications, Workshop at LREC 2004, May 25, 2004, Lisbon, Portugal, pp. 39-46.
Nivre, J. (2004) Bootstrapping Lexical Models in Deterministic Dependency Parsing. MSI rapport 04071. Växjö university: School of Mathematics and Systems Engineering.
Nivre, J. (2004) Incrementality in Deterministic Dependency Parsing. In Incremental Parsing: Bringing Engineering and Cognition Together. Workshop at ACL-2004, Barcelona, Spain, July 25, 2004.
Nivre, J. and Scholz, M. (2004) Deterministic Dependency Parsing of English Text. In Proceedings of COLING 2004, Geneva, Switzerland, August 23-27, 2004.
Nivre, J. (2005) Bootstrapping Lexical Models in Deterministic Dependency Parsing. In Proceedings of Promote IT 2005. Studentlitteratur, pp. 327-336.
Nivre, J. and Nilsson, J. (2005) Pseudo-Projective Dependency Parsing. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL), pp. 99-106.
Nilsson, J., Hall, J. and Nivre, J. (2005) MAMBA Meets TIGER: Reconstructing a Swedish Treebank from Antiquity. In Proceedings from the special session on treebanks at NODALIDA 2005.
Nivre, J. (2005) Two Notions of Parsing. In Arppe, A., Carlson, L., Lindén, K., Piitulainen, J., Suominen, M., Vainio, M., Westerlund, H. and Yli-Jyrä, A. (eds.) Inquiries into Words, Constraints and Contexts. Festschrift in the Honour of Kimmo Koskenniemi on his 60th Birthday. CSLI Publications, 106-115.
Nivre, J. and Hall, J. (2005) MaltParser: A Language-Independent System for Data-Driven Dependency Parsing. In Proceedings of the Fourth Workshop on Treebanks and Linguistic Theories, Barcelona, 9-10 December 2005.
Marinov, S. and Nivre, J. (2005) A Data-Driven Parser for Bulgarian. In Proceedings of the Fourth Workshop on Treebanks and Linguistic Theories, Barcelona, 9-10 December 2005.
Nivre, J. (2006) Two Strategies for Text Parsing. In Suominen, M., Arppe, A., Airola, A., Heinämäki, O., Miestamo, M., Määttä, U., Niemi, J., Pitkänen, K. K. and Sinnemäki, K. (eds.) A Man of Measure: Festschrift in Honour of Fred Karlsson on his 60th Birthday. Turku: The Linguistic Association of Finland.
Nivre, J. (2006) Constraints on Non-Projective Dependency Structures. In Proceedings of EACL.
Nivre, J., Hall, J. and Nilsson, J. (2006) MaltParser: A Data-Driven Parser-Generator for Dependency Parsing. In Proceedings of LREC.
Nivre, J., Nilsson, J. and Hall, J. (2006) Talbanken05: A Swedish Treebank with Phrase Structure and Dependency Annotation. In Proceedings of LREC.
Nivre, J. (2006) Inductive Dependency Parsing. Springer.
Nivre, J., Hall, J., Nilsson, J., Chanev, A., Eryigit, G., Kübler, S., Marinov, S. and Marsi, E. (2007) MaltParser: A language-independent system for data-driven dependency parsing. Natural Language Engineering, 13(2), 95-135.
Nivre, J. (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), 396-403.
Ekeklint, S. and Nivre, J. (2007) A Dependency-Based Conversion of PropBank. In Proceedings of FRAME 2007: Building Frame Semantics Resources for Scandinavian and Baltic Languages, 19-25.
Hall, J., Nivre, J. and Nilsson, J. (2007) A Hybrid Constituency-Dependency Parser for Swedish. In Proceedings of the 16th Nordic Conference on Computational Linguistics (NODALIDA), 284-287.
Nivre, J. (2007) Data-Driven Dependency Parsing across Languages and Domains: Perspectives from the CoNLL 2007 Shared Task. In Proceedings of the Tenth International Conference on Parsing Technologies, 168-170.
Nilsson, J., Nivre, J. and Hall, J. (2007) Tree Transformations for Inductive Dependency Parsing. In Proceedings of the 45th Annual Meeting of the Association for Computational Linguistics, 968-975.
McDonald, R. and Nivre, J. (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), 122-131.
Nivre, J., Hall, J., Kübler, S., McDonald, R., Nilsson, J., Riedel, S. and Yuret, D. (2007) The CoNLL 2007 Shared Task on Dependency Parsing. In Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, 915-932.
Hall, J., Nilsson, J., Nivre, J., Eryigit, G., Megyesi, B., Nilsson, M. and Saers, M. (2007) Single Malt or Blended? A Study in Multilingual Parser Optimization. In Proceedings of the CoNLL Shared Task Session of EMNLP-CoNLL 2007, 933-939.
Øvrelid, L. and Nivre, J. (2007) When word order and part-of-speech tags are not enough - Swedish dependency parsing with rich linguistic features. In Proceedings of the International Conference on Recent Advances in Natural Language Processing (RANLP), 447-451.
Nivre, J. (2007) Dependency Parsing of Spoken Swedish. In Ahlsén, E., Henrichsen, P. J., Hirsch, R., Nivre, J., Abelin, Å, Strömqvist, S., Nicholson, S. and Dorriots, B. (eds.) Communication -- Action -- Meaning. A Festschrift to Jens Allwood. Göteborg University: Department of Linguistics, 203--211.
Nivre, J. (2007) Storage in Deterministic Dependency Parsing. In Borin, L. and Larsson, S. (eds.) From Quantification to Conversation.
Eryigit, G., Nivre, J. and Oflazer, K. (2008) Dependency Parsing of Turkish. Computational Linguistics 34(3), 357--389.
Nivre, J. (2008) Algorithms for Deterministic Incremental Dependency Parsing. Computational Linguistics 34(4), 513-553.
Nilsson, J. and Nivre, J. (2008) MaltEval: An Evaluation and Visualization Tool for Dependency Parsing. In Proceedings of the Sixth International Conference on Language Resources and Evaluation (LREC).
Nivre, J. and McDonald, R. (2008) Integrating Graph-Based and Transition-Based Dependency Parsers. In Proceedings of the 46th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-08: HLT), 950--958.
Hall, J. and Nivre, J. (2008) A Dependency-Driven Parser for German Dependency and Constituency Representations. In Proceedings of the ACL Workshop on Parsing German, 47-54.
Nivre, J., Boguslavsky, I. M. and Iomdin, L. K. (2008) Parsing the SynTagRus Treebank of Russian. In Proceedings of the 22nd International Conference on Computational Linguistics (COLING), 641-648.
Nivre, J. (2008) Sorting Out Dependency Parsing. In Proceedings of the 6th International Conference on Natural Language Processing (GoTAL), 16--27.
Hall, J. and Nivre, J. (2008) Parsing Discontinuous Phrase Structure with Grammatical Functions. In Proceedings of the 6th International Conference on Natural Language Processing (GoTAL), 169-180.
Nilsson, J. and Nivre, J. (2008) Dependency Parsing by Transformation and Combination In Proceedings of the 6th International Conference on Natural Language Processing (GoTAL), 348-359.
Calacean, M. and Nivre, J. (2009). A Data-Driven Dependency Parser for Romanian. In Proceedings the Seventh International Workshop on Treebanks and Linguistic Theories, 65-76.
Fishel, M. and Nivre, J. (2009) Voting and Stacking in Data-Driven Dependency Parsing. I Jokinen, K. and Bick, E. (eds.) Proceedings of the 17th Nordic Conference of Computational Linguistics (NODALIDA).
Nivre, J. (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, 351-359.
Nilsson, J., Löwe, W., Hall, J. and Nivre, J. (2009) Parsing Formal Languages using Natural Language Parsing Techniques. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT), 49-60.
Nivre, J., Kuhlmann, M. and Hall, J. (2009) An Improved Oracle for Dependency Parsing with Online Reordering. In Proceedings of the 11th International Conference on Parsing Technologies (IWPT), 73-76.
Lavelli, A., Hall, J., Nilsson, J. and Nivre, J. (2009) MaltParser at the EVALITA 2009 Dependency Parsing Task. In Proceedings of EVALITA 2009.
Nivre, J. (2009) Parsing Indian Languages with MaltParser. In Proceedings of the ICON09 NLP Tools Contest: Indian Language Dependency Parsing, 12-18.
Hall, J., Nilsson, J. and Nivre, J. (2010) Single Malt or Blended? A Study in Multilingual Parser Optimization. In Bunt, H., Merlo, P. and Nivre, J. (eds.) New Trends in Parsing Technology. Springer.