A Model-based Approach for Merging Prioritized Knowledge Bases in Possibilistic Logic

Guilin QiAAAI 2007

Introduction

In the development of multi-agent systems and distributed databases, the ability to synthesize information from multiple, potentially conflicting sources is critical. When these sources provide information with varying degrees of certainty or importance, researchers often turn to possibilistic logic. This framework allows for the attachment of priority weights to logical formulas, creating a structured way to handle uncertainty. However, merging these prioritized knowledge bases remains a significant challenge, particularly when high-level conflicts arise.

This paper introduces a novel iterative approach for merging prioritized knowledge bases. By applying model-based merging operators layer-by-layer according to priority levels, the proposed method successfully avoids the "drowning problem"—a common pitfall where useful lower-priority information is discarded—while maintaining computational efficiency and desirable logical properties.

The Problem: The "Drowning Effect"

Traditional merging methods in prioritized logic often suffer from the drowning problem. This occurs when a conflict at a high priority level causes the system to ignore all information at lower priority levels to restore consistency.

Consider a classic example: a high-priority rule states "Birds fly," but a specific fact at the same or higher level states "Penguins are birds that do not fly." In many traditional systems, if a conflict is detected at this level, the system may "drown out" or discard subsequent lower-priority information (e.g., "Penguins live in the Antarctic") simply because it is associated with a branch of the knowledge base that encountered a contradiction. This leads to a massive loss of potentially useful, non-conflicting data.

Furthermore, existing "formula-based" merging approaches are often computationally expensive, while previous "model-based" approaches frequently resulted in inconsistent knowledge bases that required complex, ad-hoc post-processing.

The Proposed Model-based Merging Approach

The author proposes a framework that operates both semantically (on possible worlds or interpretations) and syntactically (on the formulas themselves) through an iterative process.

1. Iterative Merging (Semantic Level)

Instead of attempting to merge all information simultaneously, the approach sorts all formulas by their priority weights ($a_1 > a_2 > ... > a_l$). The process begins with the highest priority formulas, using a standard model-based merging operator—such as the majority operator ($\Delta^\Sigma$) or the max operator ($\Delta^{max}$)—to identify the "best" models. The algorithm then proceeds to the next priority level, refining the set of models while remaining strictly within the constraints established by the higher-priority levels. This ensures that high-level certainties are respected while lower-level details are used to "fill in the gaps."

2. Syntactical Counterpart

To ensure the method is practical for AI systems, the paper provides a companion algorithm that works directly with weighted formulas. This allows for the computation of the merged knowledge base without requiring the manual inspection of every possible interpretation, which would be computationally infeasible in complex domains.

Key Insights and Logical Properties

The strength of this iterative approach lies in several key logical behaviors:

  • Lexicographic Minimality: The iterative process is equivalent to finding models that are minimal with respect to a lexicographic relation. The system prioritizes satisfying high-level constraints first, but then uses lower-level information to "tie-break" between equally viable high-level models, rather than ignoring the lower levels entirely.
  • Reinforcement Effect: The approach exhibits a "reinforcement effect." If multiple sources provide the same piece of information, even at lower priorities, that information can collectively "win out" over a single conflicting piece of information from another source.
  • Syntax Independence: A crucial property for reliable AI, the results of this merging process do not change if formulas are rewritten in a different but logically equivalent way.

Results and Complexity

The paper validates the approach through formal proofs and complexity analysis rather than empirical datasets. Key findings include:

  • Logical Soundness: The method satisfies several "rationality postulates" for merging, including consistency (if the constraints are consistent, the result is consistent).
  • Computational Efficiency: The complexity of this merging approach is defined as $k \cdot X$, where $k$ is the number of distinct priority levels and $X$ is the complexity of the underlying merging operator. For common operators, the problem sits within the $\Delta^p_2$ or $\Theta^p_2$ levels of the polynomial hierarchy. This indicates that prioritized merging is not significantly harder than standard non-prioritized merging.
  • Information Retention: The method is proven to be more "productive" than standard operators, such as the minimum-based normalized conjunctive operator, meaning it infers a larger (or equal) set of valid conclusions from the same data.

Limitations and Future Work

While the approach is a significant step forward, the author identifies areas for further research. Currently, a complete set of logical postulates that uniquely characterize this specific approach has not yet been defined. Additionally, the work is currently limited to propositional logic; extending these algorithms to more expressive first-order logics—which handle complex objects and relations—remains a major challenge. Finally, the sensitivity of the results to the specific numerical weights assigned to formulas warrants further investigation, as these weights are often subjective in real-world applications.

Summary updated

BibTeX
@inproceedings{qi2007model,
  author = {Guilin Qi},
  title = {{A Model-based Approach for Merging Prioritized Knowledge Bases in Possibilistic Logic}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2007},
}
Figure