c3: lightweight incrementalized mcmc for probabilistic programs using continuations and callsite caching

02 January 2017

notes on (Ritchie et al., 2016).

summary

this paper proposes a way to make lightweight metropolis hastings (lmh) more efficient. the high level idea is to save as much computation as possible in addition to the reuse of random choices in the original lmh algorithm. the main ideas are

• source transformations.
  • caching. wraps every function call inside a cache function.
  • function tagging. tags functions (function definitions) with a lexically-unique id and free variables by wrapping them inside tag function.
  • address computation. The lmh thing.
• short-circuit on function entry. if the function is cached, reuse the result if
  1. function arguments are the same, and
  2. function itself is the same.
• short-circuit on function exit. if, after the metropolis hastings step has been made, control returns to a function whose return value is unchanged, exit computation early by calling the exit (or result in case of anglican) continuation.

there are further optimizations such as automatic cache adaptation, thunking, copy-on-write (only write changes to cache if proposal is accepted), and using hash-tables for storing random choices.

experiments show promising results.

note to self

• most important sections are 4, 4.1, 4.2, 4.3
• understanding: 7/10
• rating: 10/10
• should be reimplemented in anglican.
  • lmh addressing must be implemented (?).
  • how does one detect when contorl is returned to a function whose return value is unchanged (for short-circuiting on function exit)?
• questions:
  • how do the acceptance probabilities change from the lmh ones?

---

references

1. Ritchie, D., Stuhlmüller, A., & Goodman, N. D. (2016). C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching. Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS). http://arxiv.org/abs/1509.02151
   • Bib

   @article{ritchie2016c3,
     author = {Ritchie, Daniel and Stuhlm\"{u}ller, Andreas and Goodman, Noah D.},
     title = {C3: Lightweight Incrementalized MCMC for Probabilistic Programs using Continuations and Callsite Caching},
     booktitle = {Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS)},
     year = {2016},
     keywords = {probabilistic programming, inference, mcmc, metropolis-hastings},
     url = {http://arxiv.org/abs/1509.02151}
   }
   

[back]