Using MONA for Querying Linguistic Treebanks

Stephan KepserEMNLP 2005

TL;DR

This paper investigates using MONA, a powerful automata toolkit, for querying linguistic treebanks. While MONA's theoretical underpinnings are strong, the authors conclude it's not a practical solution for linguists due to significant computational hurdles in compilation and query execution, as well as limitations in handling linguistic labels directly.

What Problem Does This Paper Address?

Modern linguistics increasingly relies on large, annotated electronic text corpora called treebanks to test theories against real-world language. To effectively explore these rich datasets, linguists need powerful query tools that can precisely pinpoint linguistic phenomena. Existing tools often have limited query languages, forcing users to accept large, unwieldy result sets. Monadic Second-Order Logic (MSO) offers a theoretically powerful and efficient way to query tree structures, matching the expressive power of common grammar formalisms. The challenge is finding a practical implementation of MSO for treebank querying. This paper explores whether MONA, a readily available toolkit for compiling MSO formulas into tree automata, could serve this purpose.

Methods

The core of the paper is an evaluation of MONA's suitability for treebank querying. The authors propose a method where:

  1. Treebank trees are translated into MONA formulas: This involves converting arbitrarily branching trees into binary trees using the "first-daughter-next-sibling" encoding and then representing node labels (categories and functions) as sets.
  2. MONA formulas are compiled into tree automata: MONA's compiler takes these formulas and attempts to generate equivalent tree automata.
  3. Queries are translated into MONA formulas: A custom query language, based on MSO, is developed. These query formulas are then combined with the tree-specific formulas (via an import mechanism) to check for matches.

The authors focus on the "tree part" of MONA, specifically its ability to handle MSO formulas on trees.

Datasets

The primary dataset used for evaluation is the Tübingen Treebank of spoken German (TüBa-D/S). This treebank contains approximately 38,000 trees and is annotated with part-of-speech tags and syntactic information based on topological fields. The authors also mention the Penn Treebank (American English) and the TIGER Corpus (German) as examples of similar large treebanks.

Key Insights and Ideas

  • MSO's theoretical appeal: The paper highlights that MSO is theoretically well-suited for querying treebanks, offering expressive power comparable to regular tree grammars and enabling linear-time query evaluation in theory.
  • MONA's limitations for linguistics: Despite its theoretical strengths, MONA proves problematic for linguistic applications due to:
  • Inability to directly handle linguistic labels: Labels must be encoded as sets, leading to potentially huge automata.
  • No direct token querying: MONA cannot query for specific words or sequences of words, a fundamental requirement for many linguistic tasks.
  • Massive compilation overhead: Compiling even moderately sized trees into automata is computationally intensive, requiring significant resources and time.
  • Impractical query times: Even with powerful hardware, query execution times are far too slow compared to existing specialized treebank query tools.

Key Results

The evaluation revealed significant practical challenges:

  • Compilation Bottleneck: Compiling a subset of 1000 trees from TüBa-D/S, some with over 100 nodes, took 15 hours on a desktop machine, compiling only 230 trees. Even on a cluster computer, compiling 999 trees took about 4 hours, and a single tree with over 200 nodes could not be compiled.
  • Slow Query Performance: A simple query (finding nodes with category NX) on just 999 trees took 6 hours and 9 minutes on a desktop. On a cluster, the same query took 1 minute 30 seconds for a fraction of the treebank. This is orders of magnitude slower than specialized tools like TIGERSearch or fsq, which can answer queries in seconds.
  • Automata Size Explosion: The authors suspect that the indirect coding of linguistic labels leads to excessively large automata, contributing to the compilation and query performance issues.

Limitations and Future Work

The authors explicitly state that MONA is not a viable option for querying linguistic treebanks. The primary limitations are:

  • Lack of direct token querying: This is a fundamental drawback for linguistic analysis.
  • Computational infeasibility: The compilation process is too resource-intensive and slow for practical use.
  • Impractical query answer times: The performance is orders of magnitude worse than existing tools.

The paper suggests that the problem might stem from MONA's inability to handle signatures (direct support for linguistic labels). They propose that future work should focus on implementing tree automata that can directly handle labelled trees, which could potentially overcome the size explosion and performance issues encountered with MONA. This would allow for more efficient and direct treebank querying.

Summary updated

BibTeX
@inproceedings{kepser2005using,
  author = {Stephan Kepser},
  title = {{Using MONA for Querying Linguistic Treebanks}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
}
Figure