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 identity uncertainty. While such cases arise in a wide range of important real-world applications, existing general purpose inference methods for OUPMs are far less efficient than those available for more restricted languages and model classes. This paper goes some way to remedying this deficit by introducing, and proving correct, a generalization of Gibbs sampling to partial worlds with possibly varying model structure. Our approach draws on and extends previous generic OUPM inference methods, as well as auxiliary 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 substantial speedups over existing methods on several 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 identity uncertainty. While such cases arise in a wide range of important real-world applications, existing general purpose inference methods for OUPMs are far less efficient than those available for more restricted languages and model classes. This paper goes some way to remedying this deficit by introducing, and proving correct, a generalization of Gibbs sampling to partial worlds with possibly varying model structure. Our approach draws on and extends previous generic OUPM inference methods, as well as auxiliary 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 substantial speedups over existing methods on several 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 identity uncertainty. While such cases arise in a wide range of important real-world applications, existing general purpose inference methods for OUPMs are far less efficient than those available for more restricted languages and model classes. This paper goes some way to remedying this deficit by introducing, and proving correct, a generalization of Gibbs sampling to partial worlds with possibly varying model structure. Our approach draws on and extends previous generic OUPM inference methods, as well as auxiliary 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 substantial speedups over existing methods on several 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