Belief Change in a Preferential Non-monotonic Framework

Giovanni Casini, Thomas Andreas MeyerIJCAI 2017 · DOI

TL;DR

This paper bridges the gap between belief change (how to update knowledge bases) and non-monotonic reasoning (handling exceptions and defeasible information). The authors propose a novel framework that adapts classical belief change mechanisms to preferential non-monotonic settings, allowing for more nuanced and robust knowledge updates in the face of uncertainty and exceptions.

What Problem Does This Paper Address?

In artificial intelligence, we often deal with knowledge that isn't absolute. For instance, we know that birds typically fly, but we also know about penguins and ostriches that don't. This is the realm of non-monotonic reasoning, where adding new information can invalidate previous conclusions. Simultaneously, belief change theory (like the AGM framework) provides formal ways to update a knowledge base when new information arrives, ensuring consistency.

However, these two fields have largely developed independently. Classical belief change assumes a monotonic underlying logic, meaning new information never invalidates existing conclusions. Applying it directly to non-monotonic settings is problematic because the "monotonic core" of the reasoning needs to be identified and treated differently from the defeasible parts. Simply applying non-monotonic reasoning might seem to make belief change redundant, but this overlooks the crucial distinction between defeasible and non-defeasible information within a knowledge base. This paper tackles the challenge of integrating these two formalisms, specifically by defining belief change operators within a preferential non-monotonic framework.

Methods

The core idea is to leverage the "monotonic core" of a non-monotonic framework. The authors focus on preferential non-monotonic reasoning, a well-established approach using defeasible conditionals (e.g., "typically, if A then B"). They define the monotonic core as the preferential closure of the knowledge base, which essentially captures the non-defeasible information.

The paper then adapts the standard AGM (Alchourrón, Gärdenfors, Makinson) belief change postulates for expansion, contraction, and revision to this preferential setting.

  • Expansion: Simply adding a defeasible conditional to the knowledge base and ensuring it's closed under preferential entailment.
  • Contraction: This is more complex. They define contraction operators that remove a defeasible conditional while preserving consistency and coherence. This involves identifying "remainder sets" of the knowledge base that no longer entail the conditional to be removed.
  • Revision: This is defined in relation to contraction, using a preferential version of the Levi Identity. The authors distinguish between revision for consistency (ensuring the knowledge base remains non-contradictory) and revision for coherence (maintaining that classes introduced in the language can, in principle, be populated).

A key technical contribution is showing that preferential AGM belief change, as defined, can be obtained in terms of classical AGM belief change by first ranking the defeasible conditionals and then applying classical contraction to the monotonic core.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • The Monotonic Core is Key: The paper highlights that to effectively apply belief change to non-monotonic reasoning, one must first isolate the "monotonic core" – the non-defeasible part of the knowledge. Belief change operations should primarily target this core.
  • Bridging the Gap: The work provides a formal bridge between classical belief change and preferential non-monotonic reasoning, showing how established AGM postulates can be meaningfully extended.
  • Coherence Matters: Beyond just consistency, the paper emphasizes the importance of "coherence" in belief change, particularly for ontological applications, ensuring that introduced concepts remain meaningful.
  • Surprising Equivalence: A significant finding is that preferential AGM belief change can be characterized by classical AGM belief change applied to the monotonic core, suggesting a deep connection between the two formalisms.
  • Nuanced Revision: The paper distinguishes between revising for consistency and revising for coherence, offering a more refined approach to updating knowledge bases with exceptions.

Key Results

The paper presents several theoretical results:

  • It defines and characterizes contraction and revision operators for the monotonic core of supra-preferential cumulative (spc) operators, which are a broad class of non-monotonic entailment relations.
  • It demonstrates that preferential AGM contraction can be reduced to classical AGM contraction by leveraging a ranking of defeasible conditionals.
  • It provides a framework for defining revision operators for spc-operators, linking them to the revision of their monotonic cores.
  • The paper establishes representation results, showing that the defined operators satisfy specific postulates if and only if they can be constructed using partial meet functions (for contraction) or derived from contraction via the Levi Identity (for revision).

Limitations and Future Work

  • Representation Results for Coherence Revision: While the paper defines revision for coherence preservation, it notes that a full representation result analogous to the one for consistency revision is still needed.
  • Base Change for Defeasible Bases: The authors suggest extending their work to "base change" for defeasible bases, which would involve changing the base itself rather than just the closure of the base.
  • Belief Change for Description Logics: A promising future direction is applying these concepts to belief change in Description Logics, a field with significant interest in non-monotonic formalisms.
  • Practical Implementation: The paper lays theoretical foundations; future work could explore practical implementations and empirical evaluations of these new belief change operators.

Summary updated

BibTeX
@inproceedings{casini2017belief,
  author = {Giovanni Casini and Thomas Andreas Meyer},
  title = {{Belief Change in a Preferential Non-monotonic Framework}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/129},
}
Figure