A Comparative Study of Ranking Formulas Based on Consistency

Badran Raddaoui, Christian Straßer, Saïd JabbourIJCAI 2023 · DOI

TL;DR

This paper tackles the challenge of ranking formulas within an inconsistent knowledge base, proposing a framework to derive these rankings solely from the inherent structure of the information. By systematically comparing various ranking semantics against a set of desirable postulates, the authors reveal that most approaches yield incompatible rankings, highlighting the nuanced nature of defining "plausibility" in the face of contradiction.

What Problem Does This Paper Address?

In many real-world scenarios, information sources can be contradictory, leading to inconsistent knowledge bases. While classical logic treats all formulas equally, it's often crucial to understand which pieces of information are more "plausible" or "reliable" than others. This is particularly important when trying to resolve inconsistencies: should we focus on removing formulas that are involved in many conflicts, or those that are central to a single, critical conflict? This paper addresses the fundamental question of how to formally rank formulas within an inconsistent knowledge base based only on the relationships between the formulas themselves, without relying on external information like probabilities or explicit preferences.

Methods

The authors propose a framework for ranking formulas based on consistency. They begin by defining a set of desirable postulates (e.g., syntax independence, non-discrimination for consistent bases, self-contradictory formulas being least plausible) that any reasonable ranking semantics should satisfy. They then introduce and analyze several families of ranking semantics:

  • Culpability-based: Ranks formulas based on how much they contribute to the inconsistency (e.g., using the Shapley inconsistency value).
  • Clustering-based: Ranks formulas based on their involvement in minimal inconsistent sets (MI) or their presence in maximal consistent sets (MS). Variants like MI+ and MS-revision are also explored.
  • Update-based: Ranks formulas based on the impact of their removal on the knowledge base's consistency.
  • Distance-based: Ranks formulas based on their "closeness" to consistency, measured by distances to maximal consistent sets or free formulas.

The core of their methodology is a comparative analysis: they evaluate how well each proposed ranking semantics satisfies the defined postulates and, crucially, whether different semantics produce compatible (i.e., identical or perfectly inversely correlated) rankings.

Datasets

Not discussed in the paper. The paper focuses on theoretical frameworks and uses small, illustrative examples of propositional knowledge bases rather than large datasets.

Key Insights and Ideas

  • No Single "Best" Ranking: The most striking insight is that most of the proposed ranking semantics are "rank-incompatible." This means different, seemingly reasonable approaches to defining plausibility can lead to vastly different orderings of formulas. This underscores that the notion of "plausibility" is context-dependent and can be interpreted in multiple ways.
  • Postulates as a Guiding Light: The paper's systematic evaluation of ranking semantics against a comprehensive set of postulates provides a rigorous way to understand their behavior and limitations. This postulate-driven analysis is key to differentiating the semantics.
  • Free Formulas are Universally Top-Ranked: A consistent finding across almost all semantics is that formulas not involved in any conflicts (free formulas) are ranked as the most plausible. This aligns with intuition.
  • Self-Contradictory Formulas are Debated: While some semantics consistently rank self-contradictory formulas as the least plausible (as expected), others (like MI-based or Shapley-based) do not, revealing a significant point of divergence.
  • Syntax Independence is Key: Several postulates (like Syntax Independence and Non-Interference) ensure that the ranking doesn't depend on arbitrary naming of variables or irrelevant formulas, which is a desirable property for a robust framework.

Key Results

  • Rank Incompatibility is the Norm: The paper demonstrates that most pairs of ranking semantics are rank-incompatible. For instance, MI-based and Shapley-based semantics are incompatible, as are MS-based and MSR-based semantics.
  • Postulate Satisfaction Varies: While some postulates (like syntax-based ones) are widely satisfied, others (like Self-Contradictory Formula (SF) and Central Conflict (CC)) are only met by a subset of the semantics, effectively distinguishing them.
  • MI+ and MS Semantics are Strong Performers: The MI+ and MS-based ranking semantics are highlighted as satisfying a broad range of postulates, suggesting they might be more generally applicable or robust.
  • Illustrative Examples: The paper uses small, concrete examples (like K1 and K2) to demonstrate how different ranking semantics produce different orderings for the same set of formulas, making the abstract concepts tangible.

Limitations and Future Work

  • Focus on Propositional Logic: The current framework is developed for propositional logic. Extending it to more expressive languages (like description logics or first-order logic) is a natural next step.
  • Computational Complexity: While the paper defines semantics, it doesn't delve deeply into their computational complexity, which would be crucial for practical applications.
  • Other Ranking Approaches: The authors suggest exploring other ranking methods, such as those based on argumentation, multi-valued logics, or maximal consistent sets (MC sets).
  • Characterization Results: The paper aims to be a first step towards characterizing sets of criteria that lead to specific ranking behaviors. Further work could explore deeper theoretical connections and equivalences between postulates and semantics.

Summary updated

BibTeX
@inproceedings{raddaoui2023comparative,
  author = {Badran Raddaoui and Christian Straßer and Saïd Jabbour},
  title = {{A Comparative Study of Ranking Formulas Based on Consistency}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2023},
  doi = {10.24963/ijcai.2023/371},
}
Figure