A survey of belief revision and updating rules in various uncertainty models. (English) Zbl 0805.68114
Summary: The paper proposes a parallel survey of revision and updating operations available in the probability theory and in the possibility theory framework. In these two formalisms the current state of knowledge is generally represented by a \([0,1]\)-valued function whose domain is an exhaustive set of mutually exclusive possible states of the world. However, in possibility theory, the unit-interval can be viewed as a purely ordinal scale. Two general kinds of operations can be defined on this assignment function: conditioning, and imaging (or “projection”). The difference between these two operations is analogous to the one made between belief revision à la Gärdenfors and updating à la Katsuno and Mendelzon in the logical framework. In the probabilistic framework these two operations are respectively Bayesian conditioning and Lewis’ imaging. Counterparts to these operations are presented for the possibilistic framework including the case of conditioning upon uncertain observations, and justifications are given which parallel the ones existing for the probabilistic operations. More particularly, it is recalled that possibilistic conditioning satisfies all the postulates proposed by Alchourrón, Gärdenfors and Makinson for belief revision (stated in possibilistic terms), and it is proved that possibilistic imaging satisfies all the postulates proposed by Katsuno and Mendelzon. The situation where our current knowledge is stated in terms of weighted logical propositions is discussed in connection to possibility theory. Revision in other more complex numerical formalisms, namely belief and plausibility functions, and upper and lower probabilities is also surveyed. Recent results on the revision of conditional knowledge bases are also reviewed. The frameworks of belief functions, upper and lower probabilities and conditional bases are more sophisticated than the previous ones because they enable to distinguish between factual evidence and generic knowledge in a cognitive state. This framework leads to two forms of belief revision respectively taking care of the revision of evidence and the revision of knowledge.
Keywords:
models of uncertainty; updating; possibility theory; belief revision; possibilistic imaging; conditional knowledge basesReferences:
| [1] | Alchourrón, Journal of Symbolic Logic 50 pp 510– (1985) |
| [2] | Knowledge in Flux: Modeling the Dynamics of Epistemic States, the MIT Press, Cambridge, MA, 1988. · Zbl 1229.03008 |
| [3] | and , ”On the difference between updating a knowledge base and revising it,” In J. Allen, R. Fikes and E. Sandewall (Eds.), Proc. of the 2nd Inter. Conf. on Principles of Knowledge Representation and Reasoning (KR’91), Cambridge, MA, April 22-25, 1991, pp. 387–394. · Zbl 0765.68197 |
| [4] | Revised version in (Ed.), Belief Revision, Cambridge University Press, Cambridge, UK, 1992, pp. 183–203. · doi:10.1017/CBO9780511526664 |
| [5] | Lewis, The Philosophical Review 85 pp 297– (1976) |
| [6] | ”Ordinal conditional functions: A dynamic theory of epistemic states,” In and (Eds.), Causation in Decision, Belief Change, and Statistics, Vol. 2, D. Reidel, Dordrecht, 1988, pp. 105–134. · doi:10.1007/978-94-009-2865-7_6 |
| [7] | and , ”Belief change and possibility theory,” In (Ed.), Belief Revision, Cambridge University Press, Cambridge, UK, 1992, pp. 142–182. · doi:10.1017/CBO9780511526664.006 |
| [8] | Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, Morgan Kaufmann, San Mateo, CA, 1988. |
| [9] | De Finetti, Ann. Inst. Poincaré 7 pp 1– (1937) |
| [10] | Translated in: and (Eds.), Studies in Subjective Probability, Wiley, New York, 1964. · Zbl 0133.39802 |
| [11] | The Foundations of Statistics, Dover, New York, 1954. · Zbl 0055.12604 |
| [12] | Lindley, Int. Statist. Rev. 50 pp 1– (1982) |
| [13] | ”Conditionalization, observation and change of preference,” In and (Eds.), Foundations of Probability Theory, Statistical Inference, and Statistical Theories of Science, D. Reidel, Dordrecht, 1976, Vol. 1, pp. 205–259. · doi:10.1007/978-94-010-1853-1_9 |
| [14] | Cox, American J. of Physics 14 pp 1– (1946) |
| [15] | ”An axiomatic framework for belief updates,” In (Eds.), Uncertainty in Artificial Intelligence 2, North-Holland, Amsterdam, 1988, pp. 11–22. · doi:10.1016/B978-0-444-70396-5.50007-8 |
| [16] | Williams, British J. of the Philosophy of Science 31 pp 131– (1980) |
| [17] | and (Eds.), Ifs – Conditionals, Belief, Decision, Change, and Time, D. Reidel, Dordrecht, 1981. |
| [18] | Dempster, Ann. Math. Statist. 38 pp 325– (1967) |
| [19] | Sombé, Int. J. of Intelligent Systems 9 |
| [20] | The Logic of Decision, McGraw-Hill, New York, 1965. |
| [21] | and , Rational Consensus in Science and Society, D. Reidel Publ. Co., Boston, 1981. · doi:10.1007/978-94-009-8520-9 |
| [22] | Van Fraassen, Philosophy of Science 47 pp 165– (1980) · Zbl 1273.03039 |
| [23] | Domotor, Philosophy of Science 47 pp 384– (1980) |
| [24] | Domotor, Synthese 63 pp 74– (1985) |
| [25] | Yager, Human Systems Management 3 pp 246– (1983) |
| [26] | Zadeh, Fuzzy Sets and Systems 1 pp 3– (1978) · Zbl 0377.04002 |
| [27] | and , ”Automated reasoning using possibilistic logic: Semantics, belief revision, variable certainty weights,” In Proc. of the 5th Workshop on Uncertainty in Artificial Intelligence, Windsor, Ontario, Aug. 18-20, 1989, pp. 81–87. Extended version to appear in IEEE Trans. on Data and Knowledge Engineering. |
| [28] | Dubois, Int. J. of Approximate Reasoning 4 pp 419– (1990) |
| [29] | and , ”A glance at non-standard models and logics of uncertainty and vagueness,” In (Ed.), Philosophy of Probability, Kluwer, Amsterdam, 1993, pp. 169–222. · doi:10.1007/978-94-015-8208-7_9 |
| [30] | Yager, Cybernetics and Systems 16 pp 1– (1985) |
| [31] | Hisdal, Fuzzy Sets and Systems 1 pp 283– (1978) |
| [32] | Dubois, Int. J. of Approximate Reasoning 4 pp 23– (1990) |
| [33] | Decision, Order and Time in Human Affairs, (2nd edition) Cambridge University Press, Cambridge, MA, 1961. |
| [34] | and , ”Possibilistic inference under matrix form,” In and (Eds.), Fuzzy Logic in Knowledge Engineering, Verlag TÜY Rheinland, Köln, 1986, pp. 112–126. |
| [35] | A Mathematical Theory of Evidence, Princeton University Press, Princeton, 1976. |
| [36] | and , ”Possibilistic logic, preferential models, non-monotonicity and related issues,” In Proc. of the 12th Inter. Joint Conf. on Artificial Intelligence (IJCAI-91), Sydney, Australia, Aug. 24-30, 1991, pp. 419–424. · Zbl 0744.68116 |
| [37] | Zadeh, Information and Control 8 pp 338– (1965) |
| [38] | and , ”Updating with belief functions, ordinal conditional functions and possibility measures,” In , and (Eds.), Uncertainty in Artificial Intelligence 6, North-Holland, Amsterdam, 1991, pp. 311–329. · Zbl 0741.68091 |
| [39] | ”A general non-probabilistic theory of inductive reasoning,” In , and (Eds.), Uncertainty in Artificial Intelligence 4, North-Holland, Amsterdam, 1990, pp. 149–158. · doi:10.1016/B978-0-444-88650-7.50017-2 |
| [40] | Shenoy, Int. J. of Approximate Reasoning 5 pp 149– (1991) |
| [41] | and , Rule-Based Expert Systems - the MYCIN Experiments of the Stanford Heuristic Programming Project, Addison-Wesley, Reading, 1984. |
| [42] | Dubois, Computational Intelligence 4 pp 244– (1988) |
| [43] | and , ”Systems Z+: A formalism for reasoning with variable strength defaults,” In Proc. of the National Conf. on Artificial Intelligence (AAAI’91), Anaheim, CA, 1991, pp. 394–404. |
| [44] | Robust Statistics, Wiley, New York, 1981. · Zbl 0536.62025 · doi:10.1002/0471725250 |
| [45] | Suppes, Synthese 36 pp 427– (1977) |
| [46] | and , ”The concept of conditional fuzzy measure,” Int. J. of Intelligent Systems, 237–246 (1990). · Zbl 0694.68058 |
| [47] | and , ”A new approach to updating beliefs,” In Research Report n{\(\deg\)} RJ 7222 (67989), IBM Research Division, Almaden Research Center, San Jose, Ca., USA, 1989. |
| [48] | ”Approximate deduction in single evidential bodies,” In Proc. of the 2nd Workshop on Uncertainty in Artificial Intelligence, Univ. Pennsylvania, Aug. 8-10, 1986, pp. 215–222. |
| [49] | ”Bayesian updating and belief functions,” In Proc. of the 3rd Inter. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU), Paris, July 2-6, 1990, pp. 449–451. |
| [50] | Kyburg, Artificial Intelligence 31 pp 271– (1987) |
| [51] | Dubois, Int. J. of Approximate Reasoning 6 pp 295– (1992) |
| [52] | and , ”Updating ambiguous beliefs,” In (Ed.), Theoretical Aspects of Reasoning About Knowledge (Proc. of the 4th Conf. TARK’92), Morgan & Kaufmann, San Mateo, CA, 1992, pp. 143–162. |
| [53] | and , ”Updating uncertain information,” In and (Eds.), Uncertainty in Knowledge Bases (Proc. of the 3rd Inter. Conf. on Information Processing and Management of Uncertainty in Knowledge-Based Systems (IPMU’90), Paris, July 1990), Lecture Notes in Computer Science, Vol. 521, Springer Verlag, Berlin, 1991, pp. 58–67. |
| [54] | ”Belief functions,” In , and (Eds.), Non-Standard Logics for Automated Reasoning, Academic Press, New York, 1988, pp. 253–286. |
| [55] | Smets, IEEE Trans. on Pattern Analysis and Machine Intelligence 12 pp 447– (1990) |
| [56] | Ishihashi, Int. J. of Approximate Reasoning 3 pp 143– (1989) |
| [57] | Shafer, Philosophy of Science 48 pp 337– (1981) |
| [58] | ”Generalizing Jeffrey conditionalization,” In , and (Eds.), Proc. of the 8th Conf. on Uncertainty in Artificial Intelligence, Stanford, July 17-19, 1992, Morgan & Kaufmann, San Mateo, CA, 1992, pp. 331–335. |
| [59] | ”Jeffrey’s rule of conditioning generalized to belief functions,” Tech. Report No. TR/IRIDIA/93-2/2, 1993. Also in and (Eds.), Proc. of the 9th Conf. on Uncertainty in Artificial Intelligence, Washington, DC, 1993, Morgan & Kaufmann, San Mateo, CA, 1993, pp. 500–505. |
| [60] | and , ”Possibilistic logic,” to appear in and (Eds.), Handbook of Logic in Artificial Intelligence and Logic Programming, Oxford University Press, 1993, pp. 439–513. |
| [61] | Dubois, IEEE Trans. on Systems, Man and Cybernetics 17 pp 474– (1987) |
| [62] | Dubois, Int. J. on Approximate Reasoning 4 pp 1– (1990) |
| [63] | ”A theory of approximate reasoning,” In and (Eds.), Machine Intelligence, Vol. 9, Wiley, New York, 1979, pp. 149–194. 56. |
| [64] | ”Generalizing Jeffrey conditionalization,” In , and (Eds.), Proc. of the 8th Conf. on Uncertainty in Artificial Intelligence, Stanford, July 17-19, 1992, Morgan & Kaufmann, San Mateo, CA, 1992, pp. 331–335. |
| [65] | ”System Z: A natural ordering of defaults with tractable applications to default reasoning,” In (Ed.), Proc. of the 3rd Conf. on Theoretical Aspects of Reasoning about Knowledge (TARK’90), Morgan & Kaufmann, San Mateo, CA, 1990, pp. 121–135. |
| [66] | and , ”Rank-based systems: A simple approach to belief revision, belief update, and reasoning about evidence and actions,” In B. Nebel, C. Rich and W. Swartout (Eds.), Proc. of the 3rd Inter. Conf. on Principles of Knowledge Representation and Reasoning (KR’92), Cambridge, MA, Oct. 25-29, 1992, pp. 661–672. |
| [67] | and , ”Inconsistency in possibilistic knowledge bases: to live with it or not to live with it,” In and (Eds.), Fuzzy Logic for the Management of Uncertainty, Wiley, New York, 1992, pp. 335–350. |
| [68] | ”Preferred subtheories: an extended logical framework for default reasoning,” In Proc. of the 11th Inter. Joint Conf. on Artificial Intelligence (IJCAI’89), Detroit, 1989, pp. 1043–1048. |
| [69] | ”Syntax-based approaches to belief revision,” In (Ed.), Belief Revision, Cambridge University Press, Cambridge, UK, 1992, pp. 52–88. · doi:10.1017/CBO9780511526664.003 |
| [70] | , , and , ”Inconsistency management and prioritized syntax-based entailment,” In Proc. of the 13th Inter. Joint Conf. on Artificial Intelligence (IJCAI’93), Chambéry, France, 1993, pp. 640–645. |
| [71] | ”What does a conditional knowledge base entail?,” In and (Eds.), Proc. of the 1st Inter. Conf. on Principles of Knowledge Representation and Reasoning, Toronto, Ontario, 1989, pp. 212–222. · Zbl 0709.68104 |
| [72] | Lehmann, Artificial Intelligence 55 pp 1– (1992) |
| [73] | Kraus, Artificial Intelligence 44 pp 167– (1990) |
| [74] | and , ”Representing default rules in possibilistic logic,” In and (Eds.), Proc. of the 3rd Inter. Conf. on Principles of Knowledge Representation and Reasoning (KR’92), Cambridge, MA, 1992, pp. 673–684. |
| [75] | Reasoning About Change – Time and Causation from the Standpoint of Artificial Intelligence, the MIT Press, Cambridge, MA, 1988. |
| [76] | Goldszmidt, Artificial Intelligence 52 pp 121– (1991) |
| [77] | and , ”Revision by conditionals beliefs,” In Proc. of the 11th National Conf. on Artificial Intelligence (AAAI’93), Washington, DC, July 11-15, 1993, pp. 649–654. |
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.
