A Belief Revision Framework for Revising Epistemic States with Partial Epistemic States

Jianbing Ma, Weiru Liu, Salem BenferhatAAAI 2010 · DOI

Introduction

In the field of formal logic and artificial intelligence, belief revision describes the process by which an agent updates their worldview upon receiving new information. The classical Alchourrón, Gärdenfors, and Makinson (AGM) framework has long served as the standard for this process. However, AGM and its derivatives typically treat new evidence as "hard" facts—absolute truths represented by propositional formulas.

In real-world scenarios, information is rarely absolute. Evidence is often "soft," uncertain, or partial. While probability theory addresses this through Jeffrey’s rule of conditioning, logic-based systems have historically struggled to integrate evidence that carries varying degrees of "firmness." This paper introduces a unified mathematical framework that generalizes these concepts, providing a bridge between probabilistic reasoning and logic-based iterated belief revision.

The Challenge of Partial Evidence

The authors identify a significant gap in existing literature: the lack of a formalism-independent framework that defines how an agent should update an entire "epistemic state" (a total worldview) when faced with a "partial epistemic state" (uncertain evidence concerning a specific subset of the world).

Existing systems like Ordinal Conditional Functions (OCF) or possibility theory have their own specific update rules, but there has been no general theory to explain why these rules work or how they relate to one another. The goal of this research is to establish a set of rational postulates that apply regardless of whether the agent uses probabilities, integers, or qualitative labels to measure belief strength.

The Epistemic Space Framework

The authors build their theory on the concept of Epistemic Spaces. This framework relies on two primary components:

  1. Partial Epistemic States: Rather than a simple formula, evidence is represented as a mapping from a partition of the world to a set of "firmness" values ($D$). This allows the agent to receive information like "Proposition A is likely true (0.8)" rather than just "Proposition A is true."
  2. Extension Functions: These mathematical tools aggregate values within the domain $D$. They are required to satisfy properties such as identity, minimality, and monotonicity, ensuring that the mathematical operations used to update beliefs remain logically consistent.

The ER Postulates for Rational Revision

The core contribution of the paper is the proposal of four postulates (ER1–ER4) for revision operators (denoted by $\circ$):

  • ER1 (Closure): Revising a full epistemic state with a partial state must result in a new, valid full epistemic state.
  • ER2 (Success): The revision process must be successful in that the new evidence is preserved in the resulting state. The agent’s belief regarding the specific partition addressed by the evidence must match the evidence received.
  • ER3 (Neutrality): This postulate ensures semantic independence. It dictates that the outcome of a revision should depend only on the strengths (values) of the prior beliefs and the new evidence, not on the semantic meaning of the propositions. If two different scenarios involve the same prior strengths and receive evidence of the same strength, the results should be identical.
  • ER4 (Priority): In cases of iterated revision, more recent evidence overrules older evidence when they concern the same set of hypotheses.

Theoretical Results and Representation

The authors prove two major Representation Theorems. These theorems demonstrate that any revision operator satisfying the ER postulates can be characterized by specific mathematical abstractions known as "retentive" and "conductive" operators. These operators function similarly to division in probability or subtraction in OCF, providing a blueprint for constructing valid revision rules in any given formalism.

By applying this framework, the authors show that Jeffrey’s rule of conditioning is not an isolated probabilistic trick. Instead, it is a specific instance of a broader logical pattern. The framework successfully subsumes probability theory, OCF, and possibility theory under a single, unified strategy.

Relationship to Iterated Revision

A critical test for any revision framework is how it handles a sequence of updates. The authors compare their ER postulates to the well-known Darwiche-Pearl (DP) postulates for iterated revision.

They find that when a "partial state" is simplified to a standard binary formula, the ER postulates induce the core DP postulates (C1 and C2). Interestingly, the framework intentionally deviates from others (C3 and C4). The authors argue that this is a strength of the system: it allows for nuanced updates where the strength of a commitment can change even if the underlying belief does not, a feature necessary for handling soft evidence effectively.

Conclusion and Future Work

This research provides the first common revision strategy that unifies various formalisms of uncertain reasoning. By shifting the focus from "hard" propositional updates to "partial" epistemic updates, the authors have created a more flexible and robust model for artificial intelligence.

While the current work focuses on revision, the authors suggest that future research should explore how "belief expansion" (adding information) and "belief contraction" (removing information) fit into this partial framework. Additionally, they propose practical applications in computer security, specifically for alert correlation. In this context, security sensors provide uncertain, partial evidence that must be synthesized to update a system's overall security posture and threat assessment.

Summary updated

BibTeX
@inproceedings{ma2010belief,
  author = {Jianbing Ma and Weiru Liu and Salem Benferhat},
  title = {{A Belief Revision Framework for Revising Epistemic States with Partial Epistemic States}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7585},
}
Figure