CUED Publications database

Exact and approximate sampling by systematic stochastic search

Mansinghka, V and Roy, D and Jonas, E and Tenenbaum, J (2009) Exact and approximate sampling by systematic stochastic search. Journal of Machine Learning Research, 5. pp. 400-407. ISSN 1532-4435

Full text not available from this repository.


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 depth first search 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 undirected and directed graphical models, obtaining exact and approximate samples in a range of situations. © 2009 by the authors.

Item Type: Article
Divisions: Div F > Computational and Biological Learning
Depositing User: Cron Job
Date Deposited: 15 Dec 2015 13:36
Last Modified: 18 Jan 2016 06:19