SLGAD Resolution for Inference on Logic Programs with Annotated Disjunctions

• Autorzy: Riguzzi F.
• Języki publikacji: EN

Abstrakty

EN

Logic Programs with Annotated Disjunctions (LPADs) allow to express probabilistic information in logic programming. The semantics of an LPAD is given in terms of the well-founded models of the normal logic programs obtained by selecting one disjunct from each ground LPAD clause. Inference on LPADs can be performed using either the system Ailog2, that was developed for the Independent Choice Logic, or SLDNFAD, an algorithm based on SLDNF. However, both of these algorithms run the risk of going into infinite loops and of performing redundant computations. In order to avoid these problems, we present SLGAD resolution that computes the (conditional) probability of a ground query from a range-restricted LPAD and is based on SLG resolution for normal logic programs. As SLG, it uses tabling to avoid some infinite loops and to avoid redundant computations. The performances of SLGAD are evaluated on classical benchmarks for normal logic programs under the well-founded semantics, namely a 2-person game and the ancestor relation, and on games of dice. SLGAD is compared with Ailog2 and SLDNFAD on the problems in which they do not go into infinite loops, namely those that are described by a modularly acyclic program. The results show that SLGAD is sometimes slower than Ailog2 and SLDNFAD but, if the program requires the repeated computations of the same goals, as for the dice games, then SLGAD is faster than both.

Słowa kluczowe

EN

Probabilistic Logic Programming; well-founded semantics; Logic Programs with Annotated Disjunctions; SLG Resolution

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2010
• Tom: Vol. 102, nr 3/4
• Strony: 429--466
• Opis fizyczny: Bibliogr. 32 poz., rys.

Twórcy

autor

Riguzzi F.

• ENDIF, Universita di Ferrara, Via Saragat, 1, 44100 Ferrara, Italy,

Bibliografia

• [1] Apt, K. R., Bezem, M.: Acyclic Programs, New Gener. Comput., 9(3/4), 1991, 335-364.
• [2] Bratko, I.: PROLOG Programming for Artificial Intelligence, Addison-Wesley Longman, 1990.
• [3] Castro, L. F., Swift, T., Warren, D. S.: Suspending and Resuming Computations in Engines for SLG Evaluation, Practical Aspects of Declarative Languages, 2257, Springer, 2002.
• [4] Chen, W., Swift, T., Warren, D. S.: Efficient Top-Down Computation of Queries under the Well-Founded Semantics, J. Log. Program., 24(3), 1995, 161-199.
• [5] Chen, W., Warren, D. S.: Query Evaluation under the Well Founded Semantics, Principles of Database Systems, ACM Press, 1993.
• [6] Chen, W., Warren, D. S.: Tabled Evaluation With Delaying for General Logic Programs, J. ACM, 43(1), 1996, 20-74.
• [7] Clark, K. L.: Negation as Failure, Logic and Data Bases, Plenum Press, 1977.
• [8] Dantsin, E.: Probabilistic Logic Programs and their Semantics, Russian Conference on Logic Programming, 592, Springer, 1991.
• [9] De Raedt, L., Kimmig, A., Toivonen, H.: ProbLog: A Probabilistic Prolog and Its Application in Link Discovery., International Joint Conference on Artificial Intelligence, 2007.
• [10] van Emden, M. H., Clark, K. L.: The logic of two-person games, in: Micro-PROLOG: Programming in Logic, Prentice-Hall, 1984, 320-340.
• [11] Fuhr, N.: Probabilistic datalog: Implementing logical information retrieval for advanced applications, J. of the Am. Soc. for Information Science, 51(2), 2000, 95-110.
• [12] Gelder, A. V., Ross, K. A., Schlipf, J. S.: Unfounded Sets and Well-Founded Semantics for General Logic Programs, Principles of Database Systems, ACM Press, 1988.
• [13] Gelfond, M., Lifschitz, V.: The Stable Model Semantics for Logic Programming, International Conference on Logic Programming, MIT Press, 1988.
• [14] Jaeger, M.: Model-Theoretic Expressivity Analysis, Probabilistic Inductive Logic Programming - Theory and Applications, 4911, Springer, 2008.
• [15] Jaeger, M., Lidman, P., Mateo, J. L.: Comparative Evaluation of PL languages, Mining and Learning with Graphs, 2007.
• [16] Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, 1988, ISBN 1558604790.
• [17] Poole, D.: The Independent Choice Logic for Modelling Multiple Agents under Uncertainty, Artif. Intell., 94(1-2), 1997, 7-56.
• [18] Poole, D.: Abducing through negation as failure: stable models within the independent choice logic, J. Log. Program., 44(1-3), 2000, 5-35.
• [19] Przymusinski, T. C.: The Well-Founded Semantics Coincides with the Three-Valued Stable Semantics, Fundam. Inform., 13(4), 1990, 445-463.
• [20] Riguzzi, F.: Extended Semantics and Inference for the Independent Choice Logic, Log. J. IGPL, 17(6), 2009, 589-629.
• [21] Riguzzi, F.: A Top Down Interpreter for LPAD and CP-logic, Congress of the Italian Association for Artificial Intelligence, 4733, Springer, 2007.
• [22] Ross, K. A.: Modular acyclicity and tail recursion in logic programs, Principles of Database Systems, ACM Press, 1991, ISBN 0-89791-430-9.
• [23] Santos Costa, V., Page, D., Qazi, M., Cussens, J.: CLP(BN): Constraint Logic Programming for Probabilistic Knowledge, Uncertainty in Artificial Intelligence, Morgan Kaufmann, 2003.
• [24] Sato, T.: A Statistical Learning Method for Logic Programs with Distribution Semantics, International Conference on Logic Programming, MIT Press, 1995.
• [25] Sato, T., Kameya, Y.: PRISM: A Language for Symbolic-Statistical Modeling, International Joint Conference on Artificial Intelligence, Morgan Kaufmann, 1997.
• [26] Sato, T., Kameya, Y.: Parameter Learning of Logic Programs for Symbolic-Statistical Modeling, J. Artif. Intell. Res., 15, 2001, 391-454.
• [27] Swift, T.: A New Formulation of Tabled Resolution with Delay, Portuguese Conference on Artificial Intelligence, 1695, Springer, 1999.
• [28] Van Gelder, A., Ross, K. A., Schlipf, J. S.: The Well-founded Semantics for General Logic Programs, J. of the ACM, 38(3), 1991, 620-650.
• [29] Vennekens, J., Denecker, M., Bruynooghe, M.: Representing Causal Information about a Probabilistic Process, European Conference on Logics in Artificial Intelligence, 4160, Springer, September 2006.
• [30] Vennekens, J., Verbaeten, S.: Logic Programs With Annotated Disjunctions, Technical Report CW386, K. U. Leuven, 2003.
• [31] Vennekens, J., Verbaeten, S., Bruynooghe, M.: Logic Programs With Annotated Disjunctions, International Conference on Logic Programming, 3131, Springer, 2004.
• [32] Zhang, N. L., Poole, D.: Exploiting Causal Independence in Bayesian Network Inference, J. Artif. Intell. Res., 5, 1996, 301-328.