Logic Journal of IGPL Advance Access originally published online on July 17, 2009
Logic Journal of IGPL 2009 17(6):589-629; doi:10.1093/jigpal/jzp025
Extended semantics and inference for the Independent Choice Logic
ENDIF, Università di Ferrara, Via Saragat, 1, 44100 Ferrara, Italy.
E-mail: fabrizio.riguzzi{at}unife.it
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.
Key Words: Probabilistic Logic Programming • Independent Choice Logic • Modularly acyclic programs • SLDNF-Resolution
Received for publication 8 December 2008.
References
-
1 Carnap R. Logical Foundations of Probability (1950) University of Chicago Press.
2 Gaifman H. Concerning measures in first order calculi, Israel J. Math. (1964) 2:1–18.[CrossRef]
3 Scott D, Krauss P. Assigning probabilities to logical formulas—Hintikka J, Suppes P, eds. (1966) North-Holland: Aspects of Inductive Logic.
4 Halpern J. An analysis of first-order logics of probability, Artif. Intell. (1990) 46(3):311–350.[CrossRef]
5 Getoor L, Taskar B, eds. An Introduction to Statistical Relational Learning (2007) MIT Press.
6 Raedt L, Frasconi P, Kersting K, Muggleton S, eds. Probabilistic Inductive Logic Programming – Theory, & Applications (2008) Springer. Vol. 4911 of LNCS.
7 Dantsin E. Probabilistic logic programs, & their semantics. (1991) in: Russian Conference on Logic Programming. Springer. 152–164. Vol. 592 of LNCS.
8 Poole D. The independent choice logic for modelling multiple agents under uncertainty, Artif. Intell. (1997) 94(1-2):7–56.[CrossRef]
9 Sato T, Kameya Y. Prism: A language for symbolic-statistical modeling. (1997) in: International Joint Conference on Artificial Intelligence. 1330–1339.
10 Fuhr N. Probabilistic datalog: Implementing logical information retrieval for advanced applications, J. Am. Soc. Inf. Sci. (2000) 51(2):95–110.[CrossRef][Web of Science]
11 Kersting K, Raedt L. Towards combining inductive logic programming and Bayesian networks, in: Inductive Logic Programming (2001) Springer. Vol. 2157 of LNAI.
12 Vennekens J, Verbaeten S, Bruynooghe M. Logic programs with annotated disjunctions, in: International Conference on Logic Programming (2004) Springer. 195–209. Vol. 3131 of LNCS.
13 De Raedt L, Kimmig A, Toivonen H. Problog: A probabilistic prolog and its application in link discovery. (2007) in: International Joint Conference on Artificial Intelligence. 2462–2467.
14 Baral C, Gelfond M, Rushton N. Probabilistic reasoning with answer sets, The. Pra. Log. Program. (2009) 9(1):57–144. doi:10.1017/S1471068408003645.[CrossRef]
15 Poole D. Probabilistic horn abduction and bayesian networks. Artif. Intell. (1993) 64(1):81–129.[CrossRef]
16 Sato T. A statistical learning method for logic programs with distribution semantics. (1995) in: International Conference on Logic Programming. 715–729.
17 Poole D. Logic programming, abduction and probability – a top-down anytime algorithm for estimating prior and posterior probabilities. New Gener. Comput. (1993) 11(3):377–400.[CrossRef]
18 Poole D. Abducing through negation as failure: stable models within the independent choice logic, J. Log. Program. (2000) 44(1-3):5–35.[CrossRef]
19 Clark K. Negation as failure (1978) Plenum Press. in: Logic and Databases.
20 Gelfond M, Lifschitz V. The stable model semantics for logic programming (1988) 1070–1080. in: International Conference and Symposium on Logic Programming.
21 Van Gelder A, Ross K, Schlipf J. The well-founded semantics for general logic programs. J. ACM (1991) 38(3):620–650.
22 Apt K, Doets K. A new definition of SLDNF-resolution, J. Log. Program. (1994) 18(2):177–190.[CrossRef]
23 Muggleton S. Learning stochastic logic programs, Electron. Trans. Artif. Intell. (2000) 4(B):141–153.
24 Apt K, Bezem M. Acyclic programs, New Gener. Comput. (1991) 9(3/4):335–364.[CrossRef]
25 Ross K. in: Principles of Database Systems. In: Modular acyclicity and tail recursion in logic programs (1991) New York, NY, USA: ACM. 92–101. doi:10.1145/113413.113422.
26 Kolmogorov A. Foundations of the Theory of Probability (1950) New York: Chelsea Publishing Company.
27 Bryant R. Graph-based algorithms for boolean function manipulation, IEEE Trans. on Comput. (1986) 35(8):677–691.[CrossRef]
28 Thayse A, Davio M, Deschamps J. Optimization of multivalued decision algorithms. (1978) in: International Symposium on Multiple-Valued Logic. Los Alamitos, CA, USA: IEEE Computer Society Press. 171–178.
29 Miller D, Drechsler R. On the construction of multiple-valued decision diagrams. (2002) in: IEEE International Symposium on Multiple-Valued Logic. IEEE Computer Society Press. 245–253.
30 Sato T, Kameya Y. Parameter learning of logic programs for symbolic-statistical modeling, J. Artif. Intell. Res. (2001) 15:391–454.
31 Vennekens J, Verbaeten S. Logic programs with annotated disjunctions. In: Tech. Rep. (2003) CW386, K. U. Leuven. http://www.cs.kuleuven.ac.be/~joost/techrep.ps.
32 Pearl J. Causality. (2000) Cambridge University Press.
33 Riguzzi F. A top down interpreter for LPAD and CP-logic. (2007) Springer. 109–120. in: Congress of the Italian Association for Artificial Intelligence, no. 4733 in LNAI, doi:10.1007/978-3-540-74782-6\_11. http://www.springerlink.com/content/v7m1k21607xhh365/.
34 Riguzzi F. Inference with logic programs with annotated disjunctions under the well founded semantics. (2008) in: International Conference on Logic Programming. Springer. 667–771. no. 5366 in LNCS, doi:10.1007/978-3-540-89982-2\_54. http://www.springerlink.com/content/247533616617llm8/.
35 Riguzzi F. The SLGAD procedure for inference on Logic Programs with Annotated Disjunctions. In: RCRA workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion—Gavanelli M, Mancini T, eds. (2009) no. 451 in CEUR Workshop Proceedings, Sun SITE Central Europe, http://ceur-ws.org/Vol-451/paper15riguzzi.pdf.
36 Riguzzi F. SLGAD resolution for inference on Logic Programs with Annotated Disjunctions. Journal of Algorithms in Logic, Informatics and Cognition. in press.
37 Sevon P, Eronen L, Hintsanen P, Kulovesi K, Toivonen H. Link discovery in graphs derived from biological databases. In: International Workshop on Data Integration in the Life Sciences (2006) Springer. 35–49. Vol. 4075 of LNCS.
38 Lu Q, Getoor L. Link-based classification. (2003) in: International Conference on Machine Learning. AAAI Press. 496–503.
CiteULike 
Connotea 
Del.icio.us What's this?
| ||||||||||||||||||||||||||||||||||||||||||||||