Introduction aux Réseaux Bayésiens

Introduction aux Réseaux Bayésiens

• Alexandre Aussem est chercheur à l'Université Lyon 1, spécialisé en apprentissage et extraction de connaissances (LIESP).
• Son thème de recherche porte sur l'apprentissage et l'extraction de connaissances.

Modélisation de l'Incertain

• La représentation exhaustive des distributions multidimensionnelles est complexe, car le nombre de paramètres augmente exponentiellement avec le nombre de variables aléatoires.
• Une solution, apparue au début des années 1990, est l'utilisation de modèles de distributions représentés sous forme de graphes : les modèles graphiques.

Modèles Graphiques

• Ce sont des modèles probabilistes innovants reposant sur une représentation graphique des variables aléatoires.
• L'idée est de prendre en compte les dépendances et indépendances conditionnelles entre les variables.
• L'objectif est de représenter des distributions multidimensionnelles de grande taille en évitant l'explosion combinatoire.

Modèles Graphiques : Réseaux Bayésiens vs Champs de Markov

• Les Réseaux Bayésiens utilisent une représentation asymétrique des dépendances, ce qui est approprié pour modéliser des relations causales (ex. : diagnostic).
• Les Champs de Markov utilisent une représentation symétrique des dépendances et sont souvent utilisés pour modéliser des dépendances spatiales (ex : analyse d'images).

Réseaux Bayésiens

• Les Réseaux Bayésiens permettent de représenter et d'encoder de manière compacte les distributions conjointes de variables aléatoires.
• Ils exploitent les dépendances et les indépendances conditionnelles pour éliminer les paramètres superflus.
• Si A et B sont indépendants, P(A,B)=P(A)P(B).
• Si A et B sont indépendants conditionnellement à C, P(A,B|C)=P(A|C)P(B|C).
• Les Réseaux Bayésiens reposent sur l'utilisation de Graphes Acycliques Dirigés (DAG).
• Les nœuds du DAG représentent les variables aléatoires.
• Les arcs représentent les relations causales potentielles entre les variables.
• L'absence d'arc entre deux variables signifie une indépendance conditionnelle.

Tables de probabilités

• Chaque nœud du réseau stocke une table de probabilités conditionnelles locale, P(X|Pa), pour toutes les configurations des parents Pa du nœud X.

Les Réseaux Bayésiens (propriétés)

• On dit qu'un couple {G,P} est un Réseau Bayésien si chaque variable X est indépendante de ses non-descendantes conditionnellement à ses parents dans le DAG G.
• Cette propriété permet de factoriser la loi jointe P(X1, ..., Xn) = Πi=1n P(Xi|Pa₁).
• Il suffit de stocker les valeurs de P(X|Pa) pour toutes les valeurs de X et les configurations possibles des parents Pa.

Les Réseaux Bayésiens (Différents types de chaînes)

• Plusieurs types de chaînes de dépendances entre variables sont possibles, y compris une connexion convergente.

Exemple Illustratif

• Un exemple de DAG (Directed Acyclic Graph) est illustré avec la décomposition de la probabilité conjointe, P(F,C,B,L,H) = P(F|B,L)P(C|L)P(B|H)P(L|H)P(H).
• L'exemple illustre la décomposition de la loi jointe impliquée par la structure du graphe.

Exemple Illustratif (Continu)

• Un tableau illustre les indépendances conditionnelles dans l'exemple.

Complexité spatiale

• La taille de la mémoire pour la loi conjointe est exponentielle en fonction du nombre de variables.
• La taille de la mémoire du réseau bayésien est linéaire en fonction du nombre de nœuds.

Illustration (exemple)

• Un réseau bayésien est présenté, illustrant des indépendances et dépendances conditionnelles entre variables (ex: visite en Asie vs. maladie).

Equivalence de Markov

• Des DAG identiques peuvent encoder les mêmes indépendances conditionnelles.
• Ceci forme une classe d'équivalence et rend impossible la distinction entre les modèles à partir des données.

La causalité

• Le but est d'identifier les causes des phénomènes observés.
• La causalité est une notion complexe soumise à des controverses.
• Une définition opérationnelle : une manipulation d'une variable X qui modifie la distribution d'une variable Y suggère que X cause Y sous une hypothèse de corrélation entre X et Y.

Corrélation vs Causalité

• Des exemples illustrent comment la corrélation n'implique pas nécessairement la causalité.

La Causalité (Exemples)

• Différentes illustrations de cas problématiques en causalité (ex : maladie, médicament, produit X).

Contraintes sur le graphe

• La d-séparation est un critère pour caractériser les contraintes d'indépendance dans un DAG.
• La d-séparation est un outil indispensable pour comprendre comment les liens dans un graphe affectent les dépendances conditionnelles

D-séparation

• Une chaîne dans un graphe est dite ouverte si toutes les nœuds sur la chaîne sont ouverts, ce qui permet aux informations de passer.
• Si un nœud est bloqué, la chaîne est fermée, et les informations de passer.
• L'information qu'apporte X sur Y est la somme des flots d'information sur toutes les chaînes ouvertes entre X et Y.

D-séparation (Continuité)

• Formellement, une chaîne entre X et Y est fermée par un ensemble de nœuds Z si sur cette chaîne il existe un nœud W tel que les conditions sont remplies.
• Les nœuds X et Y sont d-séparés par Z dans le graphe G si toutes les chaînes entre X et Y sont fermées par Z.
• Il y a un parallèle entre l'algorithmique des graphes et les indépendances conditionnelles dans un DAG

Illustration (Réseau de la dyspnée)

• Un exemple de réseau bayésien pour diagnostiquer la dyspnée est présenté.

Inférence&Diagnostic

• Les informations observées/bruitées permettent d'inférer les connaissances (ex: P(D|C,B)).
• La représentation graphique permet aux non-spécialistes (ex: médecins) de visualiser les connaissances.
• Les requêtes probabilistes (ex: probabilité d'une maladie sachant les symptômes) sont autorisées.
• Le système peut hiérarchiser les diagnostics en fonction des probabilités a posteriori.

Schémas d'Inférence

• Des schémas (diagrammatique) illustrent différents types d'inférences causales et diagnostiques.
• Les ensembles de variables peuvent créer des problèmes de complexité (NP-difficile).

100 observations (Données)

• Un ensemble de données d'observations est présenté (variables A, B, C et D).

Illustration: Diagnostic Médical

• Un exemple de réseau bayésien, l'illustrant, est présenté.

Comment faire l'apprentissage du modèle ?

• Construction du graphe causal : détermination/apprentissage à partir de données ou experts.
• Apprentissage des tables de probabilités conditionnelles (approche fréquentielle).
• Validation du modèle (avec des experts ou des analyses statistiques).
• Construction de l'interface utilisateur du modèle.

Comment faire un diagnostic ?

• Un exemple concret de simulation, illustré par un diagramme de réseau bayésien, affiche comment des observations spécifiques conduisent à un diagnostic possible.

Apprentissage des RB

• L'apprentissage (inductif) de la structure à partir des données est NP-difficile, car la taille de l'espace des DAG est exponentielle.
• Simplement apprendre les tables de probabilités conditionnelles est polynomial/facile.
• L'inférence exacte dans un RB est NP-difficile ; mais des méthodes d'approximation existent.

Apprentissage du DAG

• Différentes familles de méthodes d'apprentissage du DAG existent.
• Méthodes basées sur les contraintes d'indépendance (déterministes et rapides).
• Méthodes basées sur des scores qui sont influencées par une probabilité a priori sur l'arbre (sujette à minima locaux).

Inférence

• Utilisation de méthodes d'envoie de messages asynchrones pour l'inférence (dans le cas où le DAG est un arbre).
• Utilisation de la technique de cut-set conditioning pour simplifier le problème d'inférence.
• L'algorithme de l'arbre de jonction et des méthodes d'approximation (échantillonnage de Gibbs) peuvent également être utilisés.

Arbre de jonction

• L'algorithme de l'arbre de jonction permet de transformer un graphe complexe en un arbre couvrant minimal pour faciliter l'inférence.
• Les techniques de moralisation, de triangulation et d'extraction de cliques font partie des étapes de la construction d'un arbre de jonction.

Applications des RB

• Les applications des Réseaux Bayésiens sont diverses, couvrant différents domaines comme la biologie, la santé, l'épidémiologie, la finance, la vision par ordinateur, le diagnostic de pannes, la science des données, le traitement du langage et bien d'autres.

Application à la sélection de variables

• Sélection de variables pertinentes dans des ensembles de données avec des milliers de variables discrètes.
• Détermination de la frontière de Markov d'une variable ciblée pour déterminer un sous-ensemble minimal de variables qui rendent le reste des variables indépendantes de la variable cible.
• Définition de la frontière de Markov.

Markov Boundary

• Définition de la frontière de Markov comme un ensemble minimal de variables qui rend le reste des variables indépendantes de la variable cible.
• Théorème reliant la frontière de Markov à la condition de fidélité pour les Graphes Acycliques Dirigés (DAG).

Faithfulness

• Présente le concept de "faithfulness" et pose la question : que se passe-t-il si une variable disparaît du graphe ?

Illustration

• Un exemple illustre comment l'observation d'une variable peut rendre d'autres variables dépendantes dans un contexte réel (ex: maladie).

Large Markov boundaries

• Présentation de l'importance des définitions et des concepts pour des problèmes plus complexes en termes de nombre de variables.

Constraint-based MB discovery

• Introduction des méthodes basées sur les contraintes pour automatiser la découverte de la frontière de Markov.
• Ces méthodes permettent de détecter des relations d'indépendance sans avoir besoin de construire tout le réseau bayésien au préalable.

Etude épidémiologique

• Présentation d'une étude épidémiologique avec ses variables et diagramme

Incremental methods

• Algorithme IAMB pour l'apprentissage incrémental de la frontière de Markov.
• Décrit comment les positives/négatives sont ajoutées/retirées à/de la frontière de Markov.

Divide-and-conquer methods

• Deux algorithmes, MMPC & MMMB, pour l'apprentissage de la frontière de Markov par une méthode de décomposition-domination.
• On y voit des aspects d'itérations et de vérifications pour la sélection de variables.