Exact Inference for Discrete Probabilistic Programs via Generating Functions
summary
Exact inference method represents program state distributions with probability generating functions and transforms those closed-form PGFs across sampling, affine updates, branching and conditioning. Observations require computing Taylor coefficients — e.g. the 10th derivative to get P(X=10) and the 100th derivative for large observations — so automatic differentiation is critical; a custom manual automatic-differentiation and direct Taylor expansion implementation replaces slow PyTorch AD. Example: posterior expected value returns 9, an animal-population model computes masses and moments in ~1s; no loops or recursion, worst-case exponential blowup.
AI-written summary · about
chapters (11)
- 0:00Exact inference intro
- 1:07Poisson and binomial example
- 2:32Limitations of tools
- 3:13Language features
- 4:16Probability generating functions
- 5:43Transforming distributions
- 7:07Posterior probabilities and expectations
- 8:10Animal population tracking
- 9:15Implementation challenges
- 9:56Language limits and performance
- 10:17Summary
related talks
24mExact Bayesian Inference for Loopy Probabilistic Programs Using Generating Functions
31mProbabilistic Programming: The What, Why and How
15mScaling Exact Inference for Discrete Probabilistic Programs
24mCompiling with Generating Functions
19mGradInf: Gradient Estimation as Probabilistic Inference
32mProbabilistic and Differentiable Programming in Scientific Simulators
01h 03mA Personal Viewpoint on Probabilistic Programming
11mProbabilistic Programming Meets Automata Theory: Exact Inference using Weighted Automata