Conditional Logics of Belief Change

Nir Friedman, Joseph Y. HalpernAAAI 1994

Introduction

How should an intelligent agent change its beliefs when presented with new information? In the early 1990s, the formal study of this question was divided into two distinct paradigms. The first, Belief Revision (exemplified by the AGM framework), focused on agents refining their knowledge about a static world. The second, Belief Update (exemplified by the KM framework), addressed agents tracking changes in a dynamic world.

Friedman and Halpern's seminal work introduces Belief Change Systems (BCS), a unified logical framework that bridges these two paradigms. By developing a new modal logic, $L^{C>}$, the authors provide a complete axiomatization for belief change while successfully sidestepping the "triviality" paradoxes that had previously suggested such a logic was impossible.

The Problem: Triviality and Fragmentation

Before this work, the field faced a significant hurdle known as the Gärdenfors Triviality Result. Gärdenfors demonstrated that any logic expressive enough to include its own belief change operator—specifically one that satisfied certain intuitive properties—would inevitably become trivial, meaning it could only represent a very limited and uninteresting set of belief states.

Furthermore, the lack of a unified language meant that researchers had to choose between modeling revision or update, with no formal way to describe systems that might involve both or to compare the two processes within a single mathematical structure.

The Belief Change System (BCS) Framework

The authors define a BCS through three core components:

  1. States ($S$): These represent the internal "epistemic states" of an agent.
  2. Belief Assignment ($\rho$): A mapping that determines what the agent believes in any given state.
  3. Transition Function ($\tau$): A rule defining how the agent moves from one state to another upon receiving new information.

To reason about these systems, the authors utilize the modal logic $L^{C>}$. This language includes two primary operators:

  • $B\phi$: "The agent believes $\phi$."
  • $\phi > \psi$: "After learning $\phi$, the agent will believe $\psi$."

A critical innovation in this framework is the separation of the language of the world ($L$) from the language of the agent's beliefs ($L^{C>}$). By restricting the agent to "learning" only objective formulas from $L$ (rather than complex conditional beliefs about their own belief process), the authors prevent the self-referential loops that lead to the Gärdenfors Triviality Result.

Key Insights

States as Primitives

In many previous models, an agent's state was synonymous with their set of beliefs. In a BCS, the epistemic state is a primitive. This allows for a distinction between what an agent believes now and their disposition to change. Two agents might currently hold identical beliefs but react differently to the same new evidence because they occupy different epistemic states with different transition functions.

Unifying Revision and Update

The authors identify a specific class of systems called Preferential BCS, where states are modeled as sets of possible worlds with a preference (or plausibility) ordering. They demonstrate that:

  • Revision occurs when an agent moves to the most plausible worlds globally.
  • Update occurs when an agent moves to the most plausible worlds locally (pointwise).

This result formally proves that AGM revision and KM update are subclasses of the broader BCS framework, providing the long-sought unification of the two fields.

Formal Results and Axiomatization

The paper's primary technical contribution is the development of System AX, a set of axioms for $L^{C>}$. The authors prove that System AX is both sound and complete with respect to the class of all Belief Change Systems. This means that every true statement about belief change in a BCS can be proven using these axioms, and vice versa.

Additionally, the authors validate the law of conditional excluded middle—$(\phi > \psi) \lor (\phi > \neg\psi)$—for subjective beliefs. While this law is often rejected in logics describing objective reality, Friedman and Halpern argue it is essential for describing the deterministic transitions of an agent's internal belief state.

Conclusion and Future Directions

By distinguishing between objective facts and subjective belief states, Friedman and Halpern provided a robust solution to the triviality problem and a unified language for the AI community. However, the work leaves several avenues for future research. The current logic does not account for "learning" conditionals themselves (e.g., learning a rule of change), nor does it fully explore the complexities of iterated revision, where an agent's strategy for changing their mind might itself evolve. Integrating these internal models with a model of the actual, external world remains a key challenge for future logical frameworks.

Summary updated

BibTeX
@inproceedings{friedman1994conditional,
  author = {Nir Friedman and Joseph Y. Halpern},
  title = {{Conditional Logics of Belief Change}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1994},
}
Figure