Incremental Computation for Efficient Programmable Inference in Probabilistic Programs
summary
Compiles probabilistic programs to deterministic density functions, then applies a compositional incrementalization based on the incremental lambda calculus with updaters to reuse intermediate results; implements unordered iteration and fresh-name trace types so removing a cluster changes only that cluster’s entries via unordered maps and stable IDs. Prototype in Julia runs several MCMC kernels on multiple models, outperforms full recomputation and Gen’s fine-grained scheme, and matches hand-written asymptotic scaling while enabling denotational logical-relations correctness proofs.
AI-written summary · about
chapters (20)
- 0:00Incremental computation intro
- 1:05Probabilistic programs
- 2:27Challenges in incrementalization
- 3:08Deterministic incrementalization
- 3:30Probabilistic clustering example
- 5:14Markov chain Monte Carlo for inference
- 7:01Need for incremental density
- 7:23Program transformations overview
- 7:43Incremental lambda calculus
- 9:05Change types for efficiency
- 10:50Updaters and their advantages
- 12:36Incremental length example
- 13:18How transformation works
- 14:23Density transformation
- 15:25Trace types
- 16:50Fresh name generation
- 17:12Correctness proofs
- 17:34Experimental results
- 17:55Summary and future
- 18:15Q&A
related talks
12mIncremental Density Computation for Efficient Programmable Inference
22mStochastic Lazy Knowledge Compilation for Inference in Discrete Probabilistic Programs
20mProbabilistic Programming with Stochastic Probabilities
35mScalable structure learning and inference for domain-specific probabilistic prog
20mVerified Density Compilation for a Probabilistic Programming Language
05mOn Iteration in Discrete Probabilistic Programming
31mProbabilistic Programming: The What, Why and How
24mHigher order programming with probabilistic effects: A model of stochastic memo...