A Consistency-Based Model for Belief Change: Preliminary Report

AAAI 2000

TL;DR

This paper introduces a novel, general framework for belief change that unifies various existing approaches. It offers a flexible way to model how an agent updates its beliefs when presented with new information, ensuring consistency and allowing for different revision strategies. This work is significant because it provides a unified, implementable foundation for belief revision, addressing limitations in prior methods, particularly for iterated belief change.

What Problem Does This Paper Address?

Belief change is a fundamental aspect of artificial intelligence, dealing with how an agent modifies its knowledge base when encountering new information. The dominant paradigm, AGM (Alchourron, Gärdenfors, and Makinson), provides a set of rationality postulates for belief revision and contraction. However, existing approaches often differ in their underlying mechanisms and can struggle with iterated belief change (revising beliefs multiple times). This paper aims to bridge this gap by proposing a general, consistency-based framework that can express existing methods and offers new insights, especially for handling sequences of belief updates. The challenge is to create a model that is both theoretically sound, capturing the essence of rational belief change, and practically implementable.

Methods

The core of the proposed framework involves a clever use of separate alphabets and a maximization process. When revising a knowledge base $K$ with a sentence $\alpha$:

  1. Disjoint Alphabets: $K$ and $\alpha$ are translated into separate, but isomorphic, alphabets. This means atomic propositions in $K$ are renamed (e.g., $p$ becomes $p'$), and similarly for $\alpha$.
  2. Maximizing Equivalences: The framework then assumes that as many renamed atoms in $\alpha$ are equivalent to their corresponding renamed atoms in $K$ as is consistently possible. This is achieved by finding "maximal sets of equivalences" ($EQ$) between the original and renamed propositions.
  3. Incorporation and Projection: Using these equivalences, as much of the original knowledge $K$ is incorporated into the new information $\alpha$ as is consistent. The final revised belief state is then projected back into the original alphabet.

This process leads to two main notions of revision:

  • Choice Revision: Selects one "extension" (a way to incorporate $K$ into $\alpha$) as the revised belief state. This is argued to be more efficient and potentially useful in certain scenarios.
  • Skeptical Revision: Takes the intersection of all possible extensions, providing a more conservative and guaranteed consistent outcome.

The framework also naturally accommodates integrity constraints (both static and dynamic) and can be expressed using finite representations, making it suitable for implementation.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Unified Framework: The paper presents a single, general framework that can express a variety of belief revision and update approaches, including those based on minimal change and distance between models.
  • Separate Alphabets for Clarity: Using disjoint alphabets for the knowledge base and the new information is a key technique that simplifies the process of identifying and maximizing equivalences.
  • Choice Revision vs. Skeptical Revision: The distinction between "choice" and "skeptical" revision is crucial. Choice revision offers potential efficiency gains and a different perspective on how agents might learn, while skeptical revision provides a more robust, intersection-based outcome.
  • Iterated Revision Handling: The framework offers a distinct approach to iterated belief change, differing from methods based on ordinal conditional functions. The authors argue that some standard postulates for iterated revision might be too restrictive.
  • Implementability: The authors emphasize that their framework is well-suited for implementation due to its finite representation capabilities and the potential for efficient choice revision.
  • Integrity Constraints: The model elegantly incorporates both consistency-based and entailment-based static integrity constraints, as well as dynamic constraints, into the belief change process.

Key Results

  • The framework provides formal definitions for both choice and skeptical belief revision and contraction.
  • Theorems demonstrate that the proposed revision and contraction operators satisfy many of the standard AGM postulates, with some weaker versions for consistency-based postulates (e.g., $K+\alpha = K_\perp$ iff $K=K_\perp$ or $\models \neg \alpha$).
  • The paper shows that the framework can be expressed using finite representations of knowledge bases, rather than requiring deductively closed sets.
  • A key result (Theorem 11) shows that when limiting the range of equivalences ($EQ$), only atomic sentences common to both the knowledge base and the revision sentence need to be considered, simplifying the process.
  • The framework is shown to support belief update (Definition 8) and can capture existing update operators.

Limitations and Future Work

  • Choice Revision's "Overly Strong" Conclusions: The authors acknowledge that choice revision might sometimes draw "overly strong conclusions," though they argue this is less problematic than in other non-monotonic reasoning contexts because inaccuracies can be corrected in subsequent revisions.
  • Iterated Revision Postulates: The authors suggest that their operators do not satisfy all Darwiche-Pearl postulates for iterated revision, arguing that these postulates might be too restrictive. This opens avenues for further research into the nature of rational iterated belief change.
  • Complexity: While choice revision is shown to be more efficient, the general complexity of deciding entailment within the framework is noted as II-complete, though specific sub-problems are shown to be in P NP.
  • Future Work: The paper suggests exploring the full generality of the framework to express other existing approaches to belief change and further investigating the implications of choice revision in practical applications. The authors also hint at the possibility of using the framework to capture knowledge base merging.

Summary updated

BibTeX
@inproceedings{2000consistency,
  title = {{A Consistency-Based Model for Belief Change: Preliminary Report}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2000},
}
Figure