2013 Poster Sessions : Just-in-time Compilation of MCMC for Probabilistic Programs

Student Name : Ling Yang
Advisor : Noah Goodman
Research Areas: Artificial Intelligence
We present a dynamic compilation technique for increasing the efficiency of Markov Chain Monte Carlo (MCMC) algorithms for inference in models specified via a probabilistic program. Our technique is based on the fact that only some random choices affect the control flow of program execution. We refer to these as structural choices, and the other choices as non-structural. Partial evaluation of the acceptance probability computation with respect to structural choices thus leaves a straight-line program with a static set of non-structural choices---a trace. We dynamically create these traces as each set of structural choices is encountered at run-time. Because the traces do not contain control flow or iteration, we may apply aggressive optimizations. In particular, we apply incrementalization: for each random choice made in the trace, we extract the subset of commands in the trace that must be recomputed when the choice changes. In total, this provides just-in-time compilation of the score computation, needed for MCMC updates, into optimized code specialized for each individual proposal. We evaluate this technique on a simple open-universe model and two standard BUGS test models. We achieve orders of magnitude speedup and become competitive with more specialized and less expressive statistical languages such as JAGS.

Lingfeng Yang is a Ph. D candidate at Stanford University, under the supervision of Dr. Patrick Hanrahan, working in computer graphics, human-computer interaction, and programming languages. He received his BS in mathematics and computer science from the California Institute of Technology.