Probabilistic Inference for Datalog with Correlated Inputs
summary
A new Datalog extension called Praline implements probabilistic inference that accounts for arbitrary input correlations by reducing exact inference to a constrained optimization problem and by providing a scalable δ-exact approximate algorithm that combines constraint solving, static analysis, and iterative refinement. Exact inference only solves about 40% of benchmarks; the δ-exact method handles all benchmarks, finishes under 100s for 76% of cases, and reports an average bound error around 0.1%. Implementation ties Soufflé-based Datalog solving to a constraint solver and an optimizer.
AI-written summary · about
chapters (11)
- 0:00Datalog programs
- 1:06Probabilistic Datalog matters
- 2:32Correlated input facts
- 4:17Exact inference for bounds
- 7:12Approximate inference with delta-exact
- 9:42Correlation type inference
- 11:27Fréchet inequalities for bounds
- 13:14Refining probability bounds
- 15:44Implementation and benchmarks
- 17:10Summary and demo
- 17:31Q&A
related talks
47mApproximate Lifted Inference with Probabilistic Databases
01h 01mBrief Tutorial on Probabilistic Databases
33mCombined Approximations for Probabilistic Query Evaluation: An Intensional Approach
13mAccelerating Program Analyses in Datalog by Merging Library Facts
36mOptimizing Relational Programs II
38mThe Intensional-Extensional Problem in Probabilistic Databases
42mBayesDB: Query the Probable Implications of Data
26mDebugging Large-Scale Datalog: A Scalable Provenance Evaluation Strategy