Probabilistic Reasoning by First-Order Model Counting

on YouTube ↗48m

" summary

Weighted first‑order model counting (WFOMC) reduces Markov logic networks to a sentence plus a weight function and exploits weight symmetry to perform lifted inference that computes partition functions and query probabilities far faster than grounding; FO2 sentences, safe UCQs and gamma‑acyclic queries are domain‑liftable, the shuffled‑deck example yields N! in polynomial time, and a learned MLN with 30k entities (≈900M ground vars) evaluates partition functions in seconds. Open‑world use adds lambda bounds for missing tuples; some three‑variable formulas are Sharp‑P1 hard and evidence breaks symmetries (mitigated by lifted MCMC using approximate symmetries).

AI-written summary · about

" chapters (38)

1. 0:00Intro
2. 0:25What we'd like to do...
3. 0:46Einstein is in the knowledge Graph
4. 4:54Statistical Relational Learning
5. 5:28What's Going On Here?
6. 5:50Tractable Reasoning
7. 6:29First-Order Model Counting
8. 7:14Weighted First Order Model Counting Model solution to first-order logic formula
9. 8:07Probabilistic Database Rules
10. 8:31Asymmetric WFOMC Rules
11. 9:29Example MLN to WFOMC
12. 12:52FOMC Inference
13. 15:18Playing Cards Revisited
14. 17:36Why not do propositional WMC?
15. 18:03Deck of Cards Graphically
16. 19:01Observations
17. 20:42Tractable Classes
18. 25:50Open World DB
19. 27:02Intuition
20. 27:50Bayesian Learning Loop
21. 28:27Problem: Broken Learning Loop
22. 29:14Problem: Curse of Superlinearity
23. 30:30Open-World Prob. Databases
24. 32:50Closed-World Lifted Query Eval
25. 34:08Open-World Lifted Query Eval
26. 35:02Complexity Results
27. 36:53Lifted Parameter Learning
28. 37:47Lifted Structure Learning
29. 38:07Generalized Model Counting
30. 38:23Weighted Model Integration
31. 38:50Probabilistic Programming
32. 39:10Probabilistic Functional Programming
33. 39:28First-Order Knowledge Compilation
34. 40:01Exchangeability
35. 40:37Results for Symmetric Inference
36. 41:01Conclusions
37. 41:33Long-Term Outlook
38. 46:11Approximate Symmetries in MCMC

" related talks

• 37mFirst-Order Model Counting and SamplingOndrej Kuzelka · Probabilistic Circuits and Logic 2023
• 01h 02mOut-of-Distribution Generalization as Reasoning: Are LLMs Competitive?Les Valiant · Emerging Generalization Settings 2024
• 11mProbabilistic Programming Meets Automata Theory: Exact Inference using Weighted AutomataTobias Winkler, Dominik Geißler · LAFI 2026
• 48mWeighted Model IntegrationZhe Zeng · Probabilistic Circuits and Logic 2023
• 36mEnhanced and Efficient Reasoning in Large Language ModelsLes Valiant · The Role of TCS in Modern Machine Learning
• 01h 05mLogic and Probabilistic Circuits 1Guy Van den Broeck · Logic and Algorithms in Database Theory and AI Boot Camp
• 24mHigher order programming with probabilistic effects: A model of stochastic memo...Younesse Kaddar, Sam Staton · HOPE 2022
• 01h 03mLogic and Probabilistic Circuits 2YooJung Choi · Logic and Algorithms in Database Theory and AI Boot Camp