C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching

Daniel Ritchie, Andreas Stuhlmüller, Noah Goodman
Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, PMLR 51:28-37, 2016.

Abstract

Lightweight, source-to-source transformation approaches to implementing MCMC for probabilistic programming languages are popular for their simplicity, support of existing deterministic code, and ability to execute on existing fast runtimes. However, they are also inefficient, requiring a complete re-execution of the program on every Metropolis Hastings proposal. We present a new extension to the lightweight approach, C3, which enables efficient, incrementalized re-execution of MH proposals. C3 is based on two core ideas: transforming probabilistic programs into continuation passing style (CPS), and caching the results of function calls. It is particularly effective at speeding up recursive programs with many local latent variables. We show that on several common models, C3 reduces proposal runtime by 20-100x, in some cases reducing runtime complexity from linear in model size to constant. We also demonstrate nearly an order of magnitude speedup on a complex inverse procedural modeling application.

Cite this Paper

BibTeX
@InProceedings{pmlr-v51-ritchie16, title = {C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching}, author = {Ritchie, Daniel and Stuhlmüller, Andreas and Goodman, Noah}, booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics}, pages = {28--37}, year = {2016}, editor = {Gretton, Arthur and Robert, Christian C.}, volume = {51}, series = {Proceedings of Machine Learning Research}, address = {Cadiz, Spain}, month = {09--11 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v51/ritchie16.pdf}, url = {https://proceedings.mlr.press/v51/ritchie16.html}, abstract = {Lightweight, source-to-source transformation approaches to implementing MCMC for probabilistic programming languages are popular for their simplicity, support of existing deterministic code, and ability to execute on existing fast runtimes. However, they are also inefficient, requiring a complete re-execution of the program on every Metropolis Hastings proposal. We present a new extension to the lightweight approach, C3, which enables efficient, incrementalized re-execution of MH proposals. C3 is based on two core ideas: transforming probabilistic programs into continuation passing style (CPS), and caching the results of function calls. It is particularly effective at speeding up recursive programs with many local latent variables. We show that on several common models, C3 reduces proposal runtime by 20-100x, in some cases reducing runtime complexity from linear in model size to constant. We also demonstrate nearly an order of magnitude speedup on a complex inverse procedural modeling application.} }
Endnote
%0 Conference Paper %T C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching %A Daniel Ritchie %A Andreas Stuhlmüller %A Noah Goodman %B Proceedings of the 19th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2016 %E Arthur Gretton %E Christian C. Robert %F pmlr-v51-ritchie16 %I PMLR %P 28--37 %U https://proceedings.mlr.press/v51/ritchie16.html %V 51 %X Lightweight, source-to-source transformation approaches to implementing MCMC for probabilistic programming languages are popular for their simplicity, support of existing deterministic code, and ability to execute on existing fast runtimes. However, they are also inefficient, requiring a complete re-execution of the program on every Metropolis Hastings proposal. We present a new extension to the lightweight approach, C3, which enables efficient, incrementalized re-execution of MH proposals. C3 is based on two core ideas: transforming probabilistic programs into continuation passing style (CPS), and caching the results of function calls. It is particularly effective at speeding up recursive programs with many local latent variables. We show that on several common models, C3 reduces proposal runtime by 20-100x, in some cases reducing runtime complexity from linear in model size to constant. We also demonstrate nearly an order of magnitude speedup on a complex inverse procedural modeling application.
RIS
TY - CPAPER TI - C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching AU - Daniel Ritchie AU - Andreas Stuhlmüller AU - Noah Goodman BT - Proceedings of the 19th International Conference on Artificial Intelligence and Statistics DA - 2016/05/02 ED - Arthur Gretton ED - Christian C. Robert ID - pmlr-v51-ritchie16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 51 SP - 28 EP - 37 L1 - http://proceedings.mlr.press/v51/ritchie16.pdf UR - https://proceedings.mlr.press/v51/ritchie16.html AB - Lightweight, source-to-source transformation approaches to implementing MCMC for probabilistic programming languages are popular for their simplicity, support of existing deterministic code, and ability to execute on existing fast runtimes. However, they are also inefficient, requiring a complete re-execution of the program on every Metropolis Hastings proposal. We present a new extension to the lightweight approach, C3, which enables efficient, incrementalized re-execution of MH proposals. C3 is based on two core ideas: transforming probabilistic programs into continuation passing style (CPS), and caching the results of function calls. It is particularly effective at speeding up recursive programs with many local latent variables. We show that on several common models, C3 reduces proposal runtime by 20-100x, in some cases reducing runtime complexity from linear in model size to constant. We also demonstrate nearly an order of magnitude speedup on a complex inverse procedural modeling application. ER -
APA
Ritchie, D., Stuhlmüller, A. & Goodman, N.. (2016). C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 51:28-37 Available from https://proceedings.mlr.press/v51/ritchie16.html.

Related Material