# Gibbs sampling in open-universe stochastic languages

### Nimar S Arora, Rodrigo de Salvo Braz, Erik Sudderth and Stuart J. Russell

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/EECS-2010-34

March 27, 2010

### http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-34.pdf

Languages for open-universe probability models (OUPMs) can represent situations with an unknown number of objects and identity uncertainty, which comprise a very important class of real-world applications. Current general-purpose inference methods for such languages are, however, much less efficient than those implemented for more restricted languages or for specific model classes. This paper goes some way to remedying the deficit by introducing, and proving correct, a general method for Gibbs sampling in partial worlds where model structure may vary across worlds. The method draws on and extends previous results on generic OUPM inference and on auxiliary-variable Gibbs sampling for non-parametric mixture models. It has been implemented for BLOG, a well-known OUPM language. Combined with compile-time optimizations, it yields very substantial speedups over existing methods on several test cases and substantially improves the practicality of OUPM languages generally.

BibTeX citation:

@techreport{Arora:EECS-2010-34, Author = {Arora, Nimar S and de Salvo Braz, Rodrigo and Sudderth, Erik and Russell, Stuart J.}, Title = {Gibbs sampling in open-universe stochastic languages}, Institution = {EECS Department, University of California, Berkeley}, Year = {2010}, Month = {Mar}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-34.html}, Number = {UCB/EECS-2010-34}, Abstract = {Languages for open-universe probability models (OUPMs) can represent situations with an unknown number of objects and identity uncertainty, which comprise a very important class of real-world applications. Current general-purpose inference methods for such languages are, however, much less efficient than those implemented for more restricted languages or for specific model classes. This paper goes some way to remedying the deficit by introducing, and proving correct, a general method for Gibbs sampling in partial worlds where model structure may vary across worlds. The method draws on and extends previous results on generic OUPM inference and on auxiliary-variable Gibbs sampling for non-parametric mixture models. It has been implemented for BLOG, a well-known OUPM language. Combined with compile-time optimizations, it yields very substantial speedups over existing methods on several test cases and substantially improves the practicality of OUPM languages generally.} }

EndNote citation:

%0 Report %A Arora, Nimar S %A de Salvo Braz, Rodrigo %A Sudderth, Erik %A Russell, Stuart J. %T Gibbs sampling in open-universe stochastic languages %I EECS Department, University of California, Berkeley %D 2010 %8 March 27 %@ UCB/EECS-2010-34 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/2010/EECS-2010-34.html %F Arora:EECS-2010-34