TL;DR
This paper dives deep into the computational complexity of various belief update formalisms, which model how an agent's knowledge changes when the world does. The authors analyze several proposed methods, finding that most remain within the second level of the polynomial hierarchy, suggesting that overcoming limitations of early models didn't necessarily increase computational cost. However, they highlight two notable exceptions: Boutilier's Generalized Update is simpler, while the Possible Causes Approach is significantly more complex.
What Problem Does This Paper Address?
Imagine an AI agent that holds beliefs about the world. These beliefs can change in two main ways: belief revision (when the agent realizes its old beliefs were wrong) and belief update (when the world itself changes, making old beliefs obsolete). This paper focuses on the latter: belief update.
Early formalizations of belief update, like Winslett's, had limitations. For instance, they struggled with disjunctive information (e.g., "the computer is in room 2 OR room 3") and sometimes failed to correctly revise beliefs about past states of the world. To address these issues, researchers have proposed various alternative update mechanisms. The central problem this paper tackles is understanding the computational cost of these different update formalisms. Specifically, it asks: how difficult is it to determine what an agent should believe after a change in the world, given these different formalisms? This is crucial for building efficient and practical AI systems that can adapt to dynamic environments.
Methods
The paper's core method is a computational complexity analysis of different belief update operators. It systematically examines several proposed formalisms, including:
- Winslett's Update: The foundational model, which operates on a model-by-model basis and uses a specific ordering based on symmetric differences of interpretations.
- Minimal Change with Exceptions (MCE): An approach designed to handle disjunctive information more intuitively by ignoring certain exceptions when measuring change.
- Minimal Change with Maximal Disjunctive Inclusion (MCD): Another method addressing disjunctive information, aiming for maximal inclusion of disjunctions.
- Update with Dependence Function: This formalism incorporates causal relationships between atoms, where changes in one atom can affect others.
- Generalized Update: A more abstract framework that uses rankings of interpretations to model plausibility and allows for revising beliefs about past states.
- Possible Causes Approach: This method frames updates as consequences of unknown actions and seeks explanations for observed changes.
The authors analyze these methods by relating them to known complexity classes within the polynomial hierarchy (like P, NP, coNP, Σ, and Π) and by proving theorems that establish their precise complexity bounds. They leverage existing results on related problems like closed-world reasoning and circumscription to derive new complexity results for belief update.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and complexity rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Complexity Stability: A key finding is that many of the proposed belief update formalisms, designed to overcome Winslett's limitations, surprisingly do not significantly increase computational complexity. Most fall within the second level of the polynomial hierarchy (Σ₂ or Π₂), similar to Winslett's original update. This suggests that addressing logical shortcomings doesn't inherently lead to intractable problems.
- Winslett's Update as a Benchmark: The paper uses Winslett's update as a reference point, analyzing how other methods compare in terms of computational difficulty.
- Disjunctive Information is Tricky: The paper highlights that handling disjunctive information is a recurring challenge, leading to the development of specialized update mechanisms like MCE and MCD.
- Generalized Update is Simpler: Boutilier's Generalized Update, while more expressive in modeling plausibility and past states, turns out to be computationally simpler (Δ₂ complete) than Winslett's update. This is a counter-intuitive but important result.
- Possible Causes Approach is Harder: Conversely, the Possible Causes Approach is found to be significantly more computationally demanding (Π₃ complete). This is attributed to its global nature, where changes affect the entire set of initial states rather than individual models, making tasks that were polynomial in Winslett's approach become NP-complete.
Key Results
- Winslett's Update: The basic entailment problem for Winslett's update is at the second level of the polynomial hierarchy (specifically, Π₂).
- Minimal Change with Exceptions (MCE): MCE is shown to be Π₂-complete, with a close relationship to the generalized closed-world assumption.
- Minimal Change with Maximal Disjunctive Inclusion (MCD): MCD is also found to be Π₂-complete.
- Update with Dependence Function: This approach is determined to be coNP-complete.
- Generalized Update (GU): This operator is Δ₂-complete.
- Possible Causes Approach: This approach is the most computationally expensive, being Π₃-complete.
Limitations and Future Work
- Assumptions for Generalized Update: The complexity result for Generalized Update relies on assumptions about the polynomial computability of functions within the revision model (e.g., determining the integer values of events, models, and rankings). If these functions are not efficiently computable, the complexity could increase.
- Focus on Propositional Logic: The analysis is confined to propositional logic. Extending these complexity results to richer logical formalisms (e.g., first-order logic) would be a natural next step.
- Practical Implications: While the paper provides theoretical complexity bounds, further research could explore how these complexities translate into practical performance for AI systems and investigate efficient algorithms or approximations for the harder cases.
- Bridging the Gap: The paper implicitly suggests that understanding the trade-offs between expressiveness and computational cost is key. Future work could focus on developing new formalisms that strike a better balance or on finding ways to efficiently implement the more complex but expressive approaches.
Summary updated