Extended semantics and inference for the Independent Choice Logic

Abstract

The Independent Choice Logic (ICL) is a language for expressing \nprobabilistic information in logic programming that adopts a distribution \nsemantics: an ICL theory defines a distribution over a set of possible worlds \nthat are normal logic programs. The probability of a query is then given by the \nsum of the probabilities of worlds where the query is true.\n\nThe ICL semantics requires the theories to be acyclic. This is a strong \nlimitation that rules out many interesting programs.\nIn this paper we present an extension of the ICL semantics that allows theories \nto be modularly acyclic.\n\nInference with ICL can be performed with the Cilog2 system that computes \nexplanations to queries and then makes them mutually incompatible by means of \nan iterative algorithm.\n\nWe propose the system PICL (for Probabilistic inference with ICL) that computes \nthe explanations to queries by means of a modification of SLDNF\\--resolution \nand then makes them mutually incompatible by means of Binary Decision Diagrams.\n\nPICL and Cilog2 are compared on problems that involve computing the probability \nof a connection between two nodes in biological graphs and social networks. \nPICL turned to be more efficient, handling larger networks/more complex queries \nin a shorter time than Cilog2. This is true both for marginal and for \nconditional queries.