Merging uncertain knowledge bases in a possibilistic logic framework

Salem Benferhat, Claudio SossaiUAI 1998

TL;DR

This paper tackles the challenge of combining uncertain information from multiple sources within a possibilistic logic framework. The authors propose novel syntactical rules for merging these knowledge bases, offering a practical way to integrate diverse, uncertain information into a coherent whole, which is crucial for complex AI systems.

What Problem Does This Paper Address?

In many real-world applications, knowledge about a system or environment comes from various sources, each with its own level of uncertainty. Representing and combining this information effectively is a significant challenge. Traditional approaches often deal with numerical parameters, but this paper focuses on combining logical information that is pervaded with uncertainty, where each logical statement is associated with a degree of certainty. The core problem is how to merge multiple "possibilistic knowledge bases" (sets of weighted logical formulas) into a single, consistent knowledge base that accurately reflects the combined information from all sources. This is essential for making robust decisions in systems that rely on diverse and uncertain inputs.

Methods

The paper introduces two main approaches for merging possibilistic knowledge bases:

  1. Syntactical Combination Rules (Meta-level): The authors first define combination rules at a meta-level, outside the formal logic. These rules operate on the weighted formulas themselves. They propose rules based on t-norms and t-conorms (mathematical operations that generalize min/max for combining uncertainty) to create new weighted formulas that represent the merged information. For instance, combining two formulas $(A \alpha)$ and $(B \beta)$ using a t-conorm dual to a t-norm $\otimes$ results in $(A \vee B \alpha \otimes \beta)$.
  2. Extended Possibilistic Logic (LPL): To integrate these combination rules directly into the logic, the authors propose an extension called LPL. This new logic enriches the language with new connectives that explicitly represent t-norm and t-conorm operations, as well as a new negation. This allows for expressing meta-level statements like "combine knowledge bases $\Sigma_1$ and $\Sigma_2$ using t-norm $\otimes$" directly within the logical language. A proof system for LPL is also presented, which is shown to be sound and complete with respect to its semantics.

Datasets

Not discussed in the paper. The paper uses a hypothetical example inspired by mobile robotics for illustration.

Key Insights and Ideas

  • Bridging Semantics and Syntax: A key contribution is the development of syntactical rules that mirror established semantical combination methods for possibility distributions. This makes the combination process more computationally tractable.
  • Expressing Combination within Logic: The LPL framework is a significant step towards a unified logical system where information fusion is not an external operation but an intrinsic part of the logic itself.
  • T-norms and T-conorms for Fusion: The paper highlights the importance of t-norms and t-conorms as fundamental tools for combining uncertain information, allowing for different strategies based on source reliability and independence.
  • Substructural Logic Principles: The proof system for LPL incorporates principles from substructural logics, acknowledging that the combination of uncertain information might not always allow for standard contraction rules, reflecting the nuanced nature of merging knowledge.
  • Formalizing Robot Localization: The paper demonstrates the practical applicability of its framework through a detailed example of robot localization, showing how uncertain sensor data can be merged to estimate the robot's position.

Key Results

  • The paper provides formal theorems for syntactical combination rules for possibilistic knowledge bases using t-norms and t-conorms.
  • A new logical system (LPL) is introduced, capable of expressing information fusion directly within its language.
  • A sound and complete proof system for LPL is presented.
  • The proposed methods are illustrated with a robotics example, demonstrating how to compute the necessity degree of a conclusion (e.g., robot's location) based on combined uncertain information. In the example, a necessity degree of 0.76 for the robot being at the North-West corner was derived.

Limitations and Future Work

  • T-conorm Limitation in LPL: The paper notes that the LPL framework, as presented, does not directly allow for the combination of bases with t-conorms other than the maximum operator.
  • Predicate Logic Extension: The first method discussed (standard possibilistic logic) does not handle predicate logic, while the second method (LPL) is presented for propositional logic. Extending LPL to first-order logic is mentioned as a future direction.
  • Choice of Schema: The paper acknowledges that the choice of merging schema (e.g., when to apply facts, how to combine bases) depends on the specific application, and different schemas can lead to different results. The example favors a local and recursive merging strategy.
  • Practical Implementation: While the framework is demonstrated with an example, further work on efficient implementation and scalability for real-world, large-scale systems would be beneficial.

Summary updated

BibTeX
@inproceedings{benferhat1998merging,
  author = {Salem Benferhat and Claudio Sossai},
  title = {{Merging uncertain knowledge bases in a possibilistic logic framework}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {1998},
}
Figure