On the implementation of the probabilistic logic programming language ProbLog

Angelika Kimmig, Bart Demoen, Luc De Raedt, Vítor Santos Costa, Ricardo Rocha

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

Abstract

The past few years have seen a surge of interest in the field of probabilistic logic learning and statistical relational learning. In this endeavor, many probabilistic logics have been developed. ProbLog is a recent probabilistic extension of Prolog motivated by the mining of large biological networks. In ProbLog, facts can be labeled with probabilities. These facts are treated as mutually independent random variables that indicate whether these facts belong to a randomly sampled program. Different kinds of queries can be posed to ProbLog programs. We introduce algorithms that allow the efficient execution of these queries, discuss their implementation on top of the YAP-Prolog system, and evaluate their performance in the context of large networks of biological entities.
BibTeX
@inproceedings{kimmig2011implementation,
  author = {Angelika Kimmig and Bart Demoen and Luc De Raedt and Vítor Santos Costa and Ricardo Rocha},
  title = {{On the implementation of the probabilistic logic programming language ProbLog}},
  booktitle = {Theory Pract. Log. Program},
  year = {2011},
  url = {https://openreview.net/forum?id=LZxe0pE9Xez},
}

Loading related content...

Figure