Inference and learning in probabilistic logic programs using weighted Boolean formulas

Daan Fierens, Guy Van den Broeck, Joris Renkens, Dimitar Sht. Shterionov, Bernd Gutmann, Ingo Thon, Gerda Janssens, Luc De Raedt

Abstract

Probabilistic logic programs are logic programs in which some of the facts are annotated with probabilities. This paper investigates how classical inference and learning tasks known from the graphical model community can be tackled for probabilistic logic programs. Several such tasks, such as computing the marginals given evidence and learning from (partial) interpretations, have not really been addressed for probabilistic logic programs before. The first contribution of this paper is a suite of efficient algorithms for various inference tasks. It is based on a conversion of the program and the queries and evidence to a weighted Boolean formula. This allows us to reduce the inference tasks to well-studied tasks such as weighted model counting, which can be solved using state-of-the-art methods known from the graphical model and knowledge compilation literature. The second contribution is an algorithm for parameter estimation in the learning from interpretations setting. The algorithm employs Expectation Maximization and is built on top of the developed inference algorithms. The proposed approach is experimentally evaluated, showing that the inference algorithms improve upon the state-of-the-art and that it is indeed possible to learn the parameters of a probabilistic logic program from interpretations.

Introduction: Bridging the Gap in Probabilistic Logic

For years, two communities—Statistical Relational Learning (SRL) and Probabilistic Logic Programming (PLP)—studied similar problems from different angles. SRL focused on extending graphical models (like Bayesian networks) with relational logic, while PLP extended logic programming (like Prolog) with probabilities.

However, PLP faced significant hurdles that limited its practical application. Most systems could only handle one query at a time and struggled with "evidence" (observed facts). Furthermore, many required programs to be acyclic or follow strict "mutual exclusiveness" rules. Finally, there wasn't a robust way to learn program parameters (probabilities) from "interpretations"—the standard way data is represented in machine learning.

Table 1: Comparison of ProbLog2 with other probabilistic logic programming systems and Markov Logic Networks (MLN).

The authors aim to bridge this gap by creating a system (ProbLog2) that handles cycles, multiple queries, and complex evidence by treating logic as a preprocessing step for probabilistic math. As shown in Table 1, ProbLog2 addresses several limitations of its predecessor and related systems, particularly regarding evidence on arbitrary atoms and multiple queries.

Methods: The Two-Step Pipeline

The core of the paper is a two-step framework that converts complex logic programs into weighted Boolean formulas, reducing probabilistic inference to weighted model counting (WMC).

1. Conversion to Weighted Boolean Formulas

  • Grounding: The system first identifies the "Relevant Ground Program" (RGP), pruning rules that don't affect the specific query or evidence.
  • Logic to Formula: It converts logic rules into a propositional Boolean formula. Crucially, it handles cycles (recursive rules) by using sophisticated conversion algorithms from the Answer Set Programming (ASP) community to "break" loops.
  • Weighting: It assigns weights to literals based on the probabilities defined in the program. This defines a distribution over "total choices," or possible worlds.
Table 2: An example of a probability distribution over total choices (C) for a probabilistic logic program.

2. Inference via Knowledge Compilation

The Boolean formula is compiled into a d-DNNF (deterministic, decomposable negation normal form). Unlike the previously standard BDDs (Binary Decision Diagrams), d-DNNFs are more compact and allow for highly efficient WMC. This reduces the "hard" probabilistic problem to a polynomial-time traversal of a circuit.

3. Learning (LFI-ProbLog)

The authors introduce an Expectation-Maximization (EM) algorithm for parameter estimation. It uses the inference engine to "fill in" missing data in partial interpretations (E-step) and then updates the fact probabilities to maximize likelihood (M-step).

Experimental Evaluation

The approach was evaluated on three primary benchmarks:

  • Social Networks (Smokers): A classic SRL dataset modeling how stress and friendship influence smoking and cancer.
  • Collective Classification (WebKB): Real-world data consisting of university webpages. The task is to predict a page's class based on words and links.
  • Probabilistic Grids: A synthetic benchmark used to test how systems handle long-distance pathfinding in a graph, which is notoriously difficult for traditional graphical models.

Key Results

ProbLog2 scaled significantly better than its predecessor, ProbLog1. On the Grid dataset, ProbLog1 failed at a path distance of 7, while ProbLog2 handled distances of 10+ with ease. Furthermore, on the WebKB dataset, the LFI-ProbLog algorithm was competitive with Alchemy (the flagship Markov Logic Network system), outperforming it in several test folds when using default settings.

Discussion and Insights

The primary "aha moment" of this research is that d-DNNFs significantly outperform BDDs for exact inference in PLP. While BDDs were the standard for a decade, they often suffer from memory explosions that d-DNNFs avoid. By viewing the logic program as a way to generate a Boolean formula, the framework can leverage any state-of-the-art SAT-based solver or model counter.

However, limitations remain. The complexity of the compilation step is still worst-case exponential in the treewidth of the Boolean formula. For very dense, highly connected networks, exact inference remains a challenge. Future work may focus on reducing I/O latency between the pipeline's components and automating prior selection for the EM algorithm.

Summary updated

Abstract

Probabilistic logic programs are logic programs in which some of the facts are annotated with probabilities. This paper investigates how classical inference and learning tasks known from the graphical model community can be tackled for probabilistic logic programs. Several such tasks such as computing the marginals given evidence and learning from (partial) interpretations have not really been addressed for probabilistic logic programs before. The first contribution of this paper is a suite of efficient algorithms for various inference tasks. It is based on a conversion of the program and the queries and evidence to a weighted Boolean formula. This allows us to reduce the inference tasks to well-studied tasks such as weighted model counting, which can be solved using state-of-the-art methods known from the graphical model and knowledge compilation literature. The second contribution is an algorithm for parameter estimation in the learning from interpretations setting. The algorithm employs Expectation Maximization, and is built on top of the developed inference algorithms. The proposed approach is experimentally evaluated. The results show that the inference algorithms improve upon the state-of-the-art in probabilistic logic programming and that it is indeed possible to learn the parameters of a probabilistic logic program from interpretations.
BibTeX
@inproceedings{fierens2015inference,
  author = {Daan Fierens and Guy Van den Broeck and Joris Renkens and Dimitar Sht. Shterionov and Bernd Gutmann and Ingo Thon and Gerda Janssens and Luc De Raedt},
  title = {{Inference and learning in probabilistic logic programs using weighted Boolean formulas}},
  booktitle = {Theory Pract. Log. Program},
  year = {2015},
  url = {https://openreview.net/forum?id=UYT2fVFLxRv},
}
Figure