TL;DR
This paper tackles the computational complexity of iterated belief change, a process where an agent updates its beliefs over a sequence of new information. The authors introduce a new representation for belief states called Compact World Rankings (CWRs) and analyze the inference problem for various belief change operators, showing that it's often "mildly" hard, suggesting practical feasibility with modern SAT solvers.
What Problem Does This Paper Address?
Belief revision theory deals with how an agent's beliefs should change when presented with new information, especially when that information contradicts existing beliefs. While single-step belief revision has been extensively studied, real-world agents often encounter information sequentially, leading to iterated belief change. This process is more complex because the order and nature of information updates matter. The challenge lies in efficiently determining what an agent would believe after a series of changes, especially when belief states are represented in a structured way. This paper focuses on the inference problem within iterated belief change: given an agent's current beliefs (represented as a Compact World Ranking or CWR) and a new piece of information, can we efficiently determine if a specific proposition is entailed by the agent's updated beliefs?
Methods
The paper introduces Compact World Rankings (CWRs) as a way to represent an agent's epistemic state. A CWR is essentially a stratified belief base where each stratum is a single formula, and these formulae partition the space of interpretations. This representation is designed to be compact and computationally tractable.
The core of the paper is the analysis of the computational complexity of the inference problem for different iterated belief change operators. They categorize operators into two main families:
- Iterated Revision Operators: These operators ensure that the new information is fully accepted. The authors analyze Darwiche and Pearl's (DP-AGM) revision operators, showing that the inference problem for these is in $\mathcal{O}^{\mathcal{P}}$ (meaning it requires a logarithmic number of calls to an NP oracle).
- Soft Improvement Operators: These operators aim to incorporate new information while minimally disturbing the existing belief structure, without necessarily guaranteeing full acceptance of the new information. The paper analyzes three specific soft improvement operators, demonstrating that their inference problems are complete for specific levels of the Boolean Hierarchy (BH), specifically coNP(3)-hard.
The authors also provide algorithms for constructing the updated CWR for each operator, which are crucial for the empirical evaluation.
Datasets
Not discussed in the paper. The authors generated their own instances for empirical evaluation.
Key Insights and Ideas
- CWRs as a Practical Representation: The introduction of Compact World Rankings (CWRs) offers a structured and potentially more efficient way to represent epistemic states compared to simpler belief bases, especially for iterated belief change.
- "Mildly" Hard Inference: The paper reveals that the inference problem for iterated belief change, while not always polynomial, is often "mildly" hard. This means it's solvable with a limited number of calls to an NP oracle (e.g., a SAT solver), suggesting that practical implementations are feasible.
- Operator-Specific Complexity: Different types of belief change operators have distinct computational complexities for inference. Iterated revision operators are generally more tractable than soft improvement operators, which exhibit higher complexity.
- Empirical Feasibility: The authors' empirical results demonstrate that iterated belief change, even for bases of significant sizes and multiple change steps, can be performed in a reasonable time using SAT-based algorithms. This bridges the gap between theoretical complexity and practical application.
Key Results
- Iterated Revision: The inference problem for DP-AGM iterated revision operators is $\mathcal{O}^{\mathcal{P}}$-complete, requiring only a logarithmic number of calls to an NP oracle.
- Soft Improvement: The inference problem for the three analyzed soft improvement operators is coNP(3)-hard. For half-improvement and best-improvement, it's shown to be coNP(5)-complete.
- Construction of Updated CWRs: The paper provides explicit procedures for constructing the updated CWR for each of the seven considered belief change operators. Notably, the size of the resulting CWR (number of strata) does not grow exponentially, which is a crucial property for computational tractability.
- Empirical Validation: Experiments show that the time and number of strata in the resulting CWRs do not grow excessively with the number of change steps, confirming the practical feasibility of iterated belief change for substantial instances.
Limitations and Future Work
- Complexity of Sequences: While the paper analyzes the inference problem for a single change step, future work will focus on identifying the computational complexity for sequences of change formulae.
- Other Operators: The authors plan to implement and analyze other belief change operators, particularly iterated contraction operators, leveraging their CWR framework.
- Code Availability: The authors intend to make their code for generating and querying CWRs publicly available, which will be valuable for future research and practical applications.
- Instance Generation: The empirical evaluation used generated instances. While designed to mimic industrial instances through modularity, real-world industrial datasets for belief change are not readily available.
Summary updated