Belief Update without Compactness in Non-finitary Languages

Jandson S. Ribeiro, Abhaya Nayak, Renata WassermannIJCAI 2019 · DOI

TL;DR

This paper tackles the challenge of belief update in logical systems that aren't "compact," meaning they can't guarantee that any logical consequence can be derived from a finite subset of premises. The authors introduce a new class of "royal reflected splinter" functions that fully capture the rationality postulates for belief update in these non-finitary settings, offering a more general framework than existing methods.

What Problem Does This Paper Address?

Belief change, the process of updating an agent's knowledge in response to new information, is typically studied within the framework of AGM (Alchourrón, Gärdenfors, Makinson) or KM (Katsuno, Mendelzon) postulates. These frameworks, however, largely assume that the underlying logic is both Tarskian and finitary. Finitaryness, specifically the property of compactness, means that if a conclusion follows from a set of premises, it must follow from a finite subset of those premises.

Many important logical systems, such as temporal logics (CTL, LTL) used in AI planning and formal verification, are not compact. This non-compactness poses a problem for standard KM belief update constructions. The authors observe that when compactness is discarded, the classical KM update functions no longer fully satisfy the KM rationality postulates; they become characterized by a subset of these postulates, making them weaker. The paper aims to bridge this gap by developing belief update mechanisms that work correctly even for non-finitary logics, ensuring that all KM rationality postulates are met.

Methods

The paper proposes a two-pronged approach:

  1. Identifying weaker CUP functions: They first analyze the standard Classical Update (CUP) functions in the context of non-finitary logics. They demonstrate that these functions, while satisfying a basic set of KM postulates, fail to capture the full set due to issues arising from infinite chains of models and the lack of compactness.
  2. Introducing "Royal Reflected Splinter" functions: To address the limitations, the authors introduce a new class of update functions called "royal reflected splinters." These functions are built upon the concept of "appointees," which are more general than the pre-orders used in CUP functions. Appointees select "best" complete consistent theories based on specific criteria.
  3. Splinter Functions: These are the initial step, using appointees to select models. They satisfy the basic KM postulates.
  4. Relational Appointees: These appointees use "contra-headed relations" (a specific type of binary relation) to select models, ensuring a richer preference structure.
  5. Royal Splinter Functions: These are splinters built with relational appointees. They are shown to satisfy supplementary KM postulates like (K◇6) and (K◇8).
  6. Quasi-Reflection: A crucial property introduced for the relations used by appointees. This property helps capture the (K◇7) postulate, which is problematic in non-finitary settings.
  7. Royal Reflected Splinters: These are royal splinters whose appointees satisfy quasi-reflection. The paper proves that these functions are fully characterized by the complete set of KM update postulates in non-finitary logics.

Essentially, the paper moves from model-based preferences (pre-orders) to theory-based preferences (appointees) and introduces specific relational properties (contra-headed, quasi-reflection) to ensure full KM rationality in non-finitary settings.

Datasets

Not discussed in the paper. The paper focuses on theoretical logical frameworks rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Compactness is Key to Standard KM: The paper highlights that the standard KM update constructions heavily rely on the compactness property of the underlying logic. Without it, the direct correspondence between constructions and rationality postulates breaks down.
  • Non-Finitary Logics Require New Tools: The challenge isn't just non-compactness, but the broader "non-finitaryness" of the logic. This necessitates moving beyond simple pre-orders to more sophisticated preference mechanisms like appointees.
  • Appointees as a Generalization: Appointees offer a more flexible way to define "closeness" between epistemic states, allowing for the development of update functions that are fully rational even in complex, non-finitary logics.
  • Quasi-Reflection for Consistency: The introduction of quasi-reflection is a novel contribution that specifically addresses the challenge of capturing the (K◇7) postulate in non-finitary settings, ensuring consistency in belief updates.
  • Representation Theorem: The paper establishes a strong representation result: fully KM rational belief update functions in non-finitary languages are precisely "royal reflected splinters." This provides a clear characterization of what constitutes a "good" belief update mechanism in these extended logical frameworks.

Key Results

  • The paper demonstrates that classical CUP functions are weaker in non-finitary logics, characterized by a proper subset of KM postulates.
  • A new class of "royal reflected splinter" functions is introduced.
  • These royal reflected splinter functions are proven to be fully characterized by the complete set of KM update postulates for non-finitary logics. This is the main representation result.
  • The paper provides a detailed breakdown of how specific KM postulates (like K◇6, K◇7, K◇8) are captured by the new constructions, particularly through the properties of appointees and their underlying relations.

Limitations and Future Work

  • Theoretical Focus: The paper is primarily theoretical, focusing on logical characterizations and constructions. While it mentions applications in temporal logics, it doesn't present empirical evaluations or benchmarks on specific non-finitary systems.
  • Complexity of Implementation: The proposed "royal reflected splinter" functions, while theoretically sound, might be computationally complex to implement in practice due to the nature of appointees and the underlying relations.
  • Future Work: The authors suggest exploring the connection between their work and other belief change operations like contraction, as well as investigating the practical implementation of these new update functions. They also hint at further work on "mirrored relations" as an alternative to quasi-reflection for capturing certain postulates.

Summary updated

BibTeX
@inproceedings{ribeiro2019belief,
  author = {Jandson S. Ribeiro and Abhaya Nayak and Renata Wassermann},
  title = {{Belief Update without Compactness in Non-finitary Languages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/257},
}

Loading related content...

Figure