Mary-Anne Williams 1541

IJCAI 1995

TL;DR

This paper introduces "Generalized Update" (GU), a novel model for belief change that unifies belief revision (handling static worlds) and belief update (handling dynamic worlds). GU allows agents to infer information about past states of the world from observations, leading to more realistic and robust belief adjustments in dynamic environments.

What Problem Does This Paper Address?

Intelligent agents need to maintain beliefs about their environment. These beliefs can become incorrect due to two main reasons: either the agent's initial beliefs were mistaken (belief revision), or the world itself has changed (belief update). Existing AI models often treat these as separate processes. Belief revision, formalized by AGM postulates, handles correcting mistaken beliefs in a static world. Belief update, as proposed by Winslett and Katsuno & Mendelzon, handles changes in the world but struggles when an observation about a changed world also provides information about the prior state of that world. For example, if an agent believes it's snowing and a truck arrives earlier than expected, the agent might infer that it didn't snow, rather than assuming some extraordinary event allowed the truck to speed through. Current update models don't naturally handle this kind of inference, forcing agents to make implausible assumptions. This paper aims to bridge this gap by creating a unified model that captures both aspects of belief change.

Methods

The authors propose a semantic model for Generalized Update (GU) based on ranked belief structures. Instead of just a set of beliefs (K), an agent's state is represented by a ranking function (κ) that assigns a plausibility score to each possible world. This ranking captures both the agent's beliefs (worlds with rank 0 are the most plausible) and the degree of willingness to give up beliefs (epistemic entrenchment).

GU is built upon a framework involving:

  • Worlds (W): Possible states of the world.
  • Ranking (κ): An epistemic state assigning plausibility to worlds.
  • Events (E): Actions or occurrences that can change the world. Each event is associated with a partial κ-ranking over worlds, indicating the plausibility of transitions from one world to another.
  • Event Orderings (μ): For each world, an ordering that ranks the plausibility of different events occurring in that world.

When an observation (A) occurs, GU calculates an updated ranking (κ°) by considering the most plausible transitions from the current state that result in A. This involves combining the plausibility of the initial world, the event, and the outcome. The new belief set is then derived from this updated ranking.

The paper also defines "static" GU models, where only a null event exists, to show how AGM belief revision can be seen as a special case of GU.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unifying Revision and Update: The core insight is that real-world belief change often involves both correcting past beliefs and adapting to a changing world. GU provides a single framework to handle this.
  • Observations Inform Past States: A key advantage of GU is its ability to use observations about the current state to infer information about the prior state. This is crucial for realistic reasoning, as seen in the snow/truck example.
  • Abductive Explanations: GU can be interpreted as finding the most plausible "abductive explanations" for an observation, where an explanation is a combination of a prior state, an event, and an outcome.
  • Ranked Structures are Key: Using ranked belief structures (κ-rankings) is essential for comparing and combining the plausibility of worlds, events, and outcomes, allowing for nuanced belief adjustments.
  • AGM Revision as a Special Case: By restricting events to a "null event," GU reduces to AGM belief revision, formally verifying the intuition that revision is for static worlds.

Key Results

The paper presents several propositions and theorems:

  • Proposition 1: Shows that the generalized update of a belief set K by observation A is equivalent to revising the updated epistemic state (K°) by A.
  • Proposition 2 & 3: Demonstrate that GU, under certain conditions (like the existence of a null event and completeness), satisfies many of the standard KM update postulates.
  • Theorem 5: States that if a GU model is complete (all satisfiable sentences are explainable) and centered (includes a null event), its induced operator satisfies all KM update postulates (U1-U9).
  • Theorem 6: Shows that if a GU model is "static" (only the null event exists), its induced operator satisfies all AGM belief revision postulates (R1-R8).

Limitations and Future Work

  • Representation Languages: The authors acknowledge the need for more sophisticated representation languages to concisely express events (with defeasible effects), defeasible beliefs, and other aspects of the GU model.
  • Iterated Updates: The paper touches upon the complexity of iterated updates (sequences of events and observations) and suggests that further work is needed to adapt existing theories of iterated revision to this framework.
  • Beliefs about Dynamics: The current model assumes events and outcomes are fixed. Future work could explore agents having beliefs about these dynamics themselves, which would also be subject to revision.
  • Concurrent Events: Handling concurrent events and actions is noted as a significant area for future research.
  • Generalizing Sequences: The plausibility of a sequence of transitions might not simply be a function of individual transitions, requiring more sophisticated update criteria.

Summary updated

BibTeX
@inproceedings{1995mary,
  title = {{Mary-Anne Williams 1541}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1995},
}
Figure