Scaling Optimization Over Uncertainty via Compilation
summary
Presents a compilation pipeline that turns loop-free probabilistic programs into a new IR — binary decision diagrams weighted by a branch-and-bound semiring — enabling branch-and-bound search that prunes suboptimal assignments and supports staged queries mid-compilation. Implements two languages, dappl and pineappl, compiling to that IR; Rust code reuses the same algorithm for MMAP and decision-theoretic optimization and achieves state-of-the-art exact results, solving instances with ~500 random variables.
AI-written summary · about
chapters (16)
- 0:00Introduction
- 0:22Probabilistic programming modeling
- 1:24Medical and network diagnosis
- 2:28Current inference capabilities
- 3:09Marginal MAP and decision-making
- 4:53Why marginal MAP is hard
- 5:15Decision-making under uncertainty
- 7:22PEOPLE and Pineapple languages
- 8:03Branch-and-bound with knowledge compilation
- 9:06Compilation pipeline and weighted formulas
- 10:09Example program and formula
- 11:34Compiling to binary decision diagrams
- 12:15Naive marginal MAP algorithm
- 13:36Improved algorithm with reordering
- 14:40Upper bounds and scalability
- 15:01Summary
related talks
20mData-oriented Design for Differentiable, Probabilistic Programming
19mCompiling Probabilistic Programs for Variable Elimination with Information Flow
22mStochastic Lazy Knowledge Compilation for Inference in Discrete Probabilistic Programs
35mScalable structure learning and inference for domain-specific probabilistic prog
19mIncremental Computation for Efficient Programmable Inference in Probabilistic Programs
19mPanel: Compilation Frameworks
48mCross-Domain Compilation: Exploiting Synergies Across the CS Community
37mA Tour of Program Optimization