Combining probabilistic logic programming with the power of maximum entropy.

*(English)*Zbl 1085.68170Summary: This paper is on the combination of two powerful approaches to uncertain reasoning: logic programming in a probabilistic setting, on the one hand, and the information-theoretical principle of maximum entropy, on the other hand. More precisely, we present two approaches to probabilistic logic programming under maximum entropy. The first one is based on the usual notion of entailment under maximum entropy, and is defined for the very general case of probabilistic logic programs over Boolean events. The second one is based on a new notion of entailment under maximum entropy, where the principle of maximum entropy is coupled with the closed world assumption from classical logic programming. It is only defined for the more restricted case of probabilistic logic programs over conjunctive events. We then analyze the nonmonotonic behavior of both approaches along benchmark examples and along general properties for default reasoning from conditional knowledge bases. It turns out that both approaches have very nice nonmonotonic features. In particular, they realize some inheritance of probabilistic knowledge along subclass relationships, without suffering from the problem of inheritance blocking and from the drowning problem. They both also satisfy the property of rational monotonicity and several irrelevance properties. We finally present algorithms for both approaches, which are based on generalizations of recent techniques for probabilistic logic programming under logical entailment. The algorithm for the first approach still produces quite large weighted entropy maximization problems, while the one for the second approach generates optimization problems of the same size as the ones produced in probabilistic logic programming under logical entailment.

##### MSC:

68T37 | Reasoning under uncertainty in the context of artificial intelligence |

68N17 | Logic programming |

##### Keywords:

Probabilistic logic programming; Maximum entropy; Conditional constraint; Probabilistic reasoning; Nonmonotonic reasoning; Algorithms
PDF
BibTeX
XML
Cite

\textit{G. Kern-Isberner} and \textit{T. Lukasiewicz}, Artif. Intell. 157, No. 1--2, 139--202 (2004; Zbl 1085.68170)

Full Text:
DOI

##### References:

[1] | Andersen, K.A; Hooker, J.N, Bayesian logic, Decision support systems, 11, 191-210, (1994) |

[2] | Apt, K.R, Logic programming, (), 493-574, Chapter 10 · Zbl 0900.68136 |

[3] | Bacchus, F; Grove, A; Halpern, J.Y; Koller, D, From statistical knowledge bases to degrees of belief, Artificial intelligence, 87, 75-143, (1996) |

[4] | Batsell, R; Brenner, L; Osherson, D.N; Tsavachidis, S; Vardi, M.Y, Eliminating incoherence from subjective estimates of chance, (), 353-364 |

[5] | Benferhat, S; Dubois, D; Prade, H, The possibilistic handling of irrelevance in exception-tolerant reasoning, Ann. math. artificial intelligence, 35, 29-61, (2002) · Zbl 1001.68139 |

[6] | Benferhat, S; Saffiotti, A; Smets, P, Belief functions and default reasoning, Artificial intelligence, 122, 1-2, 1-69, (2000) · Zbl 0948.68112 |

[7] | Boole, G, An investigation of the laws of thought, on which are founded the mathematical theories of logic and probabilities, (1958), Dover New York, Reprint |

[8] | Carnap, R, Logical foundations of probability, (1950), University of Chicago Press Chicago, IL · Zbl 0040.07001 |

[9] | Charnes, A; Cooper, W.W, Programming with linear fractional functionals, Naval research logistics quaterly, 9, 181-186, (1962) · Zbl 0127.36901 |

[10] | Cheeseman, P, A method of computing generalized Bayesian probability values for expert systems, (), 198-202 |

[11] | Chvátal, V, Linear programming, (1983), Freeman San Francisco, CA · Zbl 0318.05002 |

[12] | Dekhtyar, A; Subrahmanian, V.S, Hybrid probabilistic programs, J. logic programming, 43, 3, 187-250, (2000) · Zbl 0955.68020 |

[13] | Dekhtyar, M.I; Dekhtyar, A; Subrahmanian, V.S, Hybrid probabilistic programs: algorithms and complexity, (), 160-169 |

[14] | Delgrande, J; Pelletier, F.J, Formal senses of relevance in default reasoning, Erkenntnis, 49, 137-173, (1998) |

[15] | Dubois, D; Prade, H, Non-standard theories of uncertainty in plausible reasoning, () · Zbl 0962.68160 |

[16] | Dubois, D; Prade, H; Godo, L; López de Màntaras, R, Qualitative reasoning with imprecise probabilities, J. intell. inform. syst., 2, 319-363, (1993) |

[17] | Dubois, D; Prade, H; Toucas, J.-M, Inference with imprecise numerical quantifiers, (), 53-72, Chapter 3 |

[18] | Eiter, T; Gottlob, G, Identifying the minimal transversals of a hypergraph and related problems, SIAM J. comput., 24, 6, 1278-1304, (1995) · Zbl 0842.05070 |

[19] | Eiter, T; Lukasiewicz, T, Default reasoning from conditional knowledge bases: complexity and tractable cases, Artificial intelligence, 124, 2, 169-241, (2000) · Zbl 0952.68139 |

[20] | Fagin, R; Halpern, J.Y; Megiddo, N, A logic for reasoning about probabilities, Inf. comput., 87, 78-128, (1990) · Zbl 0811.03014 |

[21] | V. Fischer, M. Schramm, tabl—A tool for efficient compilation of probabilistic constraints, Technical Report TUM-I9636, TU München, 1996 |

[22] | Frisch, A.M; Haddawy, P, Anytime deduction for probabilistic logic, Artificial intelligence, 69, 93-122, (1994) · Zbl 0809.03016 |

[23] | Gaifman, H, Concerning measures in first order calculi, Israel J. math., 2, 1-18, (1964) · Zbl 0192.03302 |

[24] | Goldszmidt, M; Morris, P; Pearl, J, A maximum entropy approach to nonmonotonic reasoning, (), 646-652 |

[25] | Goldszmidt, M; Pearl, J, Qualitative probabilities for default reasoning, belief revision, and causal modeling, Artificial intelligence, 84, 57-112, (1996) |

[26] | Grove, A.J; Halpern, J.Y; Koller, D, Random worlds and maximum entropy, J. artificial intelligence res., 2, 33-88, (1994) · Zbl 0900.68398 |

[27] | Haddawy, P, Generating Bayesian networks from probability logic knowledge bases, (), 262-269 |

[28] | Haenni, R; Kohlas, J; Lehmann, N, Probabilistic argumentation systems, (), 221-287 · Zbl 0987.68076 |

[29] | Halpern, J.Y, An analysis of first-order logics of probability, Artificial intelligence, 46, 311-350, (1990) · Zbl 0723.03007 |

[30] | Hansen, P; Jaumard, B; Douanya Nguetsé, G.-B; Poggi de Aragão, M, Models and algorithms for probabilistic and Bayesian logic, (), 1862-1868 |

[31] | Jaeger, M, Relational Bayesian networks, (), 266-273 |

[32] | Jaeger, M, On the complexity of inference about probabilistic relational models, Artificial intelligence, 117, 297-308, (1999) · Zbl 0938.68847 |

[33] | Jaumard, B; Hansen, P; Poggi de Aragão, M, Column generation methods for probabilistic logic, ORSA J. comput., 3, 135-147, (1991) · Zbl 0800.68864 |

[34] | Jaynes, E.T, Papers on probability, statistics and statistical physics, (1983), D. Reidel Dordrecht · Zbl 0501.01026 |

[35] | Jensen, F.V, Introduction to Bayesian networks, (1996), UCL Press London |

[36] | Johnson, R.W; Shore, J.E, Comments on and corrections to “axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy”, IEEE trans. inform. theory, IT-29, 6, 942-943, (1983) · Zbl 0532.94004 |

[37] | Kavvadias, D; Papadimitriou, C.H, A linear programming approach to reasoning about probabilities, Ann. math. artificial intelligence, 1, 189-205, (1990) · Zbl 0878.68034 |

[38] | Kern-Isberner, G, A logically sound method for uncertain reasoning with quantified conditionals, (), 365-379 |

[39] | Kern-Isberner, G, Characterizing the principle of minimum cross-entropy within a conditional-logical framework, Artificial intelligence, 98, 169-208, (1998) · Zbl 0903.68181 |

[40] | Kern-Isberner, G, A note on conditional logics and entropy, Internat. J. approx. reasoning, 19, 231-246, (1998) · Zbl 0947.68140 |

[41] | Kern-Isberner, G, Conditionals in nonmonotonic reasoning and belief revision, Lecture notes in artificial intelligence, vol. 2087, (2001), Springer Berlin · Zbl 0978.03014 |

[42] | Koller, D; Pfeffer, A, Object-oriented Bayesian networks, (), 302-313 |

[43] | Kraus, S; Lehmann, D; Magidor, M, Nonmonotonic reasoning, preferential models and cumulative logics, Artificial intelligence, 14, 1, 167-207, (1990) · Zbl 0782.03012 |

[44] | Kyburg, H.E, The logical foundations of statistical inference, (1974), D. Reidel Dordrecht · Zbl 0335.02001 |

[45] | Kyburg, H.E, The reference class, Philos. sci., 50, 374-397, (1983) |

[46] | Laskey, K.B; Mahoney, S.M, Network fragments: representing knowledge for constructing probabilistic models, (), 334-341 |

[47] | Lauritzen, S.L; Spiegelhalter, D.J, Local computations with probabilities in graphical structures and their applications to expert systems, J. roy. statist. soc. B, 50, 2, 415-448, (1988) · Zbl 0684.68106 |

[48] | Lehmann, D; Magidor, M, What does a conditional knowledge base entail?, Artificial intelligence, 55, 1-60, (1992) · Zbl 0762.68057 |

[49] | Lukasiewicz, T, Efficient global probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events, (), 75-82 |

[50] | Lukasiewicz, T, Probabilistic logic programming, (), 388-392 |

[51] | Lukasiewicz, T, Local probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events, Internat. J. approx. reasoning, 21, 1, 23-61, (1999) · Zbl 0961.68135 |

[52] | Lukasiewicz, T, Probabilistic deduction with conditional constraints over basic events, J. artificial intelligence res., 10, 199-241, (1999) · Zbl 0914.68178 |

[53] | Lukasiewicz, T, Credal networks under maximum entropy, (), 363-370 |

[54] | Lukasiewicz, T, Probabilistic logic programming under inheritance with overriding, (), 329-336 |

[55] | Lukasiewicz, T, Probabilistic logic programming with conditional constraints, ACM trans. comput. logic (TOCL), 2, 3, 264-312, (2001) |

[56] | Lukasiewicz, T, Nonmonotonic probabilistic logics between model-theoretic probabilistic logic and probabilistic logic under coherence, (), 265-274 |

[57] | Lukasiewicz, T, Probabilistic default reasoning with conditional constraints, Ann. math. artificial intelligence, 34, 1-3, 35-88, (2002) · Zbl 1002.68175 |

[58] | Luo, C; Yu, C; Lobo, J; Wang, G; Pham, T, Computation of best bounds of probabilities from uncertain data, Comput. intelligence, 12, 4, 541-566, (1996) |

[59] | Meyer, C.H, Korrektes schliessen bei unvollständiger information, (1998), Peter Lang Verlag |

[60] | Neapolitan, R.E, Probabilistic reasoning in expert systems, (1990), Wiley New York |

[61] | Ng, R.T, Semantics, consistency, and query processing of empirical deductive databases, IEEE trans. knowl. data eng., 9, 1, 32-49, (1997) |

[62] | Ng, R.T; Subrahmanian, V.S, Probabilistic logic programming, Inf. comput., 101, 150-201, (1992) · Zbl 0781.68038 |

[63] | Ng, R.T; Subrahmanian, V.S, A semantical framework for supporting subjective and conditional probabilities in deductive databases, J. autom. reasoning, 10, 2, 191-235, (1993) · Zbl 0784.68082 |

[64] | Ngo, L; Haddawy, P, Answering queries from context-sensitive probabilistic knowledge bases, Theoret. comput. sci., 171, 147-177, (1997) · Zbl 0874.68280 |

[65] | Nilsson, N.J, Probabilistic logic, Artificial intelligence, 28, 71-88, (1986) · Zbl 0589.03007 |

[66] | Ohmann, C; Moustakis, V; Yang, Q; Lang, K, Evaluation of automatic knowledge acquisition techniques in the diagnosis of acute abdominal pain, Artificial intelligence in medicine, 8, 23-26, (1996) |

[67] | Paris, J.B, The uncertain Reasoner’s companion: A mathematical perspective, (1995), Cambridge University Press Cambridge, UK · Zbl 0838.68104 |

[68] | Paris, J.B; Vencovska, A, A note on the inevitability of maximum entropy, Internat. J. approx. reasoning, 14, 183-223, (1990) · Zbl 0697.68089 |

[69] | Paris, J.B; Vencovska, A, In defense of the maximum entropy inference process, Internat. J. approx. reasoning, 17, 1, 77-103, (1997) · Zbl 0939.68118 |

[70] | Pearl, J, Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann San Mateo, CA |

[71] | Pollock, J.L, Nomic probabilities and the foundations of induction, (1990), Oxford University Press Oxford |

[72] | Poole, D, Logic programming, abduction and probability, New gener. comput., 11, 377-400, (1993) · Zbl 0788.68025 |

[73] | Poole, D, Probabilistic Horn abduction and Bayesian networks, Artificial intelligence, 64, 81-129, (1993) · Zbl 0792.68176 |

[74] | Reichenbach, H, Theory of probability, (1949), University of California Press Berkeley, CA |

[75] | Rödder, W; Kern-Isberner, G, Léa sombé und entropie-optimale informationsverarbeitung mit der expertensystem-shell SPIRIT, OR spektrum, 19, 3, (1997) · Zbl 0914.90174 |

[76] | Rödder, W; Kern-Isberner, G, Representation and extraction of information by probabilistic logic, Inf. syst., 21, 8, 637-652, (1997) · Zbl 0869.68100 |

[77] | Rödder, W; Kern-Isberner, G, From information to probability: an axiomatic approach, Internat. J. intell. syst., 18, 4, 383-403, (2003) · Zbl 1016.68164 |

[78] | Rödder, W; Meyer, C.-H, Coherent knowledge processing at maximum entropy by SPIRIT, (), 470-476 |

[79] | M. Ruprecht, Implementierung und Performance-Auswertung für probabilistisches Schließen mit taxonomischem Wissen, Master’s Thesis, Universität Augsburg, 1996 |

[80] | Schramm, M; Ertel, W, Reasoning with probability and maximum entropy: the system PIT and its application in LEXMED, (), 274-280 · Zbl 1015.90506 |

[81] | Schramm, M; Fischer, V, Probabilistic reasoning with maximum entropy—the system PIT, () |

[82] | Schramm, M; Fronhöfer, B, PIT: A system for reasoning with probabilities, (), 109-123 |

[83] | Schrijver, A, Theory of linear and integer programming, (1986), Wiley New York · Zbl 0665.90063 |

[84] | M. Schweitzer, Wissensfindung in Datenbanken auf probabilistischer Basis, Master’s Thesis, FernUniversität Hagen, 1998 |

[85] | Scott, D; Krauss, P, Assigning probabilities to logical formulas, (), 219-264 · Zbl 0202.29905 |

[86] | Shannon, C.E; Weaver, W, A mathematical theory of communication, (1949), University of Illinois Press Urbana, IL · Zbl 0041.25804 |

[87] | Shore, J.E; Johnson, R.W, Axiomatic derivation of the principle of maximum entropy and the principle of minimum cross-entropy, IEEE trans. inform. theory, IT-26, 26-37, (1980) · Zbl 0429.94011 |

[88] | Shore, J.E; Johnson, R.W, Properties of cross-entropy minimization, IEEE trans. inform. theory, IT-27, 472-482, (1981) · Zbl 0459.94008 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.