On the measure of conflicts: A MUS-Decomposition Based Framework

Saïd Jabbour, Yue Ma, Badran Raddaoui, Lakhdar Sais, Yakoub SalhiarXiv 2014 · OpenReview

TL;DR

This paper introduces a novel framework for measuring inconsistencies in knowledge bases (KBs) by decomposing them into smaller, independent parts. This "MUS-decomposition" allows for parallel analysis of conflicts, making it more efficient and intuitive than existing methods, especially for large KBs. The proposed measure, ID(K), satisfies desirable properties and can be computed using optimization techniques.

What Problem Does This Paper Address?

Handling inconsistencies in large knowledge bases is a significant challenge in Artificial Intelligence. While various methods exist to measure the degree of inconsistency, many struggle with a property called "decomposability" – the ability to understand how inconsistencies in different parts of a KB contribute to the overall problem. Existing approaches often treat inconsistencies holistically, making it difficult to pinpoint specific sources of conflict or to distribute the repair process among multiple experts. This paper aims to address this by proposing a framework that explicitly models and leverages the decomposability of inconsistencies.

Methods

The core of the paper's contribution lies in the concept of MUS-decomposition.

  • MUS (Minimal Unsatisfiable Subset): The authors first define MUSes as the smallest subsets of a KB that are inherently contradictory.
  • MUS-graph: They represent the relationships between MUSes as a graph, where nodes are MUSes and edges connect MUSes that share common formulas.
  • MUS-decomposition: This decomposition partitions the KB into components based on the connected components of the MUS-graph.
  • Distributable MUS-decomposition: A key innovation is the "distributable MUS-decomposition," which further refines the partition to allow for parallel processing. This decomposition aims to create disjoint sets of inconsistencies that can be handled independently by different experts.
  • Distribution Index (ID(K)): Based on this decomposition, they define a new inconsistency measure, ID(K), which essentially counts the number of these independent inconsistent components. This measure is designed to satisfy desirable properties like consistency, monotony, and independent decomposability.
  • Computational Framework: The paper also outlines how to compute ID(K) by formulating it as a Maximum Closed Set Packing (MCSP) problem, which can then be solved using Integer Linear Programming or Min-Cost Satisfiability (MinCostSAT).

Datasets

Not discussed in the paper. The paper focuses on theoretical framework development and uses illustrative examples rather than empirical datasets.

Key Insights and Ideas

  • Decomposability is Crucial: The paper argues that "independent decomposability" is a more intuitive and practical property for inconsistency measures than previously considered notions like pre-decomposability or decomposability. This property allows for the parallel resolution of inconsistencies.
  • MUS-graphs Reveal Structure: Visualizing the relationships between MUSes through graphs provides a powerful way to understand the structure of inconsistencies within a KB.
  • Parallelism for Efficiency: The distributable MUS-decomposition directly enables parallel processing, which is essential for handling large-scale KBs and distributing the workload among multiple experts.
  • ID(K) as a Lower Bound: The proposed measure, ID(K), is shown to be a lower bound for other inconsistency measures that satisfy monotonicity, independent decomposability, and MinInc properties, suggesting its fundamental nature.

Key Results

  • The paper proposes a novel inconsistency measure, ID(K), based on distributable MUS-decomposition.
  • ID(K) satisfies several desirable properties, including Consistency, Monotony, Free Formula Independence, MinInc, and Independent Decomposability.
  • The authors demonstrate that ID(K) is a lower bound for other inconsistency measures satisfying similar properties.
  • The computation of ID(K) is framed as a Maximum Closed Set Packing problem, with encodings provided for Integer Linear Programming and MinCostSAT.
  • Preliminary experiments show that ID(K) values are often much smaller than the total number of MUSes, indicating the effectiveness of the decomposition in identifying independent conflict sets.

Limitations and Future Work

  • Computational Complexity: While the paper provides encodings for computation, the underlying MUS enumeration and MCSP problem can still be computationally intensive for very large KBs.
  • Focus on Parallelism: The primary focus is on enabling parallel resolution. The paper acknowledges that the "labor force" for resolving each component might vary, but the current measure primarily quantifies the number of components.
  • Future Work: The authors suggest studying the lower bound complexity of the measure and exploring its applications. They also hint at further research into more competitive inconsistency handling methodologies than traditional hitting-set based approaches.

Summary updated

Abstract

Measuring inconsistency is viewed as an important issue related to handling inconsistencies. Good measures are supposed to satisfy a set of rational properties. However, defining sound properties is sometimes problematic. In this paper, we emphasize one such property, named Decomposability, rarely discussed in the literature due to its modeling difficulties. To this end, we propose an independent decomposition which is more intuitive than existing proposals. To analyze inconsistency in a more fine-grained way, we introduce a graph representation of a knowledge base and various MUSdecompositions. One particular MUS-decomposition, named distributable MUS-decomposition leads to an interesting partition of inconsistencies in a knowledge base such that multiple experts can check inconsistencies in parallel, which is impossible under existing measures. Such particular MUSdecomposition results in an inconsistency measure that satisfies a number of desired properties. Moreover, we give an upper bound complexity of the measure that can be computed using 0/1 linear programming or Min Cost Satisfiability problems, and conduct preliminary experiments to show its feasibility.
BibTeX
@misc{jabbour2014measure,
  author = {Saïd Jabbour and Yue Ma and Badran Raddaoui and Lakhdar Sais and Yakoub Salhi},
  title = {{On the measure of conflicts: A MUS-Decomposition Based Framework}},
  year = {2014},
  eprint = {1406.0155},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1406.0155},
}
Figure