Modelos Gráficos Probabilistas

1 Modelos Gráficos ProbabilistasDt-1 Dt Dt+1 Dt+2 Utilida...

Author: Sanchia Terrones

0 downloads 0 Views

1 Modelos Gráficos ProbabilistasDt-1 Dt Dt+1 Dt+2 Utilidad St St+1 St+2 St+3 E E E E L. Enrique Sucar INAOE

2 De datos … a información … a decisionesDe millones de pixeles a pocos conceptos (autos, personas, …) De conceptos a decisiones (frenar, dar vuelta, seguir, …)

3 ¿Porqué el enfoque bayesiano?Combinar la información (datos) con la experiencia (conocimiento) para reducir la incertidumbre

4 ¿Porqué modelos gráficos?1030 100 Los requerimientos de espacio y de cómputo (para estimar probabilidades) crecen exponencialmente con el número de variables 16 4 … 8 3 4 2 Al considerar las relaciones de dependencia e independencia entre variables se tiene un reducción sustancial en requerimiento de cómputo (memoria y operaciones)

5 © E. Sucar, PGM: 1 IntroducciónContenido Introducción Clasificadores Bayesianos Redes Bayesianas Inferencia en Redes Bayesianas Aprendizaje de Redes Bayesianas Redes bayesianas dinámicas Ejemplos de aplicaciones © E. Sucar, PGM: 1 Introducción

6 © E. Sucar, PGM: 1 IntroducciónInformación General Página del curso en INAOE: Correo: © E. Sucar, PGM: 1 Introducción

7 1: Introducción “Vivir es el arte de derivar conclusiones suficientes de premisas insuficientes” [S. Butler]

8 Modelos ProbabilistasLos modelos probabilistas tienen varias varias ventajas: Tienen una clara interpretación y sólidos fundamentos teóricos Pueden hacer uso de las técnicas y herramientas desarrolladas en el área de probabilidad y estadística Permiten un representación declarativa - separando el conocimiento del razonamiento

9 Modelos ProbabilistasSin embargo, si construimos un modelo probabilista en forma “directa” nos enfrentamos al problema de complejidad computacional - el modelo crece exponencialmente con el número de variables Los modelos gráficos probabilistas hacen uso de las independencias entre las variables para poder resolver problemas complejos en una forma mucho más eficiente

10 Modelos Gráficos ProbabilistasRepresentaciones basadas en modelar la incertidumbre con variables aleatorias relacionadas mediante un modelo gráfico (dependencias) Muchas técnicas se pueden englobar dentro de este tipo de modelos © E. Sucar, PGM: 1 Introducción

11 Modelos Gráficos ProbabilistasPodemos clasificar los modelos gráficos probabilistas en 3 dimensiones principales: Dirigidos vs. No-dirigidos Estáticos vs. Dinámicos Probabilista vs. Decisiones © E. Sucar, PGM: 1 Introducción

12 Modelos Gráficos ProbabilistasDirigido No-dirigido 1 1 3 3 2 2 4 5 4 5 © E. Sucar, PGM: 1 Introducción

13 Modelos Gráficos ProbabilistasEstático Dinámico C St St+1 St+2 St+3 E E E E H E © E. Sucar, PGM: 1 Introducción

14 Modelos Gráficos ProbabilistasDecisiones D St St+1 St+2 A E E E B C U D © E. Sucar, PGM: 1 Introducción

15 Modelos Gráficos ProbabilistasD/N E/D P/D Clasificador bayesiano S P Cadenas ocultas de Markov D Campos / Redes de Markov N Redes bayesianas Redes bayesianas dinámicas Filtros de Kalman Redes de Decisión Procesos de decisión de Markov MDPs parcialmente observables © E. Sucar, PGM: 1 Introducción

16 © E. Sucar, PGM: 1 IntroducciónAplicaciones Existen actualmente muchas aplicaciones de PGMs, como: Reconocimiento de voz y ademanes Diagnóstico industrial Modelado del estudiante Navegación robótica Validación de sensores Recuperación de información … © E. Sucar, PGM: 1 Introducción

17 Clasificación de piel en imágenesR G B H S V Y I Q

18 © E. Sucar, PGM: 1 IntroducciónMedicina - endoscopía © E. Sucar, PGM: 1 Introducción

19 Reconocimiento de ademanesFace hand Torso Face hand Torso right above torso right above torso S S X,Y A S X,Y A S T T+1 © E. Sucar, PGM: 1 Introducción

20 Diagnóstico industrial© E. Sucar, PGM: 1 Introducción

21 Modelado del estudiante© E. Sucar, PGM: 1 Introducción

22 © E. Sucar, PGM: 1 IntroducciónNavegación robótica rt+1 rt+2 rt+3 rt at-1 at at+1 at+2 … St St+1 St+2 St+3 at-1 at at+1 at+2 rt+1 rt+2 rt+3 rt © E. Sucar, PGM: 1 Introducción

23 Validación de sensoresCámara de combustión Turbina Generador CH4 CH1 CH1 CH1 CH1 CH1 CH1 CH1 CH1 CH1 CH4 CH4 CH4 CH4 CH4 © E. Sucar, PGM: 1 Introducción

24 Anotación de Imágenes 1- P(rock)=0.542 2- P(wall)=0.4343- P(sunset)=0.412 1-child-boy 2-group-of-persons 3-child-girl 1-group-of-persons 2-man 3-woman 1-sky-blue 2-floor 3-house 1-rock 2-wall 3-sunset 1-window 1-man 2-person 3-window 1- P(group)=0.325 2- P(man)=0.321 3- P(woman)=0.3 ai = rock ai, = wall ai, = sunset 24 24

25 Predicción de mutaciones del virus del VIH

26 2: Clasificadores Bayesianos“ La teoría de probabilidades en el fondo no es nada más que sentido común reducido a cálculos ...” [Pierre Simon Laplace, 1819]

27 © L.E. Sucar: MGP - BásicosClasificación El problema de clasificación (supervisada) consiste en obtener el valor más probable de una variable (hipótesis) dados los valores de otras variables (evidencia, atributos) ArgH [ Max P(H | E1, E2, ...EN) ] ArgH [ Max P(H | E) ] E = {E1, E2, ...EN} © L.E. Sucar: MGP - Básicos

28 Regla de Bayes La probabilidad posterior se puede obtener en base a la regla de Bayes: P(H | E) = P(H) P(E | H) / P(E) P(H | E) = P(H) P(E | H) / i P(E | Hi ) P(Hi) Normalmente no se requiere saber el valor de probabilidad, solamente el valor más probable de H © L.E. Sucar: MGP - Básicos

29 Clasificador bayesiano simpleEstimar la probabilidad: P(E | H) es complejo, pero se simplifica si se considera que los atributos son independientes dada la hipotesis: P(E1, E2, ...EN | H) = P(E1 | H) P(E2 | H) ... P(EN | H) Por lo que la probabilidad de la hipótesis dada la evidencia puede estimarse como: P(H | E1, E2, ...EN) = P(H) P(E1 | H) P(E2 | H) ... P(EN | H) P(E) Esto se conoce como el clasificador bayesiano simple © L.E. Sucar: MGP - Básicos

30 Clasificador bayesiano simpleComo veíamos, no es necesario calcular el denominador: P(H | E1, E2, ...EN) ~ P(H) P(E1 | H) P(E2 | H) ... P(EN | H) P(H) se conoce como la probabilidad a priori, P(Ei | H) es la probabilidad de los atributos dada la hipótesis (verosimilitud), y P(H | E1, E2, ...EN) es la probabilidad posterior © L.E. Sucar: MGP - Básicos

31 © L.E. Sucar: MGP - BásicosVentajas Bajo tiempo de clasificación Bajo tiempo de aprendizaje Bajos requerimientos de memoria “Sencillez” Buenos resultados en muchos dominios © L.E. Sucar: MGP - Básicos

32 © L.E. Sucar: MGP - BásicosLimitaciones En muchas ocasiones la suposición de independencia condicional no es válida Para variables continuas, existe el problema de discretización Alternativas – dependencias: Estructuras que consideran dependencias Mejora estructural del clasificador Alternativas – variables continuas: Descriminador lineal (variables gaussianas) Técnicas de discretización © L.E. Sucar: MGP - Básicos

33 © L.E. Sucar: MGP - BásicosCBS – modelo gráfico C … A1 A2 An © L.E. Sucar: MGP - Básicos

34 © L.E. Sucar: MGP - BásicosExtensiones TAN Se incorpora algunas dependencias entre atributos mediante la construcción de un “árbol” entre ellos C … A1 A2 An © L.E. Sucar: MGP - Básicos

35 © L.E. Sucar: MGP - BásicosExtensiones BAN Se incorpora una “red” para modelar las dependencias entre atributos C … A1 An A2 © L.E. Sucar: MGP - Básicos

36 © L.E. Sucar: MGP - BásicosMejora estructural Otra alternativa para mejorar el CBS es partir de una estructura “simple” y modificarla mediante: Eliminación de atributos irrelevantes (selección de atributos) Verificación de las relaciones de independencia entre atributos y alterando la estructura: Eliminar nodos Combinar nodos Insertar nodos © L.E. Sucar: MGP - Básicos

37 Eliminación de atributosMedir la “dependencia” entre la clase y atributos (por ejemplo con la información mutua), y eliminar aquellos con “poca” aportación C A1 A2 A3 A4 © L.E. Sucar: MGP - Básicos

38 © L.E. Sucar: MGP - BásicosMejora estructural Medir la dependencia entre pares de atributos dada la clase (por ejemplo mediante la información mutua condicional), alterar la estructura si hay 2 dependientes: Eliminación: quitar uno de los dos (redundantes) Unión: juntar los 2 atributos en uno, combinando sus valores Inserción: insertar un atributo “virtual” entre la clase y los dos atributos que los haga independientes. © L.E. Sucar: MGP - Básicos

39 © L.E. Sucar: MGP - BásicosMejora Estructural Z W Z Y X X Y XY Z X Z © L.E. Sucar: MGP - Básicos

40 Atributos redundantesPrueba de dependencia entre cada atributo y la clase Información mutua: I(C, Ai) =  P(C, Ai) log [P(C, Ai) / P(C) P(Ai)] Eliminar atributos que no provean información a la clase © L.E. Sucar: MGP - Básicos

42 Ejemplo: clasificación de piel9 atributos - 3 modelos de color: RGB, HSV, YIQ S R G B H S V Y I Q © L.E. Sucar: MGP - Básicos

43 © L.E. Sucar: MGP - BásicosMejora estructural Elimina B S R G H S V Y I Q © L.E. Sucar: MGP - Básicos

44 © L.E. Sucar: MGP - BásicosElimina Q S R G H S V Y I © L.E. Sucar: MGP - Básicos

45 © L.E. Sucar: MGP - BásicosElimina H S R G S V Y I © L.E. Sucar: MGP - Básicos

46 © L.E. Sucar: MGP - BásicosUnir RG S RG S V Y I © L.E. Sucar: MGP - Básicos

47 © L.E. Sucar: MGP - BásicosElimina V S RG S Y I © L.E. Sucar: MGP - Básicos

48 © L.E. Sucar: MGP - BásicosElimina S Exactitud: inicial 94% final 98% S RG Y I © L.E. Sucar: MGP - Básicos

49 Clasificadores MultidimensionalesEn un clasificador multidimensional se desea maximizar la probabilidad del conjunto posible de clases dados los atributos: ArgH [ Max P(H1, H2, …Hm | E1, E2, ...EN) ] ArgH [ Max P(H1, H2, …Hm | E) ] E = {E1, E2, ...EN}

50 Enfoques Básicos Existen dos enfoques básicos para resolver este problema: Binario: se separa en “m” clasificadores independientes y se obtiene un clasificador independiente para cada clase, y luego se concatena el resultado (no considera la dependencia entre clases) Conjunto potencia: se forma una variable clase global que es la combinación de todas las clases individuales (complejidad computacional, aumenta exponencialmente con el número de clases base)

51 Clasificadores Bayesianos MultidimensionalesPara considerar las dependencias entre clases y atributos, se construye un modelo gráfico de 3 capas: Dependencias entre Clases Dependencias entre Atributos Dependencias entre Clases y Atributos Aprender y clasificar con este modelo es computacionalmente complejo (explicación más probable o MAP)

52 Clasificadores Bayesianos MultidimensionalesSubgrafo de Clases c1 c2 c3 c4 Puente Subgrafo de atributos a2 a3 a4 a5 a1

53 Clasificadores en CadenaOtra alternativa más sencilla es partir de clasificadores binarios y agregar otras clases como atributos para de cierta forma tomar en cuenta las dependencias entre clases Se forma una “cadena” entre las clases de forma que las clases previas en la cadena se incluyen como atributos de las siguientes clases

54 Clasificadores en Cadena

55 Clasificadores en Cadena BayesianosSe aprende un modelo de dependencias entre clases (red bayesiana) El modelo de dependencias puede ser de diversos tipos: árbol, poliárbol, red multiconectada Dicho modelo se utiliza para definir el orden de la cadena y los atributos adicionales que se incluyen en cada clase

56 Clasificadores en Cadena Bayesianos

57 3: Redes Bayesianas “La probabilidad no es realmente sobre números, es sobre la estructura del razonamiento” [G. Shafer]

58 Representación Las redes bayesianas son una representación gráfica de dependencias para razonamiento probabilístico, en la cual los nodos y arcos representan: Nodos: Variables proposicionales. Arcos: Dependencia probabilística La variable a la que apunta el arco es dependiente (causa-efecto) de la que está en el origen de éste. MGP - RB I, L.E. Sucar

59 Ejemplo de una red bayesianaComida Gripe Tifoidea Fiebre Dolor Reacciones MGP - RB I, L.E. Sucar

60 Estructura La topología o estructura de la red nos da información sobre las dependencias probabilísticas entre las variables. La red también representa las independencias condicionales de una variable (o conjunto de variables) dada otra variable(s). MGP - RB I, L.E. Sucar

61 Independencias condicionalesEn una RB, las relaciones de independencia condicional representadas en el grafo corresponden a relaciones de independencia en la distribución de probabilidad. Dichas independencias simplifican la representación del conocimiento (menos parámetros) y el razonamiento (propagación de las probabilidades). MGP - RB I, L.E. Sucar

62 Separación “D” El conjunto de variables A es independiente del conjunto B dado el conjunto C, si no existe trayectoria entre A y B en que Todos los nodos convergentes están o tienen descendientes en C Todos los demás nodos están fuera de C MGP - RB I, L.E. Sucar

63 Separación “D” Tres casos básicos Arcos divergentes Arcos en secuenciaArcos convergentes MGP - RB I, L.E. Sucar

64 Separación “D” – casos básicoscaso 1: Secuencia: X Z Y caso 2: Divergentes: X Z Y caso 3: Convergentes: X Z Y MGP - RB I, L.E. Sucar

65 Parámetros Complementan la definición de una red bayesiana las probabilidades condicionales de cada variable dados sus padres. Nodos raíz: vector de probabilidades marginales Otros nodos: matriz de probabilidades condicionales dados sus padres MGP - RB I, L.E. Sucar

66 Ejemplo Comida Gripe Tifoidea Fiebre Dolor Reacciones P(C) P(G) P(T|C)P(D|T,G) P(F|T,G) P(R|T) MGP - RB I, L.E. Sucar

67 Ejemplo Ins Sal 0.2 0.8 Comida Gripe Tifoidea Fiebre Dolor ReaccionesP(C) Comida P(G) P(T|C) Gripe Tifoidea Fiebre Dolor Reacciones P(D|T,G) P(F|T,G) P(R|T) MGP - RB I, L.E. Sucar

68 Ins Sal 0.2 0.8 Ins Sal Si .7 .1 No .3 .9 Comida Gripe Tifoidea FiebreP(C) Ins Sal Si .7 .1 No .3 .9 Comida P(G) P(T|C) Gripe Tifoidea Fiebre Dolor Reacciones P(D|T,G) P(F|T,G) P(R|T) MGP - RB I, L.E. Sucar

69 Ins Sal Si .7 .1 No .3 .9 Ins Sal 0.2 0.8 Comida Gripe Tifoidea FiebreP(C) Comida P(G) P(T|C) Gripe Tifoidea P(D|T,G) P(R|T) Fiebre Dolor Reacciones Si, Si Si,No No,Si No,No F 0.8 0.6 0.5 0.1 ~F 0.2 0.4 0.9 P(F|T,G) MGP - RB I, L.E. Sucar

70 Especificación ParamétricaEn general, la probabilidad conjunta se especifica por el producto de las probabilidades de cada variable dados sus padres: P(X1,X2, ..., Xn) =  P(Xi | Pa(Xi)) MGP - RB I, L.E. Sucar

71 4: Redes Bayesianas – Inferencia[Neapolitan 90]

72 Inferencia probabilísticaEn RB, la inferencia probabilística consiste en: “dadas ciertas variables conocidas (evidencia), calcular la probabilidad posterior de las demás variables (desconocidas)” Es decir, calcular: P(Xi | E), donde: E es un subconjunto de variables de la RB (posiblemente vació) Xi es cualquier variable en la RB, no en E © L.E. Sucar: MGP - Inferencia RB

73 © 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

74 © L.E. Sucar: MGP - Inferencia RBTipos de Técnicas Calcular probabilidades posteriores: Una variable, cualquier estructura: algoritmo de eliminación (variable elimination) Todas las variable, estructuras sencillamente conectadas (árboles, poliárboles): propagación Todas las variables, cualquier estructura: Agrupamiento (junction tree) Condicionamiento Técnicas aproximadas (Loopy BP, simulación estocástica) © L.E. Sucar: MGP - Inferencia RB

75 © 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

76 © L.E. Sucar: MGP - Inferencia RBTipos de estructuras Sencillamente conectadas Árboles Poliárboles Multiconectadas © L.E. Sucar: MGP - Inferencia RB

77 © 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

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

79 © 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

80 © 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

81 © 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

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

83 © 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 ) =  P ( Bi | E+ ) P(E- | Bi ) Donde  es una constante de normalización © L.E. Sucar: MGP - Inferencia RB

84 © L.E. Sucar: MGP - Inferencia RBDefiniciones: Si definimos los siguientes términos:  (Bi) = P ( E- | Bi)  (Bi) = P (Bi | E+ ) Entonces: P(Bi | E ) =   (B i)  (B i) © L.E. Sucar: MGP - Inferencia RB

85 © 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  y , así como su matriz de probabilidad condicional (CPT), 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

86 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

87 © L.E. Sucar: MGP - Inferencia RBAlgoritmo Al 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

88 © L.E. Sucar: MGP - Inferencia RBPropagación  H I(H) A(H) A B(A) I C(A) B C D(B) E(B) D E F(D) G(D) F G © L.E. Sucar: MGP - Inferencia RB

89 © L.E. Sucar: MGP - Inferencia RBPropagación  H H(I) H(A) A A(B) I A(C) B C B(D) B(E) D E D(F) D(G) F G © L.E. Sucar: MGP - Inferencia RB

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

91 © 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

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

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

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

95 © L.E. Sucar: MGP - Inferencia RBEjemplo (C) = [.8 .2] Comida (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

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

97 © L.E. Sucar: MGP - Inferencia RBEjemplo (C) = [.8 .2] Comida (E) = [ ] C) = [ ] P(C)=[ ] P(C)= [ ] (E) = [.9 .5] P(E)=[ ] P(E)= [ ] Enf. (D) = [ ] Fiebre Dolor (D)=[1,1] P(D)=[ ] P(D)= [ ] © L.E. Sucar: MGP - Inferencia RB

98 Propagación en redes multiconectadasUna red multiconectada es un grafo no conectado en forma sencilla, es decir, en el que hay múltiples trayectorias entre nodos. Para este tipo de redes existen varios tipos de técnicas de inferencia: Propagación “Loopy” Condicionamiento Simulación estocástica Agrupamiento © L.E. Sucar: MGP - Inferencia RB

99 Simulación estocásticaSe asignan valores aleatorios a las variables no asignadas, 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 número de ocurrencias de cada valor se determina la probabilidad de dicha variable. © L.E. Sucar: MGP - Inferencia P2

100 © L.E. Sucar: MGP - Inferencia P2Muestreo Lógico Para “N” muestras, repetir: Dar valores aleatorios a los nodos raíz de acuerdo a sus probabilidades En base a los valores anteriores, dar valores aleatorios a las siguientes variables (hijos de los nodos raíz) en función de la probabilidad condicional Repetir (2) hasta llegar a los nodos hoja Obtener probabilidades posteriores como frecuencias Si hay nodos evidencia, sólo considerar las muestras que correspondan a dichos valores © L.E. Sucar: MGP - Inferencia P2

101 Muestreo Lógico: ejemplovfffv fvvff v vffvf A ffvfv f vfvvf f C ffffv B fvvvf v fffff D E f fffvf vvvvf © L.E. Sucar: MGP - Inferencia P2

102 © L.E. Sucar: MGP - Inferencia P2Ejemplo Sin evidencia: P(A=V) = 4/10 = 0.4 P(B=V) = 3/10 = 0.3 P(C=V) = 5/10 = 0.5 P(D=V) = 5/10 = 0.5 P(E=V) = 3/10 = 0.3 Con evidencia: D=V (aplican 5 muestras): P(A=V) = 3/5 = 0.6 P(B=V) = 2/5 = 0.4 P(C=V) = 3/5 = 0.6 P(E=V) = 1/5 = 0.2 © L.E. Sucar: MGP - Inferencia P2

103 © L.E. Sucar: MGP - Inferencia P2Agrupamiento 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. La propagación se realiza sobre el árbol de macro-nodos obtenido, donde cada macro-nodo corresponde a un clique o unión de la RB original (junction tree) © L.E. Sucar: MGP - Inferencia P2

104 © L.E. Sucar: MGP - Inferencia P2Agrupamiento Transformación: Eliminar direccionalidad de los arcos Ordenamiento de los nodos por máxima cardinalidad Moralizar el grafo (arco entre nodos con hijos comunes) Triangular el grafo Obtener los cliques y ordenar Construir árbol de cliques © L.E. Sucar: MGP - Inferencia P2

105 © L.E. Sucar: MGP - Inferencia P2Ejemplo A A C B B C D E D E © L.E. Sucar: MGP - Inferencia P2

106 Ordenamiento de CliquesB C3 D E C2 © L.E. Sucar: MGP - Inferencia P2

107 © L.E. Sucar: MGP - Inferencia P2Árbol de Cliques C1 A,B,C C2 B,C,D C3 C,E © L.E. Sucar: MGP - Inferencia P2

108 © L.E. Sucar: MGP - Inferencia P2Propagación La propagación es mediante el envío 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 © L.E. Sucar: MGP - Inferencia P2

109 © L.E. Sucar: MGP - Inferencia P2Complejidad 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 (función del clique mayor) Para redes muy complejas (muchas conexiones), la mejor alternativa son técnicas de simulación estocástica o técnicas aproximadas © L.E. Sucar: MGP - Inferencia P2

110 5: Redes Bayesianas – Aprendizaje “Preferiría descubrir una ley causal que ser rey de Persia” [Democritus]

111 © L.E. Sucar: MGP - Aprend. RBAprendizaje El aprendizaje inductivo consiste en obtener conocimiento a partir de datos. En redes bayesianas se divide en 2 aspectos: Obtener la estructura de la red – aprendizaje estructural Obtener las probabilidades asociadas – aprendizaje paramétrico © L.E. Sucar: MGP - Aprend. RB

112 Aprendizaje ParamétricoDatos completos - se estiman las probabilidades a partir de frecuencias P(A) ~ Na / Nt P(B|A1, ..., An) ~ N a1, ..., an, b / Na1, ..., an © L.E. Sucar: MGP - Aprend. RB

113 Ejemplo - ¿Cuándo jugar golf?Ambiente Temp. Humedad Viento Jugar soleado alta alta no N soleado alta alta si N nublado alta alta no P lluvia media alta no P lluvia baja normal no P lluvia baja normal si N nublado baja normal si P soleado media alta no N soleado baja normal no P lluvia media normal no P soleado media normal si P nublado media alta si P nublado alta normal no P lluvia media alta si N © L.E. Sucar: MGP - Aprend. RB

114 © L.E. Sucar: MGP - Aprend. RBEjemplo – estructura J H V A T © L.E. Sucar: MGP - Aprend. RB

116 Información incompletaEn la práctica, en muchas ocasiones los datos no están completos Dos tipos básicos de información incompleta: Faltan algunos valores de una de las variables en algunos casos – datos incompletos Faltan todos los valores de una variable – nodos ocultos © L.E. Sucar: MGP - Aprend. RB

117 Información incompletaAmbiente Temp. Humedad Viento Jugar soleado xxx alta N soleado alta alta N nublado alta alta P lluvia media alta P lluvia baja normal P lluvia baja normal N nublado baja normal P soleado media alta N soleado xxx normal P lluvia media normal P soleado media normal P nublado media alta P nublado alta normal P lluvia media alta N © L.E. Sucar: MGP - Aprend. RB

118 © L.E. Sucar: MGP - Aprend. RBDatos incompletos Existen varias alternativas: Considerar un nuevo valor “desconocido” Tomar el valor más probable (promedio) de la variable Considerar el valor más probable en base a las otras variables Considerar la probabilidad de los diferentes valores en base a las otras variables © L.E. Sucar: MGP - Aprend. RB

119 © L.E. Sucar: MGP - Aprend. RBDatos incompletos Valor más probable: Asignar todas las variables observables. Propagar su efecto y obtener las probabilidades posteriores de las no observables. Para las variables no observables, asumir el valor con probabilidad mayor como observado. Actualizar las probabilidades previas y condicionales de acuerdo a las fórmulas anteriores. Repetir 1 a 4 para cada observación. © L.E. Sucar: MGP - Aprend. RB

120 © L.E. Sucar: MGP - Aprend. RBDatos incompletos Ambiente Temp. Humedad Viento Jugar soleado xxx alta N soleado alta alta N nublado alta alta P lluvia media alta P lluvia baja normal P lluvia baja normal N nublado baja normal P soleado media alta N soleado xxx normal P lluvia media normal P soleado media normal P nublado media alta P nublado alta normal P lluvia media alta N P(T|sol,alta,N) P(T|sol,nor,P) © L.E. Sucar: MGP - Aprend. RB

121 © L.E. Sucar: MGP - Aprend. RBDatos incompletos Ambiente Temp. Humedad Viento Jugar soleado media alta N soleado alta alta N nublado alta alta P lluvia media alta P lluvia baja normal P lluvia baja normal N nublado baja normal P soleado media alta N soleado media normal P lluvia media normal P soleado media normal P nublado media alta P nublado alta normal P lluvia media alta N P(T|sol,alta,N) P(T|sol,nor,P) © L.E. Sucar: MGP - Aprend. RB

122 Nodos ocultos – algoritmo EMEl algoritmo EM es un método estadístico muy utilizado para estimar probabilidades cuando hay variables no observables (un caso especial es el algoritmo de Baum-Welch en HMM) Consiste básicamente de 2 pasos que se repiten en forma iterativa: Paso E: se estiman los datos faltantes en base a los parámetros (P) actuales Paso M: se estiman las probabilidades (parámetros) considerando los datos estimados © L.E. Sucar: MGP - Aprend. RB

123 EM para RB con nodos ocultosIniciar los parámetros desconocidos (CPTs) con valores aleatorios (o estimaciones de expertos) Utilizar los datos conocidos con los parámetros actuales para estimar los valores de la variable(s) oculta(s) Utilizar los valores estimados para completar la tabla de datos Re-estimar los parámetros con los nuevos datos Repetir 24 hasta que no haya cambios significativos en las probabilidades © L.E. Sucar: MGP - Aprend. RB

124 © L.E. Sucar: MGP - Aprend. RBEjemplo J A T H V V es un nodo oculto Se seleccionan valores aleatorios para P(V|J) Se calcula la probabilidad de V para cada caso, dados los valores de A, T, H, J Cada caso se “pesa” de acuerdo a las probabilidades posteriores de V (un caso puede representar “n” datos) Se recalculan los parámetros ( P(V|J) ) en base a los casos obtenidos Se repite el proceso hasta que converja © L.E. Sucar: MGP - Aprend. RB

125 © L.E. Sucar: MGP - Aprend. RBEM: inicio Ambiente Temp. Humedad Viento Jugar soleado media alta N soleado alta alta N nublado alta alta P lluvia media alta P lluvia baja normal P lluvia baja normal N nublado baja normal P soleado media alta N soleado media normal P lluvia media normal P soleado media normal P nublado media alta P nublado alta normal P lluvia media alta N “Adivinar” P(V | J): V\J N P no 0.5 si © L.E. Sucar: MGP - Aprend. RB

126 © L.E. Sucar: MGP - Aprend. RBEM: paso E Ambiente Temp. Humedad Viento Jugar soleado media alta no N soleado alta alta no N nublado alta alta no P lluvia media alta no P lluvia baja normal si P lluvia baja normal si N nublado baja normal si P soleado media alta no N soleado media normal no P lluvia media normal no P soleado media normal si P nublado media alta si P nublado alta normal si P lluvia media alta si N Estimar valores de V en base a P(V | J) y los datos © L.E. Sucar: MGP - Aprend. RB

127 © L.E. Sucar: MGP - Aprend. RBEM: paso M Re-estimar P(V | J) con los Nuevos datos: Ambiente Temp. Humedad Viento Jugar soleado media alta no N soleado alta alta no N nublado alta alta no P lluvia media alta no P lluvia baja normal si P lluvia baja normal si N nublado baja normal si P soleado media alta no N soleado media normal no P lluvia media normal no P soleado media normal si P nublado media alta si P nublado alta normal si P lluvia media alta si N V\J N P no 0.6 0.44 si 0.4 0.66 © L.E. Sucar: MGP - Aprend. RB

128 Aprendizaje EstructuralDiversos métodos: Aprendizaje de árboles Aprendizaje de poliárboles Aprendizaje de redes multiconectadas Métodos basados en medidas Métodos basados en relaciones de dependencia © L.E. Sucar: MGP - Aprend. RB

129 Aprendizaje de árbolesAlgoritmo desarrollado por Chow y Liu para aproximar una distribución de probabilidad por un producto de probabilidades de segundo orden (árbol). La probabilidad conjunta de n variables se puede representar como: donde Xj(i) es la causa o padre de Xi. © L.E. Sucar: MGP - Aprend. RB

130 Aprendizaje de árbolesSe plantea el problema como uno de optimización - obtener la estructura que más se aproxime a la distribución "real". Medida de la diferencia de información entre la distribución real (P) y la aproximada (P*): El objetivo es minimizar I. © L.E. Sucar: MGP - Aprend. RB

131 Aprendizaje de árbolesLa información mutua entre pares de variables se define como: Se puede demostrar (Chow 68) que la diferencia de información es una función del negativo de la suma de las informaciones mutuas (pesos) de todos los pares de variables que constituyen el árbol. Encontrar el árbol más próximo equivale a encontrar el árbol con mayor peso. © L.E. Sucar: MGP - Aprend. RB

132 Aprendizaje de árboles - algoritmoCalcular la información mutua entre todos los pares de variables (n(n - 1)/2). Ordenar las informaciones mutuas de mayor a menor. Seleccionar la rama de mayor valor como árbol inicial. Agregar la siguiente rama mientras no forme un ciclo, si es así, desechar. Repetir (3-4) hasta que se cubran todas las variables (n -1 ramas). El algoritmo NO provee la dirección de los arcos, por lo que ésta se puede asignar en forma arbitraria o utilizando semántica externa (experto). © L.E. Sucar: MGP - Aprend. RB

133 © L.E. Sucar: MGP - Aprend. RBEjemplo (golf) Informaciones mutuas ordenadas No. Var 1 Var 2 I.M. temp. humedad humedad viento ambiente juega ambiente temp humedad juega viento juega temp. juega … viento ambiente … humedad viento … viento temp. … © L.E. Sucar: MGP - Aprend. RB

134 © L.E. Sucar: MGP - Aprend. RBEjemplo (golf) J H A V T © L.E. Sucar: MGP - Aprend. RB

135 Aprendizaje de poliárbolesParte del esqueleto (estructura sin direcciones) obtenido con el algoritmo anterior Determina la dirección de los arcos utilizando pruebas de dependencia entre tripletas de variables. Dadas 3 variables, existen 3 casos posibles: Arcos divergentes Arcos secuenciales Arcos convergentes Los primeros dos casos son indistinguibles, pero el tercero es diferente, ya que las dos variables "padre" son marginalmente independientes. © L.E. Sucar: MGP - Aprend. RB

136 © L.E. Sucar: MGP - Aprend. RBPrueba de Tripletas Tripleta de variables: X – Z – Y Si X – Y son independientes dado Z, entonces pueden ser secuenciales o divergentes X  Z  Y; X  Z  Y Si X – Y no son independientes dado Z, entonces son arcos convergentes X  Z  Y © L.E. Sucar: MGP - Aprend. RB

137 Aprendizaje de poliárboles - algoritmoObtener esqueleto utilizando el algoritmo de Chow y Liu 2. Recorrer la red hasta encontrar una tripleta de nodos que sean convergentes (tercer caso) - nodo multipadre- 3. A partir de un nodo multipadre determinar las direcciones de los arcos utilizando la prueba de tripletas hasta donde sea posible (base causal). 4. Repetir 2-3 hasta que ya no se puedan descubrir más direcciones. 5. Si quedan arcos sin direccionar, utilizar semántica externa para obtener su dirección (o fijar direcciones). © L.E. Sucar: MGP - Aprend. RB

138 © L.E. Sucar: MGP - Aprend. RBEjemplo ~I(H,J,V) I(H,J,A) J I(J,A,T) H V A T © L.E. Sucar: MGP - Aprend. RB

139 Aprendizaje de redes multiconectadasExisten dos tipos de métodos para el aprendizaje genérico de redes bayesianas: Métodos basados en medidas de ajuste y búsqueda Métodos basados en pruebas de independencia © L.E. Sucar: MGP - Aprend. RB

140 Métodos basados en medidasSe generan diferentes estructuras y se evalúan respecto a los datos utilizando alguna medida Dos aspectos principales: Medida de “ajuste” de la estructura a los datos Búsqueda de la “mejor” estructura © L.E. Sucar: MGP - Aprend. RB

141 © L.E. Sucar: MGP - Aprend. RBMedidas Evalúan que tan “buena” es una estructura respecto a los datos Hay varias posibles medidas, las dos más comunes son: Medida bayesiana Medida basada en el principio de longitud de descripción mínima (MDL) © L.E. Sucar: MGP - Aprend. RB

142 © L.E. Sucar: MGP - Aprend. RBMDL La “calidad” de la estructura se basa en el principio de “descripción de longitud mínima” (MDL): Tamaño de la descripción de la red (complejidad) Tamaño de error de predicción de los datos por la red (exactitud) Se hace una búsqueda heurística de la estructura en base al MDL © L.E. Sucar: MGP - Aprend. RB

143 © L.E. Sucar: MGP - Aprend. RBMDL Compromiso entre exactitud y complejidad- minimizar: long. de descripción del modelo + descripción de lo datos dado el modelo Ejemplo – ajustar un polinomio a un conjunto de puntos: © L.E. Sucar: MGP - Aprend. RB

144 © L.E. Sucar: MGP - Aprend. RBMDL Para redes bayesianas: Complejidad: L= i [ ki log2n + d(Si - 1) Fi si] n-# de nodos, k-# padres por nodo, Si-# de valores por variable, Fi-conj. de padres, d-# de bits Exactitud: w(xi, Fxi) =  P(xi, Fxi) log2 [P(xi,Fxi)/P(xi)P(Fxi)] W = i w(xi, Fxi) © L.E. Sucar: MGP - Aprend. RB

145 Buscando la mejor estructura“óptimo” Búsqueda de ascenso de colinas (hill climbing) Se inicia con una estructura simple (árbol) y se van agregando arcos hasta llegar a un mínimo local © L.E. Sucar: MGP - Aprend. RB

146 Métodos basados en medidasSe genera la estructura en base a ir agregando/eliminando arcos de acuerdo a medidas de dependencia entre variables Ejemplos: Árboles – método de Chow y Liu Poliárboles – método de Rebane y Pearl Multiconectadas – existen varios algoritmos basados en diferentes medidas © L.E. Sucar: MGP - Aprend. RB

147 © L.E. Sucar: MGP - Aprend. RBAlgoritmo PC Se basa en pruebas de independencia entre variables: I (Xi, Xj | A) Donde A es un subconjunto de variables Asume que: Se tienen suficientes datos Las pruebas estadísticas no tienen errores © L.E. Sucar: MGP - Aprend. RB

148 Prueba de IndependenciaPara probar si X, Y son independientes dado A se utiliza la entropía cruzada condicional: CE(X,Y | Z) = z P(z) x,y P(x,y|z) log [P(x,y|z) / P(x|z) P(y|z)] Si es cero o cercana a cero, quiere decir que son independientes (se puede usar un umbral o una prueba estadística con cierto nivel de significancia) © L.E. Sucar: MGP - Aprend. RB

149 © L.E. Sucar: MGP - Aprend. RBAlgoritmo Encontrar un “esqueleto” (grafo no dirigido) Encontrar arcos convergentes en tripletas de variables por pruebas de independencia Orientar el resto de las ligas de forma que no se produzcan ciclos © L.E. Sucar: MGP - Aprend. RB

150 © L.E. Sucar: MGP - Aprend. RBEsqueleto La idea básica para determinar el esqueleto es iniciar con un grafo completo (conectando todos vs. todos los nodos) y eliminar el arco entre X – Y si hay un subconjunto de nodos en G (excepto X, Y) que los hace independientes En principio se consideran todos los posibles subconjuntos de variables, de tamaño 1 hasta de tamaño N-1 (N es el número de nodos adyacentes a X y Y) El considerar todos los posibles subconjuntos es muy ineficiente, y normalmente se limita a considerar sólo subconjuntos de 1, 2, …, k nodos © L.E. Sucar: MGP - Aprend. RB

151 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si H,V son Independientes dados: 1: J, A, T 2: JA, JT, AT 3: JAT  si J H V A T © L.E. Sucar: MGP - Aprend. RB

152 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si H,T son Independientes dados: 1: J, A 2: JA  si J H V A T © L.E. Sucar: MGP - Aprend. RB

153 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si H,A son Independientes dados: 1: J  si J H V A T © L.E. Sucar: MGP - Aprend. RB

154 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si H,J son Independientes dados: 0,  no J H V A T © L.E. Sucar: MGP - Aprend. RB

155 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si A,J son Independientes dados: 1: T, V 2: TV  no J H V A T © L.E. Sucar: MGP - Aprend. RB

156 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si A,V son Independientes dados: 1: T, J 2: TJ  si J H V A T © L.E. Sucar: MGP - Aprend. RB

157 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si A,T son Independientes dados: 1: J  no J H V A T © L.E. Sucar: MGP - Aprend. RB

158 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si J,V son Independientes dados: 1: T  no J H V A T © L.E. Sucar: MGP - Aprend. RB

159 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si J,T son Independientes dados: 1: A,V 2: AV  si J H V A T © L.E. Sucar: MGP - Aprend. RB

160 © L.E. Sucar: MGP - Aprend. RBEjemplo Probar si V,T son Independientes dados: 1: 0  no J H V A T © L.E. Sucar: MGP - Aprend. RB

161 © L.E. Sucar: MGP - Aprend. RBArcos convergentes Se verifica cada tripleta de variables para encontrar arcos convergentes mediante pruebas de independencia: X – Z – Y Si X – Y no son independientes dado Z, entonces son arcos convergentes X  Z  Y © L.E. Sucar: MGP - Aprend. RB

164 © L.E. Sucar: MGP - Aprend. RBOtras orientaciones En base a los arcos existentes, se orientan los demás con pruebas de independencia, evitando crear ciclos Si quedan al final arcos sin orientar, se direccionan en forma aleatoria, evitando ciclos © L.E. Sucar: MGP - Aprend. RB

166 6: Redes Bayesianas DinámicasXt Xt+1 Xt+2 Xt+3 St St+1 St+2 St+3 E E E E

167 Redes Bayesianas Dinámicas (RBD)Representan procesos dinámicos Consisten en una representación de los estados del proceso en un tiempo (red base) y las relaciones temporales entre dichos procesos (red de transición) Se pueden ver como una generalización de las cadenas (ocultas) de Markov © L.E. Sucar: MGP - RB Ext y Apli

168 © L.E. Sucar: MGP - RB Ext y ApliRed base S X T E St Xt Xt+1 St+1 T T + 1 Et Et+1 Red de Transición © L.E. Sucar: MGP - RB Ext y Apli

169 Modelo expandido (4 etapas temporales)Xt Xt+1 Xt+2 Xt+3 St St+1 St+2 St+3 E E E E T T + 1 T + 2 T + 3 © L.E. Sucar: MGP - RB Ext y Apli

170 Ejemplo de RBD (equiv. HMM)St St+1 St+2 St+3 E E E E T T + 1 T + 2 T + 3 Parámetros: Probabilidades iniciales: P(St) Probabilidades de transición: P(St+1|St) Probabilidades de observación: P(E|St) © L.E. Sucar: MGP - RB Ext y Apli

171 © L.E. Sucar: MGP - RB Ext y ApliSuposiciones Básicas Proceso markoviano - el estado actual sólo depende del estado anterior (sólo hay arcos entre tiempos consecutivos) Proceso estacionario en el tiempo - las probabilidades de transición, P(St+1 | St), no cambian en el tiempo © L.E. Sucar: MGP - RB Ext y Apli

172 © L.E. Sucar: MGP - RB Ext y ApliInferencia Existen 4 tipos de inferencia en RBD: Filtrado: predecir el siguiente estado dadas observaciones pasadas - P(Xt | Y1 .. Yt-1) Predicción: predecir estados futuros basado en observaciones pasadas - P(Xt+n | Y1 .. Yt-1) Suavizamiento: estimar el estado actual dadas observaciones pasadas y futuras - P(Xt | Y1 .. YT) Decodificación: encontrar la secuencia más probable de variables ocultas dada las observaciones - P(X | Y1 .. YT) © L.E. Sucar: MGP - RB Ext y Apli

173 © L.E. Sucar: MGP - RB Ext y ApliInferencia En general el problema de inferencia es más complejo en RBD Existen soluciones eficientes para ciertos casos particulares, como los HMM En otros modelos más complejos se utilizan técnicas aproximadas basadas en simulación estocástica, como los filtros de partículas © L.E. Sucar: MGP - RB Ext y Apli

174 © L.E. Sucar: MGP - RB Ext y ApliAprendizaje El aprendizaje de RBD es similar al de las redes bayesianas “estáticas”, pero se puede dividir en dos fases: Aprender la red “base” Aprender la red de transición Cada fase a su vez implica el aprendizaje de la estructura y de los parámetros También se pueden presentar los casos de información incompleta donde se aplican las técnicas vistas para redes bayesianas (EM) © L.E. Sucar: MGP - RB Ext y Apli

175 Aprendizaje EstructuralAprender la estructura “estática” Aprender la estructura de “transición” T St E Xt St+1 E T+1 Xt+1 St E T Xt © L.E. Sucar: MGP - RB Ext y Apli

176 © L.E. Sucar: MGP - RB Ext y ApliRedes Temporales Representaciones alternativas a RBD que incorporan aspectos temporales Se orientan a representar intervalos de tiempo o eventos en el tiempo vs estados Existen diferentes propuestas, dos ejemplos representativos son: - Redes de tiempo (time net) [Kanazawa] - Redes de nodos temporales (TNBN) [Arroyo] © L.E. Sucar: MGP - RB Ext y Apli

177 Redes de Nodos TemporalesRepresentan cambios de estado (eventos) de las variables Tienen dos tipos de nodos: - Nodos de estado - representan variables de estado como en las RB - Nodos temporales - representan cambios de estado de una variable © L.E. Sucar: MGP - RB Ext y Apli

178 © L.E. Sucar: MGP - RB Ext y ApliNodo Temporal Nodo que representa un "evento" o cambio de estado de una variable de estado Sus valores corresponden a diferentes intervalos de tiempo en que ocurre el cambio Ejemplo: incremento de nivel - Valores (3): * Cambio * Cambio * No Cambio © L.E. Sucar: MGP - RB Ext y Apli

179 Redes con Nodos TemporalesPermiten una representación más compacta de ciertos dominios que las redes dinámicas Ejemplo (accidente automovilístico): (0-10) Pupils dilated (PD) Head injury (HI) (0-10) Vital signs unstable (VS) (10-30) Internal bleeding (IB) gross (30-60) Internal bleeding (IB) slight © L.E. Sucar: MGP - RB Ext y Apli

180 RB temporal para el ejemploHI VS IB PD C HI1=true HI2=false C1=severe C2=moderate C3=mild IB1=gross IB2=salight IB3=false VS1 =unstables, [0-10] VS2 =unstables, [10-30] VS3=unstable, [30-60] VS4=normal, [0-60] PD1 =dilated, [0-3] PD2 = dilated, [3-5] PD3=normal, [0-5] RB temporal para el ejemplo © L.E. Sucar: MGP - RB Ext y Apli

181 © L.E. Sucar: MGP - RB Ext y ApliTNBN Para cada nodo temporal se definen un conjunto de valores que corresponden a intervalos de tiempo y las probabilidades asociadas La propagación se hace de la misma manera que en redes estáticas © L.E. Sucar: MGP - RB Ext y Apli

182 © L.E. Sucar: MGP - RB Ext y ApliAprendizaje de TNBN El aprendizaje de TNBN implica 3 aspectos: Aprender los intervalos temporales (similar a un proceso de discretización) Aprender la estructura Aprender los parámetros © L.E. Sucar: MGP - RB Ext y Apli

183 7: Aplicaciones

184 © L.E. Sucar: MGP - RB Ext y ApliAplicaciones Modelado de la evolución del VIH Red temporal Endoscopía RB (mejora estructural) Reconocimiento de gestos RBD (clasificador bayesiano dinámico) Predicción de ozono RB (aprendizaje estructural) © L.E. Sucar: MGP - RB Ext y Apli

185 © L.E. Sucar: MGP - RB Ext y ApliVIH El VIH es uno de los organismos que más rápidamente evoluciona, entre otras causas como respuesta a los fármacos ¿Es posible modelar la evolución del virus para predecir las mutaciones futuras y poder diseñar una mejor estrategia de control? © L.E. Sucar: MGP - RB Ext y Apli

186 © L.E. Sucar: MGP - RB Ext y ApliDatos A partir de datos históricos de pacientes se aprende un modelo de la evolución del virus basado en TNBN BD de U. Stanford, más de 2000 pacientes © L.E. Sucar: MGP - RB Ext y Apli

187 © L.E. Sucar: MGP - RB Ext y ApliAprendizaje A partir de los datos se aprende una TBNB incluyendo la estructura, los intervalos temporales y los parámetros Se construyeron dos modelos considerando los medicamentos y mutaciones más probables © L.E. Sucar: MGP - RB Ext y Apli

190 © L.E. Sucar: MGP - RB Ext y ApliEndoscopía Herramienta para la observación directa del tubo digestivo El objetivo es ayudar al endoscopista a guiar el endoscopio en el colón (navegación semiautomática) Para ello se requieren reconocer los principales “objetos”, como son: Lumen – el “centro” del tubo Divertículos – “bolsas” en las paredes que se pueden confundir con el colón © L.E. Sucar: MGP - RB Ext y Apli

195 © L.E. Sucar: MGP - RB Ext y ApliMetodología La estructura de la RB se construyó con la ayuda de un experto Los parámetros de obtuvieron de datos (videos de endoscopías) Posteriormente se mejoró la estructura utilizando pruebas de independencia © L.E. Sucar: MGP - RB Ext y Apli

199 Reconocimiento de gestosReconocimiento de gestos orientados a comandar robots Inicialmente 5 gestos Reconocimiento con RBD © L.E. Sucar: MGP - RB Ext y Apli

201 Extracción de característicasDetección de piel Segmentación de cara y mano Seguimiento de la mano Características de movimiento © L.E. Sucar: MGP - RB Ext y Apli

202 © L.E. Sucar: MGP - RB Ext y ApliSegmentación Agrupamiento de pixels de piel en muestreo radial © L.E. Sucar: MGP - RB Ext y Apli

205 Entrenamiento y ReconocimientoLos parámetros para la RBD se obtienen de ejemplos de cada gesto usando el algoritmo EM Para reconocimiento, se obtiene la probabilidad de cada modelo mediante propagación © L.E. Sucar: MGP - RB Ext y Apli

206 . . Atributos de Movimiento (0,0) x Image t Image t+1 x = + x' y = –form = + y' y © L.E. Sucar: MGP - RB Ext y Apli

207 © L.E. Sucar: MGP - RB Ext y ApliAtributos de postura Relaciones espaciales (binarias) entre la mano y otras partes del cuerpo: Derecha Arriba Torso Above Right Torso © L.E. Sucar: MGP - RB Ext y Apli

209 © L.E. Sucar: MGP - RB Ext y ApliExperimentos 150 muestras de cada gesto Ambiente de laboratorio con condiciones variables de iluminación Distancia entre 3.0 m y 5.0 m Se varía el número de muestras para entrenamiento © L.E. Sucar: MGP - RB Ext y Apli

210 Resultados: DNBCs sin información de posturacome attention go-right go-left stop 98 % 2 % 3 % 87 % 10 % 100 % 4 % 39 % 1 % 56 % Promedio % © L.E. Sucar: MGP - RB Ext y Apli

211 Resultados: DNBCs con información de posturacome attention go-right go-left stop 100 % 11 % 6 % 83 % Promedio % © L.E. Sucar: MGP - RB Ext y Apli

212 Resultados: HMMs con información de posturacome attention go-right go-left stop 100 % 8 % 92 % Promedio % © L.E. Sucar: MGP - RB Ext y Apli

214 Predicción de Ozono en la Ciudad de MéxicoConstrucción de un modelo basado en redes bayesianas para predecir el Ozono 47 variables: 9 mediciones en 5 estaciones Hora del día Mes del año © L.E. Sucar: MGP - RB Ext y Apli

215 © L.E. Sucar: MGP - RB Ext y ApliExperimentos Aprendizaje estructural: 400 casos Orden causal Predicción: Nivel de ozono en una estación una hora después Diferentes porcentajes de variables conocidas © L.E. Sucar: MGP - RB Ext y Apli

217 Comparación con una red neuronalPredicción de ozono: BN vs HNN % Datos Método Error relativo Error de inter. 100% BN 21% 12% HNN 26% 12% 85% BN 21% 12% HNN 26% 9% 70% BN 25% 8% HNN 32% 12% 50% BN 21% 12% HNN 37% 29% © L.E. Sucar: MGP - RB Ext y Apli

218 © L.E. Sucar: MGP - RB Ext y ApliOtras aplicaciones Predicción del precio del petróleo Modelado de riesgo en accidentes de automóviles Diagnóstico médico Validación de sensores Modelado de usuarios (ayudantes Microsoft Office) Modelado del estudiante (tutores inteligentes) Diagnóstico de turbinas (General Electric) Reconocimiento de objetos en imágenes Reconocimiento de voz ... © L.E. Sucar: MGP - RB Ext y Apli

219 Conclusiones El enfoque bayesiano permite combinar el conocimiento previo con los datos para tomar las mejores decisiones bajo incertidumbre Los modelos gráficos probabilistas aprovechan las relaciones de independencia para lograr una implementación computacionalmente eficiente del enfoque bayesiano Bajo el paradigma de los MGPs hay una variedad de técnicas que permiten modelar diversos problemas que involucran incertidumbre, tiempo y decisiones / utilidades

220 Retos Aumentar la expresividad de los modelos gráficos probabilistasModelos gráficos relacionales Descubrir relaciones “causales” Modelos gráficos causales

221 Modelos Relacionales ProbabilistasCombinan lógica y probabilidad Ejemplo – gramática visual para reconocimiento de objetos (caras): Above(Eyes, Mouth) Above(Nose, Mouth) Within(Eyes, Skin) Within(Nose, Skin) Within(Mouth, Skin) Reglas lógicas con dichas relaciones: 2.3 AboveEM(e,m) v AboveNM(n,m) => Rostro(e,n,m,s) 1.8 WithinES(e,s) v WithinNS(n,s) => Rostro(e,n,m,s) 0.9 Rostro(e,n,m,s) => WithinMS(m,s) El peso indica una incertidumbre asociada a tales reglas

222 Modelos Gráficos CausalesBuscar representar relaciones causales; y realizar inferencias basadas en estos modelos Reto: aprender estos modelos sin necesidad de hacer intervenciones Ingresos Vino Enfermedades cardiacas Vino Enfermedades cardiacas

223 Información AdicionalPágina del curso en INAOE: Libro: L. E Sucar, “Probabilistic Graphical Models: Principles and Applications”, Springer-Verlag (por publicarse) © E. Sucar, PGM: 1 Introducción

Modelos Gráficos Probabilistas

Recommend Documents