On the Relation between the Coherence and Foundations Theories of Belief Revision

Alvaro del ValAAAI 1994

TL;DR

For decades, researchers in AI and logic debated two competing philosophies for updating knowledge: the Coherence theory (maintaining overall consistency) and the Foundations theory (tracking justifications for beliefs). This paper provides the mathematical "missing link," proving that these two approaches are formally equivalent and showing that major frameworks for non-monotonic reasoning—like Poole’s defaults and Shoham’s preferential logic—are essentially two sides of the same coin.

What Problem Does This Paper Address?

Imagine you believe that "all birds fly" and "Tweety is a bird," so you conclude "Tweety flies." Suddenly, you learn Tweety is actually a penguin and cannot fly. How do you fix your "database" of beliefs?

In the early 90s, there were two main schools of thought:

  1. Foundations Theory: Beliefs are like a building. Some are "basic" (the foundation), and others are "derived" (the upper floors). If you remove a foundation stone, everything resting on it must be discarded.
  2. Coherence Theory: Beliefs are like a web. There is no hierarchy; the goal is simply to keep the web consistent while changing as little as possible.

While philosophers and computer scientists argued over which was "better" or more "natural," no one had rigorously proven how they related to each other mathematically. This paper sets out to bridge that gap.

Methods

The author, Alvaro del Val, uses formal logic to define both theories in a way that allows for direct comparison.

  • Refining the Foundations Theory: Traditional "syntax-based" foundational approaches were criticized because they were too sensitive to how a belief was written (e.g., treating $\{A, B\}$ differently from $\{A \land B\}$). Del Val introduces a basic beliefs function ($\Sigma$) that maps a set of beliefs to its underlying "basic" components in a syntax-independent way.
  • Mapping to Coherence: The author uses the AGM framework (the gold standard for coherence theory) which relies on "postulates" (rules a rational agent should follow) and "preorders" (rankings of how much we value certain beliefs).
  • The Proof: The core of the paper consists of several theorems (Theorems 2 through 5) that demonstrate how any foundational revision operator can be represented as a coherence operator, and vice versa.

Datasets

Not discussed in the paper. As a theoretical work in mathematical logic and artificial intelligence, the paper relies on formal proofs rather than empirical data or benchmarks.

Key Insights and Ideas

  • The Equivalence Breakthrough: The most significant "aha moment" is the proof that for any "rational" way to revise beliefs under the coherence theory, there exists a corresponding set of "basic beliefs" in the foundations theory that yields the exact same result.
  • Syntax Independence: By slightly modifying the foundational approach to be syntax-independent, the author removes the primary technical hurdle that made the two theories seem incompatible.
  • Unifying Non-Monotonic Reasoning: The paper extends this equivalence to the broader field of non-monotonic reasoning (logic where new information can invalidate old conclusions). It shows that Poole’s system of default reasoning (foundational) and Shoham’s preferential logic (coherentist) are expressively equivalent—they can represent the same sets of consequence relations.

Key Results

  • Theorem 2 & 3: Proves that every foundations-based revision operator has a mathematically identical counterpart in the coherence (AGM) world.
  • Theorem 4 & 5: Proves the converse—any coherence-based revision can be "reconstructed" as a foundational revision by choosing the right set of basic beliefs.
  • Expressive Parity: The paper concludes that, at least for standard propositional logic, there is no mathematical reason to prefer one theory over the other. The choice between them is a matter of "practical convenience" or implementation preference rather than logical power.

Limitations and Future Work

  • Finitary Propositional Language: The proofs are limited to "finitary" languages (those with a finite number of symbols). While the author suggests the results could be extended to infinite cases, it requires the assumption that the belief sets are "finitely axiomatizable."
  • Iterated Revision: The author briefly mentions that "iterated" revision (revising beliefs multiple times in a row) can be tricky if the reasons for beliefs change over time, suggesting that time-indexing basic beliefs might be a necessary future step.
  • Non-Classical Logics: The paper focuses on classical propositional logic. The author notes that some foundational systems (like Truth Maintenance Systems) operate in non-classical or autoepistemic logics, which may not map as cleanly to the standard AGM coherence model.

Summary updated

BibTeX
@inproceedings{val1994relation,
  author = {Alvaro del Val},
  title = {{On the Relation between the Coherence and Foundations Theories of Belief Revision}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure