An Inconsistency-Tolerant Approach to Information Merging Based on Proposition Relaxation

Steven Schockaert, Henri PradeAAAI 2010 · OpenReview

Abstract

Inconsistencies between different information sources may arise because of statements that are inaccurate, albeit not completely false. In such scenarios, the most natural way to restore consistency is often to interpret assertions in a more flexible way, i.e. to enlarge (or relax) their meaning. As this process inherently requires extra-logical information about the meaning of atoms, extensions of classical merging operators are needed. In this paper, we introduce syntactic merging operators, based on possibilistic logic, which employ background knowledge about the similarity of atomic propositions to appropriately relax propositional statements.

Introduction

When merging information from multiple, potentially conflicting sources, classical logic-based approaches typically face a binary choice: accept a statement as true or discard it to maintain consistency. This "all-or-nothing" paradigm often leads to the loss of valuable information that is "approximately" correct but technically inconsistent with other data points. For instance, if two sources disagree on a location, standard merging operators might identify a maximal consistent subset and delete the conflicting claims entirely.

This paper proposes a more nuanced alternative: Proposition Relaxation. Instead of deleting conflicting statements, the framework broadens their meaning based on the similarity between atomic propositions until a consistent middle ground is reached. By leveraging background knowledge and possibilistic logic, the authors provide a formal methodology for merging information that is "nearly right" rather than strictly true or false.

The Framework of Proposition Relaxation

The core of the proposed approach is the use of similarity relations to guide the relaxation process. The authors assume the existence of background knowledge—such as a geographic gazetteer or a domain-specific taxonomy—that defines how "atoms" (basic facts) relate to one another.

Similarity Relations and Syntactic Relaxation

The framework defines a nested sequence of sets ($X^0, X^1, \dots, X^k$), where each level represents an increasingly tolerant notion of similarity. This allows for two primary modes of syntactic relaxation:

  1. Conjunctive Normal Form (CNF): Statements are weakened by adding disjuncts. For example, the assertion "John is in Gainesville" might be relaxed to "John is in Gainesville OR John is in a city similar to Gainesville."
  2. Disjunctive Normal Form (DNF): A dual approach is employed where literals that are only "borderline" similar to the original assertion are removed.

This syntactic relaxation is shown to be logically equivalent to the concept of "dilation" in mathematical morphology, providing a robust geometric intuition for these logical operations.

Merging via Possibilistic Logic

To manage the merging process, the authors utilize Possibilistic Logic. Standard knowledge bases are transformed into weighted structures known as N-bases or $\Delta$-bases. In these bases, formulas are assigned weights ($\lambda$) representing their certainty or priority. As a formula is relaxed (weakened), its priority level increases, reflecting the higher certainty that the broader statement is true.

The merging operators function by identifying the highest level of relaxation—the "$\lambda$-cut"—that restores consistency across the merged sources. To ensure the results remain as informative as possible, the authors propose using "preferred subtheories." This allows the system to be "liberal," preserving parts of a source that do not contribute to the conflict while only relaxing the specific components that cause inconsistency.

Key Insights and Theoretical Results

The paper provides several critical contributions to the field of information fusion:

  • Inconsistency as Vagueness: The authors reframe inconsistency not as a sign of falsehood, but as a consequence of statements being overly precise relative to the available certain knowledge.
  • Semantic Characterization: The authors prove that their syntactic relaxation method corresponds exactly to a semantic model where the set of "possible worlds" is expanded based on a similarity metric.
  • Syntax Independence: By utilizing "prime implicates," the framework ensures that the merging process is based on the underlying meaning of the data rather than its specific formatting or syntactic structure.
  • Robust Fallback: If an inconsistency is caused by a fundamental error that cannot be resolved through reasonable relaxation, the system gracefully falls back to standard distance-based merging (e.g., Hamming distance).

Conclusion and Future Work

The proposition relaxation approach is particularly promising for domains where "nearness" is a well-defined concept, such as spatial or temporal reasoning. However, the framework's effectiveness is contingent on the availability of high-quality background knowledge regarding similarities.

Future research directions include addressing the computational complexity associated with calculating prime implicates, which may limit scalability for real-time datasets. Additionally, exploring the impact of transitivity in similarity relations and extending the framework to more complex ontologies remains a priority for further development.

Summary updated

Abstract

Inconsistencies between different information sources may arise because of statements that are inaccurate, albeit not completely false. In such scenarios, the most natural way to restore consistency is often to interpret assertions in a more flexible way, i.e. to enlarge (or relax) their meaning. As this process inherently requires extra-logical information about the meaning of atoms, extensions of classical merging operators are needed. In this paper, we introduce syntactic merging operators, based on possibilistic logic, which employ background knowledge about the similarity of atomic propositions to appropriately relax propositional statements.
BibTeX
@inproceedings{schockaert2010inconsistency,
  author = {Steven Schockaert and Henri Prade},
  title = {{An Inconsistency-Tolerant Approach to Information Merging Based on Proposition Relaxation}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  url = {https://openreview.net/forum?id=BJb1JAgObB},
}
Figure