Comparing and Combining Finite-State and Context-Free Parsers

Kristy Hollingshead, Seeger Fisher, Brian RoarkEMNLP 2005

TL;DR

This paper challenges the long-held belief that finite-state (shallow) parsers are inherently more accurate and robust than context-free parsers for tasks like noun-phrase chunking. By re-evaluating evaluation methodologies and demonstrating effective combination strategies, the authors show that context-free parsers can be highly competitive, and combining their output with shallow parsers yields significant improvements over previous state-of-the-art results.

What Problem Does This Paper Address?

For years, natural language processing (NLP) has grappled with a trade-off between parsing speed and accuracy. Finite-state parsers (also known as shallow parsers or chunkers) are computationally efficient and excel at identifying local syntactic structures like noun phrases. This makes them attractive for large-scale applications where full, deep parsing is too slow. Context-free parsers, on the other hand, produce more complete, hierarchical parse trees but are computationally more expensive.

A key debate has been whether shallow parsers offer an accuracy advantage, particularly when dealing with out-of-domain data. Previous work, notably by Li and Roth (2001), suggested that shallow parsers were indeed more accurate and robust. This paper aims to re-examine these claims by:

  1. Critically analyzing how the output of context-free parsers is converted and compared to shallow parses.
  2. Investigating the impact of different evaluation conventions.
  3. Demonstrating that combining the strengths of both types of parsers can lead to superior performance.

Methods

The authors employ several key methodological innovations and analyses:

  • Re-evaluation of Conversion Routines: They identify issues in the chunklink script, commonly used to convert full parse trees into shallow constituents. Specifically, they highlight how the script's handling of empty nodes and unary productions (like S→VP) can unfairly penalize context-free parsers. They propose modifications, such as inserting empty subject NPs, to rectify these conversion errors.
  • Evaluation Convention Analysis: They investigate the impact of ignoring punctuation when evaluating constituent spans, a standard practice in context-free parsing evaluation but not always in shallow parsing.
  • System Combination Strategies: They explore two methods for combining the outputs of a high-accuracy context-free parser (Charniak's) and a competitive shallow parser (their own SPRep perceptron):
  • Unweighted Intersection: Restricting the set of shallow parse candidates to those present in the intersection of the top-k outputs from both parsers.
  • Weighted Intersection: Extending the unweighted intersection by incorporating the scores (log probabilities) from the context-free parser, weighted by a learned scaling factor.
  • Domain Shift Evaluation: They test the robustness of their findings by training on the clean Penn Wall Street Journal (WSJ) Treebank and testing on the mismatched Switchboard corpus.

Datasets

The paper utilizes standard NLP datasets for training and evaluation:

  • Penn Treebank (WSJ): Used extensively for training and evaluating parsers. Specific sections are designated for training, heldout, and testing.
  • CoNLL-2000 Chunking Task Data: A benchmark for shallow parsing, involving 11 phrase types.
  • Li & Roth Task Data: Similar to CoNLL-2000 but with more training data and a different test section (WSJ section 00).
  • Switchboard Treebank: Used for evaluating robustness to domain shift.

Key Insights and Ideas

  • Conversion Matters: The way context-free parse trees are converted to shallow parses significantly impacts reported accuracy. Previous comparisons may have unfairly penalized context-free parsers due to conversion script limitations.
  • Context-Free Parsers are Competitive: When evaluated with appropriate conversion and evaluation conventions, context-free parsers perform competitively with, and can even outperform, shallow parsers on many shallow parsing tasks.
  • Combining Strengths is Key: The most significant gains come from combining the outputs of context-free and shallow parsers. This suggests that each system captures complementary information.
  • Robustness is Achievable: Context-free parsers, when properly evaluated and combined, are not inherently less robust to domain shift than shallow parsers.

Key Results

  • Eliminating Accuracy Gaps: After correcting for conversion issues and adopting standard evaluation conventions (ignoring punctuation), the accuracy differences between context-free parsers (like Collins and Charniak) and shallow parsers (like Li and Roth's) were significantly reduced, often resulting in a "dead heat."
  • Significant Combination Gains: Both unweighted and weighted intersection methods showed substantial improvements over individual parsers. The weighted intersection, in particular, achieved improvements that were statistically significant (p < 0.001) over the unweighted intersection and previous state-of-the-art results. For example, on the Li & Roth task, weighted intersection achieved 96.33% accuracy (ignoring punctuation), a notable jump.
  • Domain Shift Robustness: The combined system also showed strong performance on the Switchboard dataset, demonstrating that the benefits of combining parsers extend to out-of-domain scenarios.

Limitations and Future Work

  • Computational Cost: The paper acknowledges that context-free parsers are less efficient than finite-state models. While their accuracy benefits are highlighted, the trade-off for specific applications still needs consideration.
  • Feature Engineering: The authors suggest exploring more sophisticated features for shallow parsers, potentially derived from context-free parse structures, to further improve performance.
  • Optimizing Phrase Types: They propose investigating whether the current set of shallow phrase types (from CoNLL-2000) is optimal for all applications, suggesting that expanding or refining these types could be beneficial.
  • Multi-Pass Parsing: The idea of using shallow parses to constrain the search space for a subsequent context-free parsing pass is mentioned as a future direction.
  • Encoding CF Features: Encoding context-free parser features into finite-state models is also suggested as a way to preserve efficiency while capturing some accuracy gains.

Summary updated

BibTeX
@inproceedings{hollingshead2005comparing,
  author = {Kristy Hollingshead and Seeger Fisher and Brian Roark},
  title = {{Comparing and Combining Finite-State and Context-Free Parsers}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
}
Figure