Exact and Approximate Sampling by Systematic Stochastic Search

Vikash Mansinghka, Daniel Roy, Eric Jonas, Joshua Tenenbaum
Proceedings of the Twelfth 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 = {Mansinghka, Vikash and Roy, Daniel and Jonas, Eric and Tenenbaum, Joshua}, booktitle = {Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics}, pages = {400--407}, year = {2009}, editor = {van Dyk, David and Welling, Max}, 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 = {https://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 Twelfth 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 %P 400--407 %U https://proceedings.mlr.press/v5/mansinghka09a.html %V 5 %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 Twelfth International Conference on Artificial Intelligence and Statistics DA - 2009/04/15 ED - David van Dyk ED - Max Welling ID - pmlr-v5-mansinghka09a PB - PMLR DP - Proceedings of Machine Learning Research VL - 5 SP - 400 EP - 407 L1 - http://proceedings.mlr.press/v5/mansinghka09a/mansinghka09a.pdf UR - https://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 Twelfth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 5:400-407 Available from https://proceedings.mlr.press/v5/mansinghka09a.html.

Related Material