MaltParser

Introduction

MaltParser is a system for data-driven dependency parsing, which can be used to induce a parsing model from treebank data and to parse new data using an induced model. MaltParser is developed by Johan Hall, Jens Nilsson and Joakim Nivre at Växjö University and Uppsala University, Sweden.

MaltParser 1.0.0 and later releases constitute a complete reimplementation of MaltParser in Java and are distributed with an open source license. The previous versions 0.1-0.4 of MaltParser were implemented in C. The Java implementation (version 1.0.0 and later releases) replaces the C implementation (version 0.x) and MaltParser 0.x will not be supported and updated any more.

Inductive Dependency Parsing

MaltParser can be characterized as a data-driven parser-generator. While a traditional parser-generator constructs a parser given a grammar, a data-driven parser-generator constructs a parser given a treebank. MaltParser is an implementation of inductive dependency parsing, where the syntactic analysis of a sentence amounts to the derivation of a dependency structure, and where inductive machine learning is used to guide the parser at nondeterministic choice points (Nivre, 2006). The parsing methodology is based on three essential components:

1. Deterministic parsing algorithms for building labeled dependency graphs (Kudo and Matsumoto,2002; Yamada and Matsumoto, 2003; Nivre,2003)
2. History-based models for predicting the next parser action at nondeterministic choice points (Black et al., 1992; Magerman, 1995; Ratnaparkhi, 1997; Collins, 1999)
3. Discriminative learning to map histories to parser actions (Kudo and Matsumoto, 2002; Yamada and Matsumoto, 2003; Nivre et al., 2004; Hall et al., 2006)

MaltParser 1.9.2

MaltParser implements nine deterministic parsing algorithms:

• Nivre arc-eager
• Nivre arc-standard
• Covington non-projective
• Covington projective
• Stack projective
• Stack swap-eager
• Stack swap-lazy
• Planar (implemented by Carlos Gómez-Rodríguez)
• 2-planar (implemented by Carlos Gómez-Rodríguez)

MaltParser allows users to define feature models of arbitrary complexity.

MaltParser currently includes two machine learning packages (thanks to Sofia Cassel for her work on LIBLINEAR):

• LIBSVM - A Library for Support Vector Machines (Chang, 2001).
• LIBLINEAR -- A Library for Large Linear Classification (Fan et al., 2008).

MaltParser can also be turned into a phrase structure parser that recovers both continuous and discontinuous phrases with both phrase labels and grammatical functions (Hall and Nivre, 2008a; Hall and Nivre, 2008b).

References

• Black, E., F. Jelinek, J. D. Lafferty, D. M. Magerman, R. L. Mercer and S. Roukos (1992). Towards history-based grammars: Using richer models for probabilistic parsing. In Proceedings of the 5th DARPA Speech and Natural Language Workshop, pp. 31-37
• Chang, C.-C. and C.-J. Lin (2001). LIBSVM: A Library for Support Vector Machines. [pdf]
• Collins, M. (1999). Head-Driven Statistical Models for Natural Language Parsing. Ph. D. thesis, University of Pennsylvania.
• Covington, M. A. (2001). A Fundamental Algorithm for Dependency Parsing. In Proceedings of the 39th Annual ACM Southeast Conference, pp. 95-102.
• Fan, R.-E., Chang, K.-W., Hsieh, C.-J., Wang, X.-R. and Lin, C.-J.. LIBLINEAR: A library for large linear classification Journal of Machine Learning Research 9(2008), 1871-1874.
• Hall, J., J. Nivre and J. Nilsson (2006). Discriminative Classifiers for Deterministic Dependency Parsing. In Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics, pp. 316-323.
• Kudo, T. and Y. Matsumoto (2002). Japanese Dependency Analysis Using Cascaded Chunking. In Proceedings of the Sixth Workshop on Computational Language Learning (CoNLL), pp. 63-69.
• Magerman, D. M. (1995). Statistical decision-tree models for parsing. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics (ACL), pp. 276-283.
• Nivre, J. (2003). An Efficient Algorithm for Projective Dependency Parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT 03), pp. 149-160.
• Nivre, J. (2006) Inductive Dependency Parsing. Springer.
• 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), pp. 49-56.
• Ratnaparkhi, A. (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), pp. 1-10.
• Yamada, H. and Y. Matsumoto (2003). Statistical Dependency Analysis with Support Vector Machines. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pp. 195-206.
• Hall, J. and J. Nivre (2008a) A Dependency-Driven Parser for German Dependency and Constituency Representations. In Proceedings of the ACL Workshop on Parsing German (PaGe08), June 20, 2008, Columbus, Ohio, US.
• Hall, J. and J. Nivre (2008b) Parsing Discontinuous Phrase Structure with Grammatical Functions. In Proceedings of the 6th International Conference on Natural Language Processing (GoTAL 2008), August 25-27, 2008, Gothenburg, Sweden.
• 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.
• 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.
• 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.
• 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.

Copyright © Johan Hall, Jens Nilsson and Joakim Nivre