Gestion des connaissances pour l’aide à la décision/

Knowledge management for decision aid

Souhila KACI

Partie 3/Part 3
Fusion d’informations/Information merging

1/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Fusion d’informations

2/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Outline

Fusion de bases propositionnelles sans priorité

Fusion de bases propositionnelles avec priorité implicite

Fusion de bases propositionnelles avec priorité explicite

3/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Outline

Fusion de bases propositionnelles sans priorité

Fusion de bases propositionnelles avec priorité implicite

Fusion de bases propositionnelles avec priorité explicite

4/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Fusion de bases propositionnelles sans priorité

Union des bases

Le résultat de l’union est souvent un ensemble incohérent

On applique les méthodes de gestion de l’incohérence vues

précédemment (argumentation, SMC, etc)

5/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Outline

Fusion de bases propositionnelles sans priorité

Fusion de bases propositionnelles avec priorité implicite

Fusion de bases propositionnelles avec priorité explicite

6/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Fusion de bases propositionnelles avec priorité implicite (1)

Les informations sont codées en logique propositionnelle

Aucune relation d’ordre n’est associée à ces informations

Une relation d’ordre implicite entre les informations est

calculée

Des opérateurs d’agrégation sont définis sur la base de cette

relation d’ordre

L’idée...
Mesurer la proximité des interprétations (outcomes) par rapport
aux informations, en se basant pour cela sur le calcul de distances.

7/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Fusion de bases propositionnelles avec priorité implicite (2)

Processus de fusion – Trois étapes :

1 Etape 1 : Calculer la proximité de chaque interprétation des
bases à fusionner. On calcule une distance locale. Un pré-ordre
total sur Ω est calculé par rapport à chacune des bases.

2 Etape 2 : Calculer un pré-ordre sur Ω par rapport à l’ensemble

des bases à fusionner. Il est obtenu au moyen d’une distance
globale; résultat de l’agrégation des distances locales.

3 Etape 3 : Calculer le résultat de la fusion.

8/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Fusion de bases propositionnelles avec priorité implicite (3)

Example 1
Un professeur demande à ses trois étudiants lesquels parmi les
langages suivants SQL (noté s), O2 (noté o) et Datalog (noté d)
ils souhaiteraient étudier.
Le premier étudiant désire étudier seulement SQL ou O2 mais
pas Datalog : K1 = (s ∨ o) ∧ ¬d.

Le deuxième ne veut pas étudier SQL et préfère étudier soit O2

soit Datalog mais pas les deux à la fois :
K2 = (¬s ∧ d ∧ ¬o) ∨ (¬s ∧ ¬d ∧ o).

Le troisième veut étudier les trois langages : K3 = (s ∧ d ∧ o).

9/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ Kn

 Etape 1 : Calcul des distances locales (1)

Soit E = {K1 , · · · , Kn } (n ≥ 1) un multi-ensemble de n bases

propositionnelles cohérentes (non nécessairement différentes) à
fusionner.
La distance locale est la distance entre une interprétation ω et
une base Ki . Elle est notée d(ω, Ki ).
Elle est basée sur la distance entre deux interprétations ω et
ω 0 , appellée distance de Hamming et notée H(ω, ω 0 ).
H(ω, ω 0 ) = nombre de littéraux différents entre ω et ω 0 .
d(ω, Ki ) = minω0 |=Ki H(ω, ω 0 ).
La distance locale permet de générer un pré-ordre sur Ω par rapport
à chacune des bases à fusionner même si ces dernières ne sont pas
stratifiées.
∀ω, ω 0 ∈ Ω, ω K ω 0 ssi d(ω, K ) ≤ d(ω 0 , K ).

10/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Etape 1 : Calcul des distances locales (2)

Intuitivement, si l’agent exprime des préférences alors ces dernières

sont vues comme un ensemble de sous-buts indépendants à
satisfaire. Une interprétation est considérée comme totalement
satisfaisante si elle satisfait tous les sous-buts, et entre deux
interprétations qui ne satisfont pas tous les sous-buts, l’une est
considérée plus satisfaisante que l’autre si elle satisfait plus de
sous-buts.

11/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Etape 1 : Calcul des distances locales (3)
Considérons le premier étudiant (étudier seulement SQL ou O2
mais pas Datalog).
Le professeur suppose que l’étudiant exprime deux buts
indépendants :
vouloir apprendre SQL, ou O2 , ou les deux (s ∨ o),
et ne pas vouloir apprendre Datalog (¬d).
A partir de ces buts, on ordonne les différentes situations possibles
comme suit :
1 les situations s¬do, ¬s¬do et s¬d¬o sont préférées
puisqu’elles satisfont les deux sous-buts ¬d et s ∨ o,
2 les situations ¬s¬d¬o, sdo, sd¬o et ¬sdo sont moins
préférées que les précédentes car elles satisfont un seul
sous-but,
3 et enfin la situation ¬sd¬o est la moins préférée puisqu’elle
falsifie les deux sous-buts.
12/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K
 Etape 1 : Calcul des distances locales (4)
Exemple 1 (suite)

ω d(ω, K1 ) d(ω, K2 ) d(ω, K3 )

ω0 : ¬s¬d¬o 1 1 3
ω1 : ¬s¬do 0 0 2
ω2 : ¬sd¬o 2 0 2
ω3 : ¬sdo 1 1 1
ω4 : s¬d¬o 0 2 2
ω5 : s¬do 0 1 1
ω6 : sd¬o 1 1 1
ω7 : sdo 1 2 0

13/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Etape 2 : Calcul des distances globales (1)

Définir une fonction qui, à partir des distances locales, calcule une
distance globale obtenue par l’agrégation des distances locales avec
un opérateur d’agrégation, noté ⊕. Cette distance est notée
d⊕ (ω, E ).
Bases d’inégales importances
Quand les bases n’ont pas la même importance, une affectation de
poids est utilisée qui consiste à attribuer des poids aux bases,
définissant ainsi leur niveau d’importance.
dWS (ω, E ) = ni=1 ki ∗ d(ω, Ki ),
P
où les ki (i = 1, · · · , n) sont des entiers positifs associés aux bases
Ki représentant leur niveau P d’importance. Ce n’est pas la somme
pondérée habituelle où ni=1 ki = 1.

∀ω, ω 0 ∈ Ω, ω WS
E ω 0 ssi dWS (ω, E ) ≤ dWS (ω 0 , E ).

14/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Etape 2 : Calcul des distances globales (2)

Tendance majoritaire
Satisfaire la majorité des bases.
Pn
dP (ω, E ) = i=1 d(ω, Ki ).
P
∀ω, ω 0 ∈ Ω, ω E ω 0 ssi dP (ω, E ) ≤ dP (ω 0 , E ).

Opérateur égalitariste idempotent

Satisfaire toutes les bases.

dMAX (ω, E ) = maxi=1,··· ,n d(ω, Ki ).

∀ω, ω 0 ∈ Ω, ω MAX
E ω 0 ssi dMAX (ω, E ) ≤ dMAX (ω 0 , E ).

15/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Etape 2 : Calcul des distances globales (3)

Opérateur égalitariste basé sur le Lexi-max (ou MAX généralisé)

Associer à chaque interprétation un vecteur ordonné (ordre
décroissant) des distances locales. Ce vecteur est noté
dGMAX (ω, E ). Ensuite, on applique l’ordre lexicographique sur les
vecteurs associés aux interprétations.

∀ω, ω 0 ∈ Ω, ω GMAX
E ω 0 ssi dGMAX (ω, E ) ≤ dGMAX (ω 0 , E ).

Opérateur prudent idempotent

dMIN (ω, E ) = mini=1,··· ,n d(ω, Ki ).

∀ω, ω 0 ∈ Ω, ω MIN
E ω 0 ssi dMIN (ω, E ) ≤ dMIN (ω 0 , E ).

16/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Etape 3 : Calcul du résultat de la fusion

Le but de l’étape précédente était de calculer un pré-ordre ⊕ E sur

Ω globalement par rapport à toutes les bases. Les interprétations
préférées sont celles qui se rapprochent le plus de l’ensemble de
toutes les bases. Ces interprétations sont les préférées par rapport à
⊕E . Le résultat de la fusion, noté Merge⊕ (E ), est l’ensemble de
ces interprétations.

Merge⊕ (E ) = max(Ω, ⊕
E ).

17/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Exemple (suite)

k1 = 1, k2 = 3, k3 = 1 pour ⊕ = WS.
P
ω d1 d2 d3 WS MAX MIN GMAX
ω0 1 1 3 5 7 3 1 (3,1,1)
ω1 0 0 2 2 2 2 0 (2,0,0)
ω2 2 0 2 4 4 2 0 (2,2,0)
ω3 1 1 1 3 5 1 1 (1,1,1)
ω4 0 2 2 4 8 2 0 (2,2,0)
ω5 0 1 1 2 4 1 0 (1,1,0)
ω6 1 1 1 3 5 1 1 (1,1,1)
ω7 1 2 0 3 7 2 0 (2,1,0)

18/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Analyse de la fusion à base de la distance de Hamming
Problème
L’associativité n’est pas garantie même si l’opérateur d’agrégation
est associatif.
Dans notre exemple, MergeP ({K1 , K2 , K3 }) 6= MergeP ({K 0 , K3 }),
avec K 0 = MergeP ({K1 , K2 }).

ω d(ω, K1 ) d(ω, K2 ) dP (ω, {K1 , K2 })

ω0 : ¬s¬d¬o 1 1 2
ω1 : ¬s¬do 0 0 0
ω2 : ¬sd¬o 2 0 2
ω3 : ¬sdo 1 1 2
ω4 : s¬d¬o 0 2 2
ω5 : s¬do 0 1 1
ω6 : sd¬o 1 1 2
ω7 : sdo 1 2 3

19/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Distance locale par rapport à K 0

ω d(ω, K 0 )
ω0 : ¬s¬d¬o 1
ω1 : ¬s¬do 0
ω2 : ¬sd¬o 2
ω3 : ¬sdo 1
ω4 : s¬d¬o 2
ω5 : s¬do 1
ω6 : sd¬o 3
ω7 : sdo 2

20/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Fusion de K 0 et K3

ω d(ω, K 0 ) d(ω, K3 ) dP (ω, {K 0 , K3 })

ω0 : ¬s¬d¬o 1 3 4
ω1 : ¬s¬do 0 2 2
ω2 : ¬sd¬o 2 2 4
ω3 : ¬sdo 1 1 2
ω4 : s¬d¬o 2 2 4
ω5 : s¬do 1 1 2
ω6 : sd¬o 3 1 4
ω7 : sdo 2 0 2

21/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Outline

Fusion de bases propositionnelles sans priorité

Fusion de bases propositionnelles avec priorité implicite

Fusion de bases propositionnelles avec priorité explicite

22/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Fusion en logique possibiliste

Input : B = {B1 , · · · , Bn }, un opérateur d’agrégation ⊕

Output : B⊕ = {(Dj , 1 − ⊕(x1 , · · · , xn )) : j = 1, · · · , n}, où

Dj sont les disjonctions de taille j entre les formules φi prises
des différentes bases Bi (i = 1, · · · , n) et xi est égal à 1 − ai si
φi ∈ Dj . Il est égal à 1 sinon.

Cas de fusion de deux bases B1 = {(φi , ai )} et B2 = {(ψj , bj )}

Le résultat de la fusion est composé
des bases initiales, avec cependant de nouveaux poids :
{(φi , 1 − ⊕(1 − ai , 1)) : (φi , ai ) ∈ B1 }∪
{(ψj , 1 − ⊕(1, 1 − bj )) : (ψj , bj ) ∈ B2 },
et des informations communes à B1 et B2 définies par :
{(φi ∨ ψj , 1 − ⊕(1 − ai , 1 − bj )) : (φi , ai ) ∈ B1 , (ψj , bj ) ∈ B2 }.

23/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Exemples de fusion en logique possibiliste

Bmin = B1 ∪ B2

Bmax = {(φi ∨ ψj , min(ai , bj ))|(φi , ai ) ∈ B1 , (ψj , bj ) ∈ B2 }

B∗ = B1 ∪ B2 ∪ {(φi ∨ ψj , ai + bj − ai ∗ bj ) : (φi , ai ) ∈
B1 , (ψj , bj ) ∈ B2 }

Le résultat de la fusion est associatif lorsque l’opérateur

d’agrégation est associatif.

24/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Propriétés des opérateurs de fusion

Opérateur min
Le résultat de la fusion peut être incohérent même si chacune
des bases à fusionner est cohérente.
Pas de renforcement des informations redondantes.

Opérateur max
Le résultat de la fusion est cohérent dès qu’une des bases à
fusionner est cohérente.
Pas de renforcement des informations redondantes.

Opérateurs *
Le résultat de la fusion peut être incohérent même si chacune
des bases à fusionner est cohérente.
Renforcement des informations redondantes.

25/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Applications de la fusion d’informations

Robotique

Systèmes multi-agents

Décision collective : Fusion de préférences, Agrégation des

jugements

26/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K

 Exercice (1)
Soient c, s et e trois variables propositionnelles qui
représentent respectivement “le chat est dans la salle”,
“la souris est dans la salle”, “la souris est effrayée”.
Soient B1 et B2 deux bases possibilistes décrivant les
observations de deux agents d’un site composé d’une salle,
d’un chat et d’une souris :
B1 = {(¬c ∨ ¬s ∨ e, 1), (¬c, .8), (s, .5)}
B2 = {(¬c ∨ ¬s ∨ e, 1), (¬c, .6), (e, .2)}

Questions
1 Interpréter les observations de chaque agent.

2 Fusionner les deux bases avec les opérateurs vus

précédemment.

3 Quelles sont vos observations ?

27/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K
 Exercice (2)

B1 = {(¬c ∨ ¬s ∨ e, 1), (¬c, .8), (s, .5)}

B2 = {(¬c ∨ ¬s ∨ e, 1), (¬c, .6), (e, .2)}

Bmin = B1 ∪ B2 = {(¬c ∨ ¬s ∨ e, 1), (¬c, .8), (s, .5), (e, .2)}

Bmax = {(¬c ∨ ¬s ∨ e, 1), (¬c, .6), (s ∨ e, .2)}
B∗ = B1 ∪ B2 ∪ {(¬c ∨ ¬s ∨ e, 1), (¬c, .92), (s ∨ e, .6)}
= {(¬c ∨ ¬s ∨ e, 1), (¬c, .92), (s ∨ e, .6), (s, .5), (e, .2)}

28/28 Souhila KACI Gestion des connaissances pour l’aide à la décision/ K