The Independent Choice Logic (ICL) 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 possible worlds that are normal logic programs. The probability of a query is then given by the sum of the probabilities of worlds where the query is true. The ICL semantics requires the theories 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 Cilog2 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 them mutually incompatible by means of Binary Decision Diagrams. PICL and Cilog2 are compared on problems that involve computing the probability of a connection between two nodes in biological graphs and social networks. PICL turned to be more efficient, handling larger networks/more complex queries in a shorter time than Cilog2. This is true both for marginal and for conditional queries.

Extended Semantics and Inference for the Independent Choice Logic

RIGUZZI, Fabrizio
2009

Abstract

The Independent Choice Logic (ICL) 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 possible worlds that are normal logic programs. The probability of a query is then given by the sum of the probabilities of worlds where the query is true. The ICL semantics requires the theories 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 Cilog2 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 them mutually incompatible by means of Binary Decision Diagrams. PICL and Cilog2 are compared on problems that involve computing the probability of a connection between two nodes in biological graphs and social networks. PICL turned to be more efficient, handling larger networks/more complex queries in a shorter time than Cilog2. This is true both for marginal and for conditional queries.
2009
Riguzzi, Fabrizio
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in SFERA sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11392/1377241
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 16
social impact