On the Logic of Theory Change Iteration of KM-Update, Revised

Liangda Fang, Tong Zhu, Quanlong Guan, Junming Qiu, Zhao-Rong Lai, Weiqi Luo, Hai Wan

Abstract

This paper refines the logical framework for iterated belief update, addressing how an agent modifies their beliefs about a dynamically evolving world upon receiving sequential information. We identify critical flaws in existing models and propose a novel approach utilizing "belief states" and "faithful collective assignments." Our findings reveal a fundamental logical inconsistency between standard principles for iterated change and the foundational Katsuno-Mendelzon (KM) rules of belief update, while providing a path forward through the compatibility of specific postulates.

Introduction

In the field of Knowledge Representation, belief change is traditionally bifurcated into two categories: Revision (AGM), which concerns learning new facts about a static world, and Update (KM), which addresses learning about a changing world. While researchers have a robust understanding of how to handle a sequence of revisions, the theory for iterated updates has remained shaky. Previous attempts to define how updates should behave over time were often too permissive or failed to account for how an agent's internal preferences—their "belief state"—evolve. This study aims to provide a mathematically sound foundation for processing a stream of updates without falling into counter-intuitive traps.

Methodology: Belief States and Collective Assignments

The authors build their framework by synthesizing and correcting two major existing theories. Instead of just looking at a "belief set" (a collection of facts), they utilize belief states (or epistemic states). A state encodes not just what is currently believed, but the agent's underlying rankings of possible worlds.

A basic representation of possible worlds for 'alarm' and 'fire' propositions used to define belief states.

They introduce Faithful Collective Assignments, a novel semantic tool that maps a belief state to a collection of partial preorders. Each preorder is centered around a specific possible world that the agent considers plausible. Furthermore, the authors migrate the famous "DP postulates" (C1–C4) from the revision context into the update context, renaming them CU1–CU4.

Synthetic Examples and Toy Worlds

As a theoretical paper in mathematical logic, this work uses synthetic examples to demonstrate logical consistency. These "toy worlds" illustrate how a naive update can lead to irrational conclusions.

Truth table for a toy world involving a book, cup, and toy across 8 possible states ($w_0$ to $w_7$).

For instance, consider a robot interacting with a table containing a book, a cup, and a toy. A naive update might lead an agent to mistakenly drop a belief about the toy simply because they were told to move the cup. The proposed framework ensures that updates are based on the most recent belief set to accurately reflect the changing state of the environment.

Key Results and the Incompatibility Bombshell

A major insight of this research is that update is significantly more complex than revision. In revision, one deals with a single ranking of worlds; in update, one must manage a collection of rankings—one for every world currently considered possible.

Perhaps the most significant finding is the Incompatibility Bombshell: the authors formally proved that postulates CU1 and CU2 (which suggest preserving old preferences if new info is consistent) are inconsistent with standard KM update rules. While these rules work perfectly in revision, the dynamic nature of a changing world means an agent cannot always preserve old rankings. However, the authors showed that CU3 and CU4 are compatible, providing a path forward for building rational agents.

Conclusion

This work successfully redefines foundational KM update rules to work with belief states. By providing representation theorems, the authors show that their new "faithful collective assignments" perfectly characterize update operators that satisfy the core logic of belief change. Future work will explore stricter rules and apply these iterated principles to "belief contraction"—the logic of how an agent should remove a belief in a changing world.

Summary updated

BibTeX
@inproceedings{fang2024logic,
  author = {Liangda Fang and Tong Zhu and Quanlong Guan and Junming Qiu and Zhao-Rong Lai and Weiqi Luo and Hai Wan},
  title = {{On the Logic of Theory Change Iteration of KM-Update, Revised}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
  url = {https://openreview.net/forum?id=sqyR97LnFJ},
}
Figure