ProbLog: a probabilistic prolog and its application in link discovery

TLDR

The paper introduces ProbLog, a probabilistic extension of Prolog, and presents an effective solver for computing query success probabilities. ProbLog defines a distribution over logic programs by assigning independent probabilities to clauses, evaluates query success probabilities via SLD‑resolution combined with Boolean formula probability techniques, and implements an approximation algorithm using iterative deepening and binary decision diagrams. Experiments on real biological networks show that ProbLog effectively discovers links, demonstrating its practical usefulness.

Abstract

We introduce ProbLog, a probabilistic extension of Prolog. A ProbLog program defines a distribution over logic programs by specifying for each clause the probability that it belongs to a randomly sampled program, and these probabilities are mutually independent. The semantics of ProbLog is then defined by the success probability of a query, which corresponds to the probability that the query succeeds in a randomly sampled program. The key contribution of this paper is the introduction of an effective solver for computing success probabilities. It essentially combines SLD-resolution with methods for computing the probability of Boolean formulae. Our implementation further employs an approximation algorithm that combines iterative deepening with binary decision diagrams. We report on experiments in the context of discovering links in real biological networks, a demonstration of the practical usefulness of the approach.