Probabilistic Programming Meets Automata Theory: Exact Inference using Weighted Automata
summary
Exact inference for a restricted class of discrete probabilistic programs using weighted automata that encode (possibly infinite-support distributions) as weighted multicounter automata; program statements map to automata operations like concatenation, intersection, sequential composition, scaling and normalization. The framework computes unnormalized posterior, then uses polynomial-time mass computation to normalize. Demonstrated on the goldfish/piranha example, producing posterior 2/3, and proven sound relative to existing automata constructions.
AI-written summary · about
chapters (14)
- 0:00Probabilistic programming meets automata
- 1:21Weighted automata overview
- 2:03Modeling distributions with automata
- 3:28Evaluating automata and distributions
- 4:29Basic automata operations
- 4:49Goldfish piranha problem solved
- 5:51Program modeling for inference
- 6:32Semantics to automaton
- 8:00Automaton validity check
- 8:42Normalizing posterior
- 9:23Goldfish piranha answer
- 9:44Summary and future work
- 10:06Conclusion and poster
- 10:28Q&A
related talks
19mOn Learning Polynomial Recursive Programs
15mScaling Exact Inference for Discrete Probabilistic Programs
31mProbabilistic Programming: The What, Why and How
01h 03mLogic and Probabilistic Circuits 2
11mExact Inference for Discrete Probabilistic Programs via Generating Functions
01h 03mA Personal Viewpoint on Probabilistic Programming
26mSemi-symbolic Inference for Efficient Streaming Probabilistic Programming
14mExact Probabilistic Inference Using Generating Functions