Construction of System of Spheres-based Transitively Relational Partial Meet Multiple Contractions: An Impossibility Result (Extended Abstract)

Maurício D. Luís Reis, Eduardo Fermé, Pavlos PeppasIJCAI 2017 · DOI

TL;DR

This paper investigates the construction of multiple belief contractions using "systems of spheres." It proves that no single system of spheres-based method can capture all possible "transitively relational partial meet multiple contractions." However, it also proposes two novel methods that generate a subset of these contractions, offering new ways to model complex belief change.

What Problem Does This Paper Address?

Belief revision is a fundamental aspect of artificial intelligence, dealing with how an agent's beliefs should change when new information is received. The AGM (Alchourrón, Gärdenfors, Makinson) framework provides a formal model for this. A key operation is contraction, where an agent removes beliefs that are inconsistent with new information.

Traditionally, AGM focused on contracting a belief set with a single sentence. However, real-world agents often receive information as a set of sentences (e.g., from multiple sensors). This paper addresses the challenge of extending belief contraction to handle these multiple contraction scenarios.

Specifically, the authors focus on a particular class of contraction functions called transitively relational partial meet multiple contractions (TRPMMCs). They also explore system of spheres-based contractions, a semantic approach to modeling belief change using possible worlds. The central question is whether systems of spheres can fully capture the TRPMMCs, analogous to how they can for single-sentence contractions.

Methods

The paper builds upon existing work in belief revision, particularly the AGM framework and its extensions.

  • Partial Meet Contractions: This is a standard model for belief contraction, based on selecting from maximal consistent subsets of the original belief set that do not entail the sentence(s) to be removed.
  • Transitively Relational Partial Meet Contractions (TRPMMCs): This is a refinement of partial meet contractions, characterized by a specific ordering (transitive relation) on the selected subsets.
  • System of Spheres: This is a possible-worlds semantics where the belief set is represented by a set of possible worlds, and a "system of spheres" (nested sets of worlds) is used to model contraction. For single-sentence contractions, it's known that systems of spheres perfectly capture TRPMMCs.
  • Multiple Contractions: The paper extends the concept of contraction to handle sets of sentences as input, rather than just single sentences. This involves defining "package selection functions" and "package remainders."
  • Impossibility Proof: The core of the paper is a proof demonstrating that no single system of spheres-based method can generate all TRPMMCs for multiple contractions. This is achieved through a counterexample and generalized theorems showing that there are more TRPMMCs than systems of spheres.
  • Constructive Methods: The paper then proposes two new methods for constructing multiple contractions using systems of spheres. These methods generate some TRPMMCs but not all, providing a way to implement a subset of these complex belief change operations.

Datasets

Not discussed in the paper. The paper is theoretical and deals with formal logic and belief revision models, not empirical data.

Key Insights and Ideas

  • The Impossibility Result is Surprising: For single-sentence contractions, systems of spheres perfectly capture TRPMMCs. The paper shows this equivalence breaks down for multiple contractions, highlighting a fundamental difference in complexity.
  • More TRPMMCs than Systems of Spheres: The paper proves that for certain belief sets, there are more possible TRPMMCs than there are distinct systems of spheres. This is a key reason why a one-to-one correspondence cannot exist.
  • New Constructive Approaches: Despite the impossibility of a complete capture, the paper offers two novel ways to construct TRPMMCs using systems of spheres. These provide practical tools for implementing a subset of these sophisticated belief change operations.
  • Generalization Challenges: The work underscores the inherent difficulties in generalizing single-agent belief revision models to handle more complex, multi-input scenarios.

Key Results

  • Impossibility Theorem: It is impossible to construct all transitively relational partial meet multiple contractions (TRPMMCs) using a single system of spheres-based method.
  • Existence of Multiple TRPMMCs: For certain belief sets, there are more TRPMMCs than there are systems of spheres.
  • Two New Construction Methods: The paper introduces two distinct system of spheres-based methods for constructing multiple contractions that generate TRPMMCs. These methods are shown to produce different results, demonstrating their distinctness.

Limitations and Future Work

  • Focus on Finite Sets: The paper primarily considers multiple contractions by finite sets of sentences. Future work could explore contractions by infinite sets.
  • Specific Belief Set Example: The counterexample used to demonstrate the impossibility result relies on a specific belief set. While generalized theorems are presented, exploring the behavior across a wider range of belief sets could be beneficial.
  • Practical Implementation: While the paper provides theoretical constructions, further research could focus on the computational efficiency and practical implementation of these methods for intelligent agents.
  • Comparison with Other Multiple Contraction Models: The paper focuses on TRPMMCs. Investigating how the proposed system of spheres-based methods relate to other models of multiple contractions (e.g., package contractions) would be valuable.

Summary updated

BibTeX
@inproceedings{reis2017construction,
  author = {Maurício D. Luís Reis and Eduardo Fermé and Pavlos Peppas},
  title = {{Construction of System of Spheres-based Transitively Relational Partial Meet Multiple Contractions: An Impossibility Result (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/719},
}

Loading related content...

Figure