# Revising possibilistic knowledge bases using FH-conditioning: -Extended abstract

Omar Et-targuy, Ahlame Begdouri, Carole Delenne, Salem Benferhat

► To cite this version:

Omar Et-targuy, Ahlame Begdouri, Carole Delenne, Salem Benferhat. Revising possibilistic knowledge bases using FH-conditioning: -Extended abstract. Journées Francophones sur les Réseaux Bayésiens et les Modèles Graphiques Probabilistes, Jun 2023, Nantes (France), France. hal-04969562

HAL Id: hal-04969562

https://hal.science/hal-04969562v1

Submitted on 27 Feb 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Revising possibilistic knowledge bases using FH-conditioning:
– Extended abstract –

Omar Et-Targuy¹,²,³,⁴, Ahlame Begdouri², Salem Benferhat¹, Carole Delenne³,⁴

¹ CRIL, CNRS UMR 8188, University of Artois, France.

² Université Sidi Mohamed Ben Abdellah (USMBA), Fez, Morocco.

³ HSM, University of Montpellier, CNRS, IRD, Montpellier, France

⁴ Inria, Team Lemon, Montpellier, France

Belief revision [5] is an important problem in knowledge representation and artificial intelligence. It consists in revising plausible beliefs of an agent in the light of new information, often considered to be completely certain and reliable. If the new information to be inserted is consistent with the a priori beliefs, then the revision comes down to simply add this information to the agent's beliefs. The problem arises when this new information contradicts a priori beliefs. In this case, the agent must decide which information to ignore or replace with other weaker, less informative and less precise information.

Within the framework of uncertainty theories, the process of belief revision is materialized by the notion of conditioning. Agents' beliefs are modeled by uncertainty distributions $\mu$ (probability distribution, mass function, possibility distribution, ordinal conditional function, etc.) which associate to each element of the universe of discourse (in our context, a set of propositional logic interpretations) a degree of plausibility.

In probability theory, Bayesian conditioning is widely used, especially in Bayesian networks, for the propagation of beliefs in the presence of new observations.

For belief functions, Dempster's rule of conditioning remains the reference operator for the revision of uncertain information.

In possibility theory, conditioning is defined in two different approaches, depending on how the uncertainty degrees are interpreted. The first definition is so-called product-based possibilistic conditioning which makes full use of the uncertainty interval [0, 1]. The second definition is called min-based possibilistic conditioning where only the relative order between uncertain information matters.

These standard conditioning operators (probabilistic Bayesian conditioning, Dempster's rule of conditioning, possibilistic min-based and product-based conditionings) have been very well studied in the literature, both from representational and computational points of view.

There is, however, another form of conditioning, called Fagin and Halpern conditioning (which we will note in the following FH-conditioning), which is little considered in the literature, in particular from a computational point of view. This conditioning was introduced in the framework of belief functions theory in [4]. FH-conditioning allows to obtain a better characterization of the conditioned belief function than that of Dempster in the context where the belief functions are interpreted as lower and upper probabilities induced by a particular family of probability distributions (see also [1] for a discussion whether FH-conditioning should be considered as a revision or prediction operator). Besides, still
within the framework of the theory of belief functions, other theoretical justifications of FH-conditioning have been proposed in [2, 6] and recent work have illustrated their use for object detection in the context of autonomous vehicles [7].

In the context of possibility theory, FH-conditioning has been approached only from a semantic point of view [3] and there is no work (to the best of our knowledge) that treats this conditioning from the point of view of syntactic representation of uncertain beliefs.

In this work, we are interested in addressing this shortcoming by studying FH-conditioning in a framework where uncertain beliefs are represented by sets of weighted propositional logical formulas. In possibility theory, the available uncertain information is represented by what is called a possibilistic belief base that we will denote by $\Sigma$. This weighted belief base is composed of a set of pairs $(\phi_i, \alpha_i)$ where $\phi_i$ is a propositional logic formula, and $\alpha_i$ is a minimum degree of certainty (more precisely a degree of necessity in the sense of the possibility theory) associated with $\phi_i$.

The question considered in this presentation is how to revise a possibilistic weighted base $\Sigma$, in the light of a new totally certain information (denoted by $(\psi, 1)$, where $\psi$ is a propositional logic formula) while being in full agreement with the possibilistic semantics of FH-conditioning. To achieve this goal, we first propose an equivalent reformulation of the semantic definition of FH-conditioning as a sequence of three transformation operations of possibility distributions. For each of these semantic transformation operations, we propose their equivalent characterisation on the weighted belief bases. At the end of the third operation, we show that the final obtained belief base corresponds exactly to the application of FH-conditioning on weighted belief bases. We provide the spatial and temporal complexity analysis of the syntactic computation of FH-conditioning. We show that the size of the revised belief base is linear with respect to the size of the initial base. Moreover, the complexity of computing the FH-conditioning, from the weighted belief bases, comes down to the complexity of computing the degree of certainty of the new information $\psi$ from the initial base $\Sigma$, which is done in $\log_2(n)$ calls to a satisfiability test of a set of propositional formulas (SAT).

**Acknowledgements:** This research has received support from the European Union's Horizon research and innovation programme under the MSCA-SE (Marie Skłodowska-Curie Actions Staff Exchange) grant agreement 101086252; Call: HORIZON-MSCA-2021-SE-01; Project title: STARWARS (STormwAteR and WastewAteR networkS heterogeneous data AI-driven management).

This research has also received support from the French national project ANR (Agence Nationale de la Recherche) CROQUIS (Collecte, représentation, complétion, fusion et interrogation de données hétérogènes et incertaines de réseaux d'eaux urbains), grant number ANR-21-CE23-0004.

## References

[1] Thierry Denœux, Didier Dubois, and Henri Prade. *Representations of Uncertainty in AI: Beyond Probability and Possibility*, pages 119–150. Springer International Publishing, Cham, 2020.

[2] Jean Dezert, Albena Tchamova, and Deqiang Han. Total belief theorem and conditional belief functions. *Int. J. Intell. Syst.*, 33(12):2314–2340, 2018.
[3] Didier Dubois and Henri Prade. Bayesian conditioning in possibility theory. *Fuzzy sets and systems*, 92(2):223–240, 1997.

[4] Ronald Fagin and Joseph Y. Halpern. A new approach to updating beliefs. In Piero P. Bonissone, Max Henrion, Laveen N. Kanal, and John F. Lemmer, editors, *UAI '90: Proceedings of the Sixth Annual Conference on Uncertainty in Artificial Intelligence, MIT, Cambridge, MA, USA, July 27-29, 1990*, pages 347–374. Elsevier, 1990.

[5] Peter Gärdenfors. *Belief Revision*. Cambridge Tracts in Theoretical Computer Science. Cambridge University Press, 1992.

[6] Ronald Meester and Timber Kerkvliet. A new look at conditional probability with belief functions. *Statistica neerlandica*, 73(2):274–291, 2019.

[7] Lalintha G. Polpitiya, Kamal Premaratne, Manohar N. Murthi, Stephen J. Murrell, and Dilip Sarkar. Efficient computation of conditionals in the dempster-shafer belief theoretic framework. *IEEE Trans. Cybern.*, 52(5):2931–2941, 2022.