Diagramme d’influence

sick

not

Harv

Loses’

yes

not

0.95

0.85

0.05

0.15

0.9

0.1

0.02

0.98

03/11/2013

7

03/11/2013

Treat

treat

not

Treat

Cost

Example

Sick

Dry

Sick’

sick

not

treat

not

sick

0.2

0.8

not

Loses

0.01

sick

not

0.99

0.02

0.99

0.01

0.98

Sick’

Dry’

Dry’

dry

not

dry

0.6

0.4

not

0.05

0.95

not

Loses’

not

0.02

0.98

dry

Loses’

yes

not

sick

0.95

0.05

Harv

not

sick

0.9

0.1

0.85

0.15

Example

Sick

Dry

Treat

treat

Cost/Utility

-8000

not

0

Treat

Cost

Loses

Sick’

Dry’

Harv

Harv/Utility

sick

3000

not

20000

Harv

Loses’

8

03/11/2013

Exemple

Est ce qu’il faut le traiter ?

Sick

Dry

Treat

Cost

Loses

Sick’

Dry’

Observer que le

pommier perds ses

feuilles

Harv

Loses’

Exemple du parapluie

Tps

Prev.

U

Parapluie

9

Exemple Forage Pétrolier

O

R

D

U

T

C

Graphical decisions tools

Modèle graphique de décision: outil puissant pour la modélisation et

la

structuration des problèmes de décision sous incertitude.

Diagrammes d’influence

(Howard and Matheson, 1981)

outil de modélisation

(Représentation du problème de décision)

Outil d’analyse

(trouver une solution pour le

problème de décision en utilisant

un algorithme d’évaluation)

03/11/2013

10

Evaluation des diagrammes d’influence

Générer la meilleure stratégie

Calculer l’utilité espérée la plus forte + Identifier la politique optimale

Une stratégie est un ensemble de politiques (de règles de décision).

Une règle de décision relative à un nœud de décision Di est un mapping:

domaine(Pa(Di)) (cid:2) domaine(Di).

Diagramme d’influence

vs Arbre de décision de Raiffa

03/11/2013

11

Règle de décision

(cid:3) Une règle de décision attribut une valeur à la

variable de décision pour chaque affectation

des variables de son passé qui l’influence.

(cid:3) Une règle de décision pour D1 pourrait être:

(cid:4) D1 = α.

(cid:3) Une règle de décision pour D2 pourrait être:

(cid:4) D2 = γ|D1 = α

(cid:4) D2 = δ|D1 = β

Evaluation des diagrammes d’influence

Plusieurs algorithmes pour évaluer un diagramme d’influence

On peut les diviser en algorithmes directs et algorithmes indirects.

Ceux qui travaillent directement sur les DIs et ceux qui transforment le

DI en une structure secondaire.

Direct

Indirect

• Olmsted (1983)

• Shachter (1986)

• Shenoy (1992)

• Ndilikilikesha (1994)

• Cooper (1988)
• Shachter and Peot (1992)
• Zhang (1998)
• Rina Dechter (2000)
• Xiang (2001)
• Sanchez et Druzdzel (2004)
• Mark Crowley (2004)

RB:

structure

secondaire

03/11/2013

12

évaluation directe des diagrammes d’influence (Shachter,

1986)

Une séquence de transformations sur le diagramme en maintenant la

faisabilité et ne modifie pas la politique optimale ou la valeur espérée

maximale

Une réduction en préservant la valeur

Deux types de réductions:

1) Enlever des nœuds.

2) Inverser les arcs.

Principe:

L’algorithme enlève les nœuds du diagramme jusqu’à ce que

uniquement le nœud de valeur (utilité) reste.

Elimination des nœuds

• Elimination des nœuds stériles

Un nœud stériles=Un nœud qui n’a pas de successeur

• Elimination des nœuds de chance

Si un nœud de chance a comme successeur unique le nœud d’utilité il sera

éliminé et tous ses prédécesseurs seront les prédécesseurs du nœud d’utilité

i

v

(cid:2) Pred new (v) = Pred old (v) U Pred (i)\{i}

v

26

03/11/2013

13

Elimination des nœuds

• Elimination des nœuds de décision

Le nœud de décision doit être un prédécesseur direct du nœud d’utilité et tous les

autres prédécesseurs du nœud d’utilité sont des prédécesseurs de ce nœud

i

v

v

(cid:2) Pred new (v) = Pred old (v) \{i}

Inversion des arcs

•On ne peut pas inverser des arcs informationnels (cid:2) ils traduisent

une précédence temporelle

•On inverse seulement les arcs conditionnels entre les nœuds de chance

•Si on a un arc ( i , j ) entre deux nœuds i et j et s’il n’existe pas un autre

chemin entre i et j cet arc peut être remplacé par ( j , i )

•Chaque nœud hérite tous les prédécesseurs conditionnels de l’autre

i

j

i

j

(cid:2) Pred new (j) = Pred old (j) U Pred old (i)\{i}

v

27

28

03/11/2013

14

Evaluation directe du diagramme d’influence(DI)

Algorithme

Répéter tant que Pred(v) ≠ Ø

•Éliminer les nœuds stériles

•S’il existe un nœud de chance qu’ on peut éliminer (cid:2) on l’élimine

•Sinon s’il existe un nœud de décision qu’ on peut éliminer (cid:2) on

l’élimine et on élimine aussi les éventuels nœuds stériles

•Sinon on cherche un arc à inverser

fin

Mise à jour:

(cid:4) des tables conditionnelles

(cid:4) des utilités.

Combinaison (Produit)

Marginalisation (Somme)

29

Exemple : Problème du diagnostic médical (3)

Première étape:

T

1. Inverser arc (D,P)

2. Calculer P(D|P)

T

S

P

D

S

U

D

P

U

03/11/2013

15

Calcul après l’inversion de l’arc DP

DP

δ=P(D)

p

=P(P|D)

(

d ˜

)p

(

d

) { }

fl P

p

=

p

d

(

p

)

{ }

fl P

)

p

=

d

1

1

d

(

TT

0.1

0.8

0.08

FT

0.9

0.15

0.135

0.215

0.3721

0.6279

TF

0.1

0.2

0.02

0.785

0.0255

FF

0.9

0.85

0.765

0.9745

Exemple : Problème du diagnostic médical (3)

Le nœud D a pour

successeur unique le

nœud de valeur U:

1. Eliminer D

2. Calculer U1

T

D

S

P

U1

T

S

P

U

03/11/2013

16

˜

˜

˜

03/11/2013

}

=

U

1

Calcul après l’élimination du nœud D

T P D

T T T

T T F

T F T

T F F

F T T

F T F

F F F

F F F

U

10

6

8

4

0

2

1

10

δ1

0.3721

0.6279

0.0255

0.9745

0.3721

0.6279

0.0255

0.9745

)

(

U

d

) {

PT

,

1

7.4884

(

˜U

d

1

3.7209

3.7674

0.2038

3.8981

0

1.2558

0.0255

9.7452

4.1019

1.2558

9.7707

Exemple : Problème du diagnostic médical (3)

T

S

P

U1

T

S

1. Inverser l’arc (P,S)

2. Calculer P(P|S)

P

U1

17

˜

fl

Calcul après l’inversion de l’arc

PS

p

1

σ

(

p

1

)d

p

(

1

s

)

{ }

S

=

s

1

(

p

(

p

1

1

s

)

s

)

{ }

S

=

p

2

TT

0.215

0.7

0.1505

T

F

0.785

0.2

0.157

F

T

0.215

0.3

.0645

F

F

0.785

0.8

0.628

0.3075

0.6925

0.4894

0.5106

0.931

0.9069

1. Supprimer le nœud P

2. Calculer U2

T

T

S

P

U1

S

U2

03/11/2013

18

˜

fl

˜

˜

fl

˜

Calcul après l’élimination du nœud P

S

T

T

T

T

F

F

F

F

T

T

T

F

F

T

T

F

F

P

T

F

T

F

T

F

T

F

U1

7.488

4.101

1.255

9.770

7.488

4.101

1.255

9.770

p

2

0.489

0.510

0.489

0.510

0.093

0.906

0.093

0.906

(

˜U

1

p

)

2

(

U

1

) {

TS

,

}

=

p

2

U

2

3.665

2.094

0.614

4.988

0.697

3.719

0.117

8.860

5.759

5.603

4.417

8.978

T

Supprimer le

Noeud T

S

U2

S

U3

dernière itération : éliminer le nœud S

U4

03/11/2013

19

˜

fl

03/11/2013

Les calculs numériques après l’élimination des nœuds T et S

TS

U2

T

T

5.759

T

F

5.603

{ }

U S =

2

5.7593

U

F

T

4.417

8.9776

F

F

8.977

Ψ

S

Ps

3

(

U ˜

3

)

sP

(

U

3

fl f

)

P

S

=

U

4

T

F

0.307

1.771

0.692

6.217

7.988

Stratégie optimale: Traiter le patient dans le cas ou il montre le symptôme S.

Avantages des diagrammes d’influence

Représentation compacte :chaque variable n’est

représenté que par un seul nœud (cid:2)organiser

visuellement des modèles complexes

Représentation qualitative : Le DI est un

formalisme qui permet de créer et présenter la

structure qualitative d’un modèle

40

20

fl

˜

Inconvénients

Perte de détails des scénarios

Prétraitement étendu et non nécessaire :

L’utilisation du DI peut exiger une collecte et une

organisation de l’information, étendu et non

nécessaire pour accomplir une représentation

41

Evaluation indirecte des diagrammes d’influence (Cooper, 1988)

Convertir chaque nœud de décision

Di en un nouveau nœud de chance

Calculer P(Di | Pa(Di))

Transformer le nœud de valeur V

en un nouveau nœud de chance

binaire

Calculer P(V | Pa(V))

Transformer DI

en un RB

Calculer le Maximum Expected Utility

(MEU)

Faire de l’inférence

(propagation) dans le RB

03/11/2013

21

Transformation phase

Transformation des nœuds de décision:

équiprobabilité

(

DP

Pa

i

(

D

)

i

)

=

1

(

D

)

i

dom

Transformation des nœuds de valeurs:

VPaTVP

(

(

=

=

))

VP

(

=

VPaF

(

))

=

(

VPaU

(

))

(

VPa

(

max

U

))

U

(

VPa

(

))

(

VPa

(

min

U

min

))

(

VPaU

(

))

(

VPa

(

min

U

))

U

(

VPa

(

))

(

VPa

(

max

U

max

))

Exemple: transformation du nœud de décision

T

S

P

D

U

T

F

F

T

T

S

F

T

F

T

P(T|S)

0.5

0.5

0.5

0.5

03/11/2013

22

-

-

-

-

Example: Value node transformation

T

S

P

D

U

D T P P(U=T|D,T,P)

P(U=F|D,T,P)

F F F

F F T

F T F

F T T

T F F

T F T

T T F

T T T

1

0.1

0.2

0

0.4

0.8

0.6

1

0

0.9

0.8

1

0.6

0.2

0.4

0

Phase de propagation:

Calcul de MEU cas d’une seule décision

Singly ou

multiply connected

Résultat de la propagation

pour Di= dij

UEDMEU

,

i

(

)

(

max

=

U

min

*)

(

(

UEdTvP

ij

)

)

+

=

,

min

max

d

ij

Etant donnée une évidence

(observation)

03/11/2013

23

-

03/11/2013

min

Exemple: calcul du MEU

Résultat de la propagation

pour Di= Dij

MEU

(

ED

,

i

)

=

U

(

max

U

*)

max

d

min

ij

(

(

UEdTvP

ij

)

)

+

=

,

Max(P(U=T|T=T, S=T)= 0.7889

MEU(T=T,S=T)=7.899

Conclusion

• L’avantage des diagrammes d’influence: intuitive et

compact.

• L’évaluation directe utilise des calculs locaux pour

générer la stratégie optimale. Cependant, ca demande

beaucoup de calculs probabiliste.

• L’évaluation indirecte est basée sur la transformation du

DI en un RB . Le problème d’inférence est plus facile à

résoudre.

24

-