Abstract
Computing the partition function in large-scale graphical models is a fundamental yet #P-hard challenge in probabilistic inference. This paper introduces Abstraction Sampling (AS), a hybrid Monte Carlo framework that combines the systematic exploration of search algorithms with the statistical efficiency of stratified sampling. By grouping similar states into abstract categories and sampling subtrees—or "probes"—rather than individual paths, AS significantly reduces variance and improves accuracy over traditional importance sampling methods.
Introduction
In graphical models such as Bayesian or Markov networks, many critical tasks depend on calculating the normalizing constant, known as the partition function ($Z$). As the number of variables increases, exact computation becomes intractable due to the exponential growth of the state space. Researchers typically rely on two primary approaches: systematic search, which is thorough but limited by an "exponential wall," and Monte Carlo sampling, which is faster but often suffers from high variance when high-probability regions are missed.
Abstraction Sampling bridges this gap by utilizing the underlying structure of the search space to make samples more informative. By leveraging AND/OR search spaces, which exploit conditional independence, the method creates a more compact representation of the problem than standard OR trees.
The Abstraction Sampling Framework
The core innovation of this work is the Abstraction Function. Unlike standard importance samplers that select a single full configuration (a path from root to leaf) at a time, Abstraction Sampling generates a "probe"—a sampled subtree.
Layer-by-Layer Stratification
At each level of the search tree, the algorithm employs an abstraction function to partition nodes into "abstract states." Instead of maintaining every node, the algorithm selects a single representative for each abstract state. This representative is then weighted to account for the nodes it replaces, effectively emulating stratified sampling dynamically throughout the tree.
The authors propose two primary abstraction families:
- RelCB (Relaxed Context-Based): Groups nodes based on a subset of their ancestor assignments.
- RandCB (Randomized Context-Based): Uses a random hash function of the node's context to assign it to an abstract state.
Key Insights and Results
A surprising finding was that randomized abstraction (RandCB) often outperformed the more principled RelCB. This is attributed to random hashing creating abstract states of more uniform size, which is a critical requirement for effective variance reduction in stratified sampling. Furthermore, the authors prove that despite collapsing the search space, the estimator remains unbiased.
The algorithm was evaluated on benchmark sets from the UAI competition, including Bayesian networks, grid models, and medical diagnostic systems. Key results include:
- Variance Reduction: A 6-fold decrease in variance compared to standard importance sampling in motivating examples.
- Accuracy Gains: On "Grids-small" benchmarks, randomized abstraction with AND/OR trees reduced average log-error from 4.94 to 0.84 within 60 minutes of computation.
- Robustness: AS acts as a safety net when the underlying proposal distribution is poor, exploring the space more broadly than standard importance sampling.
Conclusion
Abstraction Sampling provides a robust framework for approximating complex queries in large-scale graphical models. By treating search as a "license to merge" and sampling as a way to explore these merged states, it achieves state-of-the-art performance on challenging instances where traditional methods struggle to converge. Future work will focus on automated abstraction design and finding the optimal balance between abstraction levels and heuristic strength.
Summary updated