MICA: A Probabilistic Dependency Parser Based on Tree Insertion Grammars

Srinivas Bangalore, Pierre Boullier, Alexis Nasr, Owen Rambow, Benoît Sagot2009

TL;DR

This paper introduces MICA, a fast and accurate probabilistic dependency parser that generates "deep" linguistic representations. It leverages Tree Insertion Grammars (TIGs) and a supertagging approach to achieve state-of-the-art performance, offering a freely available tool for NLP researchers.

What Problem Does This Paper Address?

Understanding the grammatical structure of sentences is fundamental to natural language processing (NLP). While many parsers exist, there's a need for systems that go beyond simple surface-level relationships (like subject-verb agreement) to capture deeper, predicate-argument structures. This "deep" representation is crucial for tasks requiring a nuanced understanding of sentence meaning. Furthermore, researchers often need parsers that are not only accurate but also efficient and readily accessible for experimentation. MICA aims to fill this gap by providing a parser that delivers rich dependency structures, is computationally efficient, and is publicly available.

Methods

MICA employs a novel approach that combines Tree Insertion Grammars (TIGs) with a supertagging strategy. The process involves several key steps:

  • TIG Extraction: A TIG is extracted from the Penn Treebank, which forms the basis for both supertagging and parsing. This grammar captures richer linguistic information than standard context-free grammars.
  • Supertagging: A supertagger assigns "supertags" to words. These supertags are not just part-of-speech tags but represent elementary trees from the TIG, encapsulating predicate-argument structure and morpho-syntactic constraints. This step is crucial for disambiguating word senses and their potential grammatical roles.
  • PCFG Construction: The TIG is transformed into a Probabilistic Context-Free Grammar (PCFG). This PCFG is then "specialized" to better model lexico-syntactic phenomena.
  • Earley-like Parsing: A modified Earley parser is used to process the supertag sequences and generate a shared parse forest. This forest represents all possible parse trees according to the underlying grammar.
  • N-best Extraction and Dependency Extraction: An n-best module extracts the most probable parse trees from the forest. Finally, a dependency extractor leverages the TIG structure to transform these trees into deep dependency representations.

A key innovation is the "mother specialization" technique, which conditions attachment decisions on the mother node and its position, allowing for a more accurate modeling of syntactic dependencies.

Datasets

The primary dataset used is the Penn Treebank, specifically the Wall Street Journal (WSJ) portion.

  • Training: Sections 02-21 of the WSJ Penn Treebank were used for training the dependency parser.
  • Testing: Section 00 of the WSJ Penn Treebank was used for evaluation.

The paper also mentions using a large corpus of supertag-annotated data derived from the Penn Treebank for training the supertagging models.

Key Insights and Ideas

  • Deep Dependency Representations: MICA moves beyond surface syntactic features to represent predicate-argument structure, treating elements like prepositions in a more nuanced way (e.g., as co-heads). This offers a richer understanding of sentence meaning.
  • Supertags as a Bridge: The use of supertags, which encode rich linguistic information, acts as an effective intermediate representation. This allows the parser to leverage detailed syntactic knowledge without requiring complex, direct lexicalization in the parsing stage itself.
  • Efficiency Through Specialization: By specializing the grammar and using techniques like mother specialization, MICA achieves high accuracy while maintaining impressive speed.
  • Freely Available Tool: The decision to make MICA freely available is a significant contribution, lowering the barrier to entry for researchers needing a robust dependency parser.

Key Results

MICA demonstrates strong performance in terms of both accuracy and speed:

  • Accuracy: MICA achieves state-of-the-art unlabeled dependency accuracy of 87.6% on the WSJ Section 00 test set.
  • Speed: The parser is remarkably fast, running at approximately 450 words per second on a standard machine, with a 6-second initialization time for sentences under 200 words. This is significantly faster than the MALT parser, which runs at about 30 words per second.
  • Comparison: When compared to the MALT parser, MICA's performance is competitive, and the use of predicted supertags did not significantly improve MALT's performance.

Limitations and Future Work

  • Limitations: The paper acknowledges that while mother specialization is powerful, it can lead to data sparsity issues, necessitating the use of only a subset of specialized symbols. The current PCFG construction models multiple adjunctions at a node, but the authors note that the "bigram model" for adjunction is an alternative that could be explored further.
  • Future Work: The authors suggest that the positional model of adjunction and the "bigram model" are areas for further investigation. The paper also implies that further exploration of the TIG structure and its implications for dependency representation could be fruitful.

Summary updated

Abstract

MICA is a dependency parser which returns deep dependency representations, is fast, has state-of-the-art performance, and is freely available.
BibTeX
@misc{bangalore2009mica,
  author = {Srinivas Bangalore and Pierre Boullier and Alexis Nasr and Owen Rambow and Benoît Sagot},
  title = {{MICA: A Probabilistic Dependency Parser Based on Tree Insertion Grammars}},
  year = {2009},
}
Figure