Compatible-Based Conditioning in Interval-Based Possibilistic Logic

Salem Benferhat, Amélie Levray, Karim Tabia, Vladik KreinovichIJCAI 2015

Introduction

In artificial intelligence and automated reasoning, managing uncertainty is a fundamental challenge. Standard possibilistic logic provides a framework for ranking scenarios using single-point certainty degrees. However, real-world information is often imprecise, stemming from unreliable sources or conflicting expert opinions. Interval-Based Possibilistic Logic (IBPL) addresses this by representing certainty as ranges (e.g., $[0.4, 0.7]$). While IBPL offers greater expressiveness, a critical gap remained: a formal method for conditioning, the process of updating beliefs when new, certain evidence is acquired.

The Challenge of Imprecise Beliefs

Conditioning in a standard setting is well-understood, but applying it to intervals introduces significant theoretical hurdles. A primary concern is whether updating an interval always yields another interval. If the result is a disjoint set of values, the framework's consistency is compromised. Furthermore, a semantic approach—calculating updates for every possible world—is computationally prohibitive.

The Compatible-Based Framework

The authors propose a "Compatible-Based" approach, treating an interval-based distribution as a family of all standard distributions that fall within the specified bounds. To evaluate potential conditioning operators, they established seven desirable properties (IC1-IC7), such as ensuring that counter-models to new evidence become impossible.

Min-Based vs. Product-Based Conditioning

The research compared two primary operators: min-based (qualitative) and product-based (quantitative). A key finding is the failure of min-based conditioning in the interval context. As shown in Figure 3, min-based updates can result in disjoint sets (e.g., $[0.4, 0.7] \cup \{1\}$), breaking the interval structure required by IBPL.

Min-based conditioning can result in non-interval disjoint sets.

In contrast, the authors proved that product-based conditioning is "safe." It consistently preserves the interval structure and satisfies all seven proposed properties, making it the superior choice for IBPL.

Syntactic Characterization and Complexity

To make IBPL practical, the authors developed a syntactic counterpart to semantic conditioning. Instead of performing calculations across all possible worlds, they created an algorithm to update the knowledge base ($IK$) directly. This process utilizes SAT solvers to re-weight formulas based on new evidence $\phi$.

Commutative diagram illustrating the equivalence between syntactic and semantic conditioning.

Crucially, the paper demonstrates complexity parity: updating an interval-based knowledge base is no more computationally expensive than updating a standard one. The complexity remains $O(\log_2(m) \cdot SAT)$, where $m$ is the number of distinct weights. This ensures that the added expressiveness of intervals does not come at a performance cost.

Conclusion

This work provides a rigorous foundation for belief updates in imprecise environments. By proving the robustness of product-based conditioning and providing an efficient syntactic algorithm, the authors have made IBPL a viable tool for real-world reasoning. Future research will explore conditioning under uncertain inputs and the more complex task of belief revision when new information contradicts existing knowledge.

Summary updated

BibTeX
@inproceedings{benferhat2015compatible,
  author = {Salem Benferhat and Amélie Levray and Karim Tabia and Vladik Kreinovich},
  title = {{Compatible-Based Conditioning in Interval-Based Possibilistic Logic}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure