Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

CNAM Paris - RCP209 25/09/2013 M. Crucianu 1 25 septembre 2013 RCP209 1 Michel

CNAM Paris - RCP209 25/09/2013 M. Crucianu 1 25 septembre 2013 RCP209 1 Michel Crucianu http://cedric.cnam.fr/~crucianm/ml.html Apprentissage, réseaux de neurones et modèles graphiques Chapitre 8 : Introduction aux réseaux bayesiens 25 septembre 2013 RCP209 2 Contenu du chapitre Qu’est-ce qu’un réseau bayesien ? Inférence dans les réseaux bayesiens Méthodes exactes Méthodes approximatives Apprentissage des réseaux bayesiens CNAM Paris - RCP209 25/09/2013 M. Crucianu 2 25 septembre 2013 RCP209 3 Qu’est-ce qu’un réseau bayesien ? Réseau bayesien = 1. Graphe orienté acyclique (DAG) Nœuds : variables aléatoires (continues, booléennes…) Arcs orientés : dépendances directes probabilistes + 2. Probabilités conditionnelles Différentes interprétations et appellations correspondantes : réseaux de croyances, réseaux de causalité, modèles génératifs... Membres de la famille plus vaste des modèles graphiques, qui inclut aussi les graphes non orientés (champs de Markov) et mixtes (exemple issu de [Cha91]) Famille absente Indigestion Lumière allumée Chien dehors Aboiement 25 septembre 2013 RCP209 4 Exemple simple (notation : fa signifie FA = vrai, ¬fa signifie FA = faux) Famille absente (fa) Indigestion (in) Lumière allumée (la) Chien dehors (cd) Aboiement (ab) P(la|fa) = 0,6 P(la|¬fa) = 0,05 P(ab|cd) = 0,7 P(ab|¬cd) = 0,01 P(cd|fa,in) = 0,99 P(cd|fa,¬in) = 0,90 P(cd|¬fa,in) = 0,97 P(cd|¬fa,¬in) = 0,3 a priori : P(fa) = 0,15 a priori : P(in) = 0,01 (exemple issu de [Cha91]) CNAM Paris - RCP209 25/09/2013 M. Crucianu 3 25 septembre 2013 RCP209 5 Quelques possibilités d’utilisation Déterminer des probabilités a posteriori Exemple (prédiction) : sachant que fa & ¬in →P(ab|fa,¬in) = ? Exemple (diagnostic) : sachant que ab & ¬la →P(fa|ab,¬la) = ? Déterminer l’explication la plus vraisemblable Exemple : sachant que ab, qui de fa et in est la plus probable ? Et si en plus ¬la ? Prise de décision Exemple : pour réduire l’ambiguïté concernant fa, il vaut mieux se renseigner sur la ou sur ab ? 25 septembre 2013 RCP209 6 Connexion linéaire L’ignorance de l’état du nœud intermédiaire CD (cd ou ¬cd) lie les deux autres nœuds : P(AB|IN) ≠P(AB) La connaissance de l’état du nœud intermédiaire CD (cd ou ¬cd) sépare les deux autres nœuds (le chemin est bloqué par l’évidence) : P(AB|IN,CD) = P(AB|CD) Indigestion Chien dehors Aboiement (on ignore le reste du réseau) (si on sait que Chien dehors, alors connaître Indigestion n’apporte rien à l’évaluation de la probabilité de Aboiement) CNAM Paris - RCP209 25/09/2013 M. Crucianu 4 25 septembre 2013 RCP209 7 Connexion divergente L’ignorance de l’état du nœud intermédiaire FA (fa ou ¬fa) lie les deux autres nœuds : P(CD|LA) ≠P(CD) La connaissance de l’état du nœud intermédiaire FA (fa ou ¬fa) sépare les deux autres nœuds (le chemin est bloqué par l’évidence) : P(CD|LA,FA) = P(CD|FA) Famille absente Lumière allumée Chien dehors (si on sait que Famille absente, alors connaître l’état de la lumière n’apporte rien à l’évaluation de la probabilité de Chien dehors) 25 septembre 2013 RCP209 8 Connexion convergente L’ignorance de l’état du nœud intermédiaire CD (cd ou ¬cd) sépare les deux autres nœuds : P(FA|IN) = P(FA) La connaissance de l’état du nœud intermédiaire CD (cd ou ¬cd) lie les deux autres nœuds : P(FA|CD,IN) ≠P(FA|CD) Famille absente Indigestion Chien dehors (si on sait que Chien dehors, alors apprendre qu’il n’a pas d’indigestion rend plus probable Famille absente) CNAM Paris - RCP209 25/09/2013 M. Crucianu 5 25 septembre 2013 RCP209 9 D-dépendance, D-séparation Un chemin (non orienté) de la variable (nœud) A à C est une d-dépendance par rapport à un ensemble de variables E si, pour tout nœud B situé sur ce chemin, le chemin est linéaire ou divergent en B et B n’est pas un membre de E ou le chemin est convergent en B et soit B, soit un de ses descendants est dans E Deux variables A et C sont d-séparées par un ensemble de variables E s’il n’y a pas de d-dépendance par rapport à E entre elles 25 septembre 2013 RCP209 10 Décomposition de la distribution jointe Pour toute distribution jointe et toute numérotation des variables, En utilisant la notion de d-séparation et un ordonnancement des nœuds on peut montrer que, pour un réseau bayesien, Dans notre exemple : P(FA,IN,LA,CD,AB) = = P(FA) ⋅P(IN) ⋅ ⋅P(LA|FA) ⋅ ⋅P(CD|FA,IN) ⋅ ⋅P(AB|CD) ( ) ( ) ( ) ∏ = = n i i i n V V P V V P 1 1 parents , ,K ( ) ( ) ∏ = − = n i i i n V V V P V V P 1 1 1 1 , , , , K K Famille absente Indigestion Lumière allumée Chien dehors Aboiement 1 2 3 4 5 CNAM Paris - RCP209 25/09/2013 M. Crucianu 6 25 septembre 2013 RCP209 11 Explication de l’exemple Sans tenir compte de la structure du réseau, avec la numérotation indiquée on peut écrire P(FA,IN,LA,CD,AB) = P(FA) ⋅P(IN|FA) ⋅P(LA|FA,IN) ⋅ ⋅P(CD|FA,IN,LA) ⋅P(AB|FA,IN,LA,CD) Or, P(IN|FA) = P(IN) car le nœud convergent CD ne fait pas partie de la condition P(LA|FA,IN) = P(LA|FA) P(CD|FA,IN,LA) = P(CD|FA,IN) P(AB|CD,FA,IN,LA) = P(AB|CD) Famille absente Indigestion Lumière allumée Chien dehors Aboiement 1 2 3 4 5 25 septembre 2013 RCP209 12 Inférence dans un RB Inférence : observations (évidence) →distribution sur les variables non directement observées Dans un cas général, le problème est NP-complet ! Méthodes Exactes Complexité linéaire pour les arbres Complexité supérieure en présence de boucles (non orientées) Approximatives Échantillonnage Méthodes variationnelles Propagation CNAM Paris - RCP209 25/09/2013 M. Crucianu 7 25 septembre 2013 RCP209 13 Méthode exacte pour les arbres Méthode basée sur « l’échange de messages », introduite dans [Pea86] Caractéristiques importantes d’un arbre Chemin unique entre 2 nœuds, quels qu’ils soient Aucune connexion convergente Notations employées dans la suite Variables (nœuds) : A, B, C, … Valeurs des variables : A1, A2, … Évidence (données connues) : D Probabilités dynamiques (conditionnées par l’évidence) : Be(Bi) = P(Bi|D) (belief ou croyance : éviter la confusion avec P(Bi)) B A R C F G 25 septembre 2013 RCP209 14 Séparation ancêtres – successeurs On note par DB – l’évidence présente dans les descendants de B et par DB + l’évidence présente dans le reste de l’arbre P(Bi|DB +,DB –) = P(DB +,DB –|Bi) P(Bi) / P(DB +,DB –) = = P(DB –|Bi) P(Bi|DB +) P(DB +) / P(DB +,DB –) = = α P(DB –|Bi) P(Bi|DB +) (où α = P(DB +) / P(DB +,DB –)) Donc Be(Bi) = α P(DB –|Bi) P(Bi|DB +) = α ⋅ λ(Bi) ⋅ π(Bi) avec π(Bi) = P(Bi|DB +) : contribution causale des ancêtres, λ(Bi) = P(DB –|Bi) : contribution de diagnostic des descendants B A R C DB – DB + F G CNAM Paris - RCP209 25/09/2013 M. Crucianu 8 25 septembre 2013 RCP209 15 Calcul composante « successeurs » L’évidence présente dans DB – est à son tour composée de DB 1–, …, DB m–, pour les m descendants directs de B Comme B sépare ces sous-arbres, λ(Bi) = P(DB –|Bi) = ∏k P(DB k–|Bi) Si F est le k-ième descendant direct de B, alors P(DB k–|Bi) = ∑j P(DF –|Bi,Fj) P(Fj|Bi) or, P(DF –|Bi,Fj) = P(DF –|Fj) = λ(Fj) et donc P(DB k–|Bi) = ∑j P(Fj|Bi) λ(Fj) On notera P(DB k–|Bi) par λk(Bi) B A R C DB – F G 25 septembre 2013 RCP209 16 Calcul composante « ancêtres » π(Bi) = P(Bi|DB +) = ∑j P(Bi|Aj,DB +) P(Aj|DB +) Si A est l’unique parent direct de B, alors P(Bi|Aj,DB +) = P(Bi|Aj) Aussi, pour A on peut écrire P(Aj|DB +) = α P(Aj|DA +) ∏k λk(Aj) où λk(Aj) = P(DA k–|Aj), pour le k-ième parmi les m frères de B On obtient donc π(Bi) = β ∑j P(Bi|Aj) π(Aj) ∏k λk(Aj) On notera π(Ai) ∏l≠B λl(Ai) par πB(Ai) B A R C DB + F G CNAM Paris - RCP209 25/09/2013 M. Crucianu 9 25 septembre 2013 RCP209 17 Mécanisme de propagation Calculs réalisés pour chaque nœud (générique : B) : 1. λ(Bi) = ∏descendants de B λF((descendant k de B)i) 2. Propagation vers l’unique ascendant A, pour tout i, de λB(Ai) = ∑j P(Bj|Ai) λ(Bj) … (attente vague descendante) 3. π(Bi) = β ∑j P(Bi|Aj) πB(Aj) (A étant l’unique parent de B) 4. Propagation vers le k-ième descendant (ici F), pour tout i, de πF(Bi) = π(Bi) ∏l≠k λl(Bi) 5. Calcul croyance : Be(Bi) = α λ(Bi) π(Bi) B A R C F G 25 septembre 2013 RCP209 18 Mécanisme de propagation (2) Initialisations : Nœud d’évidence (donnée), valeur i observée : π(nœudi) = λ(nœudi) = 1, π(nœudj) = λ(nœudj) = 0 pour j ≠i Racine : π(racine) = P(racine) (a priori) Feuille : λ(feuillei) = 1 Propagation uploads/Ingenierie_Lourd/ apprentissage-reseaux-de-neurones-et-modeles-graphiques-contenu-du-chapitre 1 .pdf