Réseaux bayésiens et inférence probabiliste

Le théorème de Bayes vous dit comment mettre à jour une croyance sur une observation. Un agent réel entretient des croyances sur des dizaines de variables à la fois, et la loi jointe sur celles-ci - l’objet qui répond à toute question - compte $2^n$ entrées pour $n$ variables booléennes. Personne ne peut l’écrire. Cet article porte sur la représentation qui rend la loi jointe utilisable, et sur les algorithmes qui l’interrogent.

A. Le réseau est la loi jointe

Un réseau bayésien est un graphe orienté acyclique. Chaque nœud est une variable aléatoire ; une flèche de $X$ vers $Y$ fait de $X$ un parent de $Y$ ; et chaque nœud porte une table de probabilités conditionnelles donnant $P(X_i \mid \mathrm{Parents}(X_i))$, une ligne par combinaison de valeurs des parents. Un nœud booléen à $k$ parents booléens demande $2^k$ nombres.

L’exemple de Russell et Norvig est une alarme. Elle réagit aux cambriolages et, moins fidèlement, aux séismes ; deux voisins, John et Mary, appellent quand ils l’entendent, John confondant parfois le téléphone avec l’alarme et Mary la ratant parfois derrière sa musique forte. Les flèches $B \to A$, $E \to A$, $A \to J$, $A \to M$, et dix nombres :

$$\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 sens du dessin tient en une équation. Pour toute affectation complète,

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

La probabilité que l’alarme sonne sans cambriolage ni séisme, et que les deux voisins appellent, est donc

$$P(j, m, a, \lnot b, \lnot e) = 0.90 \times 0.70 \times 0.001 \times 0.999 \times 0.998 = 0.000628 .$$

Chacune des 32 entrées de la loi jointe est accessible ainsi, à partir de dix nombres plutôt que 31. L’économie n’est pas une astuce : c’est l’affirmation, faite par les flèches absentes, que chaque variable est conditionnellement indépendante de ses non-descendants étant donné ses parents. Plus fort encore, chaque nœud est indépendant de tous les autres étant donné sa couverture de Markov - parents, enfants, et autres parents des enfants. Étant donné l’alarme et le séisme, les appels téléphoniques ne disent plus rien d’un cambriolage.

B. Inférence exacte

Une requête demande $\mathbf{P}(X \mid \mathbf{e})$. Comme chaque entrée de la loi jointe est un produit d’entrées de TPC, la requête est une somme normalisée de produits sur les variables cachées. Les deux voisins ont appelé ; est-ce un cambriolage ?

$$P(b \mid j, m) = \alpha\, P(b) \sum_{e} P(e) \sum_{a} P(a \mid b, e)\,P(j \mid a)\,P(m \mid a).$$

Quatre termes pour $b$, quatre pour $\lnot b$, chacun un produit de cinq nombres :

$$\mathbf{P}(B \mid j, m) = \alpha\, \langle 0.00059224,\ 0.00149186 \rangle = \langle 0.284,\ 0.716 \rangle .$$

Deux signalements indépendants font monter un a priori de un sur mille à 28 %, et pas davantage, parce que la masse sans cambriolage arrive par trois voies comparables : une alarme sans cause puis les deux appels, $0{,}000628$ ; aucune alarme mais les deux appels quand même, $0{,}000498$ ; et une alarme due à un séisme puis les deux appels, $0{,}000365$. Ensemble elles pèsent 2,5 fois la voie du cambriolage, $0{,}000592$.

L’énumération évalue ceci comme un arbre en profondeur, et l’arbre se répète : le produit $P(j \mid a)\,P(m \mid a)$ est calculé une fois sous $e$ et de nouveau sous $\lnot e$. Sur $n$ variables booléennes le coût est $O(2^n)$ - mieux que le $O(n\,2^n)$ de la construction séparée de chaque entrée jointe, mais pour l’essentiel du recalcul. L’élimination de variables stocke chaque morceau comme un facteur - une table sur les variables dont il dépend encore - et combine les facteurs par produit point à point et par sommation. Sommer sur $A$ donne un facteur sur $(B, E)$ :

$$f_6(B, E) = \begin{array}{c|cc} & e & \lnot e \\ \hline b & 0.598525 & 0.592230 \\ \lnot b & 0.183055 & 0.001130 \end{array}$$

Sommer sur $E$ contre $P(E)$ laisse $f_7(B) = \langle 0.592243,\ 0.001493 \rangle$, et multiplier par $P(B)$ puis normaliser rend $\langle 0.284, 0.716 \rangle$, chaque produit de feuille n’ayant été fait qu’une fois.

Que ce soit rapide dépend de la forme du graphe. Sur un polyarbre - au plus un chemin non orienté entre deux nœuds quelconques, comme ici - l’élimination de variables est linéaire en la taille du réseau. Ajoutez un second chemin et les facteurs intermédiaires peuvent croître exponentiellement dans le pire cas. Le problème général est #P-difficile : aussi difficile que compter les affectations qui satisfont une formule propositionnelle. C’est la raison d’être du reste de cet article.

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.

C. Échantillonner quand l’exact est impossible

Le réseau de l’arroseur a quatre variables booléennes et deux chemins de $\mathit{Cloudy}$ à $\mathit{WetGrass}$, l’un par l’arroseur et l’autre par la pluie :

$$\begin{array}{ll} P(c) = 0.5 & \\[4pt] P(s \mid c) = 0.10 & P(s \mid \lnot c) = 0.50 \\ P(r \mid c) = 0.80 & P(r \mid \lnot c) = 0.20 \\[4pt] P(w \mid s, r) = 0.99 & P(w \mid s, \lnot r) = 0.90 \\ P(w \mid \lnot s, r) = 0.90 & P(w \mid \lnot s, \lnot r) = 0.00 \end{array}$$

L’échantillonnage a priori tire chaque variable dans sa TPC, parents d’abord. La probabilité de produire un événement est le produit des entrées consultées, c’est-à-dire la loi jointe elle-même : $[c, \lnot s, r, w]$ sort avec probabilité $0.5 \times 0.9 \times 0.8 \times 0.9 = 0.324$. Les fréquences convergent donc vers les probabilités, et l’estimation est consistante.

L’échantillonnage par rejet répond à une requête conditionnelle en écartant tout échantillon qui contredit l’évidence. Pour $P(\mathit{Rain} \mid \mathit{Sprinkler} = \text{true})$, de valeur exacte $0.3$, une exécution à graine fixée de 1 000 échantillons a priori en a rejeté 703 et gardé 79 avec pluie contre 218 sans, pour une estimation de $0.266$. Soixante-dix pour cent de l’effort n’ont servi à rien, et c’est le cas bénin : le taux de survie est $P(\mathbf{e})$, qui décroît exponentiellement avec le nombre de variables d’évidence. Demandez au réseau du cambriolage $\mathbf{P}(B \mid j, m)$ et environ 21 échantillons sur 10 000 survivent.

La pondération par vraisemblance fixe les variables d’évidence au lieu de les tirer, si bien que chaque événement est compatible, et pondère chaque événement par la probabilité de l’évidence étant donné les parents que l’échantillonneur a choisis. Pour $\mathbf{P}(\mathit{Rain} \mid c, w)$ dans l’ordre $C, S, R, W$ : le poids part de $1$, $C$ est une évidence donc $w \leftarrow 0.5$ ; $S$ est tiré selon $\langle 0.1, 0.9 \rangle$, disons faux ; $R$ selon $\langle 0.8, 0.2 \rangle$, disons vrai ; $W$ est une évidence donc $w \leftarrow 0.5 \times P(w \mid \lnot s, r) = 0.45$. L’événement est compté sous pluie avec le poids $0.45$. Rien n’est écarté et, parce que la probabilité d’échantillonnage multipliée par le poids égale la loi jointe, le décompte pondéré est consistant : mille échantillons avec la même graine donnent $0.9758$ contre une valeur exacte de $0.9758$. La méthode se dégrade quand l’évidence est improbable sous les valeurs tirées, parce que quelques poids lourds dominent alors tout.

L’échantillonnage de Gibbs est une méthode de Monte-Carlo par chaînes de Markov. Fixez l’évidence, partez d’un état quelconque, et rééchantillonnez de façon répétée une variable hors évidence conditionnellement à sa couverture de Markov. Cette loi conditionnelle est un produit d’une poignée d’entrées de TPC :

$$P(x_i' \mid \mathrm{mb}(X_i)) = \alpha\, P\big(x_i' \mid \mathrm{parents}(X_i)\big) \prod_{Y_j \in \mathrm{Children}(X_i)} P\big(y_j \mid \mathrm{parents}(Y_j)\big).$$

Pour $\mathbf{P}(\mathit{Rain} \mid s, w)$ depuis l’état $[c, s, \lnot r, w]$, rééchantillonner $C$ utilise $P(C)\,P(s \mid C)\,P(\lnot r \mid C)$, ce qui donne $P(c \mid s, \lnot r) = 0.048$ ; disons que le tirage donne faux. Rééchantillonner $R$ utilise ensuite $P(R \mid \lnot c)\,P(w \mid s, R)$, ce qui donne $P(r \mid \lnot c, s, w) = 0.216$. Chaque état visité est un échantillon. Mille pas avec une graine fixée estiment $0.315$ contre la valeur exacte $0.320$.

Cela fonctionne parce que la chaîne possède une distribution stationnaire et que le pas de Gibbs satisfait le bilan détaillé par rapport à la loi a posteriori, ce qui force les deux à coïncider : la fraction du temps passée à la longue dans chaque état est $P(\mathbf{x} \mid \mathbf{e})$. Aucun échantillon n’est rejeté et aucun poids ne s’effondre. Le coût est la corrélation entre états consécutifs, si bien que la chaîne a besoin de temps pour oublier d’où elle est partie.

La convergence est une affirmation sur une limite : la figure ci-dessous met donc la limite à l'écran. La ligne pointillée est la loi a posteriori exacte, obtenue en énumérant la loi jointe, sans partager une ligne de code avec les échantillonneurs. Faites glisser la taille du tirage et regardez les deux estimations marcher vers elle. Passez ensuite à la requête du cambriolage, où le rejet conserve 21 tirages sur 10 000 et où la pondération les garde tous et peine encore, parce que fixer les observations supprime le gaspillage et non la variance.

Où cela vous mène

Un réseau bayésien est une loi jointe que l’on peut réellement écrire. L’inférence exacte est une somme de produits que l’élimination de variables effectue sans répétition, bon marché sur les polyarbres et intraitable en général. Quand le graphe est trop enchevêtré, l’échantillonnage donne des estimations consistantes à un coût qui dépend de la façon dont l’évidence est traitée : le rejet gaspille, la pondération concentre, et Gibbs vagabonde - chacun étant le bon choix quelque part. Le parcours de formation Raisonnement probabiliste avec les réseaux bayésiens travaille chacun de ces calculs à la main et en code.