×

Weak nonmonotonic probabilistic logics. (English) Zbl 1132.68737

Summary: We present an approach where probabilistic logic is combined with default reasoning from conditional knowledge bases in Kraus et al.’s System \(P\), Pearl’s System \(Z\), and Lehmann’s lexicographic entailment. The resulting probabilistic generalizations of default reasoning from conditional knowledge bases allow for handling in a uniform framework strict logical knowledge, default logical knowledge, as well as purely probabilistic knowledge. Interestingly, probabilistic entailment in System \(P\) coincides with probabilistic entailment under g-coherence from imprecise probability assessments. We then analyze the semantic and nonmonotonic properties of the new formalisms. It turns out that they all are proper generalizations of their classical counterparts and have similar properties as them. In particular, they all satisfy the rationality postulates of System \(P\) and some Conditioning property. Moreover, probabilistic entailment in System \(Z\) and probabilistic lexicographic entailment both satisfy the property of Rational Monotonicity and some Irrelevance property, while probabilistic entailment in System \(P\) does not. We also analyze the relationships between the new formalisms. Here, probabilistic entailment in System \(P\) is weaker than probabilistic entailment in System \(Z\), which in turn is weaker than probabilistic lexicographic entailment. Moreover, they all are weaker than entailment in probabilistic logic where default sentences are interpreted as strict sentences. Under natural conditions, probabilistic entailment in System \(Z\) and lexicographic entailment even coincide with such entailment in probabilistic logic, while probabilistic entailment in System \(P\) does not. Finally, we also present algorithms for reasoning under probabilistic entailment in System \(Z\) and probabilistic lexicographic entailment, and we give a precise picture of its complexity.

MSC:

68T27 Logic in artificial intelligence
03B48 Probability and inductive logic
68T37 Reasoning under uncertainty in the context of artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Adams, E. W., The Logic of Conditionals, Synthese Library, vol. 86 (1975), D. Reidel: D. Reidel Dordrecht · Zbl 0202.30001
[2] Amarger, S.; Dubois, D.; Prade, H., Constraint propagation with imprecise conditional probabilities, (Proceedings UAI-91 (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 26-34
[3] Bacchus, F.; Grove, A.; Halpern, J. Y.; Koller, D., From statistical knowledge bases to degrees of belief, Artificial Intelligence, 87, 1-2, 75-143 (1996) · Zbl 1506.68146
[4] Benferhat, S.; Cayrol, C.; Dubois, D.; Lang, J.; Prade, H., Inconsistency management and prioritized syntax-based entailment, (Proceedings IJCAI-93, Chambéry, France (1993), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 640-645
[5] Benferhat, S.; Dubois, D.; Prade, H., Representing default rules in possibilistic logic, (Proceedings KR-92, Cambridge, MA (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 673-684
[6] Benferhat, S.; Dubois, D.; Prade, H., Nonmonotonic reasoning, conditional objects and possibility theory, Artificial Intelligence, 92, 1-2, 259-276 (1997) · Zbl 1017.68539
[7] Benferhat, S.; Saffiotti, A.; Smets, P., Belief functions and default reasoning, Artificial Intelligence, 122, 1-2, 1-69 (2000) · Zbl 0948.68112
[8] Biazzo, V.; Gilio, A., A generalization of the fundamental theorem of de Finetti for imprecise conditional probability assessments, Internat. J. Approx. Reason., 24, 2-3, 251-272 (2000) · Zbl 0995.68124
[9] V. Biazzo, A. Gilio, T. Lukasiewicz, G. Sanfilippo, Probabilistic logic under coherence: Complexity and algorithms, in: Proceedings ISIPTA-01, 2001, pp. 51-61; V. Biazzo, A. Gilio, T. Lukasiewicz, G. Sanfilippo, Probabilistic logic under coherence: Complexity and algorithms, in: Proceedings ISIPTA-01, 2001, pp. 51-61 · Zbl 1083.03027
[10] Biazzo, V.; Gilio, A.; Lukasiewicz, T.; Sanfilippo, G., Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning, (Proceedings ECSQARU-01. Proceedings ECSQARU-01, Lecture Notes in Comput. Sci./Lecture Notes in Artificial Intelligence, vol. 2143 (2001), Springer: Springer Berlin), 290-302 · Zbl 1001.68146
[11] Biazzo, V.; Gilio, A.; Lukasiewicz, T.; Sanfilippo, G., Probabilistic logic under coherence, model-theoretic probabilistic logic, and default reasoning in System \(P\), J. Appl. Non-Class. Logics, 12, 2, 189-213 (2002) · Zbl 1038.03023
[12] Boole, G., An Investigation of the Laws of Thought, on which are Founded the Mathematical Theories of Logic and Probabilities (1958), Walton and Maberley: Walton and Maberley London: Dover Publications: Walton and Maberley: Walton and Maberley London: Dover Publications New York, reprint
[13] Dubois, D.; Prade, H., On fuzzy syllogisms, Computational Intelligence, 4, 2, 171-179 (1988)
[14] Dubois, D.; Prade, H., Possibilistic logic, preferential models, non-monotonicity and related issues, (Proceedings IJCAI-91, Sydney, Australia (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 419-424 · Zbl 0744.68116
[15] Dubois, D.; Prade, H., Conditional objects as nonmonotonic consequence relationships, IEEE Trans. System Man Cybernet., 24, 12, 1724-1740 (1994) · Zbl 1371.03041
[16] Dubois, D.; Prade, H.; Godo, L.; de Màntaras, R. L., Qualitative reasoning with imprecise probabilities, J. Intelligent Inform. Syst., 2, 319-363 (1993)
[17] Dubois, D.; Prade, H.; Touscas, J.-M., Inference with imprecise numerical quantifiers, (Ras, Z. W.; Zemankova, M., Intelligent Systems (1990), Ellis Horwood), 53-72, Chapter 3
[18] Eiter, T.; Lukasiewicz, T., Default reasoning from conditional knowledge bases: Complexity and tractable cases, Artificial Intelligence, 124, 2, 169-241 (2000) · Zbl 0952.68139
[19] Fagin, R.; Halpern, J. Y.; Megiddo, N., A logic for reasoning about probabilities, Inform. Comput., 87, 78-128 (1990) · Zbl 0811.03014
[20] Friedman, N.; Halpern, J. Y., Plausibility measures and default reasoning, J. ACM, 48, 4, 648-685 (2001) · Zbl 1127.68438
[21] Frisch, A. M.; Haddawy, P., Anytime deduction for probabilistic logic, Artificial Intelligence, 69, 1-2, 93-122 (1994) · Zbl 0809.03016
[22] (Gabbay, D. M.; Smets, P., Handbook on Defeasible Reasoning and Uncertainty Management Systems (1998), Kluwer Academic: Kluwer Academic Dordrecht) · Zbl 0908.90001
[23] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039
[24] Geffner, H., Default Reasoning: Causal and Conditional Theories (1992), MIT Press: MIT Press Cambridge, MA
[25] Geffner, H., High probabilities, model preference and default arguments, Mind and Machines, 2, 51-70 (1992)
[26] Geffner, H.; Pearl, J., Conditional entailment: Bridging two approaches to default reasoning, Artificial Intelligence, 53, 2-3, 209-244 (1992) · Zbl 1193.68235
[27] Gilio, A., Probabilistic consistency of conditional probability bounds, (Advances in Intelligent Computing. Advances in Intelligent Computing, Lecture Notes in Comput. Sci., vol. 495 (1995), Springer: Springer Berlin), 200-209
[28] Gilio, A., Probabilistic reasoning under coherence in System \(P\), Ann. Math. Artificial Intelligence, 34, 1-3, 5-34 (2002) · Zbl 1014.68165
[29] Gilio, A.; Scozzafava, R., Conditional events in probability assessment and revision, IEEE Trans. System Man Cybernet., 24, 12, 1741-1746 (1994) · Zbl 1371.60002
[30] Giugno, R.; Lukasiewicz, T., \(P - SHOQ(D)\): A probabilistic extension of \(SHOQ(D)\) for probabilistic ontologies in the Semantic Web, (Proceedings JELIA-02. Proceedings JELIA-02, Lecture Notes in Comput. Sci./Lecture Notes in Artif. Intell., vol. 2424 (2002), Springer: Springer Berlin), 86-97 · Zbl 1014.68537
[31] Goldszmidt, M.; Morris, P.; Pearl, J., A maximum entropy approach to non- monotonic reasoning, IEEE Trans. Pattern Anal. Mach. Intell., 15, 3, 220-232 (1993)
[32] Goldszmidt, M.; Pearl, J., On the consistency of defeasible databases, Artificial Intelligence, 52, 2, 121-149 (1991) · Zbl 0749.68026
[33] Goldszmidt, M.; Pearl, J., Rank-based systems: A simple approach to belief revision, belief update and reasoning about evidence and actions, (Proceedings KR-92, Cambridge, MA (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 661-672
[34] Goldszmidt, M.; Pearl, J., Qualitative probabilities for default reasoning, belief revision, and causal modeling, Artificial Intelligence, 84, 1-2, 57-112 (1996) · Zbl 1497.68457
[35] Hailperin, T., Sentential Probability Logic: Origins, Development, Current Status, and Technical Applications (1996), Associated University Presses: Associated University Presses London · Zbl 0922.03026
[36] Hansen, P.; Jaumard, B.; Nguetsé, G.-B. D.; de Aragão, M. P., Models and algorithms for probabilistic and Bayesian logic, (Proceedings IJCAI-95, Montreal, Quebec (1995), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 1862-1868
[37] Jaumard, B.; Hansen, P.; de Aragão, M. P., Column generation methods for probabilistic logic, ORSA J. Comput., 3, 135-147 (1991) · Zbl 0800.68864
[38] Johnson, D. S., A catalog of complexity classes, (van Leeuwen, J., Handbook of Theoretical Computer Science, vol. A (1990), MIT Press: MIT Press Cambridge, MA), 67-161, Chapter 2 · Zbl 0900.68246
[39] Kern-Isberner, G.; Lukasiewicz, T., Combining probabilistic logic programming with the power of maximum entropy, Artificial Intelligence, 157, 1-2, 139-202 (2004) · Zbl 1085.68170
[40] Kraus, S.; Lehmann, D.; Magidor, M., Nonmonotonic reasoning, preferential models and cumulative logics, Artificial Intelligence, 14, 1, 167-207 (1990) · Zbl 0782.03012
[41] Kyburg, H. E., The Logical Foundations of Statistical Inference (1974), D. Reidel: D. Reidel Dordrecht · Zbl 0335.02001
[42] Kyburg, H. E., The reference class, Philos. Sci., 50, 374-397 (1983)
[43] H.E. Kyburg Jr., C.-M. Teng, Evaluating defaults, in: Proceedings NMR-02, 2002, pp. 257-264; H.E. Kyburg Jr., C.-M. Teng, Evaluating defaults, in: Proceedings NMR-02, 2002, pp. 257-264
[44] Lamarre, P., A promenade from monotonicity to non-monotonicity following a theorem prover, (Proceedings KR-92, Cambridge, MA (1992), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 572-580
[45] Lehmann, D., What does a conditional knowledge base entail?, (Proceedings KR-89 (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 212-222 · Zbl 0709.68104
[46] Lehmann, D., Another perspective on default reasoning, Ann. Math. Artificial Intelligence, 15, 1, 61-82 (1995) · Zbl 0857.68096
[47] Lehmann, D.; Magidor, M., What does a conditional knowledge base entail?, Artificial Intelligence, 55, 1, 1-60 (1992) · Zbl 0762.68057
[48] Lukasiewicz, T., Local probabilistic deduction from taxonomic and probabilistic knowledge-bases over conjunctive events, Internat. J. Approx. Reason., 21, 1, 23-61 (1999) · Zbl 0961.68135
[49] Lukasiewicz, T., Probabilistic deduction with conditional constraints over basic events, J. Artificial Intelligence Res., 10, 199-241 (1999) · Zbl 0914.68178
[50] Lukasiewicz, T., Probabilistic logic programming under inheritance with overriding, (Proceedings UAI-01 (2001), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 329-336
[51] Lukasiewicz, T., Probabilistic logic programming with conditional constraints, ACM Trans. Computat. Logic (TOCL), 2, 3, 289-339 (2001) · Zbl 1171.68762
[52] Lukasiewicz, T., Probabilistic default reasoning with conditional constraints, Ann. Math. Artificial Intelligence, 34, 1-3, 35-88 (2002) · Zbl 1002.68175
[53] T. Lukasiewicz, Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: Algorithms and implementation in nmproblog, in: Proceedings ISIPTA-05, 2005; T. Lukasiewicz, Nonmonotonic probabilistic logics under variable-strength inheritance with overriding: Algorithms and implementation in nmproblog, in: Proceedings ISIPTA-05, 2005 · Zbl 1082.03025
[54] Nilsson, N. J., Probabilistic logic, Artificial Intelligence, 28, 71-88 (1986) · Zbl 0589.03007
[55] Nilsson, N. J., Probabilistic logic revisited, Artificial Intelligence, 59, 39-42 (1993) · Zbl 1507.68015
[56] Papadimitriou, C. H., Computational Complexity (1994), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0557.68033
[57] Pearl, J., Probabilistic semantics for nonmonotonic reasoning: A survey, (Proceedings KR-89 (1989), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 505-516 · Zbl 0703.03008
[58] Pearl, J., System \(Z\): A natural ordering of defaults with tractable applications to default reasoning, (Proceedings TARK-90 (1990), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 121-135
[59] R. Pelessoni, P. Vicig, A consistency problem for imprecise conditional probability assessments, in: Proceedings IPMU-98, 1998, pp. 1478-1485; R. Pelessoni, P. Vicig, A consistency problem for imprecise conditional probability assessments, in: Proceedings IPMU-98, 1998, pp. 1478-1485
[60] Pollock, J. L., Nomic Probabilities and the Foundations of Induction (1990), Oxford University Press: Oxford University Press Oxford
[61] Poole, D., The effect of knowledge on belief: Conditioning, specificity and the lottery paradox in default reasoning, Artificial Intelligence, 49, 1-3, 281-307 (1991) · Zbl 0737.68074
[62] Reichenbach, H., Theory of Probability (1949), University of California Press: University of California Press Berkeley, CA · Zbl 0038.28604
[63] Reiter, R., A logic for default reasoning, Artificial Intelligence, 13, 1-2, 81-132 (1980) · Zbl 0435.68069
[64] Shoham, Y., A semantical approach to nonmonotonic logics, (Proceedings LICS-87 (1987), IEEE Computer Society), 275-279
[65] Spohn, W., Ordinal conditional functions: A dynamic theory of epistemic states, (Harper, W.; Skyrms, B., Causation in Decision, Belief Change, and Statistics, vol. 2 (1988), Reidel: Reidel Dordrecht), 105-134
[66] P. Vicig, An algorithm for imprecise conditional probability assessments in expert systems, in: Proceedings IPMU-96, 1996, pp. 61-66; P. Vicig, An algorithm for imprecise conditional probability assessments in expert systems, in: Proceedings IPMU-96, 1996, pp. 61-66
[67] G.R. Wheeler, A resource bounded default logic, in: Proceedings NMR-04, 2004, pp. 416-422; G.R. Wheeler, A resource bounded default logic, in: Proceedings NMR-04, 2004, pp. 416-422
[68] Walley, P., Statistical Reasoning with Imprecise Probabilities (1991), Chapman and Hall · Zbl 0732.62004
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.