Réseau bayésien

Un réseau bayésien répond à la question de savoir comment un agent peut entretenir des croyances sur de nombreuses variables à la fois sans écrire une loi jointe dont la taille croît exponentiellement avec leur nombre. Il le fait en n’enregistrant que les influences directes : une arête de X vers Y dit que X est un parent de Y, et chaque nœud stocke P(nœud | parents) sous forme de table avec une ligne par combinaison de valeurs des parents. Russell et Norvig introduisent l’idée avec une alarme anti-cambriolage qui réagit aux cambriolages et, moins fidèlement, aux séismes, et deux voisins qui appellent quand ils l’entendent. Cinq variables, quatre arêtes et dix nombres remplacent une table jointe de trente et une entrées.

La sémantique tient en une seule équation : la probabilité d’une affectation complète de toutes les variables est le produit des probabilités conditionnelles lues dans les tables. Pour l’alarme qui sonne sans cambriolage ni séisme tandis que les deux voisins appellent, ce produit vaut 0,90 × 0,70 × 0,001 × 0,999 × 0,998 = 0,000628. Comme chaque entrée de la loi jointe peut être retrouvée ainsi, le réseau n’est pas une approximation de la loi jointe ; il est la loi jointe, stockée de façon compacte.

La compacité repose sur l’indépendance conditionnelle. Comparer le produit avec la règle de la chaîne montre que le réseau est un modèle correct exactement quand chaque variable est conditionnellement indépendante de ses autres prédécesseurs étant donné ses parents, pour un certain ordre qui place les parents avant les enfants. Deux conséquences découlent du seul graphe : un nœud est indépendant de ses non-descendants étant donné ses parents, et un nœud est indépendant de tout autre nœud étant donné sa couverture de Markov, l’ensemble de ses parents, de ses enfants et des autres parents de ses enfants. Construire le réseau dans l’ordre causal le garde petit ; le construire dans le mauvais ordre force des arêtes supplémentaires et des nombres plus difficiles à estimer.

Une requête demande la loi a posteriori d’une variable étant donné une évidence sur d’autres, et toute requête de ce type est une somme normalisée de produits d’entrées de tables sur les variables cachées. L’énumération évalue cette somme directement et répète du travail ; l’élimination de variables stocke les résultats intermédiaires comme des facteurs et les combine par produit point à point et par sommation. Sur un polyarbre, un graphe avec au plus un chemin non orienté entre deux nœuds quelconques, l’élimination s’exécute en temps linéaire en le nombre d’entrées des tables. Sur les graphes multiplement connexes les facteurs peuvent croître exponentiellement, et le problème général est aussi difficile que compter les affectations satisfaisant une formule propositionnelle. Les méthodes approchées - échantillonnage par rejet, pondération par vraisemblance et Monte-Carlo par chaînes de Markov - échangent l’exactitude contre des estimations consistantes dont le coût dépend de la façon dont l’évidence est traitée.

Dans le réseau du cambriolage, la requête « les deux voisins ont appelé ; y a-t-il eu un cambriolage ? » s’écrit P(B | j, m) = α Σₑ Σₐ P(B) P(e) P(a | B, e) P(j | a) P(m | a). Sommer les quatre termes pour chaque valeur de B donne le couple non normalisé ⟨0,00059224, 0,00149186⟩.

La normalisation donne ⟨0,284, 0,716⟩ : deux signalements indépendants font monter un a priori de un sur mille à environ 28 %, et pas davantage, parce que la masse sans cambriolage, 0,00149186, 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, une alarme due à un séisme puis les deux appels 0,000365 - qui pèsent ensemble 2,5 fois la voie du cambriolage, 0,000592.

L’élimination de variables atteint la même réponse en sommant d’abord sur Alarme pour obtenir un facteur sur (B, E), puis sur Séisme pour obtenir un facteur sur B seul, de sorte que les produits aux feuilles sont calculés une fois plutôt qu’une fois par branche de l’arbre d’énumération.