Exact and Approximate Sampling by Systematic Stochastic Search

Vikash K. Mansinghka, Daniel M. Roy, Eric Jonas, Joshua B. TenenbaumAISTATS 2009 · OpenReview

Abstract

We introduce adaptive sequential rejection sampling, an algorithm for generating exact samples from high-dimensional, discrete distributions, building on ideas from classical AI search. Just as systematic search algorithms like A* recursively build complete solutions from partial solutions, sequential rejection sampling recursively builds exact samples over high-dimensional spaces from exact samples over lower-dimensional subspaces. Our algorithm recovers widely-used particle filters as an approximate variant without adaptation, and a randomized version of the directed arc consistency algorithm with backtracking when applied to deterministic problems. In this paper, we present the mathematical and algorithmic underpinnings of our approach and measure its behavior on ferromagnetic Isings and other probabilistic graphical models, obtaining exact and approximate samples in a range of situations.

Introduction

Efficient inference in high-dimensional, discrete probability models is notoriously difficult, especially when the distribution is highly multimodal, characterized by many widely separated peaks of high probability. In a strongly coupled Ising model, for instance, the system may heavily favor either an "all up" or "all down" state. Standard approximation techniques like Maximum A Posteriori (MAP) or mean-field methods often miss this bimodality entirely. Meanwhile, simulation-based methods like Gibbs sampling frequently get trapped in local modes and fail to converge.

While naive rejection sampling can theoretically yield exact samples, its acceptance probability decays exponentially as the number of dimensions grows, making it practically useless for large problems. This paper addresses this challenge by asking: Can we use deterministic constraint-satisfaction tricks from classical AI search to guide and fix stochastic sampling? We introduce adaptive sequential rejection sampling, an algorithm that merges classical AI search techniques, such as depth-first search and backtracking, with stochastic sampling to generate exact samples from high-dimensional, discrete distributions.

Methodology

Instead of guessing a full high-dimensional state all at once, the proposed algorithm builds up exact samples piece-by-piece (variable by variable), mirroring systematic search algorithms like A*.

Sequential Rejection and Factor Graphs

The algorithm recursively generates an exact sample over a lower-dimensional subspace and extends it to a higher-dimensional one using a Gibbs transition kernel as a proposal. This process can be visualized through factor graphs, where the problem is decomposed into smaller, manageable components.

Factor graph representation of sequential sampling. The algorithm builds samples over high-dimensional spaces (a) from lower-dimensional subspaces (b).

Adaptation via Stochastic Backtracking

The core novelty lies in the adaptation mechanism. In deterministic search, if a dead end is encountered, the algorithm backtracks and records the failure to avoid that path in the future. We generalize this to sampling by maintaining a "hashmap" of visited, rejected states. If a partial assignment is proven to lead to a rejection, the algorithm updates its proposal distribution to never propose that partial assignment again. This feedback loop drives the acceptance probability toward 1 over time, allowing the sampler to overcome the curse of dimensionality in structured problems.

Approximate Relaxation

For problems too massive for exact sampling, the rejection step can be swapped out for importance sampling with resampling. This effectively recovers a particle filter that still benefits from the systematic search structure and adaptive proposal mechanisms.

Experimental Evaluation

The authors evaluate the algorithm on several discrete graphical models, including Grid Ising Models (up to 100x100), Medical Diagnosis Networks (noisy-OR Bayesian networks), and a large-scale Stereo Vision MRF (61,344 nodes).

Key Results on Ising Models

The algorithm successfully generated exact samples from 10x10 ferromagnetic Isings near the critical temperature—a regime where standard Gibbs sampling fails to converge. It also effortlessly handled massive 100x100 antiferromagnetic Isings by exploiting tree-like symmetries.

Probability of success for exact sampling in 5x5 attractive and 10x10 repulsive Ising models across coupling parameters.

As shown in the performance plots, the adaptive sampler maintains a viable probability of success even as coupling parameters increase, which typically increases the difficulty for standard samplers. On randomly generated 6x6 frustrated Isings, the adaptive sampler quickly learned to avoid bad states, eventually generating approximately one exact sample per 1,000 attempts after an initial learning phase, whereas non-adaptive samplers failed almost immediately.

Large-Scale Applications

In medical diagnosis networks, adaptation proved critical for overcoming massive rejection rates caused by dense connectivity. On the 61,344-node stereo vision MRF, the approximate variant (using just 1 to 5 particles) achieved better log-probability states in a fraction of the time compared to an aggressively annealed Gibbs sampler.

Discussion and Limitations

While powerful, the approach has limitations. Calculating the optimal rejection constant ($C^*$) is worst-case exponential in the number of dimensions. While computationally cheap for sparse graphs like 2D Isings, it limits application on densely connected graphs. Furthermore, exact sampling remains fundamentally intractable for arbitrarily large problems; in those regimes, this method is best utilized as a proposal mechanism for approximate algorithms. Future work includes exploring "adaptive inference planners" to dynamically optimize variable ordering and analyzing behavior near phase transitions in combinatorial problems.

Summary updated

Abstract

We introduce _adaptive sequential rejection sampling_, an algorithm for generating exact samples from high-dimensional, discrete distributions, building on ideas from classical AI search. Just as systematic search algorithms like A* recursively build complete solutions from partial solutions, sequential rejection sampling recursively builds exact samples over high-dimensional spaces from exact samples over lower-dimensional subspaces. Our algorithm recovers widely-used particle filters as an approximate variant without adaptation, and a randomized version of the directed arc consistency algorithm with backtracking when applied to deterministic problems. In this paper, we present the mathematical and algorithmic underpinnings of our approach and measure its behavior on ferromagnetic Isings and other probabilistic graphical models, obtaining exact and approximate samples in a range of situations.
BibTeX
@inproceedings{mansinghka2009exact,
  author = {Vikash K. Mansinghka and Daniel M. Roy and Eric Jonas and Joshua B. Tenenbaum},
  title = {{Exact and Approximate Sampling by Systematic Stochastic Search}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2009},
  url = {https://openreview.net/forum?id=B0gH1vhDJGc},
}
Figure