Marginal Determinism in Structured Decomposable Circuits

on YouTube ↗43m

" summary

Introduces md-vtrees, a vtree annotated with per-node support labels that syntactically guarantees which q‑sets are marginally deterministic for any structured decomposable circuit that respects it. Shows an efficient algorithm to enumerate those q‑sets, a procedure to enforce a given family of q‑sets on any vtree, and proofs that some annotations are inadmissible (so PSDD/strong determinism is improvable). Combines md‑vtree reasoning with compositional inference to derive new polytime results — including first polytime algorithms for certain causal queries.

AI-written summary · about

" chapters (11)

1. 0:00Introduction to topic
2. 0:24Probabilistic query types
3. 2:20Formalisms for tractability
4. 6:36Defining a circuit framework
5. 9:05Probabilistic circuit basics
6. 13:28MAP and marginal map
7. 16:30Defining marginal determinism
8. 23:32MDB trees as templates
9. 30:18MDB tree properties
10. 35:18Causal inference application
11. 38:34Future work and discussion

" related talks

• 01h 00mLogic and Probabilistic Circuits 3YooJung Choi · Logic and Algorithms in Database Theory and AI Boot Camp
• 01h 06mIntroduction to Causal Graphical Models: Graphs, d-separation, do-calculusSpencer Gordon · Causality Boot Camp
• 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
• 01h 06mIntroduction to Causal Graphical Models: Graphs, d-separation, do-calculusSpencer Gordon · Causality Boot Camp
• 01h 08mIntroduction to Causal Graphical Models: Graphs, d-separation, do-calculusSpencer Gordon · Causality Boot Camp
• 37mTractable Probabilistic CircuitsGuy Van den Broeck · Algorithmic Aspects of Causal Inference 2022
• 44mMarginal DAG Models Equivalent to Another DAGRobin Evans · Quantum Physics and Statistical Causal Models (Simons Institute workshop, 2022)