TL;DR
This paper reveals a fundamental conflict between Darwiche and Pearl's influential approach to iterated belief revision and the concept of relevance in knowledge representation. The authors demonstrate that no revision function can simultaneously satisfy both the DP postulates for iterated revision and Parikh's relevance axiom, leading to significant implications for existing belief revision models.
What Problem Does This Paper Address?
The field of belief revision deals with how an agent should update its beliefs when new information arrives. The AGM (Alchourrón, Gärdenfors, Makinson) paradigm provides a foundational framework for this, but it offers limited guidance on iterated belief revision – how to handle a sequence of updates. The Darwiche and Pearl (DP) approach introduced four postulates to address this, becoming a dominant model. However, this approach has faced criticism for producing unintuitive results.
A separate line of research, initiated by Parikh, introduced axioms to capture the notion of relevance in belief revision, aiming to ensure that updates only affect beliefs directly related to the new information. This paper tackles the problem of whether these two crucial aspects of belief revision – iteration and relevance – can coexist within the established framework. Specifically, it investigates the compatibility of the DP postulates with Parikh's relevance axiom (P).
Methods
The authors employ a formal, logical approach using the possible-worlds semantics commonly used in belief revision research. They analyze the DP postulates and Parikh's axiom (P) by translating them into conditions on the ordering of possible worlds. The core of their method involves constructing specific scenarios (belief states and incoming information) and demonstrating that the requirements imposed by the DP postulates and axiom (P) lead to contradictions.
Key techniques include:
- Possible-World Semantics: Representing belief states as total preorders over possible worlds, where worlds are ranked by plausibility.
- Axiomatic Analysis: Examining the logical consequences of the DP postulates and Parikh's axiom (P) by translating them into constraints on these world orderings.
- Counterexample Construction: Creating specific examples of belief states and sentences that, when subjected to the DP postulates and axiom (P), lead to logical inconsistencies.
- Generalization: Extending previous findings (which were limited to specific language sizes) to arbitrary finite sets of propositional variables and various types of theories.
Datasets
Not discussed in the paper. The paper is a theoretical investigation and does not involve empirical evaluation on datasets.
Key Insights and Ideas
- Fundamental Conflict: The most striking insight is the inherent incompatibility between the DP approach to iterated belief revision and the principle of relevance as captured by Parikh's axiom (P). This isn't a minor issue; it suggests a deep tension in how we model these two core aspects of rational belief change.
- DP Postulates are Too Strong (or P is Too Restrictive): The paper proves that no revision function can satisfy both the DP postulates and axiom (P) simultaneously. This implies that either the DP postulates are too demanding for a relevant revision process, or axiom (P) is too restrictive for iterated revision.
- Implications for Existing Models: This incompatibility has significant consequences for several well-known belief revision operators. Parametrized Difference revision operators, including Dalal's operator, and the Independence postulate are shown to be incompatible with the DP approach when relevance is considered.
- Belief States are More Than Just Preorders: The paper argues that a simple total preorder over possible worlds is insufficient to represent a belief state if we want to accommodate all DP-compliant revision policies. This suggests that belief states might need richer representations to capture the nuances of iterated belief change.
Key Results
The paper presents several key theoretical results:
- Theorem 1: For any splittable theory, there exists a belief state and a sentence such that no modified AGM revision function can satisfy Parikh's axiom (P) along with any of the DP postulates (DP1-DP4).
- Theorem 2: For any splittable or non-trivially confined theory, there exists a belief state and a sentence such that no modified AGM revision function can satisfy Parikh's axiom (P) along with DP postulate (DP2).
- Corollary 1 & 2: Parametrized Difference revision operators and Dalal's operator are incompatible with the DP approach.
- Corollary 3: Parikh's axiom (P) is inconsistent with the Independence postulate.
- Corollary 4: Spohn's conditionalization (when restricted to revision scenarios) does not satisfy axiom (P).
- Theorem 3: A belief state cannot be fully represented by a simple total preorder over possible worlds if we aim to capture all DP-compliant revision policies, implying a "non-reductionist" view of belief states.
Limitations and Future Work
- Focus on Specific Axioms: The paper's findings are specific to the DP postulates and Parikh's axiom (P). Future work could explore the compatibility of other iterated revision frameworks or alternative relevance axioms.
- Theoretical Nature: The results are theoretical and demonstrate logical incompatibilities. Further research could explore practical implications and potential modifications to existing frameworks to reconcile iteration and relevance.
- Future Directions: The authors explicitly call for finding ways to reconcile iteration and relevance, either by weakening the involved postulates or by developing entirely new approaches. They also emphasize identifying the exact nature of a belief state as a crucial future task.
Summary updated