1 Sesión 7: Redes Bayesianas – InferenciaModelos Gráficos Probabilistas L. Enrique Sucar INAOE Sesión 7: Redes Bayesianas – Inferencia [Neapolitan 90]

2 Inferencia en Redes BayesianasIntroducción Propagación en árboles (y poliárboles) Algoritmo de eliminación Propagación en redes multi-conectadas Condicionamiento Simulación Agrupamiento Abducción © L.E. Sucar: MGP - Inferencia RB

3 © L.E. Sucar: MGP - Inferencia RBPropagación de Probabilidades El razonamiento probabilístico o propagación de probabilidades consiste en propagar de los efectos de la evidencia a través de la red para conocer la probabilidad a posteriori de las variables. © L.E. Sucar: MGP - Inferencia RB

4 © L.E. Sucar: MGP - Inferencia RBLa propagación consiste en darle valores a ciertas variables (evidencia), y obtener la probabilidad posterior de las demás variables dadas las variables conocidas (instanciadas). © L.E. Sucar: MGP - Inferencia RB

5 © L.E. Sucar: MGP - Inferencia RBInferencia bayesiana C Causal: C -> H Evidencial: E -> H Mixta: C,E -> H P(H|C) H P(E|H) E © L.E. Sucar: MGP - Inferencia RB

6 © L.E. Sucar: MGP - Inferencia RBTipos de Técnicas Calcular probabilidades posteriores: Una variable, cualquier estructura: algoritmo de eliminación (variable elimination) Cualquier variable, estructuras sencillamente conectadas (árboles, poliárboles): propagación Cualquier variable, cualquier estructura: Agrupamiento (junction tree) Simulación estocástica Condicionamiento © L.E. Sucar: MGP - Inferencia RB

7 © L.E. Sucar: MGP - Inferencia RBTipos de Técnicas Obtener variable(s) de mayor probabilidad dada cierta evidencia – abducción: Abducción total Abducción parcial © L.E. Sucar: MGP - Inferencia RB

8 © L.E. Sucar: MGP - Inferencia RBTipos de Estructuras Redes conectadas en forma sencilla: Árboles Poliárboles Redes multiconectadas: © L.E. Sucar: MGP - Inferencia RB

9 © L.E. Sucar: MGP - Inferencia RBPropagación en Árboles Cada nodo corresponde a una variable discreta, B (B 1, B 2,…, B m) con su respectiva matriz de probabilidad condicional, P(B|A)=P(Bj| Ai) © L.E. Sucar: MGP - Inferencia RB

10 Propagación en ÁrbolesH A I B C D E F G © L.E. Sucar: MGP - Inferencia RB

11 © L.E. Sucar: MGP - Inferencia RBDada cierta evidencia E --representada por la instanciación de ciertas variables-- la probabilidad posterior de cualquier variable B, por el teorema de Bayes: P( Bi | E)=P( Bi ) P(E | Bi) / P( E ) B © L.E. Sucar: MGP - Inferencia RB

12 © L.E. Sucar: MGP - Inferencia RBEvidencia H A I B C D E F G E = {I,F,E} © L.E. Sucar: MGP - Inferencia RB

13 © L.E. Sucar: MGP - Inferencia RBEvidencia Ya que la estructura de la red es un árbol, el Nodo B la separa en dos subárboles, por lo que podemos dividir la evidencia en dos grupos: E-: Datos en el árbol que cuya raíz es B E+: Datos en el resto del árbol © L.E. Sucar: MGP - Inferencia RB

14 © L.E. Sucar: MGP - Inferencia RBEvidencia H E+ A I B C D E F G E- © L.E. Sucar: MGP - Inferencia RB

15 © L.E. Sucar: MGP - Inferencia RBEntonces: P( Bi | E ) = P ( Bi ) P ( E-,E+ | Bi ) / P(E) Pero dado que ambos son independientes y aplicando nuevamente Bayes: P( Bi | E ) = a P ( Bi | E+ ) P(E- | Bi ) Donde a es una constante de normalización © L.E. Sucar: MGP - Inferencia RB

16 © L.E. Sucar: MGP - Inferencia RBDefiniciones: Si definimos los siguientes términos: l (Bi)= P ( E- | Bi) p (Bi)= P (Bi | E+ ) Entonces: P(Bi | E ) = a p (B i) l (B i) © L.E. Sucar: MGP - Inferencia RB

17 © L.E. Sucar: MGP - Inferencia RBDesarrollo En base a la ecuación anterior, se puede integrar un algoritmo distribuido para obtener la probabilidad de un nodo dada cierta evidencia Para ello se descompone el cálculo de cada parte: Evidencia de los hijos (l) Evidencia de los demás nodos (p) © L.E. Sucar: MGP - Inferencia RB

18 Evidencia de los hijos (l)Dado que los hijos son condicionalmente independientes dado el padre: l (Bi) = P ( E- | Bi) = Pk P ( Ek- | Bi) Donde Ek- corresponde a la evidencia del subárbol del hijo k © L.E. Sucar: MGP - Inferencia RB

19 © L.E. Sucar: MGP - Inferencia RBEvidencia hijos H A I B C D E-(D) E E-(E) F G J © L.E. Sucar: MGP - Inferencia RB

20 Evidencia de los hijos (l)Condicionando respecto a los posibles valores de los hijos de B: l (Bi)= Pk [ Sj P ( Ek- | Bi, Sjk) P(Sjk | Bi) ] Donde Sk es el hijo k de B, y la sumatoria es sobre los valores de dicho nodo (teorema de probabilidad total) © L.E. Sucar: MGP - Inferencia RB

21 Evidencia de los hijos (l)Dado que B es condicionalmente independiente de la evidencia dados sus hijos: l (Bi) = Pk [ Sj P ( Ek- | Sjk) P(Sjk | Bi) ] Substituyendo la definción de l: l (Bi)= Pk [ Sj P(Sjk | Bi) l (Sjk)] © L.E. Sucar: MGP - Inferencia RB

22 © L.E. Sucar: MGP - Inferencia RBEvidencia hijos H A I B C D l(D) E l(E) F G © L.E. Sucar: MGP - Inferencia RB

23 Evidencia de los hijos (l)Recordando que l es un vector (un valor por cada posible valor de B), lo podemos ver en forma matricial: l = l P (S | B) © L.E. Sucar: MGP - Inferencia RB

24 Evidencia de los demás nodos (p)Condicionando sobre los diferentes valores del nodo padre (A): p (Bi) = P (Bi | E+ ) = Sj P (Bi | E+ , Aj) P(Aj | E+ ) Donde Aj corresponde a los diferentes valores del nodo padre de B © L.E. Sucar: MGP - Inferencia RB

25 © L.E. Sucar: MGP - Inferencia RBEvidencia padre H A E+ I B C D E F G © L.E. Sucar: MGP - Inferencia RB

26 Evidencia de los demás nodos (p)Dado que B es independiente de la evidencia “arriba” de A dado A: p (Bi) = Sj P (Bi | Aj) P(Aj | E+ ) La P(Aj | E+ ) corresponde a la P posterior de A dada toda la evidencia excepto B y sus hijos, por lo que se puede escribir como: P(Aj | E+ ) = a p (A i) Pk¹B lk (A i) © L.E. Sucar: MGP - Inferencia RB

27 © L.E. Sucar: MGP - Inferencia RBEvidencia padre p(A) H A I B C l(C) D l(B) E F G © L.E. Sucar: MGP - Inferencia RB

28 Evidencia de los demás nodos (p)Substituyendo P(Aj | E+ ) en la ecuación de p : p (Bi) = Sj P (Bi | Aj) [ a p (A i) Pk¹B lk (A i) ] De forma que se obtiene combinando la p de del nodo padre con la l de los demás hijos © L.E. Sucar: MGP - Inferencia RB

29 Evidencia de los demás nodos (p)Dado que también p es un vector, lo podemos ver en forma matricial (donde PA es el producto de la evidencia de padre y otros hijos): p = P (B | A) PA © L.E. Sucar: MGP - Inferencia RB

30 © L.E. Sucar: MGP - Inferencia RBAlgoritmo Mediante estas ecuaciones se integra un algoritmo de propagación de probabilidades en árboles. Cada nodo guarda los valores de los vectores p y l, así como las matrices de probabilidad P. La propagación se hace por un mecanismo de paso de mensajes, en donde cada nodo envía los mensajes correspondientes a su padre e hijos: © L.E. Sucar: MGP - Inferencia RB

31 Mensaje a los hijos (hacia abajo) - nodo B a su hijo Sk :Mensaje al padre (hacia arriba) – nodo B a su padre A: Mensaje a los hijos (hacia abajo) - nodo B a su hijo Sk : © L.E. Sucar: MGP - Inferencia RB

32 © L.E. Sucar: MGP - Inferencia RBAl instanciarse ciertos nodos, éstos envían mensajes a sus padres e hijos, y se propagan hasta a llegar a la raíz u hojas, o hasta encontrar un nodo instanciado. Así que la propagación se hace en un solo paso en un tiempo proporcional al diámetro de la red. © L.E. Sucar: MGP - Inferencia RB

33 © L.E. Sucar: MGP - Inferencia RBPropagación l H lI(H) lA(H) A lB(A) I lC(A) B C lD(B) lE(B) D E lF(D) lG(D) F G © L.E. Sucar: MGP - Inferencia RB

34 © L.E. Sucar: MGP - Inferencia RBPropagación p H pH(I) pH(A) A pA(B) I pA(C) B C pB(D) pB(E) D E pD(F) pD(G) F G © L.E. Sucar: MGP - Inferencia RB

35 Condiciones InicialesNodos hoja no conocidos: l (Bi) = [1,1, …] Nodos asignados (conocidos): l (Bi) = [0,0, ..1, 0, …, 0] (1 para valor asignado) p (Bi) = [0,0, ..1, 0, …, 0] (1 para valor asignado) Nodo raíz: p (A) = P(A), (probabilidad marginal inicial) © L.E. Sucar: MGP - Inferencia RB

36 © L.E. Sucar: MGP - Inferencia RBEjemplo P(C) Comida P(E|C) Enf. P(F|E) P(D|E) Fiebre Dolor © L.E. Sucar: MGP - Inferencia RB

37 © L.E. Sucar: MGP - Inferencia RBEjemplo Comida Enf. F=si l=[1,0] l=[1,1] Fiebre Dolor © L.E. Sucar: MGP - Inferencia RB

38 © L.E. Sucar: MGP - Inferencia RBEjemplo Comida lF= [1,0] * [.9 .5 | .1 .5] = [.9 .5] lD= [1,1] * [.7 .4 | .3 .6] = [1 1] Enf. Fiebre Dolor P(F|E) P(D|E) © L.E. Sucar: MGP - Inferencia RB

39 © L.E. Sucar: MGP - Inferencia RBEjemplo l(C) = [.9 .5] * [.9 .7| .1 .3] = [ ] Comida P(E|C) l(E) = [.9 .5] * [1 1] = [.9 .5] Enf. Fiebre Dolor P(F|E) P(D|E) © L.E. Sucar: MGP - Inferencia RB

40 © L.E. Sucar: MGP - Inferencia RBEjemplo p(C) = [.8 .2] Comida p(E) = [.8 .2] * [.9 .7| .1 .3] = [ ] P(E|C) Enf. Fiebre Dolor P(F|E) P(D|E) © L.E. Sucar: MGP - Inferencia RB

41 © L.E. Sucar: MGP - Inferencia RBEjemplo p(C) = [.8 .2] Comida p(D) = [ ] * [.9 .5] [.7 .4| .3 .6] = [ ] p(E) = [ ] Enf. Fiebre Dolor P(D|E) © L.E. Sucar: MGP - Inferencia RB

42 © L.E. Sucar: MGP - Inferencia RBEjemplo p(C) = [.8 .2] Comida p(E) = [ ] l(C) = [ ] P(C)=a[ ] P(C)= [ ] l(E) = [.9 .5] P(E)=a[ ] P(E)= [ ] Enf. p(D) = [ ] Fiebre Dolor l(D)=[1,1] P(D)=a[ ] P(D)= [ ] © L.E. Sucar: MGP - Inferencia RB

43 © L.E. Sucar: MGP - Inferencia RBDemo 1 Ejemplo en HUGIN © L.E. Sucar: MGP - Inferencia RB

44 © L.E. Sucar: MGP - Inferencia RBPropagación en Poliárboles . Un poliárbol es una red conectada en forma sencilla, pero en la que un nodo puede tener varios padres: P(B | A1, A2, …, An) © L.E. Sucar: MGP - Inferencia RB

45 Propagación en PoliárbolesH I A B C D E F G © L.E. Sucar: MGP - Inferencia RB

46 © L.E. Sucar: MGP - Inferencia RBAlgoritmo El método es muy similar al de árboles, con algunas consideraciones adicionales: Considerar la probabilidad condicional del nodo dados todos sus padres para el cálculo de p y l Enviar los mensajes l a cada uno de los padres de un nodo © L.E. Sucar: MGP - Inferencia RB

47 © L.E. Sucar: MGP - Inferencia RBPropagación en Redes Multiconectadas Una red multiconectada es un grafo no conectado en forma sencilla, es decir, en el que hay múltiples trayectorias entre nodos (MCG). En este tipo de RP los métodos anteriores ya no aplican, pero existen otras técnicas alternativas: Condicionamiento Simulación estocástica Agrupamiento © L.E. Sucar: MGP - Inferencia RB

48 © L.E. Sucar: MGP - Inferencia RBAbducción La “abducción” se define como encontrar la mejor “explicación” (valores de un cierto conjunto de variables) dada cierta evidencia Normalmente se buscan los valores del conjunto “explicación” que tiene mayor probabilidad En general, el conjunto de mayor probabilidad NO es igual a los valores individuales de mayor probabilidad © L.E. Sucar: MGP - Inferencia RB

49 © L.E. Sucar: MGP - Inferencia RBAbducción H A I B C D E Ejemplo: Max P(A,B,F|G,I) F G © L.E. Sucar: MGP - Inferencia RB

50 © L.E. Sucar: MGP - Inferencia RBReferencias Pearl 88 – Cap. 4,5 Neapolitan 90 – Cap. 6,7,8 Notas Jordan – Cap. 4 © L.E. Sucar: MGP - Inferencia RB