Logic and Probabilistic Circuits 3

on YouTube ↗01h 00m

" summary

Defines SDD-style circuits with structured decomposability and a stronger partition (strong) determinism, proves that computing P(formula) requires compiling both formula and distribution into circuits that are decomposable and aligned to the same vtree, and gives a polynomial-time feedforward evaluation DP that sums at ORs and multiplies at ANDs down to literal probabilities. Shows consistency (weak decomposability) suffices for MAP, gives exponential separations (SDD vs OBDD) and hardness results for turning deterministic/consistent circuits into decomposable ones.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 0:30Binary Decision Diagrams
3. 2:13Structured Decomposability
4. 3:50Strong Determinism
5. 14:25Inference
6. 18:07Dynamic Programming
7. 21:04Combining
8. 21:41Trackability
9. 22:40Circuits
10. 39:58Consistency
11. 47:11Marginal Maps
12. 48:18Summary
13. 56:16Compatibility

" related talks

• 43mMarginal Determinism in Structured Decomposable CircuitsBenjie Wang · Probabilistic Circuits and Logic 2023
• 37mTractable Probabilistic CircuitsGuy Van den Broeck · Algorithmic Aspects of Causal Inference 2022
• 43mControlling Probabilistic Systems Under Partial ObservationNathalie Bertrand · Uncertainty in Computation 2016
• 01h 01mBrief Tutorial on Probabilistic DatabasesDan Suciu · Uncertainty in Computation 2016
• 24mHigher order programming with probabilistic effects: A model of stochastic memo...Younesse Kaddar, Sam Staton · HOPE 2022
• 01h 06mIntroduction to Causal Graphical Models: Graphs, d-separation, do-calculusSpencer Gordon · Causality Boot Camp
• 19mPositive Almost-Sure Termination – Complexity and Proof RulesRupak Majumdar, V.R. Sathiyanarayana · POPL 2024
• 37mSolving Marginal MAP Exactly by Probabilistic Circuit TransformationsYooJung Choi · Probabilistic Circuits and Logic 2023