Exact and approximate sampling by systematic stochastic search
URL to conference proceedings page
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Journal of Machine Learning Research
2011
|
| Online Access: | http://hdl.handle.net/1721.1/60993 https://orcid.org/0000-0002-1925-2035 |
| _version_ | 1826201955149545472 |
|---|---|
| author | Tenenbaum, Joshua B. Jonas, Eric M. Roy, Daniel Mansinghka, Vikash K. |
| author2 | Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences |
| author_facet | Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences Tenenbaum, Joshua B. Jonas, Eric M. Roy, Daniel Mansinghka, Vikash K. |
| author_sort | Tenenbaum, Joshua B. |
| collection | MIT |
| description | URL to conference proceedings page |
| first_indexed | 2024-09-23T11:59:37Z |
| format | Article |
| id | mit-1721.1/60993 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:59:37Z |
| publishDate | 2011 |
| publisher | Journal of Machine Learning Research |
| record_format | dspace |
| spelling | mit-1721.1/609932022-09-27T23:18:26Z Exact and approximate sampling by systematic stochastic search Tenenbaum, Joshua B. Jonas, Eric M. Roy, Daniel Mansinghka, Vikash K. Massachusetts Institute of Technology. Department of Brain and Cognitive Sciences Tenenbaum, Joshua B. Tenenbaum, Joshua B. Jonas, Eric M. Roy, Daniel Mansinghka, Vikash K. URL to conference proceedings page 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. NTT Communication Science Laboratories Eli Lilly and Company Google (Firm) National Science Foundation (U.S.) (Fellowships) 2011-02-18T21:07:10Z 2011-02-18T21:07:10Z 2009-04 Article http://purl.org/eprint/type/ConferencePaper 1533-792 http://hdl.handle.net/1721.1/60993 Mansinghka, Vikash, et al. "Exact and Approximate Sampling by Systematic Stochastic Search." Journal of Machine Learning Research, Workshop & Conference Proceedings, 5:400-407, 2009. https://orcid.org/0000-0002-1925-2035 en_US http://jmlr.csail.mit.edu/proceedings/papers/v5/ Proceedings of the Twelfth International Conference on Artificial Intelligence and Statistics, JMLR Workshop and Conference Proceedings Volume 5: AISTATS 2009 Attribution-Noncommercial-Share Alike 3.0 Unported http://creativecommons.org/licenses/by-nc-sa/3.0/ application/pdf Journal of Machine Learning Research MIT web domain |
| spellingShingle | Tenenbaum, Joshua B. Jonas, Eric M. Roy, Daniel Mansinghka, Vikash K. Exact and approximate sampling by systematic stochastic search |
| title | Exact and approximate sampling by systematic stochastic search |
| title_full | Exact and approximate sampling by systematic stochastic search |
| title_fullStr | Exact and approximate sampling by systematic stochastic search |
| title_full_unstemmed | Exact and approximate sampling by systematic stochastic search |
| title_short | Exact and approximate sampling by systematic stochastic search |
| title_sort | exact and approximate sampling by systematic stochastic search |
| url | http://hdl.handle.net/1721.1/60993 https://orcid.org/0000-0002-1925-2035 |
| work_keys_str_mv | AT tenenbaumjoshuab exactandapproximatesamplingbysystematicstochasticsearch AT jonasericm exactandapproximatesamplingbysystematicstochasticsearch AT roydaniel exactandapproximatesamplingbysystematicstochasticsearch AT mansinghkavikashk exactandapproximatesamplingbysystematicstochasticsearch |