Approximate Lifted Inference with Probabilistic Databases
summary
Presents an approximate inference pipeline that converts query lineage into compact representations and then applies sampling plus structural shortcuts to evaluate probabilistic conjunctive queries over databases. Uses lineage provenance to find minimal plans and exploit functional dependencies, implements five evaluation methods and reports empirical speedups (roughly 10× speedup in some cases) versus naive Monte Carlo; typically uses 1,000–50,000 samples, yields provable lower bounds from minimal plans and much faster, similarly accurate probability estimates when values are near 0 or 1.
AI-written summary · about
chapters (9)
- 0:00Approximate inference intro
- 1:29Motivation for lifted inference
- 10:09Exact to approximate methods
- 16:30Guaranteed bounds in counting
- 22:58Conjunctive queries and lineage
- 33:30Lower bounds via plans and Monte Carlo
- 38:12Independent sampling methods
- 43:14Approximate inference without learning
- 44:41Summary
related talks
01h 03mAn Overview of Probabilistic Programming
21mProbabilistic Inference for Datalog with Correlated Inputs
35mScalable structure learning and inference for domain-specific probabilistic prog
42mBayesDB: Query the Probable Implications of Data
15mScaling Exact Inference for Discrete Probabilistic Programs
14mALERT: Machine Learning-Enhanced Risk Estimation for Databases Supporting...
20mGenSQL: A Probabilistic Programming System for Querying Generative Models of Database(…)
22mStochastic Lazy Knowledge Compilation for Inference in Discrete Probabilistic Programs