Réseau bayésien

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Un réseau bayésien est en informatique et en statistique un modèle graphique probabiliste représentant des variables aléatoires sous la forme d'un graphe orienté acyclique. Intuitivement, ils sont à la fois :

  1. des modèles de représentation des connaissances ;
  2. des « machines à calculer » les probabilités conditionnelles.

Pour un domaine donné (par exemple médical), on décrit les relations causales entre variables d'intérêt par un graphe. Dans ce graphe, les relations de cause à effet entre les variables ne sont pas déterministes, mais probabilisées. Ainsi, l'observation d'une cause ou de plusieurs causes n'entraîne pas systématiquement l'effet ou les effets qui en dépendent, mais modifie seulement la probabilité de les observer.

L'intérêt particulier des réseaux bayésiens est de tenir compte simultanément de connaissances a priori d'experts (dans le graphe) et de l'expérience contenue dans les données.

Les réseaux bayésiens sont surtout utilisés pour le diagnostic (médical et industriel), l'analyse de risques, la détection des spams et le data mining.

Intuition[modifier | modifier le code]

Un exemple très simple dans la modélisation des risques[modifier | modifier le code]

Un opérateur travaillant sur une machine risque de se blesser s’il l’utilise mal. Ce risque dépend de l’expérience de l’opérateur et de la complexité de la machine. « Expérience » et « Complexité » sont deux facteurs déterminants de ce risque (fig. 1).

Bien sûr, ces facteurs ne permettent pas de créer un modèle déterministe. Quand bien même l’opérateur serait expérimenté et la machine simple, un accident reste possible. D’autres facteurs peuvent jouer : l’opérateur peut être fatigué, dérangé, etc. La survenance du risque est toujours aléatoire, mais la probabilité de survenance dépend des facteurs identifiés.

La figure 1 ci-dessous représente la structure de causalité de ce modèle (graphe).

Fig. 1 : structure de causalité.

La figure 2 représente la probabilisation de la dépendance : on voit que la probabilité d'accident augmente si l'utilisateur est peu expérimenté ou la machine complexe.

Fig. 2 : probabilité d'accident en fonction de la complexité de la machine et de l'expérience de l'utilisateur (pourcentages).

On voit ici comment intégrer des connaissances d'expert (les facteurs déterminants) et des données (par exemple, la table de probabilité d'accident en fonction des déterminants peut venir de statistiques).

Construction de réseaux bayésiens[modifier | modifier le code]

Construire un réseau bayésien, c'est donc :

  1. définir le graphe du modèle ;
  2. définir les tables de probabilité de chaque variable, conditionnellement à ses causes.

Le graphe est aussi appelé la « structure » du modèle, et les tables de probabilités ses « paramètres ». Structure et paramètres peuvent être fournis par des experts, ou calculés à partir de données, même si en général, la structure est définie par des experts et les paramètres calculés à partir de données expérimentales.

Utilisation d'un réseau bayésien[modifier | modifier le code]

L'utilisation d'un réseau bayésien s'appelle « inférence ». Le réseau bayésien est alors véritablement une « machine à calculer des probabilités conditionnelles ». En fonction des informations observées, on calcule la probabilité des données non observées. Par exemple, en fonction des symptômes d'un malade, on calcule les probabilités des différentes pathologies compatibles avec ces symptômes. On peut aussi calculer la probabilité de symptômes non observés, et en déduire les examens complémentaires les plus intéressants.

Définition formelle[modifier | modifier le code]

Loi de probabilité jointe[modifier | modifier le code]

Il existe plusieurs façons de définir un réseau bayésien. La plus simple exprime la loi de probabilité jointe sur l'ensemble des variables aléatoires modélisées dans le réseau. Un réseau bayésien est un graphe orienté acyclique G = (V, E) avec V l'ensemble des nœuds du réseaux et E l'ensemble des arcs. À chaque nœud x appartenant à V du graphe est associé la distribution de probabilité conditionnelle suivante :

P(x \,\big|\, \operatorname{pa}(x))\, où pa(x) représente les parents immédiats de x dans V

L'ensemble V est donc un ensemble de variables aléatoires discrètes. Chaque nœud de V est conditionnellement indépendant de ses non-descendants, étant donné ses parents immédiats. Il est ainsi possible de factoriser les distributions de probabilité conditionnelles sur l'ensemble des variables en en faisant le produit[1],[2] :

\mathrm P(V) = \prod_{x \in V} \mathrm P \big(x \,\big|\,  \operatorname{pa}(x) \big)

Ce résultat est parfois noté JPD, pour distribution de probabilité jointe. Cette définition peut être retrouvée dans l'article Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning, où Judea Pearl introduit le terme « réseau bayésien »[3].

Dans l'exemple donné figure 1, la probabilité jointe est égale à :

P(experience\,operateur) \times P(complexite\,machine) \times P(accident \,\big|\, experience\,operateur, complexite\,machine).

Propriété de Markov globale[modifier | modifier le code]

Une autre façon de définir un réseau bayésien est d'évaluer si un graphe orienté acyclique G = (V, E) vérifie la propriété de Markov globale (dite orientée ici, en raison de la nature de G) étant donné une loi de probabilité P sur l'ensemble des variables V. Soit X, Y, S trois sous-ensemble de V, tels que X et Y sont d-séparés par S, noté (X|S|Y) : la propriété de Markov globale exprime l'indépendance conditionnelle entre X et Y, c'est-à-dire que X est indépendant de Y conditionnellement à S. Formellement, la propriété dans un graphe orienté s'énonce ainsi[4] :

\forall\,X, Y, S \subset V disjoints, (X | S | Y) \Rightarrow X \perp\!\!\!\perp Y \,\big|\, S

Il convient de définir la d-séparation, pour « séparation dirigée » ou « séparation orientée », dans un graphe orienté. Les sous-ensembles X et Y sont d-séparés par S si et seulement si toute chaîne de nœuds de X à Y est « bloquée » par S. Pour trois nœuds x appartenant à X, y appartenant à Y et s appartenant à S, une chaîne est bloquée dans les deux cas suivants[5] :

  • soit la chaîne contient une séquence x \rightarrow s \rightarrow y ou x \leftarrow s \rightarrow y ;
  • soit la chaîne contient une séquence x \rightarrow z \leftarrow y où z n'appartient pas à S et aucun descendant de z appartient à S.

L'intuition est que S « bloque » l'information entre X et Y.

L'indépendance conditionnelle enfin, notée ci-dessus X \perp\!\!\!\perp Y \,\big|\, S, exprime que X ne dépend pas de Y étant donné S. Formellement[6] :

X \perp\!\!\!\perp Y \,\big|\, S si et seulement si P(X \,\big|\, Y, S) = P(X \,\big|\, S) et P(Y \,\big|\, X, S) = P(Y \,\big|\, S)

Dans l'exemple donné plus haut (figure 1), on peut écrire que l'expérience de l'opérateur est indépendante de la complexité de la machine, mais qu'elle est conditionnellement indépendante de la complexité de la machine étant donné le risque d'accident.

En conclusion, un graphe orienté acyclique G = (V, E) est un réseau bayésien si et seulement s'il vérifie la propriété de Markov globale orientée étant donné une loi de probabilité P sur l'ensemble des variables V.

Inférence[modifier | modifier le code]

Définition et complexité[modifier | modifier le code]

L'inférence dans un réseau bayésien est le calcul des probabilités a posteriori dans le réseau, étant donné des nouvelles informations observées. Il s'agit d'un problème de calcul car, grâce aux opérations sur les probabilité et au théorème de Bayes, toutes les probabilités a posteriori possibles dans un réseau peuvent être calculées[7]. Ainsi, étant donné un ensemble d'évidences (de variables instanciées) Y, le problème de l'inférence dans G=(V, E) est de calculer P(X | Y) avec X \subset V, Y \subset V[8],[9]. Si Y est vide (aucune évidence), cela revient à calculer P(X). Intuitivement, il s'agit de répondre à une question de probabilité sur le réseau.

Bien que le problème d'inférence dépende de la complexité du réseau (plus la topologie du réseau est simple, plus l'inférence est facile), il a été montré par G. F. Cooper en 1987 que dans le cas général, il s'agit d'un problème NP-difficile. Par ailleurs, Dagum et Luby ont également montré en 1993 que trouver une approximation d'un problème d'inférence dans un réseau bayésien est également NP-difficile. Suite à ces résultats, deux grandes catégories d'algorithmes d'inférence viennent naturellement : les algorithmes d'inférence exacte, qui calculent les probabilités a posteriori généralement en temps exponentiel, et les heuristiques qui fournissent plutôt une approximation des distributions a posteriori, mais avec une complexité computationnelle moindre[10]. Plus rigoureusement, les algorithmes d'inférence exacte fournissent un résultat et la preuve que le résultat est exact, tandis que les heuristiques fournissent un résultat sans preuve de sa qualité (c'est-à-dire que selon les instances, une heuristique peut aussi bien trouver la solution exacte qu'une approximation très grossière).

La classification du problème d'inférence comme NP-difficile est donc un résultat primordial. Pour établir sa preuve, Cooper considère le problème général P(X=x)>0 : la probabilité que la variable X prenne la valeur x est-elle supérieure à zéro dans un réseau bayésien ? Il s'agit d'un problème de décision (la réponse est oui ou non). Cooper montre tout d'abord que si le problème P(X=x)>0 est NP-complet, alors P(X=x) est NP-difficile, et donc le problème de l'inférence dans les réseaux bayésiens est NP-difficile. Pour prouver la NP-complétude de P(X=x)>0, il réduit polynomialement le problème 3-SAT (un problème NP-complet classique) au problème P(X=x)>0 : premièrement, il montre que la construction d'un réseau bayésien à partir d'une instance de 3-SAT, notée C, peut être faite avec une complexité polynomiale ; ensuite, il montre que C est satisfaite si et seulement si P(X=x)>0 est vrai. Il en résulte que P(X=x)>0 est NP-complet, donc le problème d'inférence d'un réseau bayésien l'est également[9].

Inférence exacte[modifier | modifier le code]

inférence approchée[modifier | modifier le code]

Apprentissage automatique[modifier | modifier le code]

L'apprentissage automatique désigne des méthodes ayant pour but d'extraire de l'information contenue dans des données. Il s'agit de processus d'intelligence artificielle, car ils permettent à un système d'évoluer de façon autonome à partir de données empiriques. Dans les réseaux bayésiens, l'apprentissage automatique peut être utilisé de deux façons : pour estimer la structure d'un réseau, ou pour estimer les tables de probabilités d'un réseau, dans les deux cas à partir de données.

Apprentissage des paramètres[modifier | modifier le code]

Apprentissage de la structure[modifier | modifier le code]

Variantes[modifier | modifier le code]

Réseau bayésien dynamique[modifier | modifier le code]

Article détaillé : Réseau bayésien dynamique.

Un réseau bayésien dynamique ou temporel (souvent noté RBN, ou DBN pour Dynamic Bayesian Network) est une extension d'un réseau bayésien qui permet de représenter l'évolution des variables aléatoires en fonction d'une séquence discrète, par exemple des pas temporels[11]. Le terme dynamique caractérise le système modélisé, et non le réseau qui lui ne change pas. Par exemple, partant du réseau donné en figure 1, le système pourrait être rendu dynamique en exprimant que le risque futur d'accident dépend du risque d'accident passé et présent. L'intuition est qu'au plus des utilisateurs peu expérimentés se succèdent, au plus le risque d'accident augmente ; au contraire, une succession d'utilisateurs expérimentés fait décroitre ce risque dans le temps. Dans cet exemple, la variable « accident » est dite dynamique, temporelle ou persistante.

Formellement, un réseau bayésien dynamique se définit comme un couple (B_1, B_{2d}). B_1 est un réseau bayésien classique représentant la distribution a priori (ou initiale) des variables aléatoires ; dit plus intuitivement, il s'agit du temps 0. B_{2d} est un réseau bayésien dynamique a deux pas de temps décrivant la transition du pas de temps t-1 au pas de temps t, c'est-à-dire P(x_t \,\big|\, x_{t-1}) pour tout nœud x appartenant à V, dans un graphe orienté acyclique G=(V, E) comme introduit plus haut. La probabilité jointe d'un pas de temps s'écrit alors[12],[13] :

P(V_{t} \,\big|\, V_{t-1}) = \prod_{x \in V} P(x_{t} \,\big|\, \operatorname{pa}(x_{t}))\,

Les parents d'un nœud, notés pour mémoire \operatorname{pa}(x_{t}), peuvent ainsi être soit un parent direct dans le réseau au temps t, soit un parent direct au temps t-1.

La loi de probabilité jointe factorisée se calcule en « déroulant » le réseau sur la séquence temporelle, à condition de connaître sa longueur, que l'on va noter ici T. Formellement, si P(V_{0}) est la probabilité jointe du réseau initial B_1, donc au pas de temps 0, on peut écrire[12],[13] :

P(V_{0:T}) = P(V_{0}) \times P(V_{1:T}) = \prod_{x \in V} P(x_{0} \,\big|\, \operatorname{pa}(x_{0})) \times \prod_{t=1}^T \prod_{x \in V} P(x_{t} \,\big|\, \operatorname{pa}(x_{t}))

Un réseau bayésien dynamique respecte ainsi la propriété de Markov, qui exprime que les distributions conditionnelles au temps t ne dépendent que de l'état au temps t-1 dans un processus stochastique. Les réseaux bayésiens dynamiques sont une généralisation des modèles probabilistes de séries temporelles de type modèle de Markov caché, filtre de Kalman[13]...

Classifieur bayésien naïf[modifier | modifier le code]

Article détaillé : Classification naïve bayésienne.

Un classifieur bayésien naïf est un type de classifieur linéaire qui peut au contraire être défini comme une simplification des réseaux bayésiens. Leur structure est en effet composée de seulement deux niveaux : un premier ne comportant qu'un seul nœud, noté par exemple C, et le second plusieurs nœuds ayant pour seul parent C. Ces modèles sont dits naïfs car ils font l'hypothèse que tous les fils sont indépendants entre eux. Soit les fils de C notés F1...Fn, la loi de probabilité jointe d'un classifieur bayésien s'écrit P(C | F1...Fn)[14].

Ces modèles sont particulièrement adaptés pour les problèmes de classification automatique, où C représente les classes possibles non observées d'un domaine et F1...Fn des variables observées caractérisant chaque classe de C[14]. Un exemple serait de trier dans une population les individus en deux classes, sains et malades, en fonction de symptômes observés, comme leur fièvre, etc.

Outils logiciels[modifier | modifier le code]

Logiciels
  • Bayesia (commercial)
  • Elvira (open source)
  • GeNie (gratuit et code propriétaire ; GeNie est une interface graphique pour la bibliothèque SMILE, également gratuite et propriétaire)
  • Hugin (commercial)
  • Netica (commercial)
  • OpenBUGS (open source)
  • ProBayes (commercial)
  • WinBUGS (gratuit)
  • Weka (gratuit et open source)
Bibliothèques
  • Bayesian Network tools in Java (open source, bibliothèque pour JAVA)
  • bnlearn et deal (open source, bibliothèques pour l'apprentissage sous R)
  • Bayes Net Toolbox pour Matlab (code libre pour l'environnement commercial Matlab)
  • Structure Learning Package (package pour l'apprentissage de structure en supplément du Bayes Net Toolbox)
  • SMILE (gratuit et code propriétaire, C++ ou JAVA)
  • Visual Numerics (bibliothèque pour IMSL)

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Références[modifier | modifier le code]

  1. Jean-Jacques Boreux, Éric Parent et Jacques Bernier, Pratique du calcul bayésien, Springer,‎ 2009 (ISBN 9782287996665, lire en ligne), p. 38-39
  2. Naïm et al. 2011, p. 90-91
  3. (en) Judea Pearl, « Bayesian Networks: A Model of Self-Activated Memory for Evidential Reasoning », Proceedings of the 7th Conference of the Cognitive Science Society,‎ 1985, p. 329–334 (lire en ligne)
  4. Naïm et al. 2011, p. 86-87
  5. David Bellot, Fusion de données avec des réseaux bayésiens pour la modélisation des systèmes dynamiques et son application en télémédecine, université Nancy-I,‎ 2002 (lire en ligne), p. 68 (thèse)
  6. Naïm et al. 2011, p. 354-356
  7. Naïm et al. 2011, p. 93-94
  8. (en) Nevin Lianwen Zhang, « A simple approach to Bayesian network computations », Proceedings of the 10th Canadian conference on artificial intelligence,‎ 1994 (lire en ligne)
  9. a et b (en) Gregory F. Cooper, « Probabilistic Inference Using Belief Networks Is NP-Hard », Knowledge Systems Laboratory (report),‎ 1987 (lire en ligne) ; (en) Gregory F. Cooper, « The computational complexity of probabilistic inference using Bayesian belief networks », Artificial Intelligence, vol. 42, no 2-3,‎ mars 1990, p. 393-405 (lire en ligne)
  10. Kjaerulff et Madsen 2007, p. 9
  11. (en) Thomas Dean et Keiji Kanazawa, « A model for reasoning about persistence and causation », Computational Intelligence, vol. 5, no 2,‎ 1989, p. 142-150 (lire en ligne)
  12. a et b (en) Kevin Patrick Murphy, Dynamic Bayesian Networks: Representation, Inference and Learning, université de Californie à Berkeley (lire en ligne), p. 14-15 (thèse)
  13. a, b et c Roland Donat, Philippe Leray, Laurent Bouillaut et Patrice Aknin, « Réseaux bayésiens dynamiques pour la représentation de modèles de durée en temps discret », Journées francophone sur les réseaux bayésiens,‎ 2008 (lire en ligne)
  14. a et b (en) Nir Friedman et Moises Goldszmidt, « Building Classifiers using Bayesian Networks », Proceedings of the thirteenth national conference on artificial intelligence,‎ 1996 (lire en ligne)