The Approximate Implication Problem For Probabilistic Graphical Models

on YouTube ↗48m

" summary

Defines approximate implication as a linear inequality between mutual informations and asks when exact implications relax to such bounds, proving general impossibility but positive guarantees for common cases: d-separation sound and complete for directed graphical models with a tight lambda = 1 bound for recursive bases and for saturated CIs plus functional dependencies, a |A|·|B| bound for general CIs, and links the acyclic schema error measure J to the model KL divergence (J = KL divergence). Implements a miner that finds hundreds of decomposable models and shows about 10% join error can yield ~80% storage savings.

AI-written summary · about

" chapters (24)

1. 0:00Intro
2. 0:34Outline Background
3. 1:03Conditional Independence and PGMs • A conditional independence is an assertion
4. 1:40Integrity Constraints in Relational Databases
5. 3:29Conditional Independence for Relational DBS
6. 5:21d-Separation as Implication
7. 6:31Some Notation
8. 7:15The Implication Problem: What is known
9. 8:20Approximate Conditional Independencies . Current systems of inference assume antecedents
10. 12:18Approximate Implication Does not Hold In General
11. 13:02Approximate Implication: Results
12. 15:05Entropic Functions
13. 16:13Proof Technique
14. 21:03Proof Intuition: Positive I-Measure
15. 24:02Decomposing a Relation
16. 26:31Acyclic Schemas have Join Trees
17. 28:09Saturated CIS → Acyclic Schemas
18. 29:51Information Theory for Acyclic Schemas
19. 32:35Approximations
20. 33:19Strategy
21. 33:39Too Many Saturated CIS...
22. 34:29Evaluation
23. 35:18Nursery dataset: 12960 tuples, 9atts
24. 36:32Future Work

" related talks

• 01h 06mIntroduction to Causal Graphical Models: Graphs, d-separation, do-calculusSpencer Gordon · Causality 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
• 31mStrong Data Processing Inequalities and Estimation with ConstraintsJohn Duchi · Information Theory, Learning and Big Data (Simons Institute, 2015)
• 44mMarginal DAG Models Equivalent to Another DAGRobin Evans · Quantum Physics and Statistical Causal Models (Simons Institute workshop, 2022)
• 01h 05mLogic and Probabilistic Circuits 1Guy Van den Broeck · Logic and Algorithms in Database Theory and AI Boot Camp
• 47mApproximate Lifted Inference with Probabilistic DatabasesWolfgang Gatterbauer · Uncertainty in Computation 2016
• 47mLearning Probabilistic Models for Graph Partitioning in the Presence of NoiseAravindan Vijayaraghavan · Learning, Algorithm Design and Beyond Worst-Case Analysis