Pruning Strategies for the Efficient Traversal of the Search Space in PILP Environments

Joana Côrte-Real, Inês Dutra and Ricardo Rocha

2021

---

Abstract

Probabilistic Inductive Logic Programming (PILP) is a Statistical Relational Learning technique which extends Inductive Logic Programming by considering probabilistic data. The ability to use probabilities to represent uncertainty comes at the cost of an exponential evaluation time when composing theories to model the given problem. For this reason, PILP systems rely on various pruning strategies in order to reduce the search space. However, to the best of the authors’ knowledge, there has been no systematic analysis of the different pruning strategies, how they impact the search space, and how they interact with one another.
This work presents a unified representation for PILP pruning strategies which enables end-users to understand how these strategies work both individually and combined, and to make an informed decision on which pruning strategies to select so as to best achieve their goals. The performance of pruning strategies is evaluated both time and quality-wise in two state-of-the-art PILP systems with datasets from three different domains. Besides analysing the performance of the pruning strategies, we also illustrate the utility of PILP in one of the application domains, which is a real world application.

Bibtex

@Article{corte-real-kais21,
  author =    {J. Côrte-Real and I. Dutra and R. Rocha},
  title =     {{Pruning Strategies for the Efficient Traversal of the Search Space in PILP Environments}},
  journal =   {Journal of Knowledge and Information Systems},
  pages =     {3183--3215},
  volume =    {63},
  month =     {November},
  year =      {2021},
}

Download Paper

PDF file
Springer