Réseau bayésien

Un réseau bayésien (également connu sous le nom de réseau bayésien , réseau bayésien , réseau de croyances ou réseau de décision ) est un modèle graphique probabiliste qui représente un ensemble de variables et leurs dépendances conditionnelles via un graphe acyclique dirigé (DAG). Bien qu'il s'agisse de l'une des nombreuses formes de notation causale , les réseaux causaux sont des cas particuliers de réseaux bayésiens. Les réseaux bayésiens sont idéaux pour prendre un événement qui s'est produit et prédire la probabilité que l'une des nombreuses causes connues possibles en soit le facteur contributif. Par exemple, un réseau bayésien pourrait représenter les relations probabilistes entre les maladies et les symptômes. Étant donné les symptômes, le réseau peut être utilisé pour calculer les probabilités de présence de diverses maladies.

Des algorithmes efficaces peuvent effectuer des inférences et des apprentissages dans les réseaux bayésiens. Les réseaux bayésiens qui modélisent des séquences de variables ( par exemple des signaux de parole ou des séquences de protéines ) sont appelés réseaux bayésiens dynamiques . Les généralisations des réseaux bayésiens qui peuvent représenter et résoudre des problèmes de décision dans des conditions d'incertitude sont appelées diagrammes d'influence .

Formellement, les réseaux bayésiens sont des graphes acycliques dirigés (DAG) dont les nœuds représentent des variables au sens bayésien : il peut s'agir de quantités observables, de variables latentes , de paramètres inconnus ou d'hypothèses. Chaque arête représente une dépendance conditionnelle directe. Toute paire de nœuds qui ne sont pas connectés (c'est-à-dire qu'aucun chemin ne relie un nœud à l'autre) représente des variables qui sont conditionnellement indépendantes l'une de l'autre. Chaque nœud est associé à une fonction de probabilité qui prend, en entrée, un ensemble particulier de valeurs pour les variables parentes du nœud , et donne (en sortie) la probabilité (ou la distribution de probabilité, le cas échéant) de la variable représentée par le nœud. Par exemple, si les nœuds parents représentent des variables booléennes , alors la fonction de probabilité pourrait être représentée par un tableau d' entrées, une entrée pour chacune des combinaisons parentes possibles. Des idées similaires peuvent être appliquées à des graphes non orientés, et éventuellement cycliques, tels que les réseaux de Markov .

Prenons une illustration pour illustrer les concepts d'un réseau bayésien. Supposons que nous souhaitons modéliser les dépendances entre trois variables : l'arroseur (ou plus précisément son état, s'il est allumé ou non), la présence ou l'absence de pluie et si l'herbe est mouillée ou non. Observons que deux événements peuvent provoquer l'arrosage de l'herbe : un arroseur actif ou la pluie. La pluie a un effet direct sur l'utilisation de l'arroseur (à savoir que lorsqu'il pleut, l'arroseur n'est généralement pas actif). Cette situation peut être modélisée avec un réseau bayésien (illustré à droite). Chaque variable a deux valeurs possibles, T (pour vrai) et F (pour faux).

La fonction de probabilité conjointe est, par la règle de probabilité en chaîne ,

où G = « Herbe mouillée (vrai/faux) », S = « Arroseur allumé (vrai/faux) », et R = « Il pleut (vrai/faux) ».

Le modèle peut répondre à des questions sur la présence d'une cause étant donné la présence d'un effet (ce qu'on appelle la probabilité inverse) comme « Quelle est la probabilité qu'il pleuve, étant donné que l'herbe est mouillée ? » en utilisant la formule de probabilité conditionnelle et en additionnant toutes les variables nuisibles :

En utilisant le développement de la fonction de probabilité conjointe et les probabilités conditionnelles des tables de probabilités conditionnelles (CPT) indiquées dans le diagramme, on peut évaluer chaque terme dans les sommes du numérateur et du dénominateur. Par exemple,

Ensuite, les résultats numériques (indexés par les valeurs des variables associées) sont

Pour répondre à une question interventionnelle, telle que « Quelle est la probabilité qu'il pleuve, sachant que nous mouillons l'herbe ? », la réponse est régie par la fonction de distribution conjointe post-intervention

obtenu en supprimant le facteur de la distribution pré-intervention. L'opérateur do force la valeur de G à être vraie. La probabilité de pluie n'est pas affectée par l'action :

Pour prédire l’impact de l’activation de l’arroseur :

avec le terme supprimé, montrant que l'action affecte l'herbe mais pas la pluie.

Ces prédictions peuvent ne pas être réalisables compte tenu des variables non observées, comme dans la plupart des problèmes d'évaluation des politiques. L'effet de l'action peut néanmoins être prédit, à chaque fois que le critère de porte dérobée est satisfait. Il stipule que, si un ensemble Z de nœuds peut être observé qui sépare par d (ou bloque) tous les chemins de porte dérobée de X à Y , alors

Un chemin de porte dérobée est un chemin qui se termine par une flèche vers X . Les ensembles qui satisfont au critère de porte dérobée sont appelés « suffisants » ou « admissibles ». Par exemple, l'ensemble Z = R est admissible pour prédire l'effet de S = T sur G , car R d -sépare le (seul) chemin de porte dérobée S ← R → G . Cependant, si S n'est pas observé, aucun autre ensemble d -sépare ce chemin et l'effet de l'ouverture de l'arroseur ( S = T ) sur l'herbe ( G ) ne peut pas être prédit à partir d'observations passives. Dans ce cas, P ( G | do( S = T )) n'est pas « identifié ». Cela reflète le fait que, faute de données d'intervention, la dépendance observée entre S et G est due à une connexion causale ou est fausse (dépendance apparente découlant d'une cause commune, R ). (voir le paradoxe de Simpson )

Pour déterminer si une relation causale est identifiée à partir d'un réseau bayésien arbitraire avec des variables non observées, on peut utiliser les trois règles du « do -calcul » et tester si tous les termes do peuvent être supprimés de l'expression de cette relation, confirmant ainsi que la quantité souhaitée est estimable à partir des données de fréquence.

L'utilisation d'un réseau bayésien peut permettre d'économiser des quantités considérables de mémoire par rapport aux tables de probabilité exhaustives, si les dépendances dans la distribution conjointe sont éparses. Par exemple, une manière naïve de stocker les probabilités conditionnelles de 10 variables à deux valeurs sous forme de table nécessite un espace de stockage pour les valeurs. Si la distribution locale d'aucune variable ne dépend de plus de trois variables parentes, la représentation du réseau bayésien stocke au maximum les valeurs.

L’un des avantages des réseaux bayésiens est qu’il est intuitivement plus facile pour un humain de comprendre (un ensemble clairsemé de) dépendances directes et de distributions locales que des distributions conjointes complètes.

Les réseaux bayésiens effectuent trois tâches d’inférence principales :

Parce qu'un réseau bayésien est un modèle complet de ses variables et de leurs relations, il peut être utilisé pour répondre à des requêtes probabilistes les concernant. Par exemple, le réseau peut être utilisé pour mettre à jour la connaissance de l'état d'un sous-ensemble de variables lorsque d'autres variables (les variables de preuve ) sont observées. Ce processus de calcul de la distribution postérieure des variables à partir des preuves est appelé inférence probabiliste. La distribution postérieure donne une statistique universelle suffisante pour les applications de détection, lors du choix de valeurs pour le sous-ensemble de variables qui minimisent une fonction de perte attendue, par exemple la probabilité d'erreur de décision. Un réseau bayésien peut donc être considéré comme un mécanisme permettant d'appliquer automatiquement le théorème de Bayes à des problèmes complexes.

Les méthodes d'inférence exacte les plus courantes sont : l'élimination des variables , qui élimine (par intégration ou sommation) les variables non observées non liées à la requête une par une en répartissant la somme sur le produit ; la propagation d'arbre de clique , qui met en cache le calcul afin que de nombreuses variables puissent être interrogées en même temps et que de nouvelles preuves puissent être propagées rapidement ; et le conditionnement récursif et la recherche ET/OU, qui permettent un compromis espace-temps et correspondent à l'efficacité de l'élimination des variables lorsque suffisamment d'espace est utilisé. Toutes ces méthodes ont une complexité exponentielle dans la largeur de l'arbre du réseau. Les algorithmes d'inférence approximative les plus courants sont l'échantillonnage d'importance , la simulation MCMC stochastique , l'élimination par mini-seau, la propagation de croyances en boucle , la propagation de croyances généralisées et les méthodes variationnelles .

Afin de spécifier complètement le réseau bayésien et donc de représenter complètement la distribution de probabilité conjointe , il est nécessaire de spécifier pour chaque nœud X la distribution de probabilité pour X conditionnelle aux parents de X. La distribution de X conditionnelle à ses parents peut avoir n'importe quelle forme. Il est courant de travailler avec des distributions discrètes ou gaussiennes car cela simplifie les calculs. Parfois, seules les contraintes sur la distribution sont connues ; on peut alors utiliser le principe d'entropie maximale pour déterminer une seule distribution, celle avec la plus grande entropie compte tenu des contraintes. (De manière analogue, dans le contexte spécifique d'un réseau bayésien dynamique , la distribution conditionnelle pour l'évolution temporelle de l'état caché est généralement spécifiée pour maximiser le taux d'entropie du processus stochastique implicite.)

Souvent, ces distributions conditionnelles incluent des paramètres inconnus et doivent être estimés à partir des données, par exemple via l' approche du maximum de vraisemblance . La maximisation directe de la vraisemblance (ou de la probabilité postérieure ) est souvent complexe étant donné les variables non observées. Une approche classique de ce problème est l' algorithme d'espérance-maximisation , qui alterne le calcul des valeurs attendues des variables non observées en fonction des données observées, avec la maximisation de la vraisemblance complète (ou postérieure) en supposant que les valeurs attendues précédemment calculées sont correctes. Dans des conditions de régularité modérées, ce processus converge vers des valeurs de vraisemblance maximale (ou postérieure maximale) pour les paramètres.

Une approche bayésienne plus complète des paramètres consiste à les traiter comme des variables supplémentaires non observées et à calculer une distribution postérieure complète sur tous les nœuds en fonction des données observées, puis à intégrer les paramètres. Cette approche peut être coûteuse et conduire à des modèles de grande dimension, ce qui rend les approches classiques de paramétrage plus faciles à gérer.

Dans le cas le plus simple, un réseau bayésien est spécifié par un expert et est ensuite utilisé pour effectuer des inférences. Dans d'autres applications, la tâche de définition du réseau est trop complexe pour les humains. Dans ce cas, la structure du réseau et les paramètres des distributions locales doivent être appris à partir des données.

L'apprentissage automatique de la structure graphique d'un réseau bayésien (BN) est un défi poursuivi dans le cadre du machine learning . L'idée de base remonte à un algorithme de récupération développé par Rebane et Pearl et repose sur la distinction entre les trois modèles possibles autorisés dans un DAG à 3 nœuds :

Les 2 premiers représentent les mêmes dépendances ( et sont indépendants étant donné ) et sont donc indiscernables. Le collisionneur, cependant, peut être identifié de manière unique, puisque et sont marginalement indépendants et toutes les autres paires sont dépendantes. Ainsi, alors que les squelettes (les graphes dépouillés des flèches) de ces trois triplets sont identiques, la directionnalité des flèches est partiellement identifiable. La même distinction s'applique lorsque et ont des parents communs, sauf qu'il faut d'abord conditionner sur ces parents. Des algorithmes ont été développés pour déterminer systématiquement le squelette du graphe sous-jacent et, ensuite, orienter toutes les flèches dont la directionnalité est dictée par les indépendances conditionnelles observées.

Une autre méthode d'apprentissage structurel utilise la recherche basée sur l'optimisation. Elle nécessite une fonction de notation et une stratégie de recherche. Une fonction de notation courante est la probabilité postérieure de la structure donnée par les données d'apprentissage, comme le BIC ou le BDeu. Le temps nécessaire à une recherche exhaustive renvoyant une structure qui maximise le score est superexponentiel en termes de nombre de variables. Une stratégie de recherche locale apporte des modifications progressives visant à améliorer le score de la structure. Un algorithme de recherche globale comme la chaîne de Markov Monte Carlo peut éviter de se retrouver piégé dans des minima locaux . Friedman et al. discutent de l'utilisation d'informations mutuelles entre les variables et de la recherche d'une structure qui maximise cela. Ils le font en limitant l'ensemble des candidats parents à k nœuds et en effectuant une recherche exhaustive dans ceux-ci.

Une méthode particulièrement rapide pour l'apprentissage exact de BN consiste à considérer le problème comme un problème d'optimisation et à le résoudre à l'aide de la programmation en nombres entiers . Des contraintes d'acyclicité sont ajoutées au programme en nombres entiers (IP) pendant la résolution sous la forme de plans de coupe . Cette méthode peut traiter des problèmes comportant jusqu'à 100 variables.

Pour traiter des problèmes comportant des milliers de variables, une approche différente est nécessaire. L'une d'elles consiste à échantillonner d'abord un ordre, puis à trouver la structure BN optimale par rapport à cet ordre. Cela implique de travailler sur l'espace de recherche des ordres possibles, ce qui est pratique car il est plus petit que l'espace des structures de réseau. Plusieurs ordres sont ensuite échantillonnés et évalués. Cette méthode s'est avérée être la meilleure disponible dans la littérature lorsque le nombre de variables est énorme.

Une autre méthode consiste à se concentrer sur la sous-classe des modèles décomposables, pour lesquels les MLE ont une forme fermée. Il est alors possible de découvrir une structure cohérente pour des centaines de variables.

L'apprentissage des réseaux bayésiens avec une largeur d'arbre limitée est nécessaire pour permettre une inférence exacte et traitable, car la complexité d'inférence du pire cas est exponentielle dans la largeur d'arbre k (sous l'hypothèse de temps exponentiel). Cependant, en tant que propriété globale du graphe, elle augmente considérablement la difficulté du processus d'apprentissage. Dans ce contexte, il est possible d'utiliser K-tree pour un apprentissage efficace.

Étant donné les données et les paramètres , une analyse bayésienne simple commence par une probabilité a priori ( prior ) et une vraisemblance pour calculer une probabilité a posteriori .

Souvent, la prior sur dépend à son tour d'autres paramètres qui ne sont pas mentionnés dans la vraisemblance. Ainsi, la prior doit être remplacée par une vraisemblance , et une prior sur les paramètres nouvellement introduits est nécessaire, ce qui donne une probabilité postérieure

Il s’agit de l’exemple le plus simple d’un modèle bayésien hiérarchique .

Le processus peut être répété ; par exemple, les paramètres peuvent dépendre à leur tour de paramètres supplémentaires , qui nécessitent leur propre prior. Finalement, le processus doit se terminer, avec des priors qui ne dépendent pas de paramètres non mentionnés.

Étant donné les quantités mesurées, chacune avec des erreurs distribuées normalement d' écart type connu ,

Supposons que nous soyons intéressés par l'estimation de la . Une approche consisterait à estimer la en utilisant une approche de vraisemblance maximale ; puisque les observations sont indépendantes, la vraisemblance se factorise et l'estimation de vraisemblance maximale est simplement

Cependant, si les quantités sont liées, de sorte que, par exemple, les individus ont eux-mêmes été tirés d'une distribution sous-jacente, alors cette relation détruit l'indépendance et suggère un modèle plus complexe, par exemple,

avec des priors impropres , . Lorsque , il s'agit d'un modèle identifié (c'est-à-dire qu'il existe une solution unique pour les paramètres du modèle), les distributions postérieures de l'individu auront tendance à se déplacer ou à se rétrécir par rapport aux estimations de vraisemblance maximale vers leur moyenne commune. Ce rétrécissement est un comportement typique des modèles hiérarchiques de Bayes.

Il faut faire preuve de prudence lors du choix des priors dans un modèle hiérarchique, en particulier pour les variables d'échelle situées à des niveaux supérieurs de la hiérarchie, comme la variable de l'exemple. Les priors habituels, comme le prior de Jeffreys, ne fonctionnent souvent pas, car la distribution postérieure ne sera pas normalisable et les estimations faites en minimisant la perte attendue seront inadmissibles .

Plusieurs définitions équivalentes d'un réseau bayésien ont été proposées. Pour ce qui suit, soit G = ( V , E ) un graphe acyclique orienté (DAG) et soit X = ( X _v ), v ∈ V un ensemble de variables aléatoires indexées par V .

X est un réseau bayésien par rapport à G si sa fonction de densité de probabilité conjointe (par rapport à une mesure de produit ) peut être écrite comme un produit des fonctions de densité individuelles, conditionnellement à leurs variables parentes :

où pa( v ) est l'ensemble des parents de v (c'est-à-dire les sommets pointant directement vers v via une seule arête).

Pour tout ensemble de variables aléatoires, la probabilité de tout membre d'une distribution conjointe peut être calculée à partir de probabilités conditionnelles en utilisant la règle de la chaîne (étant donné un ordre topologique de X ) comme suit :

En utilisant la définition ci-dessus, cela peut être écrit comme :

La différence entre les deux expressions est l’ indépendance conditionnelle des variables par rapport à leurs non-descendants, étant donné les valeurs de leurs variables parentes.

X est un réseau bayésien par rapport à G s'il satisfait la propriété de Markov locale : chaque variable est conditionnellement indépendante de ses non-descendants étant donné ses variables parentes :

où de( v ) est l'ensemble des descendants et V \ de( v ) est l'ensemble des non-descendants de v .

Cela peut être exprimé en termes similaires à la première définition, comme

L'ensemble des parents est un sous-ensemble de l'ensemble des non-descendants car le graphe est acyclique .

En général, l'apprentissage d'un réseau bayésien à partir de données est connu pour être NP-difficile . Cela est dû en partie à l' explosion combinatoire des DAG énumératifs à mesure que le nombre de variables augmente. Néanmoins, des informations sur un réseau bayésien sous-jacent peuvent être obtenues à partir de données en temps polynomial en se concentrant sur sa structure d'indépendance marginale : alors que les déclarations d'indépendance conditionnelle d'une distribution modélisée par un réseau bayésien sont codées par un DAG (selon la factorisation et les propriétés de Markov ci-dessus), ses déclarations d'indépendance marginales - les déclarations d'indépendance conditionnelle dans lesquelles l'ensemble de conditionnement est vide - sont codées par un simple graphe non orienté avec des propriétés spéciales telles que des nombres d'intersection et d'indépendance égaux .

Le développement d'un réseau bayésien commence souvent par la création d'un DAG G tel que X satisfasse la propriété de Markov locale par rapport à G . Il s'agit parfois d'un DAG causal . Les distributions de probabilité conditionnelles de chaque variable étant donné ses parents dans G sont évaluées. Dans de nombreux cas, en particulier dans le cas où les variables sont discrètes, si la distribution conjointe de X est le produit de ces distributions conditionnelles, alors X est un réseau bayésien par rapport à G .

La couverture de Markov d'un nœud est l'ensemble des nœuds constitués de ses parents, de ses enfants et de tout autre parent de ses enfants. La couverture de Markov rend le nœud indépendant du reste du réseau ; la distribution conjointe des variables dans la couverture de Markov d'un nœud est une connaissance suffisante pour calculer la distribution du nœud. X est un réseau bayésien par rapport à G si chaque nœud est conditionnellement indépendant de tous les autres nœuds du réseau, étant donné sa couverture de Markov .

Cette définition peut être rendue plus générale en définissant la séparation « d » de deux nœuds, où d signifie directionnel. Nous définissons d'abord la séparation « d » d'un sentier, puis nous définirons la séparation « d » de deux nœuds en fonction de cela.

Soit P un chemin allant du nœud u à v . Un chemin est un chemin sans boucle, non orienté (c'est-à-dire que toutes les directions des arêtes sont ignorées) entre deux nœuds. On dit alors que P est d -séparé par un ensemble de nœuds Z si l'une des conditions suivantes est remplie :

• P contient (mais n'a pas besoin d'être entièrement) une chaîne dirigée, ou , telle que le nœud médian m soit dans Z ,
• P contient une fourche, , telle que le nœud du milieu m soit dans Z , ou
• P contient une fourche inversée (ou collisionneur), , telle que le nœud central m n'est pas dans Z et qu'aucun descendant de m n'est dans Z .

Les nœuds u et v sont d -séparés par Z si tous les chemins entre eux sont d -séparés. Si u et v ne sont pas d-séparés, ils sont d-connectés.

X est un réseau bayésien par rapport à G si, pour deux nœuds u , v :

où Z est un ensemble qui d -sépare u et v . (La couverture de Markov est l'ensemble minimal de nœuds qui d -sépare le nœud v de tous les autres nœuds.)

Bien que les réseaux bayésiens soient souvent utilisés pour représenter des relations causales , cela n'est pas forcément le cas : une arête dirigée de u vers v ne nécessite pas que X _v soit causalement dépendante de X _u . Ceci est démontré par le fait que les réseaux bayésiens sur les graphes :

sont équivalentes : c'est-à-dire qu'elles imposent exactement les mêmes exigences d'indépendance conditionnelle.

Un réseau causal est un réseau bayésien dont l'exigence est que les relations soient causales. La sémantique supplémentaire des réseaux causaux spécifie que si un nœud X est activement amené à se trouver dans un état donné x (une action écrite comme do( X = x )), alors la fonction de densité de probabilité change pour celle du réseau obtenu en coupant les liens des parents de X à X , et en définissant X sur la valeur provoquée x . En utilisant cette sémantique, l'impact des interventions externes à partir des données obtenues avant l'intervention peut être prédit.

En 1990, alors qu'il travaillait à l'université de Stanford sur de grandes applications bioinformatiques, Cooper a prouvé que l'inférence exacte dans les réseaux bayésiens est NP-difficile . Ce résultat a incité à rechercher des algorithmes d'approximation dans le but de développer une approximation traitable de l'inférence probabiliste. En 1993, Paul Dagum et Michael Luby ont prouvé deux résultats surprenants sur la complexité de l'approximation de l'inférence probabiliste dans les réseaux bayésiens. Premièrement, ils ont prouvé qu'aucun algorithme déterministe traitable ne peut approximer l'inférence probabiliste à une erreur absolue ɛ < 1/2 près. Deuxièmement, ils ont prouvé qu'aucun algorithme randomisé traitable ne peut approximer l'inférence probabiliste à une erreur absolue ɛ < 1/2 près avec une probabilité de confiance supérieure à 1/2.

À peu près au même moment, Roth a prouvé que l'inférence exacte dans les réseaux bayésiens est en fait #P-complète (et donc aussi difficile que de compter le nombre d'affectations satisfaisantes d'une formule de forme normale conjonctive (CNF)) et que l'inférence approximative dans un facteur 2 ^{n 1− ɛ} pour chaque ɛ > 0, même pour les réseaux bayésiens à architecture restreinte, est NP-difficile.

En termes pratiques, ces résultats de complexité suggéraient que si les réseaux bayésiens étaient des représentations riches pour les applications d'IA et d'apprentissage automatique, leur utilisation dans de grandes applications du monde réel devrait être tempérée soit par des contraintes structurelles topologiques, telles que les réseaux bayésiens naïfs, soit par des restrictions sur les probabilités conditionnelles. L'algorithme de variance bornée développé par Dagum et Luby a été le premier algorithme d'approximation rapide prouvable à approximer efficacement l'inférence probabiliste dans les réseaux bayésiens avec des garanties sur l'approximation des erreurs. Cet algorithme puissant nécessitait que la restriction mineure sur les probabilités conditionnelles du réseau bayésien soit limitée à zéro et à un par où était un polynôme quelconque du nombre de nœuds du réseau, .

Parmi les logiciels notables pour les réseaux bayésiens, on peut citer :

• Encore un échantillonneur Gibbs (JAGS) – Alternative open source à WinBUGS. Utilise l'échantillonnage Gibbs.
• OpenBUGS – Développement open source de WinBUGS.
• SPSS Modeler – Logiciel commercial qui inclut une implémentation pour les réseaux bayésiens.
• Stan (logiciel) – Stan est un package open source permettant d'obtenir une inférence bayésienne à l'aide de l'échantillonneur No-U-Turn (NUTS), une variante de l'Hamiltonian Monte Carlo.
• PyMC – Une bibliothèque Python implémentant un langage intégré spécifique au domaine pour représenter les réseaux bayésiens et une variété d'échantillonneurs (y compris NUTS)
• WinBUGS – L'une des premières implémentations informatiques des échantillonneurs MCMC. N'est plus maintenu.

Le terme réseau bayésien a été inventé par Judea Pearl en 1985 pour souligner :

• la nature souvent subjective des informations saisies
• le recours au conditionnement de Bayes comme base de mise à jour des informations
• la distinction entre les modes de raisonnement causal et probant

À la fin des années 1980, le Probabilistic Reasoning in Intelligent Systems de Pearl et le Probabilistic Reasoning in Expert Systems de Neapolitan ont résumé leurs propriétés et les ont établis comme un domaine d'étude.