Exact and Approximate Sampling by Systematic Stochastic Search

Vikash Mansinghka, Daniel Roy, Eric Jonas, Joshua Tenenbaum
; Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, PMLR 5:400-407, 2009.

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.

Cite this Paper


BibTeX
@InProceedings{pmlr-v5-mansinghka09a, title = {Exact and Approximate Sampling by Systematic Stochastic Search}, author = {Vikash Mansinghka and Daniel Roy and Eric Jonas and Joshua Tenenbaum}, booktitle = {Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics}, pages = {400--407}, year = {2009}, editor = {David van Dyk and Max Welling}, volume = {5}, series = {Proceedings of Machine Learning Research}, address = {Hilton Clearwater Beach Resort, Clearwater Beach, Florida USA}, month = {16--18 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v5/mansinghka09a/mansinghka09a.pdf}, url = {http://proceedings.mlr.press/v5/mansinghka09a.html}, 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.} }
Endnote
%0 Conference Paper %T Exact and Approximate Sampling by Systematic Stochastic Search %A Vikash Mansinghka %A Daniel Roy %A Eric Jonas %A Joshua Tenenbaum %B Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2009 %E David van Dyk %E Max Welling %F pmlr-v5-mansinghka09a %I PMLR %J Proceedings of Machine Learning Research %P 400--407 %U http://proceedings.mlr.press %V 5 %W PMLR %X 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.
RIS
TY - CPAPER TI - Exact and Approximate Sampling by Systematic Stochastic Search AU - Vikash Mansinghka AU - Daniel Roy AU - Eric Jonas AU - Joshua Tenenbaum BT - Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics PY - 2009/04/15 DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-mansinghka09a PB - PMLR SP - 400 DP - PMLR EP - 407 L1 - http://proceedings.mlr.press/v5/mansinghka09a/mansinghka09a.pdf UR - http://proceedings.mlr.press/v5/mansinghka09a.html AB - 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. ER -
APA
Mansinghka, V., Roy, D., Jonas, E. & Tenenbaum, J.. (2009). Exact and Approximate Sampling by Systematic Stochastic Search. Proceedings of the Twelth International Conference on Artificial Intelligence and Statistics, in PMLR 5:400-407

Related Material