Unbounded Dependency Recovery for Parser Evaluation

Laura Rimell, Stephen Clark, Mark SteedmanEMNLP 2009

TL;DR

While modern statistical parsers boast impressive 90%+ accuracy scores on standard benchmarks, this paper reveals a "performance gap" in complex linguistic structures. By introducing a new evaluation corpus focused on unbounded dependencies—where words are separated from their logical roles by long distances—the authors show that state-of-the-art parsers actually struggle significantly, with accuracies ranging from a disappointing 25% to 59%.

What Problem Does This Paper Address?

In the world of Natural Language Processing (NLP), we often use aggregate metrics like "Parseval" scores to judge how well a parser understands a sentence. Because most sentences in standard datasets (like the Wall Street Journal section of the Penn Treebank) are grammatically straightforward, a parser can achieve a 92% F-score while still being "blind" to rare but semantically critical constructions.

The authors target unbounded dependencies (UDs). These occur when a word appears to have "moved" from its logical position, leaving a "gap." For example, in the phrase "the paper which I wrote," the word "paper" is the object of "wrote," even though it appears earlier in the sentence. These dependencies can theoretically span an unlimited number of clause boundaries, resulting in significant distances between related words.

Average and maximum distances for various unbounded dependency constructions.

Recovering these is essential for applications like Question Answering or Information Extraction, where knowing "who did what to whom" is the whole point.

Methods

The researchers took a "construction-focused" approach to evaluation:

  1. Corpus Creation: They manually curated and annotated a new test suite of ~700 sentences specifically containing UDs.
  2. Formalism Independence: To ensure a fair fight between different types of parsers, they mapped all outputs to a common format of Grammatical Relations (GRs)—head-based dependencies like dobj (direct object) or nsubj (nominal subject).
  3. Parser Selection: They tested five diverse, high-performing parsers: C&C (CCG-based), Enju (HPSG-based), Stanford Parser (PCFG), RASP (tag-sequence grammar), and a DCU post-processor (LFG-based).

Datasets

The paper introduces the Unbounded Dependency Corpus. Sentences were pulled from the Penn Treebank (WSJ and Brown sections) and the TREC Question Answering track. It covers seven specific grammatical constructions, including object/subject extraction from relative clauses, free relatives, wh-questions, and "Right Node Raising" (e.g., "Mary saw and Susan bought the book"). The final test set consists of 560 reserved sentences.

Key Results

The results were a wake-up call for the parsing community, showing that standard parsers often fail on these complex dependencies despite high overall benchmark scores.

Parser performance comparison across various linguistic constructions.
  • Top Performers: Enju (54.4%) and C&C (53.6%) were the most accurate, but still failed nearly half the time.
  • The Gap: The Stanford Parser, a staple in many NLP pipelines, scored only 38.1% overall.
  • Construction Variance: Some constructions were easier than others. Subject extraction from relative clauses saw scores up to 82%, while subject extraction from embedded clauses saw scores as low as 5.9%.
  • Domain Adaptation: Using a specialized model for questions boosted C&C’s performance on wh-questions from 27.5% to 81.2%, proving that targeted training helps immensely.

Key Insights and Ideas

  • The "Long Tail" of Language: UDs are relatively rare. Because they don't appear often, parsers can ignore them and still get a "passing grade" on standard metrics, even though they are failing at deep understanding.
  • Formalism Matters: Parsers built on "deep" linguistic formalisms like CCG (C&C) and HPSG (Enju) significantly outperformed standard phrase-structure parsers. These formalisms were designed to handle the "movement" inherent in UDs.
  • The Supertagging Bottleneck: For the C&C parser, many errors were traced back to the "supertagger." If it misses a verb's transitivity in context, the parser cannot recover the object dependency.
  • Attachment Ambiguity: Even when a parser identifies a dependency, it often attaches the "moved" word to the wrong head in complex noun phrases.

Limitations and Future Work

The authors acknowledge that their corpus is relatively small, limiting the statistical power of the error analysis. Furthermore, the evaluation was primarily a "recall" test, as calculating precision for UDs is difficult without fully annotating every possible dependency in the sentences.

Future Directions: * Active Learning: Seeking out or generating more training data for these rare UD types to bridge the performance gap. * Better Attachment Models: Improving how parsers handle prepositional phrase and relative clause attachment remains a major hurdle for recovering long-range dependencies.

Summary updated

BibTeX
@inproceedings{rimell2009unbounded,
  author = {Laura Rimell and Stephen Clark and Mark Steedman},
  title = {{Unbounded Dependency Recovery for Parser Evaluation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
}
Figure