Leendert W N van der Torre

IJCAI 1995

TL;DR

This paper revisits the foundational AGM framework for belief revision, proposing a new framework that explicitly handles iterated revisions. It demonstrates that the original AGM postulates, when extended to iterated revisions, lead to a triviality result, meaning only a simplistic revision operation satisfies them. The authors introduce a new set of postulates and a corresponding model-theoretic semantics that offer a more nuanced approach to belief updates.

What Problem Does This Paper Address?

Intelligent agents need to update their beliefs when new information arrives. The seminal AGM (Alchourrón, Gardenfors, and Makinson) framework provides a formal basis for single-step belief revision: how to update a belief set (a theory) with a new piece of information. However, real-world agents often encounter information sequentially, requiring iterated belief revision. The original AGM postulates, while elegant for single revisions, don't explicitly address the properties of sequences of revisions. This paper argues that simply applying single-step revision repeatedly might not capture the full picture of how beliefs should evolve over time, especially concerning how past revisions influence future ones. The core problem is to formalize rational behavior for agents that learn and revise beliefs over multiple steps.

Methods

The paper introduces a new framework for studying iterated belief revision. Instead of just considering a belief set $A$ and a formula $\alpha$ for revision, the new framework uses sequences of formulas to represent the history of information an agent has received. A revision operation is then defined over these sequences.

Key methodological contributions include:

  • Triviality Result: The authors prove that if the original AGM postulates are extended with certain natural postulates for iterated revisions (specifically, K+1 to K+6, C1, and D1), the only possible revision operation is the "trivial revision," which essentially discards all previous beliefs and accepts the new information, or a similarly simplistic outcome. This highlights a potential inadequacy in directly extending AGM to iterated scenarios without modification.
  • New Postulates: A new set of rationality postulates (11-17) is proposed. These postulates are designed to characterize reasonable iterated revision methods. They address aspects like consistency, inclusion of new information, and, crucially, how sequences of revisions interact. Postulates 14 and 15, for instance, deal with the redundancy of information and the impact of confirmations.
  • Widening Ranked Models: A model-theoretic semantics is developed using "widening ranked models." These models assign plausibility ranks to possible states of affairs. The revision process is then defined based on how the agent navigates these ranks when encountering new information. This provides a formal way to construct revision procedures that satisfy the new postulates.
  • Representation Theorem: A key result (Theorem 4) shows that any revision procedure satisfying the new postulates (11-17) can be represented by a widening ranked model. This establishes a strong connection between the syntactic postulates and the semantic models.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Problem of "Forgetting": The paper highlights that simply applying single-step AGM revisions iteratively can lead to agents "forgetting" crucial information about their revision history. Postulate 14, for example, suggests that if a piece of information is confirmed, it shouldn't influence future revisions, which might be too strong for dynamic "theory update" scenarios.
  • Iterated Revisions are Fundamentally Different: The triviality result for extended AGM postulates suggests that iterated belief revision isn't just a repeated application of single-step revision; it requires a distinct formal treatment.
  • The Principle of Minimal Change is Tricky with Iterated Revisions: The paper argues that the Principle of Minimal Change (keeping as much of the old theory as possible) becomes difficult to satisfy with iterated revisions, especially when dealing with "severe" revisions (those that fundamentally alter beliefs). The authors suggest that postulates 15 and 16, while not directly about minimal change, embody a form of "informational economy" that might conflict with it.
  • Confirmation vs. Update: The paper distinguishes between "belief revision" (updating beliefs about a static world) and "theory update" (updating beliefs about a dynamic, changing world). Postulate 14, which seems reasonable for static revision, might be problematic for dynamic updates where confirmations could provide valuable temporal information.

Key Results

  • Triviality of Extended AGM: The paper proves that under certain natural assumptions for iterated revision, the only revision operation satisfying the extended AGM postulates is trivial.
  • New Postulates Characterize Revision: The proposed postulates (11-17) are shown to be a coherent set for characterizing reasonable iterated revision methods.
  • Representation Theorem: A formal link is established between the new postulates and widening ranked models, showing that these models precisely capture the behavior defined by the postulates.
  • Postulate 15 is Powerful: Postulate 15, concerning the redundancy of information when a later revision confirms an earlier one, is presented as a significant strengthening of the AGM framework and a key element in the new postulates.

Limitations and Future Work

  • Finite Language Assumption: The representation theorem (Theorem 4) is currently proven only under the assumption of a finite number of atomic propositions. Extending this to infinite languages is a direction for future work.
  • Principle of Minimal Change Conflict: The paper acknowledges that the revision procedures defined by widening ranked models might not adequately satisfy the Principle of Minimal Change, especially for severe revisions. This tension between minimal change and other desiderata (like informational economy embodied in postulates 15 and 16) is a significant philosophical and technical challenge.
  • Theory Update vs. Belief Revision: The authors suggest that their postulates might need further refinement for "theory update" scenarios (changing beliefs about a dynamic world), particularly regarding postulate 14.
  • Retraction Postulates: The paper raises questions about the philosophical underpinnings of retraction (removing beliefs) and suggests that new postulates might be needed to distinguish between retracting beliefs due to unreliable sources versus retracting them due to new, contradictory information.
  • Open Problems: The authors explicitly mention the need for representation theorems for weaker systems and the quest for a suitable system for belief update as intriguing future research directions.

Summary updated

BibTeX
@inproceedings{1995leendert,
  title = {{Leendert W N van der Torre}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure