Revision by Conditional Beliefs

Craig Boutilier, Moisés GoldszmidtAAAI 1993 · OpenReview

Abstract

Both the dynamics of belief change and the process of reasoning by default can be based on the conditional belief set of an agent, represented as a set of "if-then" rules. In this paper we address the open problem of formalizing the dynamics of revising this conditional belief set by new if-then rules, be they interpreted as new default rules or new revision policies. We start by providing a purely semantic characterization, based on the semantics of conditional rules, which induces logical constraints on any such revision process. We then introduce logical (syntax-independent) and syntax-dependent techniques, and provide a precise characterization of the set of conditionals that hold after the revision. In addition to formalizing the dynamics of revising a default knowledge base, this work also provides some of the necessary formal tools for establishing the truth of nested conditionals, and attacking the problem of learning new defaults.

Introduction

Traditional belief revision, exemplified by the AGM theory, focuses on how an agent updates its factual beliefs. For example, if an agent believes "birds fly" and learns "Tweety is a penguin and doesn't fly," it updates its belief about Tweety. However, a significant gap remains: how does an agent revise the rules themselves? If an agent learns a new general rule, such as "Typically, penguins don't fly," its entire internal reasoning policy—its "operating system"—must be updated. This paper formalizes the dynamics of revising these conditional beliefs (if-then rules or defaults).

The Semantic Framework: Natural Revision

The authors build upon the model of "Natural Revision," where an agent's state is represented as a ranked model $M$—an ordering of possible worlds from most plausible to least plausible. A conditional $A \to B$ is accepted if $B$ is true in the most plausible worlds where $A$ holds.

To revise a model $M$ by a new conditional $A \to B$, the process is decomposed using the Levi Identity:

  1. Natural Contraction ($M^-_{A \to B}$): The agent "forgets" any belief contradicting the new rule by shifting the most plausible worlds where $A \land \neg B$ is true so they are at least as plausible as the most plausible $A$-worlds.
  2. Natural Expansion ($M^+_{A \to B}$): The agent "adds" the new rule by making $A \land \neg B$ worlds less plausible than the most plausible $A$-worlds.
  3. Natural Revision ($M^*_{A \to B}$): The combination of contraction and expansion to incorporate the new rule while maintaining consistency.
Semantic operations for natural contraction, expansion, and revision of a conditional belief set.

Key Insights and Results

  • Conditionals as Revision Policies: A conditional $A \to B$ is treated as a constraint on how the agent should behave when it learns $A$. Revising a conditional is essentially "revising how you revise."
  • Plausibility Shift: Natural revision is minimal, shifting only the necessary worlds to satisfy the new rule while preserving the relative ordering of others.
  • Theorem 6: This central result provides a logical characterization that determines which conditionals hold after a revision based solely on the prior state. It proves the new state of mind is predictable from the old.
  • Independence of $\neg A$ worlds: Revising by $A \to B$ only affects the relative plausibility of worlds where $A$ is true, leaving the "internal logic" of $\neg A$ scenarios untouched.

Syntax-Dependent Revision

Recognizing that real-world knowledge bases (KBs) are often incomplete, the authors propose a method to isolate the "Minimal Consistent Inconsistent" (MCI) set. This identifies the specific rules responsible for a conflict, allowing the agent to preserve as much original structure as possible while incorporating the new rule. This is particularly useful when the agent's knowledge is represented as a set of discrete rules rather than a complete plausibility ordering.

Discussion and Limitations

While providing a robust formal framework, the approach has limitations. Finding the MCI set can be computationally expensive, potentially requiring exponential satisfiability tests. Furthermore, the paper focuses on how to revise once a decision is made, rather than why or when an agent should change its rules. Future work may involve incorporating causal interpretations of rules, which the current purely logical framework does not fully capture. Additionally, the framework provides a way to evaluate "nested" conditionals by defining what it means for a conditional to be true after another one is adopted.

Summary updated

Abstract

Both the dynamics of belief change and the process of reasoning by default can be based on the conditional belief set of an agent, represented as a set of "if-then" rules. In this paper we address the open problem of formalizing the dynamics of revising this conditional belief set by new if-then rules, be they interpreted as new default rules or new revision policies. We start by providing a purely semantic characterization, based on the semantics of conditional rules, which induces logical constraints on any such revision process. We then introduce logical (syntax-independent) and syntax-dependent techniques, and provide a precise characterization of the set of conditionals that hold after the revision. In addition to formalizing the dynamics of revising a default knowledge base, this work also provides some of the necessary formal tools for establishing the truth of nested conditionals, and attacking the problem of learning new defaults.
BibTeX
@inproceedings{boutilier1993revision,
  author = {Craig Boutilier and Moisés Goldszmidt},
  title = {{Revision by Conditional Beliefs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1993},
  url = {https://openreview.net/forum?id=r14c_6e_Zr},
}
Figure