Skip Navigation


Journal of Logic and Computation Advance Access originally published online on February 1, 2008
Journal of Logic and Computation 2008 18(5):721-738; doi:10.1093/logcom/exm092
This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Dubois, D.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

© The Author, 2008. Published by Oxford University Press. All rights reserved. For Permissions, please email: journals.permissions@oxfordjournals.org

This article appears in the following Journal of Logic and Computation issue: Special Issue: Belief Revision in Rational Agents [View the issue table of contents]

Original Articles

Three Scenarios for the Revision of Epistemic States*

Didier Dubois

IRIT-CNRS, Université de Toulouse, France. E-mail: dubois{at}irit.fr

Received 18 September 2007.

This position paper discusses the difficulty of interpreting the iterated belief revision problem. Axioms of iterated belief revision are often presented as extensions of the AGM axioms, upon receiving a sequence of inputs, likely to alter not only the belief set, but also the epistemic entrenchment relation underlying the revision operator. Iterated belief revision presupposes that more recent inputs have priority over less recent ones. We argue that this view of iterated revision is at odds with the suggestion of Gärdenfors and Makinson, that belief revision and non-monotonic reasoning are two sides of the same coin. It is not clear that non-monotonic reasoning modifies the ranking of possible worlds implicit in default rules. We lay bare three different paradigms of revision based on specific interpretations of the epistemic entrenchment implicitly at work and of the input information. If the epistemic entrenchment stems from default rules and the input is a specific piece of evidence, then AGM revision is a matter of changing plausible conclusions, and iterated revision makes no sense. However, if the epistemic entrenchment encodes uncertain factual evidence and the input information as well, then iterated revision reduces to prioritized merging. A third problem where iteration makes sense corresponds to the revision, by the addition of new default rules, of a conditional knowledge base describing background information. The three scenarios are compared with similar problems in the framework of probabilistic reasoning.

Keywords: Belief revision; uncertainty; non-monotonic reasoning; probability theory; possibility theory; Bayesian networks; belief functions

*This position article was triggered by discussions with Jérôme Lang and Jim Delgrande at a Belief Revision seminar in Dagstuhl, in August 2005, and presented at the 2006 Non-Monotonic Reasoning Workshop, Windermere, UK.



References

  1. Adams E. The Logic of Conditionals (1975) Reidel, UK, Dordrecht, The Netherlands.
  2. Alchourrón C, Gärdenfors P, Makinson D. On the logic of theory change: partial meet contraction and revision functions. Journal of Symbolic Logic (1985) 50:510–530.[CrossRef][Web of Science]
  3. Ben-Amor N, Benferhat S, Mellouli K. Anytime propagation algorithm for min-based possibilistic graphs. Soft Computing (2003) 8:150–161.[Web of Science]
  4. Benferhat S, Dubois D, Garcia L, Prade H. On the transformation between possibilistic logic bases and possibilistic causal networks. International Journal of Approximate Reasoning (2002) 29:135–173.[CrossRef][Web of Science]
  5. Benferhat S, Dubois D, Kaci S, Prade H. Encoding information fusion in possibilistic logic: a general framework for rational syntactic merging. In. In: Proceedings of 14th European Conference on Artificial Intelligence (ECAI2000) (2000) Amsterdam: IOS Press. 3–7.
  6. Benferhat S, Dubois D, Lagrue S, Papini O. Making revision reversible: an approach based on polynomials. Fundamenta Informaticae (2002) 53:251–280.[Web of Science]
  7. Benferhat S, Dubois D, Prade H. Nonmonotonic reasoning, conditional objects and possibility theory. Artificial Intelligence (1997) 92:259–276.[CrossRef][Web of Science]
  8. Benferhat S, Dubois D, Prade H. Possibilistic and standard probabilistic semantics of conditional knowledge. Journal of Logic and Computation (1999) 9:873–895.[Abstract/Free Full Text]
  9. Benferhat S, Dubois D, Prade H, Williams MA. A practical approach to fusing prioritized knowledge bases. In. (1999) Springer, Berlin. 222–236. Proceedings of 9th Portuguese Conference on Artificial Intelligence Lecture Notes in Artificial Intelligence.
  10. Benferhat S, Dubois D, Prade H, Williams MA. A practical approach to revising prioritized knowledge bases. Studia Logica (2002) 70:105–130.[CrossRef]
  11. Benferhat S, Kaci S. Fusion of possibilistic knowledge bases from a postulate point of view. International Journal of Approximate Reasoning (2003) 33:255–285.[CrossRef][Web of Science]
  12. Biazzo V, Gilio A, Lukasiewicz T, Sanfilippo G. Probabilistic Logic under Coherence, Model-Theoretic Probabilistic Logic, and Default Reasoning in System P. Journal of Applied Non-Classical Logics (2002) 12:189–213.[CrossRef]
  13. Boutilier C. Revision sequences and nested conditionals. In. In: Proceedings of IJCAI'93 (1993) Menlo Park, CA: AAAI Press. 519–525.
  14. Boutilier C, Brafman RI, Domshlak C, Hoos HH, Poole D. Cp-nets: a tool for representing and reasoning with conditional ceteris paribus preference statements. Journal of Artificial Intelligence Research (2004) 21:135–191.[Web of Science]
  15. Boutilier C, Goldszmidt M. Revision by conditionals beliefs. In. (1993) Menlo Park, CA: AAAI Press. 649–654. Proceeding of the 11th National Conference on Artificial Intelligence (AAAI'93).
  16. Darwiche A, Pearl J. On the logic of iterated belief revision. Artificial Intelligence (1997) 89:1–29.[CrossRef][Web of Science]
  17. Domotor Z. Probability kinematics and representation of belief change. Philosophy of Science (1980) 47:284–403.
  18. Domotor Z. Probability kinematics – conditional and entropy principles. Synthese (1985) 63:74–115.
  19. Dubois D, Fargier H, Prade H. Ordinal and probabilistic representations of acceptance. Journal of Artificial Intelligence Research (2004) 22:23–56.[Web of Science]
  20. Dubois D, Fargier H, Prade H. Acceptance, conditionals, and belief revision. In. In: Conditionals, Information, and Inference (2005) Springer, Berlin. 38–58. Vol. 3301 of Lecture Notes in Artificial Intelligence.
  21. Dubois D, Lang J, Prade H. Possibilistic logic. Handbook of Logic in Artificial Intelligence and Logic Programming, In—Gabbay DM, Hogger CJ, Robinson JA, eds. (1994) Vol. 3. Oxford: Clarendon Press. 439–513.
  22. Dubois D, Moral S, Prade H. Belief change rules in ordinal and numerical uncertainty theories. In:. Belief Change—Dubois D, Prade H, eds. (1998) Dordrecht: Kluwer Acad. Publ. 311–392. Vol. 3 in Handbook on Defeasible Reasoning and Uncertainty Management Systems.
  23. Dubois D, Prade H. Belief change and possibility theory. In:. In: Belief Revision—Gärdenfors P, ed. (1992) Cambridge UK: Cambridge University Press. 142–182.
  24. Dubois D, Prade H. Non-standard theories of uncertainty in knowledge representation and reasoning. The Knowledge Engineering Review (1994) 9:399–416.
  25. Dubois D, Prade H. A synthetic view of belief revision with uncertain inputs in the framework of possibility theory. International Journal of Approximate Reasoning (1997) 17:295–324.[CrossRef][Web of Science]
  26. Dubois D, Prade H. Possibility theory in information fusion. In. Data Fusion and Perception (2001) Springer, Berlin. 53–76. Vol. 431 of CISM Courses and Lectures.
  27. Fishburn PC. The axioms of subjective probabilities. Statistical Science (1986) 1:335–358.[Medline]
  28. Freund M. On the revision of preferences and rational inference processes. Artificial Intelligence (2004) 152:105–137.[CrossRef][Web of Science]
  29. Friedman N, Halpern J. Belief revision: a critique. In. In: Proceedings of KR'96 (1996) 421–631.
  30. Friedman N, Halpern JY. Plausibility measures and default reasoning. In. In: Proceedings of AAAI'96 (1996) International Conference on Principles of Knowledge Representation and Reasoning, Morgan Kaufmann: San Francisco. 1297–1304.
  31. Gärdenfors P. Knowledge in Flux: Modeling the Dynamics of Epistemic States (1988) Menlo Park, Ca: MIT Press, AAAI Press.
  32. Gärdenfors P, Makinson D. Nonmonotonic inference based on expectations. Artificial Intelligence (1994) 65:197–245.[Medline]
  33. Grove A. Two modellings for theory change. Journal of Philosophical Logic (1988) 17:157–170.[Web of Science]
  34. Maynard-Reid Pedrito II, Shoham Yoav. Journal of Logic, Language and Information (2001) 10:183–209. Belief fusion: aggregating pedigreed belief states.[CrossRef]
  35. Lang J, Delgrande J, Dubois D. Iterated belief revision as prioritized merging. In. In: Proceedings of KR'06, Windermere, UK (2006) International Conference on Principles of Knowledge Representation and Reasoning. Menlo Park, CA: AAAI Press. 210–220.
  36. Jeffrey R. The Logic of Decision (1965) New York: McGraw-Hill.
  37. Jin Y, Thielscher M. Iterated revision, revised. In. Proceedings of IJCAI_05 (2005) 478–483.
  38. Kelly Kevin T. Iterated belief revision, reliability, and inductive amnesia. Erkenntnis (1999) 50:7–53.[CrossRef]
  39. Kern-Isberner G. Conditionals in Nonmonotonic Reasoning and Belief Revision (2001) Berlin: Springer. Vol. 2087 of Lecture Notes in Artificial Intelligence.
  40. Konieczny S, Pino Pérez R. Merging information under constraints: a qualitative framework. Journal of Logic and Computation (2002) 12:773–808.[Abstract/Free Full Text]
  41. Kraus S, Lehmann D, Magidor M. Nonmonotonic reasoning, preferential models and cumulative logics. Artificial Intelligence (1990) 44:167–207.[CrossRef][Web of Science]
  42. Lehmann D. Belief revision, revised. In. In: Proceedings of IJCAI'95 (1995) Menlo Park, Ca: AAAI Press. 1534–1540.
  43. Lehmann D, Magidor M. What does a conditional knowledge base entail? Artificial Intelligence (1992) 55:1–60.[CrossRef][Web of Science]
  44. Lewis D. Counterfactuals (1973) Basil Blackwell, UK.
  45. Makinson D, Gärdenfors P. Relations between the logic of theory change and nonmonotonic logic. In. In: The Logic of Theory Change (1991) Berlin: Springer. 185–205. Vol. 465 of Lecture Notes in Artificial Intelligence.
  46. Maung I. Two characterizations of a minimum information principle for possibilistic reasoning. In: International Journal of Approximate Reasoning (1995) 12. San Francisco: Morgan Kaufmann. 133–156.[CrossRef][Web of Science]
  47. Nayak A. Iterated belief change based on epistemic entrenchment. Erkenntnis (1994) 41:353–390.[CrossRef]
  48. Nayak A, Foo N, Pagnucco M, Sattar A. Changing conditional beliefs unconditionally. In. Proceedings of TARK96 (1996) 119–135.
  49. Nayak A, Pagnucco M, Peppas P. Dynamic belief revision operators. In: Artificial Intelligence (2003) 146:193–228.[CrossRef][Web of Science]
  50. Paris J. The Uncertain Reasoner_s Companion (1994) Cambridge: Cambridge University Press.
  51. Pearl J. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference (1988) San Francisco: Morgan Kaufmann.
  52. Pearl J. System z: a natural ordering of defaults with tractable applications to default reasoning. In. (1990) San Mateo, CA: Morgan & Kaufmann. 121–135. Proceedings of the 3rd Conference on Theoretical Aspects of Reasoning about Knowledge (TARK'90).
  53. Rott H. Change, Choice and Inference (2001) Oxford, UK: Oxford University Press.
  54. Shafer G. A Mathematical Theory of Evidence (1976) Princeton, N.J: Princeton University Press.
  55. Spohn W. Ordinal conditional functions: a dynamic theory of epistemic states. In. In: Causation in Decision, Belief Change and Statistics—Harper William L, Skyrms Brian, eds. (1988) volume 2. Dordrecht, The Netherlands: Kluwer Academic Publishers. 105–134.
  56. van Fraassen B. Rational belief and probability kinematics. (1980) 47:165–187. Philosophy of Science.
  57. van Fraassen B. A problem for relative information minimizers. British Journal of the Philosophy of Science (1981) 33:375–379.
  58. Weydert E. How to revise ranked probabilities. In. (2000) Amsterdam: IOS Press. 38–44. Proceedings of the 14th European Conference on Artificial Intelligence (ECAI2000).
  59. Williams MA. Iterated theory-based change. In. (1995) Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI_95). Menlo Park, Ca: AAAI Press. 1541–1550.
  60. Williams MA. On the logic of theory base change. In. In: Proceedings of the European Workshop on Logics in Artificial Intelligence (JELIA'95) (1995) Berlin: Springer Verlag. 1541–1550. Vol. 838 of Lecture Notes in Computer Sciences.

Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?



This Article
Right arrow Abstract Freely available
Right arrow Full Text (PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in ISI Web of Science
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Dubois, D.
Right arrow Search for Related Content
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?