Rational Inference Relations from Maximal Consistent Subsets Selection

Sébastien Konieczny, Pierre Marquis, Srdjan VesicIJCAI 2019 · DOI

TL;DR

This paper introduces a new family of inference relations for inconsistent knowledge bases by intelligently selecting subsets of maximal consistent subsets. This selection process, guided by monotonic criteria, allows for stronger inferences than traditional methods while guaranteeing logical rationality, effectively providing a new characterization of rational inference.

What Problem Does This Paper Address?

In artificial intelligence, particularly in knowledge representation and reasoning, dealing with inconsistent information is a common challenge. When a knowledge base (a collection of facts or beliefs) contains contradictions, it can lead to nonsensical conclusions or prevent any useful inferences from being drawn. A standard approach to handle this is to consider "maximal consistent subsets" (MCSs) – the largest possible subsets of the original knowledge base that are internally consistent.

However, existing inference methods based on MCSs have limitations. "Skeptical" inference (requiring a conclusion to hold in all MCSs) is too weak, while "credulous" inference (requiring a conclusion to hold in at least one MCS) can lead to contradictory conclusions. While focusing on the largest MCSs offers some improvement, the authors argue that there's a need for more powerful and yet still "rational" inference relations. The core problem is how to select which MCSs to use for inference to gain more expressive power without sacrificing logical soundness.

Methods

The paper proposes a novel approach based on selecting maximal consistent subsets (MCSs) rather than using all of them. The key idea is to define criteria for comparing and selecting "better" MCSs.

  1. Scoring Functions: They introduce various ways to assign a "score" to individual formulas within a belief base, reflecting their "consensus" or how well they fit with other information. Examples include:
  2. #mc: How many MCSs a formula belongs to (more is better).
  3. #mus: How many minimal inconsistent subsets a formula belongs to (fewer is better, with a specific formula to ensure non-trivial formulas get non-zero scores).
  4. MIV: An inconsistency measure that considers both the number and size of minimal inconsistent subsets a formula is part of.
  5. Aggregation Functions: These scores are then aggregated (e.g., summed) for each MCS to get a score for the entire subset.
  6. Monotonic Selection Relations: The core contribution is the definition of "monotonic selection relations." These are criteria that compare MCSs. A relation is monotonic if adding a non-trivial formula to a consistent set always makes it "better" or at least as good according to the relation. This is crucial for ensuring the resulting inference is rational.
  7. Inference from Selected MCSs: An inference relation is then defined based on the MCSs that are "best" according to a chosen monotonic selection relation. This means a formula is inferred if it's entailed by all of these selected "best" MCSs.

Datasets

Not discussed in the paper. The paper uses propositional logic examples to illustrate its concepts rather than relying on specific datasets.

Key Insights and Ideas

  • Beyond "All" or "Largest" MCSs: The paper demonstrates that simply considering all MCSs or only the largest ones is not the only path to rational inference. Intelligent selection offers a richer landscape.
  • Monotonicity is Key to Rationality: The crucial insight is that a selection criterion (a "monotonic selection relation") is sufficient to guarantee a rational inference relation. This provides a powerful theoretical link.
  • Characterization of Rationality: The paper establishes a significant result: the class of rational inference relations is precisely equivalent to inference relations derived from selecting MCSs using monotonic selection relations. This offers a new perspective on what makes an inference relation "rational."
  • Flexibility in Scoring and Aggregation: The framework is flexible, allowing for different scoring functions and aggregation methods, as long as they satisfy certain properties (like monotonicity for selection).

Key Results

  • The paper defines a family of inference relations based on selecting MCSs using monotonic selection relations.
  • It proves that any inference relation derived from a monotonic selection relation is a rational inference relation.
  • It provides a characterization theorem: any rational inference relation can be represented as an inference relation derived from selecting MCSs using some monotonic selection relation. This means the proposed selection mechanism precisely captures the essence of rational inference.
  • Examples are provided showing how different scoring functions (#mc, #mus, miv) can lead to different, yet rational, inference results, sometimes yielding stronger conclusions than existing methods.

Limitations and Future Work

  • Focus on Propositional Logic: The current work is confined to classical propositional logic. Extending these ideas to more expressive logics (like first-order logic or modal logics) is a natural next step.
  • Prioritized vs. Flat Knowledge Bases: The paper primarily deals with "flat" knowledge bases (where all information is treated equally in terms of source reliability). Future work could explore how these selection principles can be integrated with prioritized belief revision frameworks, where information sources have different levels of trust.
  • Computational Complexity: While the theoretical framework is established, the computational complexity of finding MCSs and applying these selection criteria in practice for large knowledge bases remains an area for further investigation.

Summary updated

BibTeX
@inproceedings{konieczny2019rational,
  author = {Sébastien Konieczny and Pierre Marquis and Srdjan Vesic},
  title = {{Rational Inference Relations from Maximal Consistent Subsets Selection}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.24963/ijcai.2019/242},
}
Figure