Investigations into a Theory of Knowledge Base Revision: Preliminary Report

AAAI 1988

TL;DR

This paper introduces a novel, purely model-theoretic approach to knowledge base revision, focusing on how to consistently incorporate new, potentially contradictory information. The proposed theory is grounded in desirable principles like preserving prior knowledge and prioritizing new information, offering a formal framework that is both semantically sound and syntactically implementable.

What Problem Does This Paper Address?

In many AI applications, knowledge bases (KBs) are central to representing information about a domain. However, these KBs are not static; they must be updated when new information arrives. A significant challenge arises when this new information contradicts existing beliefs within the KB. Simply adding the new information would lead to inconsistency, rendering the KB useless. Therefore, a robust mechanism is needed to revise the KB, which involves not only incorporating the new information but also judiciously abandoning some of the old beliefs to maintain consistency. This paper tackles this fundamental problem of knowledge base revision, aiming to formalize the process in a principled and systematic way.

Methods

The authors propose a new theory of knowledge base revision that is defined at the "knowledge level," meaning it's independent of the specific symbolic representation used for the KB. The core of their approach is model-theoretic: they represent a KB as a set of models (possible worlds) consistent with its beliefs.

The revision process, denoted as $\psi \circ \mu$ (revising knowledge $\psi$ with new information $\mu$), is defined by a series of generalization steps. If $\psi$ and $\mu$ are inconsistent, they systematically "generalize" the models of $\psi$ by changing the truth values of atoms. This generalization is done using an operator $g$, which expands a set of models by considering interpretations that differ in at most one atom's truth value. This process is repeated ($g^k$) until a set of models is found that is consistent with $\mu$. The revised knowledge $\psi \circ \mu$ is then constructed from these consistent models.

A syntactic characterization of this model-theoretic approach is also provided, offering a practical way to compute revisions without directly manipulating models. This involves a technique to compute the generalized formula $G(\psi)$ syntactically, which is then used to define the revision.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Model-Theoretic Foundation: Defining revision purely in terms of models provides a clear, unambiguous semantic basis, avoiding issues related to the specific syntax of knowledge representation.
  • Principled Revision: The theory is built upon a set of desirable principles for knowledge revision, including:
  • Adequacy of Representation: The revised KB should have the same representation as the old one.
  • Irrelevance of Syntax: The revision should not depend on the specific wording of the old or new information.
  • Maintenance of Consistency: If the old knowledge and new information are consistent, the revised KB should also be consistent.
  • Primacy of New Information: The revised KB must conform to the new information.
  • Persistence of Prior Knowledge: As much of the old knowledge as possible should be retained.
  • Minimality of Change: The generalization process implicitly defines a notion of "minimal change" to the KB's models to accommodate new information.
  • Fairness: The approach aims for fairness by considering all possible minimal changes, avoiding arbitrary choices.
  • Syntactic Implementation: The development of a syntactic method for revision makes the theory practically applicable.

Key Results

The paper presents a formal definition of knowledge base revision ($\psi \circ \mu$) based on model generalization. It provides a syntactic method for computing this revision, which is crucial for practical implementation. The authors also establish that their revision scheme satisfies the Gärdenfors postulates for theory change, a well-regarded set of axioms in the field. Furthermore, they argue that their approach retains more old knowledge than some other revision schemes, making it more "conservative."

Limitations and Future Work

The authors acknowledge that the consistency checks required for determining the minimum generalization step ($k$) can be computationally expensive (NP-Complete for propositional logic). They also note that their current work is limited to propositional logic and suggest extending it to first-order logic and epistemic languages. Future work includes investigating further criteria for fairness and preservation of old knowledge, and exploring differential treatment of certain beliefs (e.g., integrity constraints) to relax the fairness principle when necessary.

Summary updated

BibTeX
@inproceedings{1988investigations,
  title = {{Investigations into a Theory of Knowledge Base Revision: Preliminary Report}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1988},
}
Figure