Stratified Evidence Logics

Philippe Balbiani, David Fernández-Duque, Andreas Herzig, Emiliano LoriniIJCAI 2019 · DOI

TL;DR

This paper introduces "stratified evidence logics" that go beyond traditional qualitative models of belief formation. By quantifying the amount of evidence needed to justify a belief, these logics offer a more nuanced way to model how agents aggregate information from various sources, with potential applications in AI and multi-agent systems.

What Problem Does This Paper Address?

Current formalisms for modeling belief formation, often called "evidence logics," typically treat evidence in a binary way: an agent either has evidence for a proposition or they don't. This approach, while useful, doesn't capture the intuitive idea that some beliefs might require more substantial or diverse evidence than others. For instance, forming a strong opinion about a movie might necessitate consulting multiple review sites, not just one. The paper aims to bridge this gap by introducing a quantitative dimension to evidence, allowing us to measure the "effort" or the number of distinct evidence sources required to justify a belief. This is particularly relevant for artificial agents that need to gather, filter, and synthesize information from potentially fallible sources.

Methods

The core contribution is the development of "stratified evidence logics" (SEL). The authors extend existing evidence logic frameworks by introducing a cardinal number parameter to modal operators. Specifically, a formula like [α]φ now means "φ can be justified using up to α pieces of evidence." The parameter α can be a natural number or the transfinite cardinal ω (representing a finite but arbitrarily large amount of evidence).

The paper defines a formal language with these stratified modalities and then develops a corresponding semantics based on "stratified evidence frames." These frames are extensions of standard neighborhood models, where the neighborhoods are organized into a hierarchy indexed by cardinal degrees. A key aspect is the definition of stratified evidence frames with a "strict" condition, which allows for a more direct correspondence with existing evidence logics.

A complete deductive calculus (axioms and rules) is provided for SEL, and its soundness and completeness for stratified evidence models are proven. The authors also establish decidability for SEL, a crucial property for practical applications. Furthermore, they demonstrate how existing evidence logics can be embedded within their new framework.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Quantifying Evidence: The most significant insight is the introduction of a quantitative parameter (cardinal numbers) to modal operators representing evidence. This moves beyond a simple "yes/no" for evidence to a graded notion of justification.
  • Effort as Evidence Count: The quantitative parameter can be interpreted as either the number of distinct evidence sources or as a measure of "effort" (e.g., computational cost, precision of measurement) required to establish a belief.
  • Stratified Hierarchy: The use of a hierarchy of evidence sets indexed by cardinal degrees provides a structured way to represent varying levels of evidential support.
  • Embedding Existing Logics: The framework's ability to naturally embed previously developed evidence logics (like those by van Benthem et al. and Baltag et al.) highlights its generality and power.
  • Decidability and Completeness: Establishing both completeness for stratified evidence models and decidability for the logic are crucial theoretical results that pave the way for practical implementation.

Key Results

  • Soundness and Completeness: The paper proves that the stratified evidence logic SEL is sound and strongly complete for the class of stratified evidence models. It is also sound and weakly complete for finite stratified evidence models.
  • Decidability: The set of theorems of SEL is decidable, meaning there's an algorithm to determine if any given formula is provable.
  • Embedding: Existing evidence logics, particularly those with modalities for qualitative evidence, can be expressed within the stratified evidence logic framework. For instance, SEL{0,1,w} is shown to be expressively equivalent to L∀ (a language used by Baltag et al.) over strict stratified evidence models.

Limitations and Future Work

  • Expressiveness Gap: The paper notes that their framework might not fully capture all expressiveness of certain existing logics, specifically mentioning that SEL□∀ cannot express [2]φ, although a proof is left for future work.
  • Complexity Analysis: While decidability is proven, the paper suggests further work on the complexity of the satisfiability problem and the development of tableau decision procedures for practical AI applications.
  • Dynamic and Multi-Agent Extensions: The authors propose extending the framework to dynamic epistemic logic by formalizing evidence expansion and contraction operations. They also plan to generalize it to multi-agent settings, allowing agents to exchange evidence.
  • Qualitative vs. Quantitative: While the paper focuses on quantitative aspects, it acknowledges that other frameworks exist that model trust or qualitative notions of effort.

Summary updated

BibTeX
@inproceedings{balbiani2019stratified,
  author = {Philippe Balbiani and David Fernández-Duque and Andreas Herzig and Emiliano Lorini},
  title = {{Stratified Evidence Logics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/211},
}
Figure