Compiling Probabilistic Programs for Variable Elimination with Information Flow
summary
This paper presents a compiler, Maple, that uses an information-flow type system to partition and eliminate discrete latent variables in recursive probabilistic programs, producing pure programs that compute marginal likelihoods. It proves semantic preservation via a measure-theoretic noninterference proof, recovers known PTIME algorithms for recursive models, and shows compilation time scales with inference problem size; Maple handles recursive HMMs that existing PPLs time out on but requires termination of all recursion paths and does not exploit local factor structure.
AI-written summary · about
chapters (7)
- 0:00Introduction
- 2:29PPL compilers for HMM
- 5:19Variable elimination via partitioning
- 8:34Information flow typing
- 12:45Maple correctness and scalability
- 15:15Limitations and future work
- 15:37Conclusion and Q&A
related talks
15mScaling Optimization Over Uncertainty via Compilation
19mIncremental Computation for Efficient Programmable Inference in Probabilistic Programs
17mLazy Knowledge Compilation for Discrete PPLs
27mPartial Evaluation of Reversible Flowchart Programs
06mStatic Delayed Sampling for Probabilistic Programming Languages
05mOn Iteration in Discrete Probabilistic Programming
20mVerified Density Compilation for a Probabilistic Programming Language
24mPractical Probabilistic Programming with Figaro