Solving Marginal MAP Exactly by Probabilistic Circuit Transformations

on YouTube ↗37m

" summary

Presents an exact marginal MAP solver that never performs search but iteratively transforms probabilistic circuits by alternating prune irrelevant edges and split to introduce decision nodes. Key technical claim: compute a tight upper bound per edge in linear time via a single feedforward pass and a backward pass (edge bounds computed in one forward/backward pass), prune edges whose bound ≤ current lower bound, and iterate — at most one split per query variable (worst-case doubling per split). On 20 discrete benchmarks the method solves almost all large cases that search times out on, with the MPE-derived lower bound stabilizing quickly.

AI-written summary · about

" chapters (8)

1. 0:00Introduction to marginal map
2. 2:01Tractability and circuits
3. 4:32Proposed iterative approach
4. 7:34Bounding and pruning
5. 11:29Algorithm mechanisms
6. 15:29Iterative tightening process
7. 20:31Splitting and performance
8. 24:30Conclusion and Q&A

" related talks

• 01h 03mLogic and Probabilistic Circuits 2YooJung Choi · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 05mLogic and Probabilistic Circuits 1Guy Van den Broeck · Logic and Algorithms in Database Theory and AI Boot Camp
• 37mTractable Probabilistic CircuitsGuy Van den Broeck · Algorithmic Aspects of Causal Inference 2022
• 47mExploiting Combinatorial Structure in Constraint Programming: ...Gilles Pesant · Satisfiability: Theory, Practice, and Beyond 2023
• 51mRandom Projections for Probabilistic InferenceStefano Ermon · Uncertainty in Computation 2016
• 01h 01mLogic and Probabilistic Circuits 4Guy Van den Broeck · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 00mLogic and Probabilistic Circuits 3YooJung Choi · Logic and Algorithms in Database Theory and AI Boot Camp
• 20mStatic Posterior Inference of Bayesian Probabilistic Programming via Polynomial SolvingGuanyan Li, Peixin Wang, Hongfei Fu, Tengshun Yang, C.-H. Luke Ong · PLDI 2024