On the Expressivity of Inconsistency Measures (Extended Abstract)

Matthias ThimmIJCAI 2017 · DOI

TL;DR

This paper introduces a novel way to evaluate inconsistency measures in propositional logic by quantifying their "expressivity" – how many different inconsistent knowledge bases they can distinguish. By proposing four expressivity characteristics, the authors provide a framework to compare existing measures, finding that the "Talal" measure exhibits maximal expressivity across all considered dimensions.

What Problem Does This Paper Address?

In artificial intelligence, knowledge bases (collections of facts and rules) can become inconsistent, meaning they contain contradictory information. This inconsistency renders them useless for standard logical reasoning. Inconsistency measures aim to quantify how inconsistent a knowledge base is, providing a score that indicates the severity of the contradiction. While many such measures exist, it's challenging to determine which one is "best" or most meaningful for a given task. Existing evaluation methods, like rationality postulates, focus on desirable properties but can be criticized for addressing only specific aspects. This paper addresses the gap by proposing a quantitative evaluation metric: expressivity. They argue that a good inconsistency measure should be able to distinguish between a large number of different inconsistent scenarios, reflecting a nuanced understanding of the problem.

Methods

The core contribution of this paper is the introduction of four "expressivity characteristics" to quantitatively assess inconsistency measures. These characteristics measure the number of distinct inconsistency values a measure can produce when applied to specific subsets of knowledge bases. These subsets are defined by limiting:

  • Number of propositions: Ku(n) - knowledge bases using at most n propositions.
  • Number of formulas: Kf (n) - knowledge bases containing at most n formulas.
  • Maximal formula length: K¹(n) - knowledge bases where all formulas have a maximal length of n.
  • Number of propositions per formula: KP(n) - knowledge bases where each formula mentions at most n propositions.

The authors then analytically evaluate a selection of 15 existing inconsistency measures against these four characteristics, classifying them based on their ability to distinguish between different knowledge bases within these defined constraints.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis and evaluation of inconsistency measures on syntactically defined classes of knowledge bases, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Expressivity as a Key Quality Metric: The paper argues that beyond simply satisfying rationality postulates, an inconsistency measure's ability to differentiate between various degrees of inconsistency is a crucial aspect of its quality.
  • Complementary Evaluation: Expressivity characteristics offer a quantitative complement to the qualitative evaluation provided by rationality postulates.
  • Trade-offs in Measure Design: The analysis reveals that many measures are designed to focus on specific aspects (e.g., minimal inconsistent subsets vs. conflicting propositions), leading to trade-offs in their expressivity across different dimensions.
  • Maximal Expressivity Achieved: The "Talal" measure from Grant and Hunter (2013) is identified as having maximal expressivity across all four proposed characteristics among the measures studied.
  • Drastic Measure is Least Expressive: The simple "drastic" measure, which only distinguishes between consistent and inconsistent, is the least expressive, as expected.

Key Results

The paper presents a detailed analytical evaluation of 15 inconsistency measures against the four expressivity characteristics. The results are summarized in a table (Table 1), which shows the number of distinct values each measure can produce for each characteristic as a function of n.

  • The drastic measure (Id) has a constant expressivity of 2 for Cf(I,n) and Cv(I,n), and is generally the least expressive.
  • Measures like IMI (counting minimal inconsistent subsets) and IMIC (related to profiles of Boolean functions) show varying expressivity depending on the characteristic.
  • The Talal measure consistently achieves maximal expressivity, often resulting in an infinite number of distinct values (∞) for the characteristics, indicating its superior ability to distinguish between a wide range of inconsistent knowledge bases.
  • The paper also notes interesting relationships between some measures and concepts from set theory and Boolean functions.

Limitations and Future Work

  • Extended Abstract: This is an extended abstract, meaning the full proofs and detailed discussions are likely in a separate, longer publication ([Thimm, 2016a]).
  • Focus on Propositional Logic: The analysis is primarily for propositional logic. Extending these expressivity characteristics to other logical formalisms (e.g., first-order logic, description logics) would be a valuable future direction.
  • Expressivity Alone is Not Sufficient: The authors emphasize that high expressivity alone does not guarantee a good inconsistency measure. Measures that are highly expressive but fail to satisfy basic rationality postulates (like consistency) are not useful. Future work should continue to integrate expressivity analysis with rationality postulate evaluation.
  • Further Exploration of Relationships: The paper hints at deeper connections between inconsistency measures and other mathematical fields. Further investigation into these relationships could lead to new insights and measure designs.
  • Empirical Validation: While the paper provides analytical results, empirical validation of these expressivity characteristics on real-world or benchmark datasets could further solidify their utility.

Summary updated

BibTeX
@inproceedings{thimm2017expressivity,
  author = {Matthias Thimm},
  title = {{On the Expressivity of Inconsistency Measures (Extended Abstract)}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/724},
}
Figure