Speed and Accuracy in Shallow and Deep Stochastic Parsing

Ron Kaplan, Stefan Riezler, Tracy H. King, John T. Maxwell Iii, Alex Vasserman, Richard CrouchNAACL 2004

TL;DR

This paper challenges the conventional wisdom that shallow parsers are always faster and "good enough" for meaning-sensitive NLP tasks. By comparing a popular shallow parser (Collins) with a deep, grammar-based parser (XLE), the authors found that the deep parser achieved significantly higher accuracy with only a modest increase in parsing time, suggesting a better trade-off for applications requiring rich semantic understanding.

What Problem Does This Paper Address?

In natural language processing, accurately extracting the meaning of sentences is crucial for applications like summarization, information extraction, and question answering. Statistical parsers are widely used for this, with the Collins parser being a popular choice due to its perceived balance of accuracy, speed, and robustness. However, deep linguistic grammars, like Lexical Functional Grammar (LFG), promise richer semantic representations. The common belief is that these deep parsers are too slow and complex for practical use. This paper empirically investigates this trade-off, directly comparing the accuracy and speed of a state-of-the-art shallow parser against a deep LFG-based parser.

Methods

The authors compare two parsing systems:

  • Collins Parser: A popular shallow, statistical parser that produces tree structures with semantically relevant distinctions (e.g., arguments vs. adjuncts).
  • XLE Parser: A deep-parsing system based on Lexical Functional Grammar (LFG). It couples a formal grammar with a stochastic disambiguation component (a log-linear, maximum-entropy model). XLE produces both constituent structures (trees) and functional structures (attribute-value matrices) that encode richer semantic information. The system uses dynamic programming for efficient parsing and disambiguation, and incorporates robustness mechanisms to handle out-of-grammar sentences.

Both systems' outputs were converted into a dependency bank format for fair comparison. The XLE parser's performance was evaluated with two configurations: a "Core" grammar and a more extensive "Complete" grammar.

Datasets

  • PARC 700 Dependency Bank: This is the gold standard dataset used for evaluation. It consists of 700 sentences randomly sampled from section 23 of the Wall Street Journal (WSJ) corpus, annotated with dependency relations. The authors used a "Reduced" version of this bank, focusing on argument and boundary dependencies, and a few selected semantically relevant features.
  • Held-out set: 1/5 of the PARC 700 dependency bank was used to tune the performance parameters of both parsers. The final evaluation was performed on the remaining 560 sentences.

Key Insights and Ideas

  • Challenging Conventional Wisdom: The paper directly contests the assumption that shallow parsers offer a superior speed-accuracy trade-off for meaning-sensitive tasks.
  • Deep Parsing's Accuracy Advantage: The deep LFG-based parser (XLE) significantly outperforms the Collins parser in recovering semantically relevant grammatical dependencies.
  • Modest Speed Penalty for Deep Parsing: The performance gain of the deep parser comes at a relatively small cost in parsing speed, contradicting the expectation of a drastic slowdown.
  • Grammar Complexity Matters: Expanding the LFG grammar in XLE (from "Core" to "Complete") further boosts accuracy, albeit with a more substantial increase in parsing time.
  • Dependency Extraction is Hard: Extracting semantic dependencies is a more challenging task than traditional bracketing accuracy, as evidenced by the lower F-scores compared to typical evaluations of syntactic parsing.

Key Results

  • Accuracy: The XLE system achieved a 12% reduction in error rate compared to the Collins parser. Specifically, XLE achieved a 77.6% F-score, while the Collins parser achieved 74.6%.
  • Speed: The XLE system (Core grammar) was 1.49 times slower than the Collins parser. The Complete XLE system was 5 times slower.
  • Collins Parser Tuning: A beam size of 1000 for the Collins parser was found to be optimal for balancing speed and accuracy, offering a better trade-off than the default beam size of 10000.
  • XLE Grammar Impact: The Complete XLE grammar provided a 5% overall improvement in F-score over the Collins parser, but at a significant cost in parsing time.

Limitations and Future Work

  • Conversion Complexity: Converting the output of both parsers to the dependency bank format was non-trivial, especially for the Collins parser, requiring careful handling of linguistic nuances and potential penalties.
  • Named Entity Handling: The paper notes that proper names were treated as single multi-word expressions in the DEPBANK. To match this, named entities were marked with XML markup for XLE and by using underscores for the Collins parser. This highlights the importance of consistent named entity handling for fair evaluation.
  • Future Work: The authors suggest that extracting semantic dependencies is a valuable but difficult task. The results indicate that deep grammars, despite their complexity, offer a promising path towards achieving higher accuracy for meaning-sensitive applications. Further research could explore more efficient deep parsing techniques or hybrid approaches.

Summary updated

BibTeX
@inproceedings{kaplan2004speed,
  author = {Ron Kaplan and Stefan Riezler and Tracy H. King and John T. Maxwell III and Alex Vasserman and Richard Crouch},
  title = {{Speed and Accuracy in Shallow and Deep Stochastic Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2004},
}
Figure