Raisonnement probabilistelamontagne/ift17587/modules/module5/réseauxBayesiens.pdfL’approche est impraticable pour les problèmes complexes Autre approche – Pondération de la

1

1

IFT-17587 Concepts avancés pour systèmes intelligents

Luc Lamontagne

Raisonnement probabiliste

2

Plan

Réseaux bayésiens

Inférence dans les réseaux bayésiens

Inférence exacte

Inférence approximative

3

Contexte

Jusqu’à maintenant, nous avons principalement étudié des techniques pour des environnements déterministesQue faire lorsque l’environnement est non déterministe?

Observabilité partielleInformation bruitéeComportement stochastiqueEnvironnement complexe…

Envir__ε…mentInférence

Agent

Effecteurs

Capteurpercepts

actions

4

Quel type d’agent? Un agent doit pouvoir gérer :

L’incertitude lié à l’environnement probabilitéLa qualité de ses décisions utilité

Capteurs

Comment le monde est maintenant?

Quelle action dois-je faire maintenant?

Effecteurs

Agent

Envir___ε…m

ent

État

Comment le monde évolue?

Quel est l’impact de mes actions? Comment sera le mondesi je fais l’action A?

À quel point je vais êtresatisfait dans un tel état?

Utilité

2

5

Agent basé sur l’utilité

Théorie de la décision (ch.16-17)

Raisonnement incertain (ch.13-14)

6

Raisonnement incertain :

Réseaux bayésiensDans cette section, nous étudions les réseaux bayésiens

Basés sur les probabilités – un formalisme éprouvéPermettent de représenter les dépendances entre les variablesDonnent une spécification concise des distributions de probabilités conjointes.

Attaque

Visible

Armé Proche

Audible

Niveau_énergie

Dangereux

7

Réseaux bayésiens :

Notions de probabilitéRévision des concepts de probabilité au chapitre 13

Règle du produit

Règle de bayes

Distributions de probabilités conjointes P(x,y,z)Utile pour faire des inférences Mais peuvent être difficile à calculer en pratique (grande taille)

Conditionnement

Indépendance et indépendance conditionnelle Permettent de réduire les calculs reliés à ces distributions.

( ) ( ) ( ) ( ) ( )aPabPbPbaPbaP ==,

( ) ( ) ( )( )bP

aPbaPbaP =

( ) ( ) ( )∑=z

zPzYPYP

( ) ( )XPYXP = ( ) ( ) ( )YPXPYXP =,8


Syntaxe

Réseau bayésienUn graphe orienté acyclique Chaque nœud annoté d’une table de probabilités conditionnelles.

Plus spécifiquement, il contient:Un ensemble de variables aléatoiresUn ensemble de liens orientés connectant deux nœuds.

S’il y a un lien du nœud X vers Y, on dit que X est le parent de Y.Chaque nœud a une distribution de probabilité conditionnelle

P(Xi | Parents(Xi)) qui quantifie l’effet du parent sur le nœud.

Carie

MalDeDents SondeAccroche

0.15F

0.6V

P(MD)Carie

0.2F

0.7V

P(SA)Carie

0.02

P(Carie)

3

9

Syntaxe des réseaux bayésiens :

Exemple du dentiste

Indépendance :Météo est indépendante des autres variables

Indépendance conditionnelle :MalDeDents et SondeAccroche le sont sachant Carie.Il n’y a aucun lien direct entre MalDeDents et SondeAccroche.

MétéoCarie

MalDeDents SondeAccroche

10


Exemple de l’alarmeVous avez un nouveau système d’alarme à la maison :

Il sonne lorsqu’il y a un cambriolage (Burglary)Il sonne parfois lorsqu’il y a un tremblement de terre (Earthquake)

Vous avez deux voisins qui vous appellent au bureau s’ils entendent l’alarme.

John appelle tout le temps quand il entend l’alarme, mais parfois il confond le téléphone avec l’alarme (JohnCalls).Mary aime écouter de la musique forte et parfois elle n’entend pas l’alarme (MaryCalls).

Sachant qui a appelé : Quelle est la probabilité qu’il y ait un cambriolage ?

11


Exemple de l’alarme

12


Exemple de l’alarmeLa topologie du réseau reflète un ensemble de relations d’indépendances conditionnelles

Bulgary et Earthquake affectent directement la probabilité de déclenchement d’une alarmeLe fait que John ou Mary appelle ne dépend que de l’alarme.

John et Mary ne perçoivent pas directement le cambriolage Ils ne perçoivent pas les tremblements de terre mineursIls ne se consultent pas avant d’appeler

4

13


Exemple de l’alarme

14


Spécification conciseTable de probabilités conditionnelles (TPC)

Pour une variable booléenne Xi avec k parents booléens Elle contient 2k rangés.

Chaque rangée a une probabilité p pour Xi = VraiLa valeur pour Xi = Faux est 1 – p

Si on borne le nombre maximal de parents à kAlors le réseau demande O(n2k) nombres.Linéaire en n, au lieu de O(2n) pour une table complète

Pour notre exemple On a besoin de 10 valeur au lieu de 25 = 32 pour la table complète de probabilité conjointe.

15


SémantiqueUn réseau définit la distribution conjointe complète de probabilités

Correspond au produit des distributions conditionnelles locales :

Exemple:

16


ConstructionIl faut une méthode garantissant qu’une série d’indépendances conditionnelles vérifiées localement induise la sémantique globale requise

Choisir un ordre sur les variables Choisir un ordre sur les variables XX11, , ……,,XXnnPourPour i = 1 i = 1 àà n n FaireFaire

-- Ajouter Ajouter XXii au rau rééseauseau-- SSéélectionner ses parents dans lectionner ses parents dans XX11,, ……, , XXii--11 tels que tels que

PP((XXi i | | ParentsParents((XXii)) = )) = PP((XXi i | | XX11, , ……,,XXii--11))Fin PourFin Pour

Il est préférable d’avoir un modèle causal• C’est-à-dire qu’il est mieux d’ajouter la cause « racine » en premier • Et ensuite les variables qui sont influencées par la cause

5

17


ExempleSupposons que l’on choisit l’ordre B, E, A, M, J

MaryCalls JohnCalls

Alarm

Bulgary Earthquake

18


ExempleSupposons que l’on choisit le mauvais ordre M, J, A, B, E

MaryCalls

JohnCalls

Alarm

Bulgary

Earthquake

P(J|M) = P(J)? P(A|J,M) = P(A|J)? P(A|J,M) = P(A|M)? P(B|A,J,M) = P(B|A) ?P(B|A,J,M) = P(B) ? P(E|B,A,J,M) = P(E|A) ? P(E|B,A,J,M) = P(E|A,B) ?

NonNonNonNon

NonNon

NonNonNonNon

OuiOui

OuiOui

On obtient un réseaux plus complexe avec des probabilités plus difficiles à déterminer.

19


SémantiqueSémantique locale :chaque nœud est conditionnellement indépendant des nœuds qui ne sont pas ses descendants étant donné ses parents.

20


SémantiqueChaque nœud est indépendant des autres sachant sa couverture de Markov (Markov Blanket)

Parent + Enfants + Parents des enfants.

6

21

Sommaire

Les réseaux bayésiens sont une manière naturelle de représenter les dépendances causales.C’est une représentation compact des distributions conjointes de probabilité.Généralement facile à construire.

22


Inférence exacteBut :

Calculer la distribution de probabilité a posteriori d’un ensemble de variables de requêteÉtant donnée un événement observé, c.-à-d. à des variables d’évidence dont les valeurs sont déterminées

L’ensemble complet de variables X: X : variable de questionE: l’ensemble des variables d’évidencee: un événement particulierY: l’ensemble des variables cachées

{ } YEX UUX=

23


Inférence exacte

Une question typique: P(X | e)Dans l’exemple du cambriolage

On pourrait observer l’événement JohnCalls = vrai et MaryCalls = vari.

Par la suite, on pourrait se demander s’il y a eu un cambriolage.

24

Inférence exacte :

Inférence par énumérationLes réseaux bayésiens donnent la représentation complète de la table de distribution conjointe

Alors on peut utiliser la formule suivante (voir chapitre 13)

Si on reprend l’exemple précédent où les variables cachées sont Earthquake et Alarm.

7

25

Inférence exacte :

Inférence par énumérationOn peut réécrire la formule en utilisant les entrées des tables de probabilités conditionnelles du réseau bayésien. Pour Burglary = vrai, on obtient:

En simplifiant, on obtient:

M JA

B E

26

Inférence exacte :

Inférence par énumérationArbre de calcul :

Répétitions

27

Inférence exacte :

Inférence par énumérationEn effectuant les calculs, on obtient:

Si on fait la même chose pour Burglary = false, on obtient:

Même si les deux appellent, il n’y a que 28% des chances qu’il y ait eu un cambriolage.La complexité en temps de l’inférence par énumération est de O(2n).

28

Inférence exacte :

Inférence par énumération

8

29

Inférence exacte :

Élimination de variablesAméliore l’algorithme par énumération en évitant les calculs répétés.La somme est effectuée de la droite vers la gauche.Exemple cambriolage :

Facteurs30

Inférence exacte :

Élimination de variables - Exemple

Pour le facteur M, on enregistre les probabilités, étant donné chaque valeur de a, dans un vecteur à deux éléments.

On fait la même chose pour J.Pour le facteur A, on obtient une matrice de 2 x 2 x 2, fA(A,B,E)

31

Inférence exacte :


Il faut maintenant faire la somme du produit des trois facteurs

La barre sur le A, indique que l’on a fait la somme pour A

La multiplication utilisée est un pointwise product32

Inférence exacte :


Le facteur et la sommation sur E sont calculés de la même manière.

Finalement, on obtient:

9

33

Inférence exacte :

Pointwise productLe pointwise product de deux facteurs f1et f2donne un nouveau facteur f

Les variables sont l’union des variables de f1 et f2.Exemple:

34

Inférence exacte :

Variables inutilesConsidérons: P(J | b)

La somme sur M donne 1Donc M est inutile.

Théorème: Y est inutile sauf si

Ici:

donc, M est inutile.

35

Réseaux bayésiens

Inférence approximativeLes méthodes d’inférences exactes que l’on vient de voir ne sont pas utilisables pour de grands réseaux.C’est pourquoi on considère des approches approximatives.On va voir des algorithmes basés sur l’échantillonnage aléatoire (Monte Carlo) dont la précision va dépendre du nombre d’échantillons.

36

Inférence approximative :

Méthodes d’échantillonnage directe

La forme la plus simple d’échantillonnage aléatoire est de générer des événements sans variable d’évidenceLa distribution de probabilité à partir de laquelle un échantillon pour une variable est choisi est basée sur les valeurs attribuées aux parents.

10

37


Exemple d’échantillonnage directe

38



39



40



11

41



42



43



Résultat = [T, F, T, T]

On répète plusieurs fois pour obtenir un échantillon!

44



12

45

Échantillonnage directe :

Estimer la probabilité d’un événement

On peut estimer la probabilité d’un événement avec la fraction des événements générés aléatoirement qui remplit la condition.Par exemple

Si on génère 1000 échantillons Que pour 511 d’entre eux Rain = trueDonc on peut faire l’estimation suivante :

46


Échantillonnage par rejetUtiliser pour déterminer les probabilités conditionnelles.Méthode:

Génère des échantillons comme la méthode précédenteEnlève tous les échantillons où les variables d’évidence n’ont pas les bonnes valeursEstime la probabilité en comptant parmi les échantillons restants.

47


Échantillonnage par rejet

48


Échantillonnage par rejetSupposons que l’on veut estimer

P(Rain|Sprinkler = true) en utilisant 100 échantillons.

Dans 73 échantillons, Sprinkler = falseIls sont donc rejetés

Pour les 27 échantillons où Sprinkler = true8 ont Rain = true19 ont Rain = false

Donc

13

49


Échantillonnage par rejetProblème de cette méthode

Elle rejette beaucoup d’échantillonsElle génère donc beaucoup d’échantillons inutiles.

Si un grand nombre de variables d’évidenceL’approche est impraticable pour les problèmes complexesAutre approche – Pondération de la vraisemblance

Likelihood weighting

50


Pondération de la vraisemblanceÉvite l’inefficacité de l’échantillonnage par rejet

Génère uniquement des échantillons consistants avec les variables d’évidence

Idée : Fixer les variables d’évidenceÉchantillonner uniquement sur les autres variables Attribuer un poids aux échantillons selon la probabilitéque l’événement survienne en accord avec les évidences.

51

Réseaux bayésiens – Inférence approximative

Pondération de la vraisemblance

, e)

52



w = 1

14

53



w = 154



w = 1

55



w = 1 * 0.156



w = 1 * 0.1

15

57



w = 1 * 0.158



w = 1 * 0.1 * 0.99 = 0.099

59


Pondération de la vraisemblanceL’estimation de la probabilité

La somme pondérée des échantillons où ce qui est recherchée est vrai.

Plus efficace que l’échantillonnage par rejetMais l’efficacité de la méthode se dégrade si le nombre de variables d’évidence augmente, parce que:

La majorité des échantillons vont avoir des petits poidsSeulement une minorité d’échantillons vont avoir pratiquement tout le poids total.

60


Inférence par MCMCAlgorithme Markov Chain Monte Carlo (MCMC)

Génère les événements en faisant un changement aléatoire à l’événement précédent.

L’algorithme maintient donc un état courant oùtoutes les variables ont une valeurs.Pour générer le prochain état:

Choisir une variable qui n’est pas une variable d’évidence.La distribution de cette variable dépend des valeurs des variables dans son Markov Blanket

16

61


Inférence par MCMC

Avec Sprinkler = true et WetGrass = true, il y a quatre états possibles.

62


Inférence par MCMCExemple: si on génère 100 échantillons et que l’on trouve:

31 où Rain = true69 où Rain = false

Donc, l’estimation de la distribution est Normalize(31,69) = (0.31,0.69).

63

ConclusionUn réseau bayésien est un graphe dirigé acyclique

Les nœuds correspondent à des variables aléatoiresChaque nœud a une distribution conditionnelle

Moyen concis de représenter les relations d’indépendance conditionnelleReprésente une distribution conjointe complèteL’inférence revient à calculer la distribution de probabilitéd’un ensemble de variables étant donné un ensemble de variables d’observationsOn peut approximer ce calcul par de l’échantillonnage et les techniques MCMC

Documents

Raisonnement probabilistelamontagne/ift17587/modules/module5/réseauxBayesiens.pdfL’approche est impraticable pour les problèmes complexes Autre approche – Pondération de la