Download PDF

Efficient Algorithms for Prolog Based Probabilistic Logic Programming (Efficiënte algoritmen voor prolog gebaseerd probabilistisch logisch programmeren)

Publication date: 2012-11-30

Author:

Mantadelis, Theofrastos

Keywords:

ProbLog, Probabilistic Logic Programming, Statistical Relational Learning, Artificial Intelligence

Abstract:

The integration of probabilistic reasoning with logic programming has become one of the challenges in Artificial Intelligence. Lately, a lot of Probabilistic Logic Programming (PLP) formalisms have surfaced. Given that PLP is the combination of logic programming and probabilities which are two very different fields, it is expected that researchers from several fields come up with different approaches to tackle the presented challenges. This has resulted in a new discipline called Probabilistic Logic Learning (PLL) or Statistical Relational Learning (SRL) and a very active research community.Within this community, ProbLog a probabilistic extension of Prolog, has appeared. ProbLog was motivated by the task of mining links in large probabilistic graphs. The simple but powerful ProbLog formulation was extended in order to support inference on several different models. Soon ProbLog evolved into a general purpose probabilistic programming language that provides infrastructure for many PLL/SRL tasks. The two most critical aspects of a PLP language are its expression power, and its scalability over common PLL problems.This thesis focuses on the extension and implementation of ProbLog. Tabling is a well known method for avoiding re-computation in logic programming; we present how tabling can be implemented for ProbLog. Tabling has significant benefits for performance and also allows ProbLog to handle cyclic programs. In order for the ProbLog system to perform inference, it manipulates large Boolean formulae. We present the manipulation of Boolean formulae and several novel algorithms that improve the performance of this task. Furthermore, we present patterns, called AND/OR-clusters, that can be used to reduce a Boolean formula to an equivalent one. Besides performance improvements of the ProbLog system, we also present several novel extensions to the ProbLog language, such as: general negation, probabilistic meta calls and ProbLog answers. Finally, we present two applications of ProbLog that use several of the features we have contributed to ProbLog.