Finding the single most likely parse for a sentence—the "Viterbi parse"—is a cornerstone of natural language processing. However, as grammars expand and sentences grow in length, standard exhaustive algorithms like CKY become computationally expensive, typically scaling at $O(n^3)$. To mitigate this, researchers often resort to "greedy" shortcuts like beam search. While fast, these methods are "inadmissible"—they prune low-probability partial parses that might have eventually led to the globally optimal tree.
In this work, Dan Klein and Christopher Manning demonstrate that speed does not have to come at the cost of accuracy. By applying A* search to the parsing hypergraph, they find the exact Viterbi parse while exploring only a tiny fraction of the search space.
Methodology: A* Search for Parsing
The core innovation is the application of the A* algorithm to the parsing process. In this framework, the priority of a parse item (an "edge") in the search agenda is determined by the sum of its known cost and an estimated future cost: $$\text{Priority} = \text{Inside Cost} + \text{Estimated Outside Cost}$$
The Inside Cost represents the known probability of building a specific constituent (e.g., an NP spanning words 2 to 5). The Outside Cost is an estimate of the cost required to complete the rest of the tree to reach the root "S" symbol.
To guarantee optimality, the estimate must be admissible (never underestimating the true cost) and monotonic. The authors propose two primary strategies for constructing these estimates:
- Context Summary Estimates: These precompute the best possible outside score for a grammar symbol based on its span size and immediate neighbors (adjacent tags).
- Grammar Projection: This involves parsing with a simplified version of the grammar (e.g., collapsing specific noun categories into a general NP) to establish a "cheap" upper bound for the full grammar.
Key Insights: The Lattice of Heuristics
A significant theoretical contribution of the paper is the observation that different estimates form a lattice. By combining simple estimates (like span length) with richer context (like adjacent tags), one can "sharpen" the heuristic. This sharpening makes the search more restrictive and efficient without sacrificing the guarantee of finding the optimal parse.
Furthermore, the A approach offers structural simplicity. Unlike best-first parsers that require complex "upward propagation" of scores when a better path is discovered, an A parser with a monotonic heuristic never needs to update a score once an item is removed from the agenda.
Results and Performance
The parser was evaluated using the Penn Treebank (Wall Street Journal section), focusing on sentences of length 18–26. The results demonstrate massive efficiency gains:
- Massive Pruning: The most detailed estimate reduced the number of edges processed to less than 3% of the exhaustive baseline.
- Efficiency vs. Precomputation: Even a lightweight estimate ("SX"), requiring only one minute of pre-computation, reduced the workload to less than 5%.
- Optimality Guaranteed: Unlike beam search, this method is mathematically guaranteed to return the Viterbi parse.
- Speedup: The best estimates provided a speedup of over 35 times compared to uniform-cost search.
Conclusion and Limitations
While A* parsing provides a powerful tool for exact Viterbi selection, the authors note some limitations. Local estimates become less effective as the "outside" context grows, particularly for sentences exceeding 40-50 words, where the gap between the estimate and true cost increases linearly with span length. Additionally, while the method is applicable to lexicalized models via grammar projection, the most powerful heuristics can require significant memory (up to 1GB) and precomputation time. Nonetheless, the framework offers a robust, simple, and exact alternative to approximate parsing methods.
Summary updated