An Inconsistency Tolerant Model for Belief Representation and Belief Revision

TL;DR

This paper introduces a novel "B-structure" model for representing and revising an agent's beliefs. It tackles the challenge of real-world agents holding inconsistent beliefs by allowing for localized consistency and using a four-valued logic, offering a more psychologically plausible and computationally tractable approach than traditional methods.

What Problem Does This Paper Address?

Traditional models of belief representation and revision, like the widely-cited AGM (Alchourron, Gardenfors, Makinson) framework, often assume that an agent's beliefs form a consistent set (a "theory"). However, this is unrealistic. Real individuals and even large databases often harbor inconsistencies, either explicitly or implicitly. Furthermore, these models can be computationally expensive, and they struggle to distinguish between beliefs that are directly asserted (explicit) versus those that are logical consequences (implicit), especially when the explicit beliefs are inconsistent. The paper aims to address these limitations by proposing a model that:

  • Tolerates inconsistency: Allows for inconsistencies without collapsing the entire belief system.
  • Maintains minimal change: Ensures that belief revisions are as close as possible to the original beliefs.
  • Is computationally tractable: Aims for efficiency, especially for complex belief systems.
  • Distinguishes explicit and implicit beliefs: Provides a psychologically plausible way to handle these two types of beliefs, even in the presence of inconsistency.

Methods

The core of the paper is the introduction of the B-structure model. This model generalizes the traditional "theory" representation of beliefs. Instead of a single set of beliefs, a B-structure is a collection of pairs (Li, Ti), where Li is a language (a set of propositional symbols) and Ti is a theory (a consistent set of beliefs) within that language. These languages Li can overlap, allowing for "cross-talk" between different belief areas.

Key methodological contributions include:

  • Language Splitting (LS Model): Building on prior work, the paper utilizes the idea of splitting a language into disjoint or partially overlapping sub-languages. This allows for local processing of beliefs.
  • B-structure: A belief structure B is defined as {(L1, T1), ..., (Ln, Tn)} where L = UL_i and each T_i is a theory in L_i. The L_i form a k-partition, meaning each propositional symbol appears in at most k languages. This allows for controlled overlap.
  • m-consistency: A B-structure is m-consistent if any m of the T_i are jointly consistent. This provides a quantifiable measure of inconsistency tolerance.
  • Four-Valued Logic: To handle inconsistency gracefully, the model employs Belnap's four-valued logic, with truth values {1, true, false, T} (where T represents over-defined or inconsistent). This allows for nuanced answers to queries.
  • Query Answering: A query "A?" is answered by identifying the relevant theories Ti whose languages Li intersect with the language of A, forming a combined theory ΓA, and then evaluating A within ΓA using the four-valued logic.
  • B-structure Revision: Two options for revision are proposed:
  • Option A (Non-merging): Each Ti is revised independently using local AGM-style operators. This preserves the separation of belief areas.
  • Option B (Merging): If new information overlaps multiple languages, those languages and their theories are merged. This reflects a more significant update where the division of beliefs is deemed artificial.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Realism through controlled inconsistency: The most significant insight is that by allowing for partial overlap of languages and using a four-valued logic, the model can represent agents who are locally consistent but globally inconsistent, mirroring human cognition more accurately.
  • Computational advantage of splitting: Separating beliefs into smaller, potentially overlapping, language chunks can significantly reduce the computational cost of belief revision, especially when the new information is localized.
  • Distinguishing explicit/implicit beliefs: The model naturally handles this by considering the explicit beliefs within each Ti and their logical consequences. When Ti are inconsistent, the four-valued logic prevents trivial consequences.
  • Flexibility in revision: The two revision options (merging vs. non-merging) provide flexibility, allowing the model to adapt to different scenarios of new information.

Key Results

  • The paper presents a formal definition of a B-structure and its properties, including m-consistency.
  • It defines query answering procedures using the four-valued logic, which can yield "true," "false," "no information" (1), or "inconsistent" (T) answers.
  • Two revision operators (Option A and Option B) are proposed, along with axioms that show how they relate to AGM postulates and maintain desirable properties like minimal change.
  • The paper argues that the B-structure framework is computationally more efficient than traditional models for certain types of queries and revisions.

Limitations and Future Work

  • Complexity of m-consistency: While m-consistency provides a measure of tolerance, determining the optimal m and ensuring it can be maintained might be complex.
  • Choice of k-partition: The paper suggests that a smaller k (more disjoint languages) leads to more separation, but the optimal partitioning strategy is not fully elaborated.
  • Implementation and empirical evaluation: The paper outlines the theoretical framework and suggests future work in implementing and thoroughly studying the query answering and revision procedures.
  • Further exploration of revision options: While two options are presented, further investigation into their properties and practical implications is suggested.

Summary updated

BibTeX
@inproceedings{1999inconsistency,
  title = {{An Inconsistency Tolerant Model for Belief Representation and Belief Revision}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {1999},
}
Figure