Hierarchical Search for Parsing

Adam Pauls, Dan KleinNAACL 2009 · OpenReview

TL;DR

This paper compares two hierarchical parsing strategies: coarse-to-fine (CTF) and hierarchical A (HA). They find CTF is generally faster but makes search errors, while HA is optimal but slower. They also introduce the first experiments with HA for parsing, showing its potential but also its sensitivity to heuristic quality.

What Problem Does This Paper Address?

Parsing natural language sentences with large, complex grammars is computationally expensive. To make this tractable, researchers have developed methods that use simpler "coarser" grammars to guide the search for parses in the full, "finer" grammar. Two prominent approaches are:

  1. Coarse-to-Fine (CTF) Pruning: This method uses a sequence of increasingly complex grammars. At each step, it prunes away parts of the search space that are unlikely to lead to a good parse according to the simpler grammar. This is efficient but can lead to search errors if the pruning is too aggressive.
  2. A* Search: This is a more principled search algorithm that uses a heuristic function to estimate the cost to reach the goal. In parsing, this means using a simpler grammar to estimate the "remaining cost" of a partial parse. A* guarantees optimality if the heuristic is "consistent," meaning it never overestimates the true cost.

The challenge is to effectively combine these hierarchical approaches for parsing, understand their trade-offs, and explore how to make them even more efficient. Specifically, the authors want to know:

  • Can hierarchical A* be applied effectively to parsing, similar to how CTF uses hierarchies?
  • What are the fundamental differences and trade-offs between CTF and HA* in terms of speed and accuracy?
  • When and why do these methods fail?

Methods

The authors frame both CTF and HA* within a common agenda-based parsing framework. This allows for a fair comparison by normalizing the implementation details.

  • Agenda-Based Parsing: This is a general best-first search strategy. It maintains a priority queue (agenda) of potential parsing steps (edges) and a chart of completed steps. The algorithm repeatedly takes the highest priority step from the agenda, processes it, and adds new potential steps to the agenda.
  • Hierarchical A* (HA*): This is an extension of A* search. It uses a hierarchy of grammars, where each grammar is a "relaxed projection" of the next. HA* tracks both "inside" edges (representing partial parses) and "outside" edges (representing the completion of a parse to the root). The key innovation is that the heuristics for the finer grammars are derived from the outside scores of coarser grammars. This allows the computation of heuristics to be integrated into the search process itself, rather than being a separate, offline step.
  • Agenda-Based CTF: The authors adapt CTF pruning to the agenda-based framework. Instead of exhaustively parsing each level, they use a modified priority function. This function effectively prunes edges that would have been discarded by CTF, allowing for a direct comparison with HA*.

Datasets

The experiments were conducted using:

  • Penn Treebank: This is a standard corpus for natural language processing. The authors used sections 2-21 for training and section 23 for testing.
  • State-Split Grammars: These grammars were derived from the Penn Treebank using a split-merge procedure, creating a natural hierarchy of grammars.
  • Lexicalized Grammars: These grammars were constructed using the Stanford Parser and are based on a dependency model and a PCFG.

Key Insights and Ideas

  • HA* integrates heuristic computation into search: Unlike standard A* where heuristics are often precomputed, HA* computes them "on the fly" using coarser grammars. This is a novel way to leverage hierarchical information for heuristic generation.
  • CTF's cascading pruning is highly effective: The paper highlights that CTF's strength lies in how pruning decisions at coarser levels cascade and eliminate large portions of the search space at finer levels. This makes it significantly faster than HA* in many scenarios.
  • The "slack" in HA* heuristics is critical: The performance of A* (and HA*) degrades rapidly as the heuristic's "slack" (the difference between the estimated cost and the true cost) increases. This explains why HA* can be slow when using very coarse auxiliary grammars.
  • Not all hierarchies are beneficial for HA*: The authors found that adding too many very coarse grammars to HA* can decrease performance. This is because these grammars become too cheap, leading to excessive processing of low-level information before significant progress is made in the target grammar.
  • CTF scales better with sentence length: CTF's performance degrades more gracefully with increasing sentence length compared to HA*, which suffers from increasing heuristic slack.

Key Results

  • Speed vs. Optimality: CTF is generally much faster than HA*, but it makes search errors. HA* guarantees optimality but is slower.
  • CTF Speedup: CTF achieved significant speedups (up to 8x) by adding coarse grammars, with minimal search errors.
  • HA* Performance: Using a single auxiliary grammar (3-split) provided a 10% speedup over standard A*. Adding more levels (up to 5-split) further improved performance by 25%. However, using all 6 levels degraded performance.
  • Lexicalized Parsing Trade-off: For lexicalized grammars, HA* was consistently faster than CTF, even when CTF made search errors. This was attributed to the very tight heuristics used in this model, resulting in minimal slack.
  • Search Errors and Speed: For CTF, there's a clear trade-off: fewer search errors lead to slower parsing. Below a 1% search error rate, HA* becomes faster than CTF.

Limitations and Future Work

  • HA* Sensitivity to Heuristic Slack: The paper demonstrates that HA*'s performance is highly sensitive to the quality of heuristics. Overly loose heuristics lead to exponential increases in work. This suggests future work could focus on developing tighter heuristics or more robust HA* variants.
  • CTF's "Average" Grammars: For CTF, the authors used grammars that were "average" projections rather than strict lower bounds. While this improved performance, it means CTF's results are not strictly optimal in the same way as HA*. The paper notes that using these "average" grammars as heuristics in HA* led to consistency issues and search errors.
  • Lexicalized Grammar Limitations: The experiments with lexicalized grammars were limited to a single projection level for HA*. The authors mention that generalizing HA* to factored models is straightforward but not effective, suggesting further research is needed in this area.
  • Future Work: The authors implicitly suggest exploring better ways to manage heuristic slack in HA* and further investigating the benefits of hierarchical pruning in CTF. The contrast between the two approaches for different grammar types also opens avenues for understanding when each is most appropriate.

Summary updated

Abstract

Both coarse-to-fine and A* parsing use simple grammars to guide search in complex ones. We compare the two approaches in a common, agenda-based framework, demonstrating the tradeoffs and relative strengths of each method. Overall, coarse-to-fine is much faster for moderate levels of search errors, but below a certain threshold A* is superior. In addition, we present the first experiments on hierarchical A* parsing, in which computation of heuristics is itself guided by meta-heuristics. Multi-level hierarchies are helpful in both approaches, but are more effective in the coarse-to-fine case because of accumulated slack in A* heuristics.
BibTeX
@inproceedings{pauls2009hierarchical,
  author = {Adam Pauls and Dan Klein},
  title = {{Hierarchical Search for Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
  url = {https://openreview.net/forum?id=HyW7Bm-O-H},
}
Figure