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

TL;DR

This paper introduces a novel framework for performing inference and learning in probabilistic logic programs (PLPs) by converting them into weighted Boolean formulas. This approach bridges the gap between PLP and graphical models, enabling the use of efficient, state-of-the-art solvers for tasks like marginal probability computation and parameter learning.

What Problem Does This Paper Address?

Probabilistic logic programming (PLP) aims to combine the expressiveness of logic programming with the uncertainty handling capabilities of probability. However, traditional PLP systems have limitations in performing standard probabilistic inference tasks like computing marginal probabilities given evidence (MARG) and finding the most probable explanation (MPE), especially when dealing with complex programs or partial observations. Furthermore, learning parameters from interpretations, a common practice in graphical models, has been underexplored in PLP. This paper addresses these gaps by adapting established graphical model inference and learning techniques to the PLP domain.

Methods

The core of the paper's contribution lies in a two-step approach for inference:

  1. Conversion to Weighted Boolean Formulas: A ProbLog program, along with queries and evidence, is converted into an equivalent weighted Boolean (propositional) formula. This conversion is crucial as it allows leveraging existing, highly optimized solvers. The process involves:
  2. Grounding: Identifying the "relevant ground program" by considering only the parts of the program necessary for the given queries and evidence. This is an optimization over considering the full program grounding.
  3. Rule Conversion: Transforming logic programming rules into an equivalent Boolean formula. For acyclic rules, Clark's completion is used, while for cyclic rules, more sophisticated proof-based or rule-based conversion algorithms are employed.
  4. Evidence Assertion and Weighting: Incorporating evidence as hard constraints and defining a weight function for literals based on probabilistic facts.
  5. Inference on Weighted Formulas: Once the weighted Boolean formula is constructed, standard inference tasks are reduced to well-studied problems:
  6. MARG (Marginal Probability) and EVID (Probability of Evidence): These are solved using Weighted Model Counting (WMC). The paper details how to compile the weighted formula into a d-DNNF (deterministic, decomposable negation normal form) and then into an arithmetic circuit, which allows for efficient WMC.
  7. MPE (Most Probable Explanation): This is reduced to weighted MAX-SAT, though the paper focuses more on MARG and EVID.

For learning, the paper proposes an Expectation-Maximization (EM) algorithm called LFI-ProbLog. This algorithm leverages the developed inference procedures within its expectation step to estimate the unknown probabilities of probabilistic facts from (potentially partial) interpretations.

Datasets

The paper evaluates its approach using the following datasets:

  • Smokers Example: A standard example used in the literature for probabilistic reasoning, modeling factors like stress and influence on smoking.
  • WebKB Dataset: A real-world dataset for collective classification, where web pages are classified based on their content and links.
  • Probabilistic Grids: A benchmark task for comparing inference algorithms, involving finding paths in a probabilistic graph.

Key Insights and Ideas

  • Bridging PLP and Graphical Models: The paper successfully demonstrates that complex inference and learning tasks in PLP can be effectively tackled by translating them into the well-understood framework of weighted Boolean formulas, thereby leveraging decades of research in graphical models and knowledge compilation.
  • "Inference Algorithms for Free": By converting PLP to weighted Boolean formulas, the authors gain access to a rich ecosystem of state-of-the-art solvers for WMC and MAX-SAT, effectively obtaining inference algorithms without needing to develop them from scratch for PLP.
  • d-DNNFs Outperform BDDs for Exact Inference: The experimental results highlight that using d-DNNFs for knowledge compilation leads to significantly better performance and scalability for exact inference in PLP compared to the previously standard BDDs, especially for rule-based formulas.
  • Relevant Ground Program (RGP) Efficiency: Using a "relevant ground program" (which prunes inactive and irrelevant rules) significantly reduces the size of the resulting Boolean formula, leading to more efficient inference, with minimal computational overhead during the grounding phase.
  • LFI-ProbLog for Learning: The proposed EM-based learning algorithm, LFI-ProbLog, is shown to be capable of recovering original probabilities from data, even with partial observations, and is competitive with existing state-of-the-art systems like Alchemy.

Key Results

  • Inference Speedup: The d-DNNF-based inference approach significantly outperforms previous PLP inference methods (using BDDs) and scales much better, enabling exact inference on larger and more complex problems. For instance, ProbLog2 (using d-DNNFs) was tractable up to distance 10 on the probabilistic grid query, while ProbLog1 (using BDDs) timed out beyond distance 6.
  • Conversion Algorithm Performance: The proof-based conversion algorithm produces more compact formulas than the rule-based one for smaller domains, leading to better inference results. However, for larger domains, the rule-based algorithm is more scalable.
  • Learning Accuracy: LFI-ProbLog demonstrated the ability to learn accurate probabilistic parameters from generated data, with performance metrics like Mean Absolute Error (MAE) and Kullback-Leibler (K-L) divergence approaching optimal values as more data was provided.
  • Real-World Performance: On the WebKB dataset, LFI-ProbLog showed competitive results against Alchemy, a state-of-the-art system for Markov Logic, especially when Alchemy was used with default parameters.

Limitations and Future Work

  • MPE Inference Focus: While the paper discusses MPE inference, its implementation and experimental evaluation primarily focus on MARG and EVID tasks.
  • Parameter Tuning for Learning: The paper notes that parameter tuning can significantly impact learning performance, as seen in the comparison with Alchemy*. Exploring more sophisticated prior settings for LFI-ProbLog is suggested as future work.
  • Computational Complexity: The complexity of parameter learning and inference is still worst-case exponential in the treewidth of the weighted Boolean formula, although knowledge compilation helps manage this for many practical cases.
  • Approximate Inference: While MC-SAT is mentioned for approximate inference, the paper's primary focus is on exact inference via knowledge compilation.
  • System Integration Challenges: The loosely-coupled nature of the ProbLog2 system, while offering flexibility, can lead to latency issues due to I/O and complexity in installation and configuration.

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 the conversion of the program and the queries and evidence to a weighted Boolean formula. This allows us to reduce 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