Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs

Alexandre Bouchard-Côté, Slav Petrov, Dan KleinNeurIPS 2009 · OpenReview

TL;DR: Randomized pruning replaces a single, biased pruning mask with a sequence of masks generated via MCMC sampling. This allows researchers to calculate expectations in massive dynamic programs—like those used in bitext parsing—with theoretical convergence guarantees and significantly lower bias than traditional fixed-mask heuristics.

The Bottleneck in Large Dynamic Programs

In Natural Language Processing, many tasks (like training discriminative models or minimum risk decoding) require calculating expectations over massive combinatorial spaces, such as all possible parse trees for a sentence. While Dynamic Programming (DP) algorithms like the inside-outside algorithm make this possible, they become prohibitively slow as the complexity of the model or the "degree" of the algorithm increases. For instance, bitext parsing can reach $O(n^6)$ complexity.

Parse tree and corresponding chart assignments

To stay efficient, researchers usually use pruning: they create a "mask" to skip low-probability regions of the search space. However, any single fixed mask introduces systematic bias. If a feature's supporting structure is pruned, its expectation is incorrectly zeroed out. Tuning these masks is a delicate, often manual balancing act between speed and accuracy.

A New Approach: Randomized Pruning

The authors introduce Randomized Pruning, a framework grounded in auxiliary variable Markov Chain Monte Carlo (MCMC) sampling. Instead of relying on one static mask, the algorithm generates a sequence of different masks and averages the results.

  1. Auxiliary Variables: The "mask" is formalized using auxiliary variables that track which parts of the DP chart are "selected" and whether those parts are "positive" (a constituent) or "negative" (not a constituent).
  2. Block Gibbs Sampling: The algorithm iterates through two main steps:
  3. The Mask Step: A new pruning mask is generated based on the current state.
  4. The Expectation Step: A pruned version of the DP (like the inside-outside algorithm) is run using that mask to calculate "soft counts" (expectations).
Selections and assignments combining to create a pruning mask
  1. Accelerated Averaging: Rather than just averaging "hard counts" from sampled trees, the authors use "soft counts" from the pruned DP. This "accelerated averaging" is more efficient and helps the estimate converge faster to the true expectation.
  2. Theoretical Guarantees: Because the method is built on the framework of block Gibbs sampling, it inherits desirable convergence properties: as you run more iterations (more masks), the bias is guaranteed to decrease toward zero.

Key Insights and Results

The authors evaluated their approach using the Chinese Treebank, focusing on the challenging task of bitext parsing (simultaneously parsing and aligning two languages). In this domain, the DP complexity is high enough that exact computation is nearly impossible for long sentences.

  • Trading Time for Quality: Randomized pruning turns the "hard" constraint of pruning into a "soft" one. You can directly trade computation time for approximation quality by simply running more iterations.
  • Continuous Revision: Unlike fixed pruning, where a mistake is permanent, randomized pruning continuously revisits and revises pruning decisions. If a mask is too aggressive in one iteration, a subsequent iteration will likely "un-prune" those areas.
  • Efficiency and Scalability: Each sampling step was found to be three orders of magnitude faster than exact computation. The system processed nearly 1,500 sentence pairs (with product lengths up to 1,000) in just 28 minutes on a single CPU.
  • Bias Reduction: While a single mask's bias grows with sentence length, the bias of the randomized approach remains roughly constant when averaged over multiple masks. It substantially outperformed tic-tac-toe pruning, a popular heuristic for bitext parsing.

Limitations and Future Work

The method is most effective for "high-degree" algorithms. For simpler, lower-degree dynamic programs (like basic monolingual parsing), existing "coarse-to-fine" pruning methods are already very efficient and may be preferable.

Additionally, the efficiency of the algorithm depends on the "selection chain" (how the next set of spans to mask is chosen). While the authors provide a working version, they suggest that more sophisticated, model-aware selection strategies could further improve performance. Finally, while theoretically guaranteed to converge, the number of iterations required for very complex models might still be significant, though the paper shows it is highly competitive within realistic training timeframes.

Summary updated

Abstract

Pruning can massively accelerate the computation of feature expectations in large models. However, any single pruning mask will introduce bias. We present a novel approach which employs a randomized sequence of pruning masks. Formally, we apply auxiliary variable MCMC sampling to generate this sequence of masks, thereby gaining theoretical guarantees about convergence. Because each mask is generally able to skip large portions of an underlying dynamic program, our approach is particularly compelling for high-degree algorithms. Empirically, we demonstrate our method on bilingual parsing, showing decreasing bias as more masks are incorporated, and outperforming fixed tic-tac-toe pruning.
BibTeX
@inproceedings{bouchardcote2009randomized,
  author = {Alexandre Bouchard-Côté and Slav Petrov and Dan Klein},
  title = {{Randomized Pruning: Efficiently Calculating Expectations in Large Dynamic Programs}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=Bk4dbtZObB},
}
Figure