On the Implementation of the Probabilistic Logic Programming Language ProbLog

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

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.

Introduction

Combining logic programming with probability provides a powerful framework for modeling complex, uncertain domains, particularly in fields like bioinformatics. ProbLog extends Prolog by allowing facts to be annotated with probabilities, representing the likelihood of that fact being true in a randomly sampled world.

A sample ProbLog program represented as a directed graph with probabilistic edges.

The primary computational challenge in ProbLog is calculating the success probability of a query—the probability that it is provable in a randomly sampled program. This task is complicated by the disjoint-sum problem: different proofs for the same query often share common facts. Simply summing the probabilities of individual proofs leads to double-counting, making exact inference #P-complete. Previous implementations often struggled to scale beyond small examples, necessitating a more robust, high-performance architecture.

Implementation and Inference Methods

To address these challenges, the authors developed a high-performance implementation of ProbLog integrated with the YAP-Prolog engine. The system employs several key strategies:

1. Efficient Proof Search and Storage

Instead of relying on slow meta-interpreters, ProbLog facts are compiled into efficient YAP-Prolog code using source-to-source transformation. During execution, the system explores the SLD-tree to find all proofs for a given query.

SLD-tree for the query path(c,d) illustrating the search for proofs.

To manage memory and speed up subsequent calculations, proofs are stored in tries (prefix trees). This structure exploits the fact that many proofs share common prefixes, avoiding redundant storage and computation.

2. BDD-Based Exact Inference

To solve the disjoint-sum problem, the system converts the DNF formula representing the set of all proofs into a Binary Decision Diagram (BDD). BDDs provide a compact representation of Boolean functions; once constructed, the exact probability of the query can be computed in linear time relative to the size of the BDD. This approach allows the system to handle tens of thousands of proofs, far exceeding the capabilities of traditional inclusion-exclusion methods.

3. Scalable Approximation Algorithms

For massive networks where exact inference is infeasible, ProbLog offers several approximation techniques:

  • Bounded Approximation: Uses iterative deepening to find the most likely proofs, establishing both upper and lower bounds on the true probability.
  • K-Best: Computes the probability based on the $k$ most likely explanations.
  • Lazy Monte Carlo: Samples facts "on-the-fly" during proof attempts, avoiding the need to sample the entire database upfront.

Experimental Evaluation

The implementation was evaluated using the Biomine dataset, a large-scale biological network. The evaluation spanned three scales:

  • Small: 79 nodes, 144 edges (for exact inference benchmarks).
  • Medium: 5,220 nodes, 11,532 edges.
  • Biomine Full: Approximately 1,000,000 nodes and 6,000,000 edges.

The results demonstrated significant scalability. The system successfully queried the full 6-million-edge Biomine network, with $k$-best queries ($k=1024$) completing in 1.5 to 3.8 seconds. On smaller graphs, the new implementation achieved speedups of several orders of magnitude over previous meta-interpreter versions. While exact inference was competitive on small graphs, approximation methods proved essential as the network size increased.

Conclusion

The high-performance implementation of ProbLog demonstrates that probabilistic logic programming can scale to "Big Data" relational contexts. By leveraging BDDs for inference and integrating deeply with the YAP-Prolog engine, the system enables complex reasoning on million-node networks. Future work includes addressing the limitations of Monte Carlo sampling for low-probability queries and incorporating tabling (memoization) to further optimize proof search.

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},
}
Figure