TL;DR
This paper details the high-performance implementation of ProbLog, a probabilistic extension of Prolog. By tightly integrating with the YAP-Prolog engine and leveraging Binary Decision Diagrams (BDDs) to solve the #P-complete "disjoint-sum problem," the authors enable probabilistic reasoning on massive biological networks containing millions of edges.
What Problem Does This Paper Address?
Combining logic programming with probability is powerful for modeling complex, uncertain domains like bioinformatics. However, calculating the success probability of a query (the probability that it is provable in a randomly sampled program) is computationally grueling.
The core challenge is the disjoint-sum problem: different proofs for the same query often share facts. You can't simply sum their probabilities because you'd be double-counting the overlapping parts. This makes exact inference #P-complete. Previous implementations relied on slow meta-interpreters or methods that didn't scale beyond tiny examples. This paper aims to make ProbLog fast enough for real-world "Big Data" relational contexts.
Methods
The authors introduce several architectural and algorithmic improvements:
- YAP-Prolog Integration: Instead of a slow meta-interpreter, they use source-to-source transformation to compile ProbLog facts into efficient YAP-Prolog code, utilizing YAP’s advanced indexing.
- Trie-Based Proof Storage: Proofs are stored in tries (prefix trees). This exploits the fact that many proofs share common prefixes, significantly reducing memory usage and speeding up the hand-off to the probability calculator.
- BDD-Based Inference: To solve the disjoint-sum problem, the DNF formula representing all proofs is converted into a Binary Decision Diagram (BDD). Once a BDD is built, calculating the exact probability becomes a simple linear-time traversal.
- Approximation Algorithms:
- Bounded Approximation: Uses iterative deepening to find the most likely proofs first, providing both an upper and lower bound on the true probability.
- K-Best: Computes the probability using only the $k$ most likely explanations.
- Lazy Monte Carlo: Instead of sampling the entire million-fact database, it samples facts "on-the-fly" only as they are encountered during a proof attempt.
Datasets
The evaluation centers on the Biomine project, a massive biological network of genes, proteins, and phenotypes.
- Small: 79 nodes, 144 edges (used for exact inference benchmarks).
- Medium: 5,220 nodes, 11,532 edges.
- Biomine Full: ~1,000,000 nodes and ~6,000,000 edges.
Key Insights and Ideas
- The Power of BDDs: While the disjoint-sum problem is hard, BDDs are remarkably efficient at representing the Boolean structure of proofs in relational graphs. They can handle tens of thousands of proofs where traditional inclusion-exclusion methods would fail after just ten.
- Backtracking is a Feature: By using Prolog’s native backtracking and global variables, the system avoids recomputing shared proof prefixes, making the "logical" part of the search much faster.
- Lazy Sampling is Essential: In massive graphs, the "standard" Monte Carlo approach of generating a full sample program is a non-starter. Lazy sampling (only tossing the "probabilistic coin" when a fact is actually needed for a proof) is the only way to scale to millions of facts.
Key Results
- Scalability: The system successfully queried the full Biomine network (6M edges). For example, finding the connection probability between specific genes took roughly 1.5 to 3.8 seconds using the $k$-best approach ($k=1024$).
- Speedup: The new implementation achieved speedups of several orders of magnitude compared to the previous meta-interpreter-based version.
- Exact vs. Approx: On the "Small" graph, exact inference was surprisingly competitive with approximation, taking less than a second. On the "Medium" graph, exact inference became infeasible, but Bounded Approximation and Monte Carlo provided tight intervals quickly.
Limitations and Future Work
- Unlikely Queries: Monte Carlo inference struggles when the success probability is extremely low, as it requires a massive number of samples to reach a tight confidence interval.
- Non-Ground Facts: The current Monte Carlo implementation has limitations with non-ground probabilistic facts (facts with variables), requiring them to be ground at call-time.
- Tabling: The authors suggest that incorporating tabling (memoization of sub-goals) could further optimize the search for proofs, a technique that has proven successful in other logic systems like PRISM.
Summary updated