Hierarchical A* Parsing with Bridge Outside Scores
Adam Pauls, Dan Klein · 2010
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. 1