Using Iterative Deepening for Probabilistic Logic Inference
Theofrastos Mantadelis and Ricardo Rocha
January 2017
Abstract
We present a novel approach that uses an iterative deepening algorithm
in order to perform probabilistic logic inference for ProbLog, a
probabilistic extension of Prolog. The most used inference method for
ProbLog is exact inference combined with tabling. Tabled exact
inference first collects a set of SLG~derivations which contain the
probabilistic structure of the ProbLog program including the
cycles. At a second step, inference requires handling these cycles in
order to create a non-cyclic Boolean representation of the
probabilistic information. Finally, the Boolean representation is
compiled to a data structure where inference can be performed in
linear time. Previous work has illustrated that there are two limiting
factors for ProbLog's exact inference. The first factor is the target
compilation language and the second factor is the handling of the
cycles. In this paper, we address the second factor by presenting an
iterative deepening algorithm which handles cycles and produces
solutions to problems that previously ProbLog was not able to
solve. Our experimental results show that our iterative deepening
approach gets approximate bounded values in almost all cases and in
most cases we are able to get the exact result for the same or one
lower scaling factor.
Bibtex
@InProceedings{mantadelis-padl17,
author = {T. Mantadelis and R. Rocha},
title = {{Using Iterative Deepening for Probabilistic Logic Inference}},
booktitle = {Proceedings of the 19th International Symposium on Practical Aspects of Declarative
Languages (PADL 2017)},
pages = {198--213},
number = {10137},
series = {LNCS},
publisher = {Springer},
editor = {Y. Lierler and W. Taha},
month = {January},
year = {2017},
address = {Paris, France},
}
Download Paper
PDF file
Springer