×

Belief functions and default reasoning. (English) Zbl 0948.68112

Summary: We present a new approach to deal with default information based on the theory of belief functions. Our semantic structures, inspired by Adams’ epsilon semantics, are epsilon-belief assignments, where mass values are either close to 0 or close to 1. In the first part of this paper, we show that these structures can be used to give a uniform semantics to several popular non-monotonic systems, including Kraus, Lehmann and Magidor’s system \(P\) , Pearl’s system \(Z\) , Brewka’s preferred subtheories, Geffner’s conditional entailment, Pinkas’ penalty logic, possibilistic logic and the lexicographic approach. In the second part, we use epsilon-belief assignments to build a new system, called LCD, and show that this system correctly addresses the well-known problems of specificity, irrelevance, blocking of inheritance, ambiguity, and redundancy.

MSC:

68Q55 Semantics in the theory of computing
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Adams, E. W., Probability and the logic of conditionals, (Hintikka, J.; Suppes, P., Aspects of Inductive Logic (1966), North-Holland: North-Holland Amsterdam), 253-316 · Zbl 0202.30001
[2] Adams, E. W., The Logic of Conditionals (1975), Reidel: Reidel Dordrecht · Zbl 0202.30001
[3] Baral, C.; Kraus, S.; Minker, J.; Subrahmanian, V. S., Combining knowledge bases consisting in first order theories, Comput. Intelligence, Vol. 8, 1, 45-71 (1992)
[4] Benferhat, S.; Cayrol, C.; Dubois, D.; Lang, J.; Prade, H., Inconsistency management and prioritized syntax-based entailment, (Proc. IJCAI’93, Chambéry, France (1993)), 640-645
[5] Benferhat, S.; Dubois, D.; Lang, J.; Prade, H.; Saffiotti, A.; Smets, P., A general approach for inconsistency handling and merging information in prioritized knowledge bases, (Proc. Sixth Conf. on Principles of Knowledge Representation and Reasoning (KR’98), Trento, Italy (1998))
[6] Benferhat, S.; Dubois, D.; Prade, H., Representing default rules in possibilistic logic, (Proc. 3rd Conf. on Principles of Knowledge Representation and Reasoning (KR’92), Cambridge, MA (1992)), 673-684
[7] Benferhat, S.; Dubois, D.; Prade, H., Possibilistic and standard probabilistic semantics of conditional knowledge bases, J. Logic Comput., Vol. 9, 873-895 (1999) · Zbl 0945.68166
[8] Bourne, R. A.; Parsons, S., Maximum entropy and variable strength defaults, (Proc. IJCAI-99, Stockholm, Sweden (1999)) · Zbl 1045.68136
[9] Boutilier, C., What is a Default priority?, (Proc. 9th Canadian Conf. on Artificial Intelligence (AI’92), Vancouver, BC, May 1992 (1992)), 140-147
[10] Brewka, G., Preferred subtheories: An extended logical framework for default reasoning, (Proc. IJCAI’89, Detroit, MI (1989)), 1043-1048 · Zbl 0713.68053
[11] Delgrande, J. P.; Schaub, T. H., A general approach to specificity in default reasoning, (Proc. 4th Conf. on Principles of Knowledge Representation and Reasoning (KR’94), Bonn, Germany (1994)), 146-157
[12] Dubois, D.; Lang, J.; Prade, H., Possibilistic logic, (Gabbay, D. M.; Hogger, C. J.; Robinson, J. A.; Nute, D., Handbook of Logic in Artificial Intelligence and Logic Programming, Vol. 3 (1994), Oxford University Press), 439-513
[13] Dubois, D.; Lang, J.; Prade, H., Inconsistency in possibilistic knowledge bases - To live or not live with it, (Zadeh, L. A.; Kacprzyk, J., Fuzzy Logic for the Management of Uncertainty (1992), Wiley: Wiley New York), 335-351
[14] Dubois, D.; Prade, H., Possibility Theory - An Approach to Computerized Processing of Uncertainty (1988), Plenum Press: Plenum Press New York, (with the collaboration of H. Farreny, R. Martin-Clouaire, C. Testemale)
[15] Dubois, D.; Prade, H., Conditional objects, possibility theory and default rules, (Crocco, G.; Farinas del Cerro, L.; Herzig, A., Conditionals: From Philosophy to Computer Sciences (1995), Oxford University Press), 311-346 · Zbl 0741.68091
[16] Dupin de Saint Cyr, F.; Lang, J.; Schiex, T., Penalty logic and its link with Dempster-Shafer theory, (Proc. 10th Conference on Uncertainty in Artificial Intelligence (UAI-94), Seattle, WA (1994)), 204-211
[17] Eiter, T.; Lukasiewicz, T., Complexity results for default reasoning from conditional knowledge bases, (Principles of Knowledge Representation and Reasoning: Proceedings of the Seventh International Conference (KR’2000), Breckenridge, CO, April 2000 (2000)), 62-73 · Zbl 0952.68139
[18] de Kleer, J., Using crude probability estimates to guide diagnosis, Artificial Intelligence, Vol. 45, 381-391 (1990)
[19] Gabbay, D. M., Theoretical foundations for non-monotonic reasoning in expert systems, (Apt, K. R., Logics and Models of Concurrent Systems (1985), Springer: Springer Berlin), 439-457 · Zbl 0581.68068
[20] Gärdenfors, P.; Makinson, D., Nonmonotonic inference based on expectations, Artificial Intelligence, Vol. 65, 197-245 (1994) · Zbl 0803.68125
[21] Geffner, H., Default Reasoning: Causal and Conditional Theories (1992), MIT Press: MIT Press Cambridge, MA
[22] Gilio, A., Precise propagation of upper and lower probability bounds in system \(P\), (Proc. 8th International Workshop on Non-Monotonic Reasoning (NMR’2000), Special Session on Uncertainty Frameworks in Nonmonotonic Reasoning, Breckenridge, CO (2000))
[23] Goldszmidt, M., Qualitative Probabilities: A Normative Framework for Commonsense Reasoning (1992), Cognitive Systems Laboratory UCLA: Cognitive Systems Laboratory UCLA Los Angeles, CA, Ph.D. Thesis, Technical Report R-190
[24] Goldszmidt, M.; Pearl, J., System \(Z^+\) : A formalism for reasoning with variable-strength defaults, (Proc. AAAI-91, Anaheim, CA (1991)), 399-404
[25] Goldszmidt, M.; Pearl, J., Qualitative probabilities for default reasoning, belief revision, and causal modeling, Artificial Intelligence, Vol. 84, 57-112 (1996) · Zbl 1497.68457
[26] Hsia, Y-T., A belief-function semantics for cautious non-monotonicity (1991), Université Libre de Bruxelles: Université Libre de Bruxelles Belgium, Technical Report TR/IRIDIA/91-3
[27] Keisler, H. J., Foundations of Infinitesimal Calculus (1976), Prindle, Weber and Schmidt, Boston, MA · Zbl 0333.26001
[28] Kennes, R., Evidential reasoning in a categorial perspective: Conjunction and disjunction of belief functions, (Proc. 7th Conf. on Uncertainty in AI, Los Angeles, CA (1991)), 174-181
[29] Klawonn, F.; Smets, Ph., The dynamics of belief in the transferable belief model, (Proc. 8th Conf. on Uncertainty in AI (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 130-137
[30] Kohlas, J.; Monney, P. A., A Mathematical Theory of Hints. An Approach to Dempster-Shafer Theory of Evidence. A Mathematical Theory of Hints. An Approach to Dempster-Shafer Theory of Evidence, Lecture Notes in Economics and Mathematical Systems, Vol. 425 (1995), Springer: Springer Berlin · Zbl 0833.62005
[31] Kraus, S.; Lehmann, D.; Magidor, M., Non-monotonic reasoning, preferential models and cumulative logics, Artificial Intelligence, Vol. 44, 167-207 (1990) · Zbl 0782.03012
[32] Lang, J., Syntax-based default reasoning as probabilistic model-based diagnosis, (Proc. UAI’94, Seattle, WA (1994)), 391-398
[33] Lehmann, D., What does a conditional knowledge base entail?, (Brachman, R. J.; etal., Proc. 1st Internat. Conf. on Principles of Knowledge Representation and Reasoning (KR’89), Toronto, Ont. (1989)), 212-222 · Zbl 0709.68104
[34] Lehmann, D., Another perspective on default reasoning, Ann. Math. Artificial Intelligence, Vol. 15, 61-82 (1995) · Zbl 0857.68096
[35] Lehmann, D.; Magidor, M., What does a conditional knowledge base entail?, Artificial Intelligence, Vol. 55, 1-60 (1992) · Zbl 0762.68057
[36] Makinson, D., General theory of cumulative inference, (Reinfrank, M.; de Kleer, J.; Ginsberg, M. L.; Sandewall, E., Non-Monotonic Reasoning, Proc. of the 2nd Internat. Workshop, Grassau, FRG, June 1988. Non-Monotonic Reasoning, Proc. of the 2nd Internat. Workshop, Grassau, FRG, June 1988, Lecture Notes in Artif. Intell., Vol. 346 (1989), Springer: Springer Berlin), 1-18
[37] Nelson, E., Internal set theory: A new approach to non-standard analysis, Bull. Amer. Math. Soc., Vol. 83, 1165-1198 (1977) · Zbl 0373.02040
[38] S. Parsons, R.A. Bourne, On proofs in System P, Internat. J. Uncertainty, Fuzziness and Knowledge Base Systems, World Scientific Company, Singapore, to appear; S. Parsons, R.A. Bourne, On proofs in System P, Internat. J. Uncertainty, Fuzziness and Knowledge Base Systems, World Scientific Company, Singapore, to appear
[39] Pearl, J., Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA
[40] Pearl, J., System Z: A natural ordering of defaults with tractable applications to default reasoning, (Proc. Theoretical Aspects of Reasoning about Knowledge, Pacific Grove, CA (1990)), 121-135
[41] Poole, D., Average-case analysis of a search algorithm for estimating prior and posterior probabilities in Bayesian networks with extreme probabilities, (Proc. IJCAI-93, Chambéry, France (1993)), 606-612
[42] Pinkas, G., Propositional nonmonotonic reasoning and inconsistency in symmetric neural networks, (Proc. IJCAI-91, Sydney, Australia (1991), Morgan Kaufmann: Morgan Kaufmann San Mateo, CA), 525-530 · Zbl 0742.68070
[43] Reiter, R., A logic for default reasoning, Artificial Intelligence, Vol. 13, 81-132 (1980) · Zbl 0435.68069
[44] Reiter, R.; Griscuolo, G., On interacting defaults, (Proc. IJCAI-81, Vancouver, BC (1981)), 270-276
[45] Robinson, A., Non-standard Analysis (1966), Noth-Holland: Noth-Holland Amsterdam · Zbl 0151.00803
[46] Schurz, G., Probabilistic semantics for Delgrande’s conditional logic and a counterexample to his default logic, Artificial Intelligence, Vol. 102, 81-95 (1998) · Zbl 0908.03028
[47] Shafer, G., A Mathematical Theory of Evidence (1976), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0359.62002
[48] Shoham, Y., Reasoning about Change - Time and Causation from the Standpoint of Artificial Intelligence (1988), MIT Press: MIT Press Cambridge, MA
[49] Smets, Ph., Belief functions, (Smets, Ph.; Mamdani, E. H.; Dubois, D.; Prade, H., Non-Standard Logics for Automated Reasoning (1988), Academic Press: Academic Press New York), 253-286
[50] Smets, Ph., The combination of evidence in the transferable belief model, IEEE Trans. Pattern Anal. Machine Intelligence, Vol. 12, 447-458 (1990)
[51] Smets, Ph., The concept of distinct evidence, (Proc. IPMU’92, Palma de Mallorca, Spain (1992)), 789-794
[52] Smets, Ph., The normative representation of quantified beliefs by belief functions, Artificial Intelligence, Vol. 92, 229-242 (1997) · Zbl 1017.68544
[53] Smets, Ph., The \(α\) -junctions: Combination operators applicable to belief functions, (Gabbay, D.; Kruse, R.; Nonnengart, A.; Ohlbach, H. J., Qualitative and Quantitative Practical Reasoning (1997), Springer: Springer Berlin), 131-153
[54] Smets, Ph., The transferable belief model for quantified belief representation, (Gabbay, D. M.; Smets, Ph., Handbook of Defeasible Reasoning and Uncertainty Management Systems, Vol. 1 (1998), Kluwer: Kluwer Dordrecht), 267-301 · Zbl 0939.68112
[55] Smets, Ph.; Hsia, Y.-T., Default reasoning and the transferable belief model, (Bonissone, P.; Henrion, M.; Kanal, L.; Lemmer, J., Uncertainty in Artificial Intelligence 6 (1991), North-Holland: North-Holland Amsterdam), 495-504
[56] Smets, Ph.; Kennes, R., The transferable belief model, Artificial Intelligence, Vol. 66, 191-234 (1994) · Zbl 0807.68087
[57] Snow, P., Standard probability distributions described by rational default entailment (1996), Personal communication
[58] Snow, P., Diverse confidence levels in a probabilistic semantics for conditional logics, Artificial Intelligence, Vol. 113, 269-279 (1999) · Zbl 0940.03026
[59] Spohn, W., Ordinal conditional functions: A dynamic theory of epistemic states, (Harper, W. L.; Skyrms, B., Causation in Decision, Belief Change, and Statistics (1988), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, Netherlands), 105-134
[60] Touretzky, D., Implicit ordering of defaults in inheritance systems, (Proc. AAAI-84, Austin, TX (1984)), 322-325
[61] Walley, P., Statistical Reasoning with Imprecise Probabilities (1991), Chapman and Hall: Chapman and Hall London · Zbl 0732.62004
[62] Weydert, E., Defaults and infinitesimals defeasible inference by nonarchimedean entropy maximization, (Proc. 11th Conf. on Uncertainty in Artificial Intelligence (UAI’95) (1995)), 540-547
[63] Wilson, N., Some theoretical aspects of the Dempster-Shafer theory (1992), Oxford Polytechnic, Ph.D. Thesis
[64] Wilson, N., Default logic and Dempster-Shafer theory, (Kruse, R.; etal., Proc. 2nd European Conference on Symbolic and Qualitative Approaches to Reasoning and Uncertainty (ECSQARU-93) (1993), Springer: Springer Berlin), 372-379
[65] Wilson, N., Extended probability, (Proc. 12th European Conf. on Artif. Intell. (ECAI’96) (1996), John Wiley and Sons Ltd), 667-671
[66] Zadeh, L. A., Fuzzy sets as a basis for a theory of possibility, Fuzzy Sets Systems, Vol. 1, 3-28 (1978) · Zbl 0377.04002
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.