1 Sesión 6: Redes Bayesianas - Inferencia
2 Incertidumbre - RB I, L.E. Sucar[Neapolitan 90] Incertidumbre - RB I, L.E. Sucar
3 Inferencia en Redes BayesianasIntroducción Propagación en árboles Propagación en poliárboles Propagación en redes multi-conectadas Condicionamiento Simulación Agrupamiento Abducción Incertidumbre - RB I, L.E. Sucar
4 Incertidumbre - RB I, L.E. SucarPropagació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. Incertidumbre - RB I, L.E. Sucar
5 Incertidumbre - RB I, L.E. SucarLa 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). Incertidumbre - RB I, L.E. Sucar
6 Incertidumbre - RB I, L.E. SucarInferencia bayesiana C Causal: C -> H Evidencial: E -> H Mixta: C,E -> H P(H|C) H P(E|H) E Incertidumbre - RB I, L.E. Sucar
7 Incertidumbre - RB I, L.E. SucarAlgoritmos Los algoritmos de propagación dependen de la estructura de la red: Árboles Poliárboles Redes multiconectadas Incertidumbre - RB I, L.E. Sucar
8 Incertidumbre - RB I, L.E. SucarPropagación en Árboles . Cada nodo corresponde a una variable discreta, B{B 1, B 2,…, B n) con su respectiva matriz de probabilidad condicional, P(B|A)=P(Bj| Ai) Incertidumbre - RB I, L.E. Sucar { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.es/5621879/2/images/8/Incertidumbre+-+RB+I%2C+L.E.+Sucar.jpg", "name": "Incertidumbre - RB I, L.E. Sucar", "description": "Propagación en Árboles . Cada nodo corresponde a una variable discreta, B{B 1, B 2,…, B n) con su respectiva matriz de probabilidad condicional, P(B|A)=P(Bj| Ai) Incertidumbre - RB I, L.E. Sucar.", "width": "800" } 9 Propagación en ÁrbolesH A I B C D E F G Incertidumbre - RB I, L.E. Sucar { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.es/5621879/2/images/9/Propagaci%C3%B3n+en+%C3%81rboles.jpg", "name": "Propagación en Árboles", "description": "H. A. I. B. C. D. E. F. G. Incertidumbre - RB I, L.E. Sucar.", "width": "800" } 10 Incertidumbre - RB I, L.E. SucarDada 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 Incertidumbre - RB I, L.E. Sucar { "@context": "http://schema.org", "@type": "ImageObject", "contentUrl": "http://slideplayer.es/5621879/2/images/10/Incertidumbre+-+RB+I%2C+L.E.+Sucar.jpg", "name": "Incertidumbre - RB I, L.E. Sucar", "description": "Dada 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. Incertidumbre - RB I, L.E. Sucar.", "width": "800" } 11 Incertidumbre - RB I, L.E. SucarEvidencia H A I B C D E F G E = {I,F,E} Incertidumbre - RB I, L.E. Sucar
12 Incertidumbre - RB I, L.E. SucarEvidencia 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 Incertidumbre - RB I, L.E. Sucar
13 Incertidumbre - RB I, L.E. SucarEvidencia H E+ A I B C D E F G E- Incertidumbre - RB I, L.E. Sucar
14 Incertidumbre - RB I, L.E. SucarEntonces: 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 Incertidumbre - RB I, L.E. Sucar
15 Incertidumbre - RB I, L.E. SucarDefiniciones: 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) Incertidumbre - RB I, L.E. Sucar
16 Incertidumbre - RB I, L.E. SucarDesarrollo 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) Evidenica de los demás nodos (p) Incertidumbre - RB I, L.E. Sucar
17 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 Incertidumbre - RB I, L.E. Sucar
18 Incertidumbre - RB I, L.E. SucarEvidencia hijos H A I B C D E-(D) E E-(E) F G J Incertidumbre - RB I, L.E. Sucar
19 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) Incertidumbre - RB I, L.E. Sucar
20 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)] Incertidumbre - RB I, L.E. Sucar
21 Incertidumbre - RB I, L.E. SucarEvidencia hijos H A I B C D l(D) E l(E) F G Incertidumbre - RB I, L.E. Sucar
22 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) Incertidumbre - RB I, L.E. Sucar
23 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 Incertidumbre - RB I, L.E. Sucar
24 Incertidumbre - RB I, L.E. SucarEvidencia padre H A E+ I B C D E F G Incertidumbre - RB I, L.E. Sucar
25 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) Incertidumbre - RB I, L.E. Sucar
26 Incertidumbre - RB I, L.E. SucarEvidencia padre p(A) H A I B C l(C) D l(B) E F G Incertidumbre - RB I, L.E. Sucar
27 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 Incertidumbre - RB I, L.E. Sucar
28 Evidencia de los demás nodos (p)Dado que también p es un vector, lo podemos ver en forma matricial: p = P (B | A) PA Incertidumbre - RB I, L.E. Sucar
29 Incertidumbre - RB I, L.E. SucarAlgoritmo 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: Incertidumbre - RB I, L.E. Sucar
30 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 : Incertidumbre - RB I, L.E. Sucar
31 Incertidumbre - RB I, L.E. SucarAl 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. Incertidumbre - RB I, L.E. Sucar
32 Incertidumbre - RB I, L.E. SucarPropagació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 Incertidumbre - RB I, L.E. Sucar
33 Incertidumbre - RB I, L.E. SucarPropagació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 Incertidumbre - RB I, L.E. Sucar
34 Condiciones InicialesNodos no conocidos: l (Bi) = [1,1, …] p (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) Incertidumbre - RB I, L.E. Sucar
35 Incertidumbre - RB I, L.E. SucarEjemplo P(C) Comida P(E|C) Enf. P(F|E) P(D|E) Fiebre Dolor Incertidumbre - RB I, L.E. Sucar
36 Incertidumbre - RB I, L.E. SucarEjemplo Comida Enf. F=si l=[1,0] l=[1,1] Fiebre Dolor Incertidumbre - RB I, L.E. Sucar
37 Incertidumbre - RB I, L.E. SucarEjemplo 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) Incertidumbre - RB I, L.E. Sucar
38 Incertidumbre - RB I, L.E. SucarEjemplo 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) Incertidumbre - RB I, L.E. Sucar
39 Incertidumbre - RB I, L.E. SucarEjemplo 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) Incertidumbre - RB I, L.E. Sucar
40 Incertidumbre - RB I, L.E. SucarEjemplo p(C) = [.8 .2] Comida p(D) = [ ] * [.9 .5] [.7 .4| .3 .6] = [ ] p(E) = [ ] Enf. Fiebre Dolor P(D|E) Incertidumbre - RB I, L.E. Sucar
41 Incertidumbre - RB I, L.E. SucarEjemplo 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)= [ ] Incertidumbre - RB I, L.E. Sucar
42 Incertidumbre - RB I, L.E. SucarEjemplo Ejemplo propagación en árboles en HUGIN Incertidumbre - RB I, L.E. Sucar
43 Incertidumbre - RB I, L.E. SucarPropagació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) Incertidumbre - RB I, L.E. Sucar
44 Propagación en PoliárbolesH I A B C D E F G Incertidumbre - RB I, L.E. Sucar
45 Incertidumbre - RB I, L.E. SucarAlgoritmo 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 Incertidumbre - RB I, L.E. Sucar
46 Incertidumbre - RB I, L.E. SucarPropagació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 Incertidumbre - RB I, L.E. Sucar
47 Incertidumbre - RB I, L.E. SucarCondicionamiento Si instanciamos una variable, ésta bloquea las trayectorias de propagación. Entonces asumiendo valores para un grupo seleccionado de variables podemos descomponer la gráfica en un conjunto de SCG. Propagamos para cada valor posible de dichas variables y luego promediamos las probabilidades ponderadas. Incertidumbre - RB I, L.E. Sucar
48 Incertidumbre - RB I, L.E. SucarCondicionamiento 1=V 1=V 1 1 1 3 3 2 2 4 5 4 5 Incertidumbre - RB I, L.E. Sucar
49 Incertidumbre - RB I, L.E. SucarSimulación Estocástica: Se asignan valores aleatorios a las variables no instanciadas, se calcula la distribución de probabilidad y se obtienen valores de cada variable dando una muestra. Se repite el procedimiento para obtener un número apreciable de muestras y en base al numero de ocurrencias de cada valor se determina la probabilidad de dicha variable. Incertidumbre - RB I, L.E. Sucar
50 Incertidumbre - RB I, L.E. SucarSimulación Estocástica: v 1 f f 3 2 v 4 5 f vfffv Incertidumbre - RB I, L.E. Sucar
51 Incertidumbre - RB I, L.E. SucarAgrupamiento: El método de agrupamiento consiste en transformar la estructura de la red para obtener un árbol, mediante agrupación de nodos usando la teoría de grafos. Incertidumbre - RB I, L.E. Sucar
52 Incertidumbre - RB I, L.E. SucarAgrupamiento Transformación: Eliminar direccionalidad de los arcos Ordenamiento de los nodos por máxima cardinalidad Moralizar el grafo (arco entre nodos con hijos comunes) Triangularizar el grafo Obtener los cliques y ordenar Construir árbol de cliques Incertidumbre - RB I, L.E. Sucar
53 Incertidumbre - RB I, L.E. SucarEjemplo 1 1 3 2 3 2 4 5 4 5 Incertidumbre - RB I, L.E. Sucar
54 Ordenamiento de Cliques1 C1 3 2 C3 4 5 C2 Incertidumbre - RB I, L.E. Sucar
55 Incertidumbre - RB I, L.E. SucarÁrbol de Cliques C1 1,2,3 C2 2,3,4 C3 3,5 Incertidumbre - RB I, L.E. Sucar
56 Incertidumbre - RB I, L.E. SucarPropagación La propagación es mediante el envio de mensajes en el árbol de cliques (en forma similar a árboles) Inicialmente se calcula la probabilidad conjunta (potencial) de cada clique, y la condicional dado el padre Dada cierta evidencia se recalculan las probabilidades de cada clique La probabilidad individual de cada variable se obtiene de la del clique por marginalización Incertidumbre - RB I, L.E. Sucar
57 Incertidumbre - RB I, L.E. SucarComplejidad En el peor caso, la propagación en redes bayesianas es un problema NP-duro En la práctica, en muchas aplicaciones se tienen redes no muy densamente conectadas y la propagación es eficiente aún para redes muy grandes Se realiza nvestigación en técnicas de propagación aproximada Incertidumbre - RB I, L.E. Sucar
58 Incertidumbre - RB I, L.E. SucarEjemplo Propagación en redes multiconectadas en HUGIN Incertidumbre - RB I, L.E. Sucar
59 Incertidumbre - RB I, L.E. SucarAbducció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 Incertidumbre - RB I, L.E. Sucar
60 Incertidumbre - RB I, L.E. SucarAbducción H A I B C D E Ejemplo: Max P(A,B,F|G,I) F G Incertidumbre - RB I, L.E. Sucar
61 Incertidumbre - RB I, L.E. SucarReferencias Pearl 88 – Cap. 4,5 Neapolitan 90 – Cap. 6,7,8 Incertidumbre - RB I, L.E. Sucar
62 Incertidumbre - RB I, L.E. SucarActividades Hacer ejercicios de propagación en redes bayesianas Incertidumbre - RB I, L.E. Sucar