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-4435Full 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.
|Divisions:||Div F > Computational and Biological Learning|
|Depositing User:||Cron Job|
|Date Deposited:||07 Mar 2014 12:21|
|Last Modified:||08 Dec 2014 02:30|