Merging Stratified Knowledge Bases under Constraints

Guilin Qi, Weiru Liu, David A. BellAAAI 2006

Introduction

In the field of Artificial Intelligence, belief merging is the critical process of fusing information from multiple sources into a single, coherent knowledge base. While classical logic effectively handles "flat" knowledge bases, real-world information is frequently stratified, meaning some facts are more reliable or important than others. A significant hurdle in existing merging methods is the "commensurability assumption"—the requirement that all sources use a common scale to rank their beliefs. This paper introduces the $\Delta^{PLMIN}$ family of operators, which allows for the merging of prioritized knowledge bases without forcing them into a global score.

The $\Delta^{PLMIN}$ Merging Framework

The authors propose a model-theoretic approach that focuses on the meaning of formulas rather than their syntactic structure. The merging process follows three main steps:

  1. Stratifying Possible Worlds: For each knowledge base, the set of all possible worlds (interpretations) is ranked based on an ordering strategy such as Best-out, Maxsat, or Leximin. In illustrative examples, these worlds $\omega$ are represented as binary strings.
  2. Creating Priority Lists: Every possible world is assigned a vector $\vec{l}_E(\omega)$ representing its priority level across the different knowledge bases.
  3. Lexicographical Merging: The operator identifies worlds that satisfy the integrity constraints and selects those that are minimal according to a lexicographical comparison of their priority vectors.
Table 1: Mapping possible worlds to priority vectors across three knowledge bases.

Key Insights and Strategy Flexibility

A primary contribution of this work is the removal of the commensurability barrier. By using lexicographical ordering on priority levels, the system respects the internal rankings of each source. Furthermore, the framework is highly flexible, allowing for "hybrid" merging where different agents use different internal ranking strategies (e.g., distance-based vs. formula-based).

Table 2: Priority vectors under a different ordering strategy for the same knowledge bases.

As shown in the comparison between Table 1 and Table 2, changing the underlying strategy for a knowledge base (such as $K_2$) alters the resulting priority vectors, demonstrating the framework's adaptability. This model-theoretic grounding ensures that the merge result is robust, even when individual knowledge bases are internally inconsistent—a common occurrence in real-world data fusion.

Postulate Satisfaction and Complexity

The authors prove that $\Delta^{PLMIN}$ generalizes classical merging operators for flat knowledge bases and satisfies a broad set of logical requirements known as "IC postulates." These postulates ensure that the merging process is fair, consistent, and independent of the syntactic representation of the information.

In terms of computational complexity, the decision problem for merging is found to be $\Theta^p_2$-complete. While more complex than standard SAT-solving, this level of complexity is relatively efficient within the context of non-monotonic reasoning tasks, especially considering the expressive power of the framework.

Conclusion

The $\Delta^{PLMIN}$ family of operators provides a robust and flexible solution for merging prioritized information from diverse sources. By allowing for independent internal priority structures and ensuring semantic consistency, this framework advances the state of the art in multi-agent knowledge representation and reasoning.

Summary updated

BibTeX
@inproceedings{qi2006merging,
  author = {Guilin Qi and Weiru Liu and David A. Bell},
  title = {{Merging Stratified Knowledge Bases under Constraints}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2006},
}
Figure