Hierarchical A* Parsing with Bridge Outside Scores

Adam Pauls, Dan KleinACL 2010 · OpenReview

Abstract

Hierarchical A (HA) uses of a hierarchy of coarse grammars to speed up parsing without sacrificing optimality. HA prioritizes search in refined grammars using Viterbi outside costs computed in coarser grammars. We present Bridge Hierarchical A (BHA), a modified Hierarchial A algorithm which computes a novel outside cost called a bridge outside cost. These bridge costs mix finer outside scores with coarser inside scores, and thus constitute tighter heuristics than entirely coarse scores. We show that BHA substantially outperforms HA when the hierarchy contains only very coarse grammars, while achieving comparable performance on more refined hierarchies.

Introduction

In natural language processing, "parsing" involves finding the most likely grammatical structure (a tree) for a sentence. For complex grammars, the search space is astronomical. To manage this, researchers use Hierarchical A (HA), which employs a hierarchy of grammars ranging from "coarse" (simple and fast) to "fine" (complex and accurate).

HA* uses the coarse grammars to compute "outside scores"—estimates of how much it will cost to complete a partial tree. These scores act as heuristics to guide the search in the finer, more expensive grammars. However, if the coarse grammar is a poor approximation of the target grammar, the heuristic is "loose," and the algorithm ends up doing a massive amount of unnecessary work in the refined levels. The authors aim to create a tighter heuristic that reduces this wasted effort.

Methods: The Bridge Outside Score

The authors introduce Bridge Hierarchical A (BHA). The core innovation is the bridge outside score. While standard HA computes outside scores using only the coarse grammar, BHA computes a "bridge" score that mixes levels.

Structure of a bridge derivation, mixing refined (blue) and coarse (red) grammar rules to create a tighter heuristic.

Specifically, for a given edge in the parse tree, the bridge derivation uses rules from the refined grammar for the "spine" (the path to the root) and everything to the "left" of it, while using the coarse grammar for everything to the "right" and "below." Because these bridge scores incorporate more information from the refined grammar, they provide a much tighter lower bound on the true cost. While bridge scores are more computationally expensive to calculate than purely coarse ones, the reduction in the overall search space (the number of "items pushed" onto the search agenda) results in a net win for speed.

Experimental Setup

The researchers evaluated their approach using the standard benchmark for English parsing:

  • Penn Treebank: They trained on Sections 2-21 and tested on 300 sentences (length $\le$ 25) from Section 23.
  • Grammar Hierarchy: They used the Berkeley Parser to generate a hierarchy of seven grammars via state-splitting (from a simple "0-split" X-bar grammar to a highly refined "5-split" target grammar).

Key Results

BHA* proves that spending a bit more time calculating a "smarter" heuristic (the bridge score) pays off by drastically pruning the search space.

Comparison of items pushed for HA* and BHA* across different grammar refinement levels, showing BHA*'s superior efficiency at coarse levels.
  • Significant Speedups: When using the coarsest possible grammar (0-split) as a starting point, BHA pushed roughly 15 billion items onto the search agenda, compared to over 30 billion for standard HA. This represents a 2x improvement in search efficiency.
  • Robustness to "Bad" Coarse Grammars: BHA performs remarkably well even when the coarsest level is a very loose approximation. As the coarse grammars became more refined, the gap between HA and BHA narrowed. At the 3-split level, HA slightly outperformed BHA*, suggesting that the extra overhead of bridge scores is most valuable when the hierarchy is "gappy" or poorly constructed.
  • Multi-level Success: BHA* successfully scales to multi-level hierarchies, though adding too many very coarse grammars can eventually hurt overall performance due to cumulative overhead.

Conclusion

Bridge Hierarchical A* offers a more robust alternative to standard hierarchical parsing by utilizing asymmetric bridge scores. While bridge scores are more expensive to compute per item, the dramatic reduction in the total number of items explored makes it a powerful tool for efficient parsing, particularly when high-quality coarse grammars are unavailable. Future work may explore how these overheads scale with longer sentences and more complex, non-CNF grammars.

Summary updated

Abstract

Hierarchical A* (HA*) uses of a hierarchy of coarse grammars to speed up parsing without sacrificing optimality. HA* prioritizes search in refined grammars using Viterbi outside costs computed in coarser grammars. We present Bridge Hierarchical A* (BHA*), a modified Hierarchial A* algorithm which computes a novel outside cost called a bridge outside cost. These bridge costs mix finer outside scores with coarser inside scores, and thus constitute tighter heuristics than entirely coarse scores. We show that BHA* substantially outperforms HA* when the hierarchy contains only very coarse grammars, while achieving comparable performance on more refined hierarchies.
BibTeX
@inproceedings{pauls2010hierarchical,
  author = {Adam Pauls and Dan Klein},
  title = {{Hierarchical A* Parsing with Bridge Outside Scores}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2010},
  url = {https://openreview.net/forum?id=r1Zdh2xO-H},
}
Figure