Kernel Contraction and Base Dependence: Redundancy in the Base Resulting in Different Types of Dependence

Mehrdad Oveisi, James P. Delgrande, Fred Popowich, Francis Jeffry PelletierIJCAI 2015

Abstract

This paper establishes a formal link between belief contraction—the process of removing information from a knowledge base—and the concept of dependence. By focusing on "belief bases" (finite, non-closed sets of information) rather than idealized belief sets, the authors uncover how redundancy creates distinct types of dependence: strong and weak. They provide an axiomatic characterization proving that these relations correspond to Kernel Contraction, offering a theoretical benchmark for relevance measures in Artificial Intelligence.

Introduction

In Artificial Intelligence, "belief change" is the critical process of updating a system's knowledge when new, possibly conflicting, information arrives. A fundamental operation in this field is contraction: the removal of a belief along with everything that logically implies it to maintain consistency.

However, updating large knowledge bases is computationally expensive. To optimize this, researchers seek to identify which beliefs are "dependent" on the one being removed, ensuring that only necessary modifications are made. While previous work focused on the AGM paradigm—which deals with infinite, logically closed "belief sets"—this paper addresses the more practical scenario of belief bases. These are finite sets of formulas that are not necessarily closed under implication, reflecting how real-world AI systems actually store information.

Defining Dependence in Belief Bases

The core challenge in belief bases is that a piece of information might be explicitly removed but remain "implicitly" present because it is still implied by other remaining facts. To formalize this, the authors utilize Gärdenfors’ Preservation Criterion (GPC), which posits that beliefs independent of a change should remain intact.

Comparison of contraction in belief sets (a) and belief bases (b).

The authors define three distinct types of dependence using formal logic:

  1. Base Dependence ($\approx$): The most general form, where a belief is simply removed from the base during contraction.
  2. Strong Base Dependence ($\hat{\approx}$): A belief is removed from the base and is no longer implied by the remaining information.
  3. Weak Base Dependence ($\check{\approx}$): A belief is removed from the base but remains logically implied by the remaining formulas—a "non-persistent" dependence.

The Role of Redundancy and Relative Closure

A key insight of this research is that weak dependence is a direct consequence of redundancy within the knowledge base. If a belief base contains no redundant information, weak dependence effectively vanishes.

Visualizing how base dependence reduces to standard dependence when the base is logically closed.

The authors identify relative closure as the critical property for managing this. If a contraction operator satisfies relative closure, it "cleans up" the base such that weak dependencies cannot occur. This provides a formal method to distinguish between the "informative" parts of a knowledge base and the "redundant" parts based on their behavior during contraction.

Formal Characterization and Results

The paper provides an axiomatic characterization, proving that these dependence relations correspond mathematically to Kernel Contraction, a general class of operations for modifying belief bases.

Key results include:

  • Theorem 10: Formally proves that weak base dependence exists if and only if the contraction operator fails to satisfy "relative closure."
  • Theorem 16 (Characterization): Establishes that a dependence relation is a "base dependence" if and only if the corresponding change operation is a kernel contraction.
  • Generalization: The authors show that earlier definitions of dependence (e.g., by Fariñas del Cerro and Herzig) are actually special cases of this broader framework.

Conclusion and Future Directions

By formalizing these relations, the authors provide a "gold standard" for theoretical benchmarking. Researchers developing heuristic-based relevance measures can now test their methods against these formal definitions to verify correctness.

While the paper provides the logical foundation, it does not offer specific algorithms for massive real-world databases. Future work may involve exploiting weak base dependence to develop redundancy-removal tools or applying this framework to other belief change operations like "revision" or "merging."

Summary updated

BibTeX
@inproceedings{oveisi2015kernel,
  author = {Mehrdad Oveisi and James P. Delgrande and Fred Popowich and Francis Jeffry Pelletier},
  title = {{Kernel Contraction and Base Dependence: Redundancy in the Base Resulting in Different Types of Dependence}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure