Coarse-To-Fine Parsing for Expressive Grammar Formalisms

Christoph Teichmann, Alexander Koller, Jonas GroschwitzIWPT 2017 · OpenReview

Introduction

Parsing is a fundamental task in natural language processing and graph analysis, yet it remains computationally expensive for expressive grammars. Coarse-to-Fine (CTF) pruning has long been a staple for accelerating Probabilistic Context-Free Grammars (PCFGs). By first parsing with a simplified "coarse" grammar and then refining the search space for the "fine" grammar, researchers have achieved significant speedups. This paper investigates whether these benefits extend to more complex formalisms, specifically Tree-Adjoining Grammars (TAG) and Hyperedge Replacement Grammars (HRGs).

Methodology: A Unified Framework

The authors utilize Interpreted Regular Tree Grammars (IRTGs) as a mathematical foundation to unify these disparate formalisms. IRTGs separate the derivation process from the final interpretation (string or graph), allowing for a generalized approach to "coarsification." In this framework, non-terminals are merged to create simpler grammars, provided the merged rules share the same interpretation (homomorphism).

This study evaluates CTF across three tasks: PCFG parsing using the Penn Treebank, TAG parsing induced from the same data, and graph parsing using HRGs induced from the Abstract Meaning Representation (AMR) corpus.

The PCFG vs. TAG Paradox

The experimental results reveal a surprising divergence in CTF's effectiveness. While the technique delivered a 20x speedup for standard PCFGs with no loss in accuracy, it failed to provide any meaningful performance gain for TAGs. In fact, aggressive pruning in TAGs actually led to a decrease in F-score without reducing runtime.

Table showing the performance comparison between PCFG and TAG parsing using CTF.

As shown in the data, the TAG parser's runtime remained stagnant at approximately 11 seconds, while the F-score dropped from 70.9 to 68.5 under the CTF:10⁻⁹ setting. This suggests that the structural constraints of TAGs differ fundamentally from PCFGs in ways that resist standard coarsening strategies.

The HRG Slowdown: When Pruning Backfires

The results for graph parsing (HRG) were even more counterintuitive. Instead of speeding up the process, coarsening the grammar significantly slowed down the parser. For example, the "Both" coarsening strategy took 3926ms, nearly six times longer than the unpruned baseline of 622ms.

Performance metrics for various coarsening strategies in HRG graph parsing.

This slowdown occurs because coarsening removes the very constraints that keep the graph search space manageable. By merging specific categories, the parser is forced to consider a vastly larger number of ways to combine subgraphs, effectively expanding the search space rather than pruning it.

Key Insight: The Role of Saturation

The authors identify "saturation"—the percentage of possible categories that appear in the parse chart—as the deciding factor for CTF success. PCFGs exhibit high saturation, meaning many categories can derive the same string, which leaves ample room for pruning. Conversely, TAGs and HRGs have low saturation; they are naturally restrictive. In these cases, the overhead of parsing a coarse grammar outweighs any potential savings, as there are few "unlikely" paths to throw away.

Conclusion

This research demonstrates that CTF is not a universal solution for grammar parsing. Its effectiveness is highly dependent on the structural properties and saturation levels of the grammar formalism. Future work must look beyond simple coarsening, perhaps exploring A* parsing or dynamic feedback mechanisms to optimize the processing of expressive grammars.

Summary updated

BibTeX
@inproceedings{teichmann2017coarse,
  author = {Christoph Teichmann and Alexander Koller and Jonas Groschwitz},
  title = {{Coarse-To-Fine Parsing for Expressive Grammar Formalisms}},
  booktitle = {IWPT},
  year = {2017},
  url = {https://openreview.net/forum?id=nn1YOaabsbj},
}
Figure