TL;DR
This paper introduces a novel revision-based approach to handle conflicting information in stratified knowledge bases. By generalizing the Disjunctive Maxi-Adjustment (DMA) method, the authors propose two versions of their approach, one using model-based revision operators and the other using formula-based operators, offering more computationally efficient alternatives to DMA.
What Problem Does This Paper Address?
In artificial intelligence, particularly in areas like knowledge integration and belief revision, dealing with inconsistent information is a fundamental challenge. Knowledge bases are often structured with priorities, forming "stratified knowledge bases," where some information is considered more reliable than others. When new information is introduced, it can conflict with existing beliefs, leading to inconsistencies. Traditional methods like coherence-based approaches select consistent subsets, while "adjustment" methods aim to resolve conflicts by weakening or removing information. The Disjunctive Maxi-Adjustment (DMA) approach is a prominent method for this, but it can be computationally expensive due to the need to identify conflicts. This paper aims to provide more efficient alternatives to DMA for resolving conflicts in stratified knowledge bases.
Methods
The core contribution is a revision-based approach that generalizes the DMA method. Instead of directly applying DMA, the authors propose to handle inconsistencies by iteratively revising information stratum by stratum.
The approach has two main versions, depending on the type of revision operator used:
- Model-based Revision Operator: This version uses operators like Dalal's revision operator. A key advantage here is that the approach is independent of the syntactic form of the formulas within each stratum, focusing instead on their models. This version aims to capture a notion of "minimal change."
- Formula-based Revision Operator: This version utilizes operators like the cardinality-maximal based revision operator. When this operator is chosen, the proposed approach becomes equivalent to the DMA approach.
The authors also analyze the computational complexity of their proposed methods, suggesting they are more tractable than the original DMA.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Generalizing DMA: The paper successfully generalizes the DMA approach by framing conflict resolution as a revision process across strata, offering flexibility in how conflicts are handled.
- Model vs. Formula-Based Revision: The distinction between model-based and formula-based revision operators leads to two distinct versions of the proposed approach, each with its own properties and advantages (syntactic independence vs. equivalence to DMA).
- Computational Efficiency: A significant insight is that both proposed revision-based approaches are computationally easier than the original DMA, which is crucial for practical applications.
- Minimal Change: The model-based version, using Dalal's operator, is shown to capture a notion of minimal change, a desirable property in belief revision.
- Stratified Knowledge Bases as a Target: The work specifically targets stratified knowledge bases, acknowledging their importance in representing prioritized information and the unique challenges they present for inconsistency handling.
Key Results
The paper presents two main revision-based algorithms:
- Revision-based Algorithm I (Model-based): This algorithm, when using Dalal's revision operator, is shown to be equivalent to a generalized Dalal's revision operator on stratified knowledge bases, capturing minimal change and being computationally efficient.
- Revision-based Algorithm II (Formula-based): This algorithm, when using the cardinality-maximizing based revision operator (CM-revision), is proven to be equivalent to the Disjunctive Maxi-Adjustment (DMA) approach. Furthermore, it is shown to be computationally less demanding than DMA and, in some cases, can produce knowledge bases with fewer formulas.
The paper also provides theoretical results and propositions demonstrating the properties of these operators and their relationships to existing methods like DMA and lexicographical systems.
Limitations and Future Work
- Choice of Revision Operator: The authors acknowledge that they only considered two specific revision operators (Dalal's and cardinality-maximal based). A key future direction is to explore how to choose an appropriate revision operator from a wider range of options, potentially by comparing their complexity and the resulting size of the revised knowledge bases.
- Generalization of CMR vs. DMA: While the paper shows that the CMR approach can generate smaller knowledge bases than DMA in some cases, it notes that this conclusion doesn't hold universally. Investigating this further to determine if CMR is generally more parsimonious than DMA is suggested.
- Application to Belief Revision: The proposed methods are presented as applicable to belief revision and knowledge integration, especially for stratified and inconsistent knowledge bases. However, the paper suggests that further work is needed to fully explore these applications.
Summary updated