Réseaux bayésiens et loi jointe

La loi jointe complète répond à toute question probabiliste, et elle est inutilisable en pratique : sur $n$ variables booléennes elle compte $2^n$ entrées, personne ne peut les fournir et personne ne pourrait les stocker. Un réseau bayésien conserve la puissance de la loi jointe en ne payant que pour les dépendances qui existent réellement.

Ce qu’est un réseau

Un réseau bayésien est un graphe orienté acyclique dans lequel

• chaque nœud est une variable aléatoire,
• une flèche de $X$ vers $Y$ dit que $X$ est un parent de $Y$, donc que $X$ a une influence directe sur $Y$, et
• chaque nœud $X_i$ porte une table de probabilités conditionnelles (TPC) donnant $P(X_i \mid \mathrm{Parents}(X_i))$, une ligne par combinaison de valeurs des parents.

Chaque ligne d’une TPC doit sommer à un ; pour une variable booléenne on n’écrit donc que la probabilité de vrai, l’autre s’en déduit. Un nœud booléen à $k$ parents booléens demande par conséquent $2^k$ nombres, et un nœud racine exactement un.

Le réseau du cambriolage

L’exemple qui porte tout ce parcours est l’alarme antivol de Judea Pearl, celle dont Russell et Norvig se servent pour introduire les réseaux bayésiens. Vous êtes au travail. Une alarme anti-cambriolage installée chez vous réagit assez fidèlement aux cambriolages et, faisant office de détecteur sismique de fortune, parfois aux petits tremblements de terre. Deux voisins, John et Mary, ont promis d’appeler quand ils l’entendent. John appelle presque toujours quand il entend l’alarme, mais la confond parfois avec le téléphone ; Mary aime la musique forte et rate souvent l’alarme tout à fait.

$$\begin{array}{ll} P(b) = 0.001 & P(e) = 0.002 \\[4pt] P(a \mid b, e) = 0.95 & P(a \mid b, \lnot e) = 0.94 \\ P(a \mid \lnot b, e) = 0.29 & P(a \mid \lnot b, \lnot e) = 0.001 \\[4pt] P(j \mid a) = 0.90 & P(j \mid \lnot a) = 0.05 \\ P(m \mid a) = 0.70 & P(m \mid \lnot a) = 0.01 \end{array}$$

Le graphe a pour flèches $B \to A$, $E \to A$, $A \to J$, $A \to M$, et rien d’autre. C’est un ensemble d’affirmations : John et Mary ne perçoivent pas directement les cambriolages, ils ne remarquent pas les petits séismes, et ils ne se concertent pas avant d’appeler. Tout ce qui pourrait faire échouer l’alarme - une pile à plat, un fil coupé - ou empêcher un voisin de la signaler est absorbé dans les nombres plutôt que modélisé. Ce n’est pas de la négligence ; c’est ainsi qu’un petit agent se débrouille dans un grand monde.

Ce que signifie un réseau

La sémantique tient en une seule équation. Pour toute affectation complète $x_1, \dots, x_n$ de toutes les variables,

$$P(x_1, \dots, x_n) \;=\; \prod_{i=1}^{n} P\big(x_i \mid \mathrm{parents}(X_i)\big),$$

où $\mathrm{parents}(X_i)$ désigne les valeurs des parents de $X_i$ dans cette affectation. Le réseau est la loi jointe, écrite comme un produit des entrées de ses TPC.

Exemple travaillé : un événement complet

L’alarme a sonné, il n’y a eu ni cambriolage ni séisme, et les deux voisins appellent. En lisant une entrée dans chaque table :

$$\begin{aligned} P(j, m, a, \lnot b, \lnot e) &= P(j \mid a)\,P(m \mid a)\,P(a \mid \lnot b, \lnot e)\,P(\lnot b)\,P(\lnot e) \\ &= 0.90 \times 0.70 \times 0.001 \times 0.999 \times 0.998 \\ &= 0.000628 . \end{aligned}$$

Comme chacune des 32 entrées de la loi jointe peut être produite ainsi, tout ce à quoi la loi jointe complète sait répondre, le réseau sait y répondre aussi - en sommant les entrées pertinentes. La leçon suivante montre comment le faire sans produire les 32.

Pourquoi le réseau est tellement plus petit

Comptons les nombres. Cambriolage et Séisme en demandent un chacun, Alarme a deux parents et en demande quatre, et chaque appel a un parent et en demande deux :

$$1 + 1 + 4 + 2 + 2 = 10$$

contre $2^5 - 1 = 31$ entrées indépendantes dans la table jointe complète. L’écart se creuse de façon explosive : avec 30 variables booléennes ayant chacune au plus cinq parents, le réseau demande au plus $30 \times 2^5 = 960$ nombres là où la loi jointe en demande plus d’un milliard. L’économie vient de la localité : chaque variable n’est influencée directement que par quelques autres.

Le réseau ci-dessous est celui-là, et chacun de ses nombres est exact : les probabilités a posteriori viennent de la somme des 32 affectations, non d’un échantillonnage. Cliquez un nœud pour dire ce que vous savez. Commencez par les deux voisins qui appellent : le cambriolage monte à 28,4 %, ce qui mérite déjà qu’on s’y arrête, car les appels renseignent excellemment sur l’alarme et l’alarme témoigne mal du cambriolage. Ajoutez ensuite le séisme. Il rend les appels plus probables, et il renvoie le cambriolage vers rien.

Les indépendances que le graphe affirme

Appliquons la règle de la chaîne à un ordre quelconque des variables :

$$P(x_1, \dots, x_n) = \prod_{i=1}^{n} P(x_i \mid x_{i-1}, \dots, x_1).$$

En comparant avec la sémantique ci-dessus, le réseau est une représentation correcte exactement quand, pour chaque variable,

$$P(X_i \mid X_{i-1}, \dots, X_1) = P\big(X_i \mid \mathrm{Parents}(X_i)\big)$$

pour un certain ordre dans lequel chaque nœud vient après ses parents. En mots : chaque variable est conditionnellement indépendante de ses autres prédécesseurs étant donné ses parents. Deux autres conséquences découlent du seul graphe.

• Un nœud est conditionnellement indépendant de ses non-descendants étant donné ses parents. Dans le réseau du cambriolage, $J$ est indépendant de $B$, $E$ et $M$ dès que $A$ est connu.
• Un nœud est conditionnellement indépendant de tout autre nœud étant donné sa couverture de Markov : ses parents, ses enfants, et les autres parents de ses enfants. La couverture de $B$ est $\{A, E\}$ : étant donné l’état de l’alarme et celui du séisme, les deux appels téléphoniques ne vous apprennent plus rien sur un cambriolage.

L’ordre compte quand on en construit un. Ajoutez les nœuds dans l’ordre $M, J, A, B, E$ et vous êtes forcé de tracer $M \to J$, puis les deux appels vers $A$, puis $A \to B$, puis $A \to E$ et $B \to E$ : deux liens et trois nombres de plus que le réseau causal, dont certains décrivent des relations véritablement difficiles à estimer. Placer les causes avant les effets est ce qui garde le réseau petit.

Avant le quiz

Sachez écrire le produit qui définit la loi jointe, l’évaluer pour un événement complet, compter les nombres qu’un réseau demande contre la table complète, et dire ce qu’est une couverture de Markov et pourquoi conditionner sur elle isole un nœud.