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, who are members of the MALT group
at the School of Mathematics and Systems Engineering (MSI) at Växjö 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:
- Deterministic parsing algorithms for building labeled dependency graphs (Kudo and Matsumoto,2002; Yamada and Matsumoto, 2003; Nivre,2003)
- History-based models for predicting the next parser action at nondeterministic choice points (Black et al., 1992; Magerman, 1995; Ratnaparkhi, 1997; Collins, 1999)
- 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.1
MaltParser implements four deterministic parsing algorithms:
- Nivre arc-eager
- Nivre arc-standard
- Covington non-projective
- Covington projective
MaltParser allows users to define feature models of arbitrary complexity.
MaltParser currently includes one machine learning package (interfaces to other learning packages will be included in later releases):
- LIBSVM - A Library for Support Vector Machines (Chang, 2001).
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.
- 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, pp. x-x. (to appear)
- 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, pp. x-x. (to appear).