Reasoning on Logic Programs with Annotated Disjunctions

Article type: Research Article

Authors: Bragaglia, Stefano

Affiliations: DEIS, University of Bologna, Viale Risorgimento, Bologna, Italy. Email: [email protected]

Abstract: Probabilistic Inductive Logic Programming and Statistical Relational Learning are families of techniques that are exploited in Machine Learning applications to perform advanced tasks in several domains. Every day the size and complexity of such problems increases and advanced, expressive and efficient tools are needed to successfully solve them. The literature proposes several algorithms to cope with these problems, each of them with its own quirks and perks. Among various solutions, Logic Programming with Annotated Disjunctions (LPAD) is one of the more attractive formalisms, thanks to the expressiveness and readability of its language. Unfortunately, its most advanced implementations are lacking efficient features and techniques that have been introduced for other formalisms, such as ProbLog. In this work, after introducing LPADs and an inference algorithm for computing the probability of a query, we investigate four different approximated algorithms, inspired by similar work done in ProbLog. In particular, we present each algorithm and we evaluate its performances on real and artificial datasets. The results show that our approaches have performances that are usually in line with ProbLog. The Monte Carlo algorithm, however, has performances that are better than the exact approach in terms of both the maximum size of the problems and the execution time, with a neglectable loss in the accuracy of the result.

Keywords: Probabilistic Inductive Logic Programming, Logic Programs with Annotated Disjunctions, ProbLog

DOI: 10.3233/IA-2012-0029

Journal: Intelligenza Artificiale, vol. 6, no. 1, pp. 77-96, 2012