Anytime Belief Revision

IJCAI 1997

TL;DR

This paper introduces an "anytime" algorithm for belief revision, specifically a strategy called "maxi-adjustment." This approach allows intelligent agents to efficiently update their beliefs in a rational way, even when faced with inconsistent information, by prioritizing the retention of more important beliefs. The work also provides practical guidelines for building such belief revision systems.

What Problem Does This Paper Address?

Intelligent agents, from chatbots to sophisticated AI systems, need to constantly update their understanding of the world as new information comes in. This process, known as belief revision, is crucial for rational behavior. The standard framework for this is the AGM (Alchourron, Gardenfors, Makinson) paradigm, which provides a solid theoretical foundation for how beliefs should change to maintain consistency.

However, implementing these theoretical frameworks in practice presents challenges. One key issue is how to efficiently revise beliefs while minimizing unnecessary changes, a principle known as "minimal change." Simply discarding beliefs that contradict new information can lead to losing valuable knowledge. Furthermore, dealing with iterated revisions (multiple updates over time) and ensuring these revisions are computationally feasible, especially in real-time applications, are significant hurdles. This paper tackles the problem of developing a practical, efficient, and rational belief revision strategy that can be implemented in computer systems.

Methods

The paper focuses on a specific belief revision strategy called maxi-adjustment, proposed by Williams [1996]. Maxi-adjustment aims to preserve as much information as possible by retracting only the minimally entrenched beliefs that are inconsistent with new information.

The core contribution is an anytime decision procedure for maxi-adjustments. An "anytime" algorithm is one that can be interrupted at any point and will have produced a valid, albeit potentially incomplete, solution. The longer it runs, the better the approximation of the final solution. This is crucial for real-time AI systems where immediate responses are often necessary.

The algorithm works in two main phases:

  1. Determining the degree of acceptance: This phase involves calculating how entrenched a belief is, especially in relation to new information. The paper introduces the concept of partial entrenchment rankings to represent these degrees of belief.
  2. Refining the ranking: This phase involves removing minimal sets of sentences that entail the information to be contracted, while salvaging as much of the remaining ranking as possible.

The paper also discusses subsumption removal as an optional feature to further refine the revision process by removing beliefs that are logically implied by the information being contracted.

Datasets

Not discussed in the paper. The paper focuses on the theoretical development and algorithmic design of belief revision, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Anytime Algorithms for Rationality: The concept of an "anytime" algorithm is applied to belief revision, meaning agents can provide a rational response even under time constraints. This is a significant practical advantage.
  • Maxi-Adjustment's Efficiency: Maxi-adjustment is presented as a strategy that preserves more information than standard methods by focusing on the "minimal" set of beliefs to retract.
  • Partial Entrenchment Rankings: These provide a practical way to represent an agent's beliefs and their relative importance, forming the basis for the revision process.
  • Protomethodology for Design: The paper offers practical guidelines for knowledge engineers and system designers on how to build belief revision systems using maxi-adjustment, emphasizing clarity, explicitness, and logical form of information.
  • Connection to Other AI Fields: The paper notes that maxi-adjustments have connections to possibilistic and nonmonotonic reasoning, suggesting broader applicability.

Key Results

The paper presents an anytime algorithm for maxi-adjustments that, if interrupted, guarantees that the constructed partial solution satisfies AGM postulates for revision and withdrawal. The first phase of the algorithm is computationally less demanding and, if completed, is sufficient for query evaluations. The complexity of computing the degree of acceptance is NP-hard in general, but can be polynomial for fragments of propositional logic. The second phase of the algorithm is in A2, meaning it can be solved with a polynomial number of calls to an NP oracle.

Limitations and Future Work

  • Computational Complexity: While the algorithm is anytime, the underlying computation of belief degrees can be NP-hard, posing challenges for very large or complex knowledge bases. The paper suggests that hybrid strategies and interpolation techniques could improve performance.
  • Syntax Sensitivity: Maxi-adjustment, like many belief revision methods, is sensitive to the syntax of the input information. The authors acknowledge that methodologies for handling this are still developing.
  • Contraposition of Reasons: The paper highlights a potential issue with contraposition when using material implication for reasons, suggesting that maxi-adjustment can be adapted to handle cases where this assumption is not appropriate.
  • Future Work: The authors mention that the algorithm is under development in the CIN Project, aiming to create an intelligent information management toolkit. Further development of methodologies and experience with real-world applications are anticipated.

Summary updated

BibTeX
@inproceedings{1997anytime,
  title = {{Anytime Belief Revision}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1997},
}
Figure