📄 MaltParser: A Data-Driven Parser-Generator for Dependency Parsing

Summary

Data-driven parsing promises faster development for new languages, but only when a treebank exists, and most available treebanks are small (roughly 100k tokens or fewer). The authors present MaltParser 0.3, a parser-generator that takes a dependency treebank instead of a grammar and induces a parser for that treebank's language. It implements inductive dependency parsing, which combines three components:

• a deterministic algorithm that builds the dependency graph step by step;
• a history-based feature model describing the current parser state;
• a discriminative classifier that selects the next parser action.

The core design goal is that these three components can be swapped and tuned independently. Users can choose among parsing algorithms and learning back-ends, and can write their own feature models in a compact tab-separated specification language. The paper documents functionality rather than new experiments. Evaluations reported elsewhere on Swedish, English, Czech, Danish and Bulgarian give dependency accuracy of 80–90%. That error rate is at most about 5% higher than state-of-the-art parsers, with no language-specific tuning and modest training data. This makes MaltParser a practical way to build parsers for languages with limited annotated resources.

Key points

• Two parsing algorithms are included, each with two modes:

  • Nivre's algorithm runs in linear time, handles projective structures only, and can be run arc-eager or arc-standard.
  • Covington's algorithm runs in quadratic time and has a projective mode and a non-projective (acyclic) mode.

• The arc-eager variant of Nivre's algorithm gave the best accuracy on every language and data set tested so far.

• Two learning back-ends are supported:

  • memory-based learning (k-nearest neighbour) via TiMBL;
  • support vector machines via LIBSVM.

  All results published for the system so far use the memory-based learner.

• Each feature draws on one of three token attributes: the lexical form (LEX), the POS tag (POS), or the dependency label (DEP). Tokens are located relative to STACK, INPUT or CONTEXT, with further navigation via head, leftmost/rightmost child and left/right sibling functions. A baseline feature set is informally called "model 7."

• Input uses the Malt-TAB format: one token per line with form, POS tag, head and relation, and blank lines between sentences. Output can be Malt-TAB, Malt-XML or TIGER-XML.

Interesting ideas

• I1. A parser built like a compiler. Treating the treebank the way a classic parser-generator treats a grammar turns "build a parser for language X" into a routine training run. This is attractive wherever new treebanks keep appearing, for example small UD treebanks.
• I2. Separate algorithm, features and learner. Keeping the three components decoupled lets each be varied and optimized without touching the others. The same architecture suits any transition-based system, such as tagging or chunking pipelines, where you want controlled ablation experiments.
• I3. Features as data, not code. Each feature is written as an address path: base structure, then position in the stack or list, then linear shift, then steps up to heads, then steps to children and siblings. This makes feature engineering declarative, reproducible and easy to share as a config file. Undefined addresses simply get a null value instead of causing errors.
• I4. Suffixes instead of full words when data is scarce. For small datasets, the authors suggest dropping peripheral lexical and POS features, or replacing whole word forms with suffixes (about 6 characters often works well). This is a cheap way to fight sparsity, and it is likely helpful for morphologically rich languages.
• I5. A simple, line-based interchange format. A tab-separated token-per-line format with blank-line sentence breaks keeps tooling simple. Optional XML outputs then cover integration with other corpus tools.