Diagramme d’influence

Ce document présente les diagrammes d’influence, un outil graphique puissant pour modéliser et résoudre des problèmes de décision sous incertitude. Destiné aux étudiants et chercheurs en sciences de la décision, il explique la structure, l’évaluation et les applications pratiques des diagrammes d’influence, illustrés par un exemple médical de diagnostic.

Introduction aux diagrammes d’influence

Un diagramme d’influence est un modèle graphique qui représente un problème de décision en intégrant les décisions, les états de nature, les conséquences et les utilités associées. Il sert à la fois d’outil de modélisation, pour structurer visuellement le problème, et d’outil d’analyse, permettant de trouver la meilleure solution à l’aide d’algorithmes d’évaluation.

Les diagrammes d’influence sont une extension des réseaux bayésiens, enrichis par des nœuds de décision et d’utilité. Ils permettent de représenter les relations de causalité, d’information et d’influence entre variables aléatoires et décisions.

Structure et composants des diagrammes d’influence

Un diagramme d’influence est constitué de :

• Nœuds de chance (ou d’état de nature) : variables aléatoires modélisant l’incertitude.
• Nœuds de décision : points où une décision doit être prise, non quantifiés directement.
• Nœuds de valeur (ou d’utilité) : représentent la fonction d’utilité à maximiser.

Ces nœuds sont reliés par des arcs orientés qui traduisent différents types d’influence :

• Influence conditionnelle : un nœud de chance affecte la probabilité d’un autre nœud de chance suivant.
• Influence d’information : une décision est prise en connaissant les variables précédentes.
• Précédence temporelle : une décision antérieure influence la décision courante.

Exemple simplifié de relations entre nœuds

Si A influence B, cela signifie que la probabilité associée à B dépend de la valeur prise par A. Par exemple, dans un contexte médical, la présence d’une maladie (D) influence l’état pathologique (P), qui lui-même influence l’apparition d’un symptôme (S).

Exemple : problème du diagnostic médical

Un médecin doit décider s’il traite un patient suspecté d’une maladie D. La maladie D cause un état pathologique P, qui provoque un symptôme S. Le médecin observe le symptôme S, puis décide de traiter (T) ou non. La fonction d’utilité U dépend de la décision T, de la présence de la maladie D et de l’état pathologique P.

Variable	Valeur	Probabilité
D (maladie)	Vrai (T)	0.1
D (maladie)	Faux (F)	0.9
P(S|P)	S vrai si P vrai	0.8
P(S|P)	S vrai si P faux	0.3

La fonction d’utilité U(P,D,T) est donnée par :

U(P,D,T) =
10  4  1
8   2  6
0  10  0

où chaque valeur correspond à une combinaison des états de P, D et T.

Évaluation des diagrammes d’influence

L’objectif est de générer la stratégie optimale, c’est-à-dire la politique qui maximise l’utilité espérée. Une stratégie est un ensemble de règles de décision, où chaque règle attribue une valeur à une décision en fonction des variables précédentes qui l’influencent.

Règle de décision

Une règle de décision pour un nœud D1 peut être simplement :

D1 = α

Pour un nœud D2 dépendant de D1 :

D2 = γ | D1 = α
D2 = δ | D1 = β

Algorithmes d’évaluation

Deux grandes familles d’algorithmes existent :

• Évaluation directe : travaille directement sur le diagramme d’influence en appliquant des transformations successives.
• Évaluation indirecte : transforme le diagramme d’influence en un réseau bayésien (RB) puis utilise des méthodes d’inférence dans ce réseau.

Évaluation directe (Shachter, 1986)

Cette méthode repose sur une séquence de transformations qui préservent la faisabilité et la valeur optimale :

• Élimination des nœuds stériles : nœuds sans successeurs.
• Élimination des nœuds de chance : si un nœud de chance a pour successeur unique un nœud d’utilité, il peut être supprimé.
• Élimination des nœuds de décision : si un nœud de décision est prédécesseur direct du nœud d’utilité et que tous les autres prédécesseurs du nœud d’utilité sont aussi prédécesseurs de ce nœud de décision, il peut être éliminé.
• Inversion des arcs conditionnels : seuls les arcs entre nœuds de chance peuvent être inversés, à condition qu’il n’existe pas d’autre chemin entre ces nœuds.

Algorithme d’évaluation directe

Répéter tant que Pred(v) ≠ Ø :
  - Éliminer les nœuds stériles
  - Si possible, éliminer un nœud de chance
  - Sinon, éliminer un nœud de décision et les nœuds stériles associés
  - Sinon, inverser un arc conditionnel
Mettre à jour les tables conditionnelles et les utilités.

Exemple d’évaluation directe : diagnostic médical

Première étape : inversion de l’arc (D, P) pour calculer P(D|P).

Deuxième étape : élimination du nœud D, calcul de la nouvelle fonction d’utilité U1.

Troisième étape : inversion de l’arc (P, S) pour calculer P(P|S), puis élimination du nœud P et calcul de U2.

Quatrième étape : élimination des nœuds T et S successivement, mise à jour des utilités U3 et U4.

La stratégie optimale est de traiter le patient uniquement s’il présente le symptôme S.

Avantages et inconvénients des diagrammes d’influence

• Avantages : représentation compacte et intuitive, chaque variable est représentée par un seul nœud, ce qui facilite la visualisation de modèles complexes. Le formalisme permet de structurer qualitativement le problème.
• Inconvénients : perte de détails dans certains scénarios, prétraitement étendu nécessaire pour collecter et organiser l’information, ce qui peut être coûteux.

Évaluation indirecte des diagrammes d’influence

Cette méthode consiste à transformer chaque nœud de décision en un nœud de chance avec une distribution équiprobable, et le nœud de valeur en un nœud de chance binaire. Le diagramme d’influence est ainsi converti en un réseau bayésien, ce qui facilite le calcul du Maximum Expected Utility (MEU) par propagation d’inférence dans ce réseau.

Transformation des nœuds

• Nœuds de décision : P(Di | Pa(Di)) = 1 / |dom(Di)| (distribution uniforme).
• Nœud de valeur : P(V | Pa(V)) est calculé en fonction des utilités maximales et minimales associées aux parents.

Calcul du MEU

Le MEU est calculé par propagation dans le réseau bayésien transformé, en tenant compte des observations (preuves) disponibles. Par exemple, pour une décision Di prenant la valeur dij :

MEU(ED, i) = max_dij (UEdTvP_ij) + min_dij (UEdTvP_ij)

Glossaire des termes clés

• Diagramme d’influence (DI) : modèle graphique représentant un problème de décision avec incertitude, intégrant décisions, états de nature et utilités.
• Nœud de chance : variable aléatoire modélisant l’incertitude dans le DI.
• Nœud de décision : point où une décision doit être prise, influencé par les variables précédentes.
• Nœud de valeur : représente la fonction d’utilité à maximiser.
• Arc conditionnel : lien entre deux nœuds de chance indiquant une dépendance probabiliste.
• Arc d’information : lien indiquant que la décision est prise en connaissant la variable précédente.
• Élimination de nœud : opération qui supprime un nœud tout en conservant la structure et la valeur optimale du DI.
• Inversion d’arc : changement de direction d’un arc conditionnel entre deux nœuds de chance, sous certaines conditions.
• Maximum Expected Utility (MEU) : utilité espérée maximale que l’on cherche à atteindre par une stratégie optimale.
• Réseau bayésien (RB) : modèle probabiliste graphique utilisé pour l’inférence, en particulier dans l’évaluation indirecte des DI.

Points clés à retenir

• Les diagrammes d’influence permettent de modéliser graphiquement des problèmes de décision sous incertitude de manière compacte et intuitive.
• Ils combinent des nœuds de chance, de décision et d’utilité pour représenter la structure du problème.
• L’évaluation directe utilise des transformations successives sur le diagramme pour éliminer les nœuds et calculer la stratégie optimale.
• L’évaluation indirecte transforme le diagramme en réseau bayésien, facilitant le calcul du MEU par inférence probabiliste.
• Les règles de décision définissent la politique optimale en fonction des variables observées.
• Les diagrammes d’influence sont particulièrement utiles pour organiser visuellement des modèles complexes, mais nécessitent un prétraitement important.