Extended semantics and inference for the Independent Choice Logic
- 17 July 2009
- journal article
- Published by Oxford University Press (OUP) in Logic Journal of the IGPL
- Vol. 17 (6), 589-629
- https://doi.org/10.1093/jigpal/jzp025
Abstract
The Independent Choice Logic (ICL), proposed by Poole, is a language for expressing probabilistic information in logic programming that adopts a distribution semantics: an ICL theory defines a distribution over a set of normal logic programs. The probability of a query is then given by the sum of the probabilities of the programs where the query is true. The ICL semantics requires the theory to be acyclic. This is a strong limitation that rules out many interesting programs. In this paper we present an extension of the ICL semantics that allows theories to be modularly acyclic. Inference with ICL can be performed with the Ailog2 system that computes explanations to queries and then makes them mutually incompatible by means of an iterative algorithm. We propose the system PICL (for Probabilistic inference with ICL) that computes the explanations to queries by means of a modification of SLDNF-resolution and then makes the explanations mutually incompatible by means of Binary Decision Diagrams. PICL and Ailog2 are compared on problems that involve computing the probability of a connection between two nodes in biological graphs and in social networks. Moreover, they are also applied to three games of dice. The problems considered are easily expressible in P-log, a probabilistic language based on Answer Set Programming. Therefore, the Plog system was also applied to the programs. PICL was able to handle larger problems than Ailog2 and Plog. Moreover, it was the fastest of the three algorithms except for one case of one of dice games.Keywords
This publication has 11 references indexed in Scilit:
- Probabilistic reasoning with answer setsTheory and Practice of Logic Programming, 2009
- Abducing through negation as failure: stable models within the independent choice logicThe Journal of Logic Programming, 2000
- Probabilistic datalog: Implementing logical information retrieval for advanced applicationsJournal of the American Society for Information Science, 2000
- The independent choice logic for modelling multiple agents under uncertaintyArtificial Intelligence, 1997
- A new definition of SLDNF-resolutionThe Journal of Logic Programming, 1994
- Probabilistic Horn abduction and Bayesian networksArtificial Intelligence, 1993
- Logic programming, abduction and probabilityNew Generation Computing, 1993
- Acyclic programsNew Generation Computing, 1991
- An analysis of first-order logics of probabilityArtificial Intelligence, 1990
- Concerning measures in first order calculiIsrael Journal of Mathematics, 1964