Université de Blida1

Département d’informatique
Master 1- ISI

Cours 3: Réseaux Bayésiens

Mme Fareh
2023/2024

1
 Plan

1. C’est quoi un réseau bayésien (RB)?

➢ Structure d’un RB
➢ Calcul de probabilités dans un RB
2. Indépendance conditionnelle dans un RB
3. Inférence dans un réseau bayésien
➢ Inférence exacte
➢ Inférence approximative
4. Apprentissage automatique des réseaux bayésiens
➢ Apprentissage de paramètre
➢ Apprentissage de structure

2
 Réseaux bayésiens

● On a vu les bases du raisonnement probabiliste et de la

théorie des probabilité
◆ à partir d’une table des probabilités conjointes, comment
calculer toute autre probabilité
● On a utilisé un exemple simple (MalDeDent, Croche, Carie)
◆ souvent, on aura besoin de centaines de variables
aléatoires
» la table des probabilités ne pourra pas être stockée en
mémoire
● On va voir une façon plus efficace de construire un modèle de
raisonnement probabiliste

3
 Réseaux bayésiens

● Les réseaux bayésiens (RB) sont un couplage entre la théorie des graphes
et la théorie des probabilités

● Un RB permet de représenter les connaissances probabilistes d’une

application donnée :
◆ par exemple, les connaissances cliniques d’un médecin sur des liens de
causalité entre maladies et symptômes

● Les RB sont utiles pour modéliser des connaissances d’un système expert
ou d’un système de support à la décision, dans une situation pour laquelle :
◆ la causalité joue un rôle important (des événements en causent d’autres)

4
 Application : diagnostique médical

● Déterminer la maladie d’un

patient, sachant des symptômes Age Gender

● On peut avoir une maladie mais

montrer seulement un sous- Exposure- Smoking
ensemble des symptômes possibles to-Toxics

Cancer

Serum- Lung-
Calcium Tumor

5
 Applications
● Diagnostique : P(Causes | Symptômes) Cause
● Prédiction : P(Symptomes | Causes)
● Classification : max P(Classe |Données)
classe C1 C2

Symptom

6
 Application : diagnostique médical

● Pathfinder (version 4)
◆ en accord avec un panel
d’experts 50 fois sur 53
◆ prédictions aussi bonnes
que celles des experts qui
ont développé le système

M. Pradhan, G. Provan, B. Middleton, M. Henrion, UAI 1994

7
 Applications
● Troubleshooting Wizard : détection et analyse de problèmes
informatiques

8
 Syntaxe

● Un RB est un graphe
◆ orienté
◆ acyclique
◆ dont les nœuds sont des variables aléatoires et
◆ les arcs représentent
» des dépendances (par exemple des causalités) probabilistes entre les variables et
» des distributions de probabilités conditionnelles (locales) pour chaque variable
étant donnés ses parents
P(C)
.001
Carie

M P(M|C) Cr P(Cr|C)
MalDeDents Croche T .90
T .90
F .05 F .05

9
 Exemple

● Considérons la situation suivante :

◆ je suis au travail, et mes voisins Marie et Jean m’ont promis de m’appeler
chaque fois que mon alarme sonne
◆ mon voisin Jean m’appelle pour me dire que mon alarme sonne
» parfois il confond l’alarme avec la sonnerie du téléphone
◆ par contre ma voisine Marie ne m’appelle pas toujours
» parfois elle met la musique trop fort
◆ parfois mon alarme se met à sonner lorsqu’il y a de légers séismes
◆ comment conclure qu’il y a ou non un cambriolage chez moi?

● On peut représenter ce problème par un RB

10
 Exemple

● Variables aléatoires : Cambriolage Séisme

◆ Cambriolage
◆ Séisme
◆ Alarme
◆ JeanAppelle Alarme
◆ MarieAppelle

JeanAppelle MarieAppelle

11
 Exemple
P(C) P(S)
● La topologie du RB modélise les .001 .002
relations de causalité
● Un arc d’un nœud X vers un nœud
Cambriolage Séisme
Y signifie que la variable X
influence la variable Y
C S P(A|C,S)
◆ un cambriolage peut déclencher
T T .95
l’alarme Alarme T F .94
◆ un séisme aussi
F T .29
F F .001
◆ l’alarme peut inciter Jean à appeler
◆ idem pour Marie
● Une table de probabilités
conditionnelles (TPC) donne la JeanAppelle MarieAppelle
probabilité pour chaque valeur du
A P(J|A) A P(M|A)
nœud étant donnés les combinaisons
T .90 T .70
des valeurs des parents du nœud (c’est F .05 F .01
l’équivalent d’une distribution)
12
 Définitions
P(C) P(S)
● S’il y a un arc d’un nœud Y vers .001 .002
un nœud X, cela signifie que la
variable Y influence la variable X Cambriolage Séisme
◆ Y est appelé le parent de X
◆ Parents(X) est l’ensemble des
parents de X C S P(A|C,S)
T T .95
Alarme T F .94
● Si X n’a pas de parents, sa F
F
T
F
.29
.001
distribution de probabilités est
dite inconditionnelle ou a priori

● Si X a des parents, sa distribution JeanAppelle MarieAppelle

de probabilités est dite A P(J|A) A P(M|A)
conditionnelle T .90 T .70
F .05 F .01

13
 Sémantique

● Un RB est une façon compacte de représenter des probabilités conjointes

● Par définition, la probabilité conjointe de X1 et X2 est donnée par la

distribution P(X1,X2), pour une valeur donnée de X1 et X2
◆ P(X1,X2) = P(X1 | X2) P(X2)

● La distribution conditionnelle de X1 sachant X2 est notée P(X1| X2)

● Soit X = {X1, …, Xn}, l’ensemble des variables d’un RB :

P(X1, …, Xn) =ni = 1 P(Xi | Parents(Xi))

● La distribution conjointe des variables d’un RB est définie comme étant le

produit des distributions conditionnelles (locales)
14
 Calcul de probabilité conjointe

● Nous avons vu que, quelque soit l’ensemble de variables

X = {X1, …, Xn}, par définition :
P(X1, …, Xn) = P(Xn | Xn-1, …, X1) P(Xn-1 | Xn-2, …, X1) … P(X2|X1) P(X1)
=n i = 1 P(Xi | Xi-1, …, X1)

n
● Pour un RB : P(X1, …, Xn) =i = 1 P(Xi | Parents(Xi))
◆ceci est cohérent avec l’assertion précédente pour autant que
Parents(Xi) soit l’ensemble de {Xi-1, …, X1}

15
 Exemple : probabilité conjointe
P(C) P(S)
.001 .002
P(X1, … ,Xn) =
n
 i = 1 P(Xi | Parents(Xi)) Cambriolage Séisme

P(j, m, a, ¬c, ¬s)

C S P(A|C,S)
= P(j|a) P(m|a) P(a| ¬ c, ¬ s)
T T .95
P(¬ c) P(¬ s) Alarme T F .94
F T .29
= .90 * .70 * .001 * F F .001

.999 * . 998
≈ .00062
JeanAppelle MarieAppelle
P(J=j, M=m, A=a, C=¬c, S=¬s) A P(M|A)
A P(J|A)
est aussi noté P(j, m, a, ¬c, ¬s) T .70
T .90
F .05 F .01

16
 Exemple: probabilité marginale
P(C) P(S)
.001 .002
P(¬c, a) = Σm Σj Σs P(J=j,M=m,a,¬c,S=s)
Cambriolage Séisme
= Σm Σj Σs P(j|a) P(m|a) P(a| ¬ c, s) P(¬c) P(s)

C S P(A|C,S)
= Σs Σj Σm P(j|a) P(m|a) P(a| ¬ c, s) P(¬c) P(s)
T T .95
Alarme T F .94
F T .29
= Σs Σj P(j|a) P(a| ¬ c, s) P(¬c) P(s) Σm P(m|a) F F .001

=1
= Σs P(a| ¬ c, s) P(¬c) P(s) Σj P(j|a)
=1 MarieAppelle
= P(a|¬c,s) P(¬c) P(s) + P(a|¬c,¬s) P(¬c) P(¬s) JeanAppelle
= .29 * .999 * .002 + .001 * .999 * .998 A P(J|A) A P(M|A)
T .90 T .70
≈ 0.0016 F .01
F .05

17
 Probabilité marginale
P(C) P(S)
.001 .002
P(¬ c, a) = Σm Σj Σs P(J=j,M=m,a,¬c,S=s)
= Σs P(a| ¬ c, S=s) P(¬c) P(S=s) Cambriolage Séisme

●Pour les probabilités marginales, on

C S P(A|C,S)
peut ignorer les nœuds dont les
T T .95
descendants ne sont pas les nœuds Alarme T F .94
F T .29
observés F F .001
◆ JeanAppelle et MarieAppelle et
leurs descendants ne sont pas
observés, alors on peut les ignorer
◆ Séisme est un ancêtre de Alarme, MarieAppelle
JeanAppelle
alors on doit le marginaliser
explicitement A P(J|A) A P(M|A)
T .90 T .70
F .05 F .01

18
 Indépendance conditionnelle
dans un RB
P(C) P(S)
.001 .002
1. Relation entre grand-parent et
enfant étant donné le parent Cambriolage Séisme
◆ sont indépendants si parent
observé.
● Exemples : C S P(A|C,S)
◆ Cambriolage et MarieAppelle V V .95
Alarme V F .94
sont indépendants étant donné F V .29
Alarme : F F .001

P(M|A,C) = P(M|A)
◆ si A est connu, C n’intervient pas
dans le calcul
JeanAppelle MarieAppelle
◆ connaître A « bloque » le
chemin entre M et C A P(J|A) A P(M|A)
V .90 V .70
F .05 F .01

19
 Indépendance conditionnelle
dans un RB
P(C) P(S)
.001 .002
2. Relation entre deux enfants
étant donné un parent: Cambriolage Séisme
◆ sont indépendants si parent
observé
● Exemples : C S P(A|C,S)
◆ JeanAppelle et MarieAppelle V V .95
Alarme V F .94
sont indépendants étant donné F V .29
Alarme : F F .001

P(M|A,J) = P(M|A)
◆ si A est connu, J n’intervient pas
dans le calcul
JeanAppelle MarieAppelle
◆ connaître A « bloque » le chemin
entre J et M A P(J|A) A P(M|A)
V .90 V .70
F .05 F .01

20
 Indépendance conditionnelle
dans un RB
P(C) P(S)
.001 .002
3. Relation entre deux parents
étant donné un enfant Cambriolage Séisme
◆ sont indépendants si enfant non
observé
● Exemples : C S P(A|C,S)
◆ Cambriolage et Séisme sont V V .95
Alarme V F .94
indépendants si Alarme est non F V .29
observé F F .001

◆ ne pas connaître A « bloque » le

chemine entre C et S

JeanAppelle MarieAppelle

A P(J|A) A P(M|A)
V .90 V .70
F .05 F .01

21
 Indépendance conditionnelle
dans un RB : D-séparation
● D-séparation : critère général pour décider si un nœud X est indépendant
d’un nœud Y, étant donnés d’autres nœuds Z = {Z1, ..., Zm}

● X est indépendant de Y sachant Z si tous les chemins non-dirigés entre X et Y

sont bloqués par Z

● Un chemin est bloqué s’il contient au moins un noeud N qui satisfait une ou
l’autre des conditions suivantes :
1. il inclue un noeud N ou N , où N ∈ {Z1, ..., Zm}
2. il inclue un noeud N et N ∉ {Z1, ..., Zm}, et aucun des descendants de N
appartient {Z1, ..., Zm}.

22
 Exemple

● Est-ce que Age et Gender sont

indépendants ? Age Gender

Exposure- Smoking
to-Toxics

Cancer

Serum- Lung-
Calcium Tumor

23
 Exemple

● Est-ce que Age et Gender sont

indépendants ? Age Gender

◆ chemin 1 est bloqué au niveau

de Smoking N Exposure- Smoking
» Smoking et ses descendants to-Toxics
Cancer, Serum-Calcium et Lung-
Tumor ne sont pas observés

Cancer

Serum- Lung-
Calcium Tumor

24
 Exemple

● Est-ce que Age et Gender sont

indépendants ? Age Gender

◆ chemin 1 est bloqué au niveau

de Smoking N Exposure- Smoking
» Smoking et ses descendants to-Toxics
Cancer, Serum-Calcium et Lung-
Tumor ne sont pas observés

Cancer
◆ chemin 2 est aussi Cancer
» même raisons N

● Réponse : oui Serum- Lung-

Calcium Tumor

25
 Exemple

● Est-ce que Age et Lung-Tumor

sont indépendants sachant Age Gender
Smoking ?

Exposure- Smoking
to-Toxics

Cancer

Serum- Lung-
Calcium Tumor

26
 Exemple

● Est-ce que Age et Lung-Tumor

sont indépendants sachant Age Gender
Smoking ?

◆ chemin 1 est bloqué au niveau Exposure- Smoking

de Smoking N to-Toxics
» Smoking est observé

Cancer

Serum- Lung-
Calcium Tumor

27
 Exemple

● Est-ce que Age et Lung-Tumor

sont indépendants sachant Age Gender
Smoking ?

◆ chemin 1 est bloqué au niveau Exposure- Smoking

de Smoking N to-Toxics
» Smoking est observé

◆ chemin 2 n’est pas bloqué

Cancer
» Exposure-to-Toxics N
n’est pas observé
» Cancer N
n’est pas observé Serum- Lung-
Calcium Tumor
● Réponse : non
28
 Exemple

● Est-ce que Exposure-to-Toxics et

Smoking sont indépendants Age Gender
sachant Age et Lung-Tumor?

Exposure- Smoking
to-Toxics

Cancer

Serum- Lung-
Calcium Tumor

29
 Exemple

● Est-ce que Exposure-to-Toxics et

Smoking sont indépendants Age Gender
sachant Age et Lung-Tumor?

◆ chemin 1 est bloqué au niveau Exposure- Smoking

de Age N to-Toxics
» Age est observé

Cancer

Serum- Lung-
Calcium Tumor

30
 Exemple

● Est-ce que Exposure-to-Toxics et

Smoking sont indépendants Age Gender
sachant Age et Lung-Tumor?

◆ chemin 1 est bloqué au niveau Exposure- Smoking

de Age N to-Toxics
» Age est observé

◆ chemin 2 n’est pas bloqué

Cancer
» Cancer N
ne bloque pas le chemin puisque
Lung-Tumor, un de ses
descendants, est observé
Serum- Lung-
Calcium Tumor
● Réponse : non
31
 Exercice

G┴ L │ C

32
 Exercice

A┴ J │ G

33