Compiling with Generating Functions
summary
A compiler called Genie compiles probabilistic programs to generating functions as a deterministic target (PIL → DIL) and proves correctness against a measure-transformer denotational semantics, with artifacts available. It handles infinite-support Poisson loops and a loop-sum that Dice cannot express, and computes exact posteriors far faster than Pyro’s importance sampling (Pyro shows convergence only after ~10 minutes while Genie returns the exact result immediately). Benchmarks show Dice’s runtime grows exponentially in grid side squared while Genie grows exponentially in side length, and the compiler keeps GFs factorized and marginalizes variables when they expire to reduce complexity.
AI-written summary · about
chapters (18)
- 0:00Introduction
- 2:31Probabilistic programming challenges
- 3:39Probability generating functions
- 5:49Multivariate GFs and independence
- 6:33Arithmetic to generating functions
- 7:15Unbounded loops with GFs
- 8:18Exploiting independence for scalability
- 10:48Early marginalization
- 12:56Avoiding differentiation
- 14:42Compiler correctness and semantics
- 16:51Benchmark results
- 17:35Packet model vs importance sampling
- 18:20Comparison with model checkers
- 19:23Bayesian network performance
- 20:50Conclusion
- 21:35Q&A: Marginalization
- 22:40Q&A: Financial contracts
- 23:25Q&A: Approximate inference
related talks
14mExact Probabilistic Inference Using Generating Functions
24mExact Bayesian Inference for Loopy Probabilistic Programs Using Generating Functions
11mExact Inference for Discrete Probabilistic Programs via Generating Functions
15mScaling Exact Inference for Discrete Probabilistic Programs
05mOn Iteration in Discrete Probabilistic Programming
36mProbabilistic scripts for automating common-sense tasks
32mProbabilistic and Differentiable Programming in Scientific Simulators
43mThe Power of Probabilistic Programming