Gibbs sampling in open-universe stochastic languages

Nimar Arora, Erik Sudderth, Rodrigo de Salvo Braz, Stuart Russell
Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, PMLR R8:30-39, 2010.

Abstract

Languages for open-universe probabilistic models (OUPMs) can represent situations with an unknown number of objects and iden- tity uncertainty. While such cases arise in a wide range of important real-world appli- cations, existing general purpose inference methods for OUPMs are far less efficient than those available for more restricted lan- guages and model classes. This paper goes some way to remedying this deficit by in- troducing, and proving correct, a generaliza- tion of Gibbs sampling to partial worlds with possibly varying model structure. Our ap- proach draws on and extends previous generic OUPM inference methods, as well as aux- iliary variable samplers for nonparametric mixture models. It has been implemented for BLOG, a well-known OUPM language. Combined with compile-time optimizations, the resulting algorithm yields very substan- tial speedups over existing methods on sev- eral test cases, and substantially improves the practicality of OUPM languages generally.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR8-arora10a, title = {{G}ibbs sampling in open-universe stochastic languages}, author = {Arora, Nimar and Sudderth, Erik and Braz, Rodrigo de Salvo and Russell, Stuart}, booktitle = {Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence}, pages = {30--39}, year = {2010}, editor = {Grünwald, Peter and Spirtes, Peter}, volume = {R8}, series = {Proceedings of Machine Learning Research}, month = {08--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r8/main/assets/arora10a/arora10a.pdf}, url = {https://proceedings.mlr.press/r8/arora10a.html}, abstract = {Languages for open-universe probabilistic models (OUPMs) can represent situations with an unknown number of objects and iden- tity uncertainty. While such cases arise in a wide range of important real-world appli- cations, existing general purpose inference methods for OUPMs are far less efficient than those available for more restricted lan- guages and model classes. This paper goes some way to remedying this deficit by in- troducing, and proving correct, a generaliza- tion of Gibbs sampling to partial worlds with possibly varying model structure. Our ap- proach draws on and extends previous generic OUPM inference methods, as well as aux- iliary variable samplers for nonparametric mixture models. It has been implemented for BLOG, a well-known OUPM language. Combined with compile-time optimizations, the resulting algorithm yields very substan- tial speedups over existing methods on sev- eral test cases, and substantially improves the practicality of OUPM languages generally.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Gibbs sampling in open-universe stochastic languages %A Nimar Arora %A Erik Sudderth %A Rodrigo de Salvo Braz %A Stuart Russell %B Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2010 %E Peter Grünwald %E Peter Spirtes %F pmlr-vR8-arora10a %I PMLR %P 30--39 %U https://proceedings.mlr.press/r8/arora10a.html %V R8 %X Languages for open-universe probabilistic models (OUPMs) can represent situations with an unknown number of objects and iden- tity uncertainty. While such cases arise in a wide range of important real-world appli- cations, existing general purpose inference methods for OUPMs are far less efficient than those available for more restricted lan- guages and model classes. This paper goes some way to remedying this deficit by in- troducing, and proving correct, a generaliza- tion of Gibbs sampling to partial worlds with possibly varying model structure. Our ap- proach draws on and extends previous generic OUPM inference methods, as well as aux- iliary variable samplers for nonparametric mixture models. It has been implemented for BLOG, a well-known OUPM language. Combined with compile-time optimizations, the resulting algorithm yields very substan- tial speedups over existing methods on sev- eral test cases, and substantially improves the practicality of OUPM languages generally. %Z Reissued by PMLR on 04 October 2026.
APA
Arora, N., Sudderth, E., Braz, R.d.S. & Russell, S.. (2010). Gibbs sampling in open-universe stochastic languages. Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R8:30-39 Available from https://proceedings.mlr.press/r8/arora10a.html. Reissued by PMLR on 04 October 2026.

Related Material