Revision Sequences and Nested Conditionals

Craig BoutilierIJCAI 1993 · OpenReview

Abstract

The truth conditions for conditional sentences have been well-studied, but few compelling attempts have been made to define means of evaluating iterated or nested conditionals. In particular, most approaches impose very few constraints on the set of conditionals an agent can hold after revision of its belief set. In this paper we describe the method of natural revision that ensures the preservation of conditional beliefs after revision by an objective belief. Our model, based on a simple modal logic for beliefs and conditionals, extends the AGM theory of belief revision to account for sentences of objective revisions of a belief set. This model of revision ensures that an agent makes as few changes as possible to the conditional component of its belief set. Adopting the Ramsey test, natural revision provides truth conditions for arbitrary right-nested conditionals. We show that the problem of determining acceptance of any such nested conditional can be reduced to acceptance tests for unnested conditionals, indicating that iterated revision can be simulated by virtual updates. We also briefly describe certain reductions to (sometimes tractable) propositional inference, and other informational properties.

Introduction

In artificial intelligence, belief revision is the fundamental process of an agent updating its knowledge when encountering new, potentially conflicting information. The established gold standard for this process is AGM theory, which dictates that when an agent learns a new fact $A$, it should modify its existing beliefs as minimally as possible to accommodate $A$.

However, AGM theory suffers from a significant limitation regarding "memory": it focuses primarily on objective facts while largely ignoring conditionals (e.g., "If I had taken the bus, I would have been late"). When an agent undergoes a standard AGM revision, it often loses these conditional relationships or lacks a principled way to update them. This deficiency makes it difficult to handle iterated revision (a sequence of updates) or nested conditionals ("If $A$ were true, then if $B$ were true, $C$ would follow") in a consistent manner.

The Semantic Model: Plausibility Orderings

To address these issues, we propose a semantic model based on modal logic ($CO^*$) and plausibility orderings. In this framework, an agent's mental state is represented as a set of "possible worlds" ranked by their plausibility.

Figure 1: An initial plausibility ordering of possible worlds (K-worlds), where the downward arrow indicates increasing plausibility.

Under this model, the most plausible worlds represent the agent's current beliefs. To evaluate a conditional statement "If $A$ then $B$" (the Ramsey Test), the agent hypothetically shifts its focus to the most plausible worlds where $A$ is true and verifies if $B$ holds within that subset.

Natural Revision: Minimal Mutilation

The core innovation of this work is the Natural Revision Operator. When an agent learns a new fact $A$, the operator doesn't simply select the best $A$-worlds; it restructures the entire ordering to ensure that:

  1. The most plausible $A$-worlds from the original model become the new most plausible worlds overall.
  2. The relative ordering of all other worlds remains unchanged.
Figure 5: The resulting structure of a model $M^*_A$ after natural revision by $A$, showing the promotion of $A$-worlds to the highest plausibility rank.

This "minimal surgery" on the ordering structure ensures that the agent's conditional "common sense"—the underlying reasons for its beliefs—is preserved as much as possible during the update.

Key Insights and Results

  • Conditionals as Structural Orderings: By treating conditional beliefs as the structure of the plausibility model rather than mere facts, we can preserve them by maintaining the ordering's integrity.
  • Reduction of Complexity: A powerful result of this approach is that nested conditionals, which are typically computationally difficult to evaluate, can be reduced to a series of simple, unnested conditional tests.
  • Virtual Updates: We demonstrate that a sequence of revisions can be simulated through "virtual updates." This allows an agent to reason about the outcomes of long chains of events without physically rebuilding its entire belief model at every step.
  • AGM Compatibility and Tractability: Natural revision is proven to satisfy standard AGM postulates. Furthermore, for specific models like Pearl’s System Z, computing these revisions can be reduced to standard propositional inference, making the approach computationally feasible in many practical scenarios.

Conclusion

Natural revision provides a robust extension to AGM theory, offering a principled way to handle iterated updates and nested conditionals. By focusing on the preservation of the plausibility ordering, the model ensures that agents retain maximal conditional information. Future work will explore more complex nesting structures and the integration of this logic into diagnostic and planning systems.

Summary updated

Abstract

The truth conditions for conditional sentences have been well-studied, but few compelling attempts have been made to define means of evaluating iterated or nested conditionals. In particular, most approaches impose very few constraints on the set of conditionals an agent can hold after revision of its belief set. In this paper we describe the method of natural revision that ensures the preservation of conditional beliefs after revision by an objective belief. Our model, based on a simple modal logic for beliefs and conditionals, extends the AGM theory of belief revision to account for sentences of objective revisions of a belief set. This model of revision ensures that an agent makes as few changes as possible to the conditional component of its belief set. Adopting the Ramsey test, natural revision provides truth conditions for arbitrary right-nested conditionals. We show that the problem of determining acceptance of any such nested conditional can be reduced to acceptance tests for unnested conditionals, indicating that iterated revision can be simulated by virtual updates. We also briefly describe certain reductions to (sometimes tractable) propositional inference, and other informational properties.
BibTeX
@inproceedings{boutilier1993revision,
  author = {Craig Boutilier},
  title = {{Revision Sequences and Nested Conditionals}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1993},
  url = {https://openreview.net/forum?id=S1WLgSfObB},
}
Figure