Iterated Belief Base Revision: A Dynamic Epistemic Logic Approach

Marlo Souza, Álvaro F. Moreira, Renata VieiraAAAI 2019 · DOI

Abstract

This research bridges the gap between syntactic belief representations in AI—specifically priority graphs—and the semantic requirements of rational iterated belief revision. By characterizing standard postulates as transformations on priority graphs, the authors identify the mathematical boundaries of syntactic belief bases. The study provides a formal "recipe" for ensuring rationality in belief updates while proving that certain popular revision policies, such as natural revision, are mathematically impossible to represent within these syntactic structures.

Introduction

In the field of Artificial Intelligence, belief revision is the study of how an autonomous agent should incorporate new, potentially conflicting information into its existing knowledge base. For decades, the gold standard for this process has been the AGM paradigm (named for Alchourrón, Gärdenfors, and Makinson). Traditionally, the AGM paradigm treats beliefs as "belief sets"—massive, deductively closed sets of formulas. However, in practical computational applications, agents do not store infinite sets; they use "belief bases," which are small, finite sets of explicit formulas.

When an agent receives a single update, the logic is well-understood. However, when an agent receives a sequence of updates—known as iterated revision—maintaining rationality becomes significantly more complex. This paper addresses the disconnect between high-level semantic constraints (how an agent's worldview should shift) and the low-level syntactic data structures (how the agent's code actually stores those beliefs) used in Dynamic Epistemic Logic (DEL).

Methodology: Priority Graphs and DEL

The authors utilize two primary frameworks: Dynamic Epistemic Logic and Priority Graphs (P-graphs).

Priority Graphs are syntactic structures where nodes represent propositional formulas and edges represent a priority or preference ranking. These graphs are not merely static lists; they can be "lifted" to create a semantic preference relation between possible worlds, allowing an agent to determine which state of affairs is most plausible given its current evidence.

To bridge the gap between syntax and semantics, the authors focus on the Darwiche-Pearl (DP) postulates (DP-1 through DP-4). These postulates describe how the relative ordering of possible worlds should persist or change after an update. The core methodology of the paper involves deriving the necessary syntactic constraints on P-graph transformations to ensure that any change to the graph automatically satisfies these semantic rationality rules.

Key Insights and The Bridge to Rationality

The paper’s primary contribution is the creation of a formal "recipe" (Propositions 11-16) for building graph-transformation functions. This allows developers and logicians to verify if a specific implementation of a belief base actually follows established logical theory.

Lexicographic Revision

One of the most significant findings is the validation of "Lexicographic Revision." In this policy, new information is simply given top priority (a process called prefixing). The authors formally prove that prefixing a P-graph with a new formula is a mathematically sound implementation of Lexicographic Revision and satisfies the most critical postulates, including DP-1, DP-2, and Recalcitrance (REC).

The "Minimal World" Limitation

A crucial theoretical insight identified in the paper (Fact 20) is that priority graphs possess an inherent limitation: they cannot uniquely identify the "minimal worlds" (the most plausible states) of a model using a single formula. This is a subtle but vital distinction in formal epistemology. Because some revision policies, such as "Natural Revision," rely heavily on the ability to isolate these minimal worlds, the authors prove a significant "No-Go" theorem: Natural Revision cannot be represented as a P-graph transformation.

Results and Formal Characterizations

The authors successfully provide formal syntactic conditions for P-graph transformations to satisfy a suite of postulates:

  • DP-1 through DP-4: The standard requirements for iterated revision.
  • REC (Recalcitrance): Ensuring that new information is not immediately discarded by subsequent updates.
  • IND (Independence): Ensuring that unrelated beliefs are not unnecessarily disturbed.

Furthermore, the paper demonstrates a fundamental boundary for syntactic belief bases. They show that no relevant P-graph transformation can satisfy both the FAITH (basic AGM faithfulness) and CB (Conditional Belief) postulates simultaneously. This result effectively delineates the limits of what syntactic belief bases can achieve compared to full, infinite semantic models.

Conclusion

By connecting the syntactic world of belief bases with the semantic world of iterated revision, this research provides a roadmap for implementing more robust and logically sound computational agents. While it identifies clear limitations—such as the impossibility of representing natural revision in P-graphs—it solidifies lexicographic revision as a gold standard for graph-based belief management.

Future work remains to explore more general syntactic representations that might overcome the "minimal world" limitation and to apply these characterizations to Belief-Desire-Intention (BDI) systems and Evidence Logics, where beliefs are constructed from multiple, potentially conflicting sources of evidence.

Summary updated

BibTeX
@inproceedings{souza2019iterated,
  author = {Marlo Souza and Álvaro F. Moreira and Renata Vieira},
  title = {{Iterated Belief Base Revision: A Dynamic Epistemic Logic Approach}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33013076},
}

Loading related content...

Figure