Belief Change Based on Global Minimisation

James P. Delgrande, Jérôme Lang, Torsten SchaubIJCAI 2007

Abstract

This paper presents a unified mathematical framework for belief change by representing information sources as nodes in an undirected graph. By minimizing disagreements across the edges of the graph, the authors demonstrate that belief revision, merging, and temporal extrapolation are all specific instances of a single "global minimization" principle. This graph-based approach allows for a generalized logic of minimizing change across arbitrary structures, providing a powerful tool for knowledge representation and reasoning.

Introduction

In the field of Knowledge Representation, "belief change" refers to the process of updating a set of beliefs when new, potentially conflicting information is introduced. Historically, researchers have treated different types of belief change as distinct problems:

  • Belief Revision: An agent updates their beliefs based on a new fact.
  • Belief Merging: Multiple agents reach a consensus from differing viewpoints.
  • Temporal Extrapolation: Predicting the state of the world over time based on intermittent observations.

Despite their conceptual similarities, these operations were often studied in isolation. This paper addresses the gap by proposing a single framework that elegantly handles these scenarios and extends to new ones, such as spatial reasoning (e.g., inferring weather in one city based on its neighbors).

The Graph-Based Framework

The proposed approach represents a problem instance as an undirected graph $G = \langle V, E \rangle$. Each vertex $v \in V$ is associated with a logical formula representing the information known at that specific "point"—whether that point represents a moment in time, a physical location, or a specific agent.

Key Technical Components

  1. Change Sets ($\Delta$): To track disagreements, a change set identifies which atomic facts differ between two connected nodes.
  2. Global Minimization: Rather than updating nodes sequentially, the framework considers the entire graph. It identifies "preferred interpretations"—models of the world that minimize the total set of disagreements across all edges, typically using set-containment or cardinality.
  3. Completion and Consensus:
    • The Completion of a scenario provides a refined formula for every node, incorporating information gleaned from its neighbors.
  4. The Consensus represents the invariant information that holds true across the entire system after minimization.
  5. Syntactic Characterization: The authors provide an algorithm to compute these completions using "maximal fits," bridging the gap between abstract model theory and practical logic computation.

Topology and Reasoning

A central insight of this work is that the topology of the graph determines the specific type of reasoning being performed:

  • Chain Graph: Nodes arranged in a line result in temporal extrapolation.
  • Star Graph: Multiple nodes connected to a single center result in belief merging with integrity constraints.
  • Complete Graph: A fully connected graph results in a specific type of consensus merging.
  • Two-Node Graph: Simplifies to classical belief revision.

The framework formalizes the intuition of information persistence: "change is exceptional." If a fact is known at Node A, the system assumes it holds at a connected Node B unless explicit evidence suggests otherwise.

Theoretical Results and Complexity

The paper successfully proves that several landmark operators in AI—such as Satoh’s revision and Delgrande & Schaub’s merging—are mathematically equivalent to specific graph configurations within this framework.

Regarding computational complexity, the authors show that this generalized framework is $\Pi^p_2$-complete. While this is computationally demanding, it is no more complex than the specific belief change operators it replaces, meaning there is no "generality tax." Furthermore, for problems where beliefs are simple conjunctions of literals, the completion can be computed in polynomial time, suggesting viability for certain real-world applications.

Discussion and Future Work

While the current model utilizes global minimization, future research could explore "local" minimization, where nodes only consider immediate neighbors, potentially leading to interesting iterative processes. Additionally, the current framework primarily handles "belief strengthening," where nodes add to their beliefs. Future iterations could allow for full revision, where an agent might discard their own data if a neighbor is deemed more reliable. Finally, while the conjunctive case is efficient, optimizing the general case for large-scale systems remains an open challenge.

Summary updated

BibTeX
@inproceedings{delgrande2007belief,
  author = {James P. Delgrande and Jérôme Lang and Torsten Schaub},
  title = {{Belief Change Based on Global Minimisation}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2007},
}

Loading related content...

Figure