Measuring Strong Inconsistency

Markus Ulbricht, Matthias Thimm, Gerhard BrewkaAAAI 2018 · DOI

TL;DR

This paper extends the field of inconsistency measurement from classical, monotonic logics to more complex nonmonotonic frameworks (like Answer Set Programming). The authors introduce three new measures based on the concept of "strong inconsistency" and propose a refined set of "rationality postulates" to evaluate how well these measures capture the intuitive severity of logical conflicts.

What Problem Does This Paper Address?

In classical logic, if a set of statements is inconsistent, adding more information can never make it consistent—this is called monotony. However, in nonmonotonic reasoning (common in AI and human-like logic), new information can actually resolve existing conflicts. For example, "Birds fly" and "Tweety is a bird" might conflict with "Tweety does not fly," but adding "Tweety is a penguin" resolves the surprise.

Existing tools for measuring "how inconsistent" a database is were designed for the classical world. They fail in nonmonotonic settings because they don't account for the fact that some conflicts are "resolvable" while others are "strong" (persistent). The authors aim to bridge this gap by defining measures that can handle the fluid nature of nonmonotonicity.

Methods

The authors build their approach on an abstract definition of a logic that covers both classical and nonmonotonic systems. The centerpiece is the notion of Strong $K$-inconsistency: a subset of a knowledge base is strongly inconsistent if it remains inconsistent no matter which other parts of the knowledge base you combine it with.

They propose three specific measures:

  1. $I_{MSI}$: Simply counts the number of minimal strongly inconsistent subsets.
  2. $I_{MSIC}$: A weighted count where smaller inconsistent sets contribute more to the "inconsistency score" than larger ones (based on the intuition that small, tight conflicts are more severe).
  3. $I_P$: Counts the total number of unique formulas involved in all minimal strongly inconsistent subsets.

To evaluate these, they adapt "rationality postulates"—mathematical litmus tests for whether a measure behaves "sensibly"—to the nonmonotonic context.

Datasets

As a theoretical paper in formal logic, this work does not use empirical datasets or training sets. Instead, it uses formal examples from Answer Set Programming (ASP) and propositional logic to provide counter-examples and proofs of concept.

Key Insights and Ideas

  • Redefining Monotony: The classical "Monotony" postulate (more data = more inconsistency) is replaced by Strong Monotony. A measure should only increase if the new data preserves existing conflicts rather than resolving them.
  • The "Neutral" Formula: They introduce the concept of a "neutral" formula—one that neither creates nor resolves any conflicts. A robust measure should be "Independent" of such formulas.
  • Context Matters: The authors argue that the inconsistency of a subset can only be truly understood within the "context" of the whole knowledge base. They introduce a "Contextual" version of their measures to account for how the surrounding rules might mitigate a local conflict.
  • Complexity Trade-offs: Measuring inconsistency is computationally expensive. The paper maps out exactly how hard these problems are, showing they often sit high up in the polynomial hierarchy (e.g., involving counting problems like $\# \cdot coNP$).

Key Results

  • Postulate Compliance: The authors proved that $I_{MSI}$ and $I_{MSIC}$ satisfy most of the desirable properties (Consistency, Strong Monotony, Independence, etc.), while the simpler $I_P$ fails on "Separability" (the idea that independent conflicts should just be summed up).
  • The "SI-free" Surprise: Interestingly, none of the proposed measures satisfy the "SI-free" postulate, which suggests that even formulas not involved in a conflict can still influence the overall structure of inconsistency in nonmonotonic systems.
  • Computational Hardness: For Answer Set Programming, calculating these measures is significantly harder than just checking for consistency. Specifically, finding the value of $I_{MSI}$ is $\# \cdot \Pi^p_2$-complete for disjunctive logic programs.

Limitations and Future Work

The primary limitation is computational complexity. Because these measures require identifying all minimal strongly inconsistent sets, they are difficult to scale to massive knowledge bases without significant optimization or approximation techniques.

The authors suggest that future work should explore:

  • Refining the "Contextual" measures further to better handle "resolvable" vs. "unresolvable" conflicts.
  • Investigating other classical measures (like those based on the Shapley value from game theory) and seeing how they translate to the nonmonotonic "Strong Inconsistency" framework.
  • Developing more tailored postulates for specific frameworks like Argumentation Graphs.

Summary updated

BibTeX
@inproceedings{ulbricht2018measuring,
  author = {Markus Ulbricht and Matthias Thimm and Gerhard Brewka},
  title = {{Measuring Strong Inconsistency}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.1609/aaai.v32i1.11546},
}
Figure