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.


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


[1] Adams, E.W., Probability and the logic of conditionals, (), 253-316 · Zbl 0202.30001
[2] Adams, E.W., The logic of conditionals, (1975), 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, (), 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, ()
[6] Benferhat, S.; Dubois, D.; Prade, H., Representing default rules in possibilistic logic, (), 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, () · Zbl 1045.68136
[9] Boutilier, C., What is a default priority?, (), 140-147
[10] Brewka, G., Preferred subtheories: an extended logical framework for default reasoning, (), 1043-1048 · Zbl 0713.68053
[11] Delgrande, J.P.; Schaub, T.H., A general approach to specificity in default reasoning, (), 146-157
[12] Dubois, D.; Lang, J.; Prade, H., Possibilistic logic, (), 439-513
[13] Dubois, D.; Lang, J.; Prade, H., Inconsistency in possibilistic knowledge bases - to live or not live with it, (), 335-351
[14] Dubois, D.; Prade, H., Possibility theory - an approach to computerized processing of uncertainty, (1988), 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, (), 311-346 · Zbl 0741.68091
[16] Dupin de Saint Cyr, F.; Lang, J.; Schiex, T., Penalty logic and its link with Dempster-Shafer theory, (), 204-211
[17] Eiter, T.; Lukasiewicz, T., Complexity results for default reasoning from conditional knowledge bases, (), 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, (), 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 Cambridge, MA
[22] Gilio, A., Precise propagation of upper and lower probability bounds in system \(P\), ()
[23] Goldszmidt, M., Qualitative probabilities: A normative framework for commonsense reasoning, (1992), 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, (), 399-404
[25] Goldszmidt, M.; Pearl, J., Qualitative probabilities for default reasoning, belief revision, and causal modeling, Artificial intelligence, Vol. 84, 57-112, (1996)
[26] Hsia, Y-T., A belief-function semantics for cautious non-monotonicity, (1991), 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, (), 174-181
[29] Klawonn, F.; Smets, Ph., The dynamics of belief in the transferable belief model, (), 130-137
[30] Kohlas, J.; Monney, P.A., A mathematical theory of hints. an approach to Dempster-Shafer theory of evidence, Lecture notes in economics and mathematical systems, vol. 425, (1995), 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, (), 391-398
[33] Lehmann, D., What does a conditional knowledge base entail?, (), 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, (), 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
[39] Pearl, J., Probabilistic reasoning in intelligent systems: networks of plausible inference, (1988), Morgan Kaufmann San Mateo, CA
[40] Pearl, J., System Z: A natural ordering of defaults with tractable applications to default reasoning, (), 121-135
[41] Poole, D., Average-case analysis of a search algorithm for estimating prior and posterior probabilities in Bayesian networks with extreme probabilities, (), 606-612
[42] Pinkas, G., Propositional nonmonotonic reasoning and inconsistency in symmetric neural networks, (), 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, (), 270-276
[45] Robinson, A., Non-standard analysis, (1966), 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, NJ · Zbl 0359.62002
[48] Shoham, Y., Reasoning about change - time and causation from the standpoint of artificial intelligence, (1988), MIT Press Cambridge, MA
[49] Smets, Ph., Belief functions, (), 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, (), 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, (), 131-153
[54] Smets, Ph., The transferable belief model for quantified belief representation, (), 267-301 · Zbl 0939.68112
[55] Smets, Ph.; Hsia, Y.-T., Default reasoning and the transferable belief model, (), 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, (), 105-134
[60] Touretzky, D., Implicit ordering of defaults in inheritance systems, (), 322-325
[61] Walley, P., Statistical reasoning with imprecise probabilities, (1991), Chapman and Hall London · Zbl 0732.62004
[62] Weydert, E., Defaults and infinitesimals defeasible inference by Nonarchimedean entropy maximization, (), 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, (), 372-379
[65] Wilson, N., Extended probability, (), 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. 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.