una por pagina
Transcript of una por pagina
Razonamiento con incertidumbre Introducción
Incertidumbre y conocimiento
Todos los mecanismos de representación de conocimiento vistos estánbasados en la lógica bajo estos supuestos:
Todo hecho sobre el que razonemos debe poder ser evaluado comocierto o falsoPara poder razonar necesitamos tener todos los hechos a nuestradisposición
Pero en la práctica nos encontramos con estos problemasRepresentar el conocimiento para cubrir todos los hechos que sonrelevantes para un problema es difícilExisten dominios en los que se desconocen todos los hechos y reglasnecesarias para resolver el problemaExisten problemas en los que aún teniendo las reglas para resolverlos nodisponemos de toda la información necesaria o no tenemos confianzaabsoluta en ellasEn otros problemas la reglas no se aplican siempre o su confianzacambia con la confianza que tenemos en los hechos
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 1 / 53
Razonamiento con incertidumbre Introducción
Tratamiento de la incertidumbre
Dentro de la IA se han desarrollado diferentes formalismos que permitenhacer razonamiento con incertidumbre, nos fijaremos en dos de ellos:
Modelos probabilistas (Redes bayesianas)Modelos posibilistas (Lógica difusa)
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 2 / 53
Modelos Probabilistas Introducción
Modelos Probabilistas
Los modelos probabilistas se basan en la teoría de la probabilidadLas probabilidades se utilizan para modelizar nuestra creencia sobrelos posibles valores que pueden tomar los hechosCada hecho tendrá una distribución de probabilidad asociada que nospermitirá tomar decisionesLa probabilidad de un hecho podrá ser modificada por nuestracreencia en otros hechos que estén relacionados
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 3 / 53
Modelos Probabilistas Introducción
Decisiones Probabilistas
¿Cogerás un paraguas mañana?
Vivo en Barcelona, no llueve nunca
La previsión es que haya nubes
Igual sí, igual no
Hoy el suelo esta mojado
Pues mejor que lo coja
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 4 / 53
Modelos Probabilistas Introducción
Decisiones Probabilistas
¿Cogerás un paraguas mañana?
Vivo en Barcelona, no llueve nunca
La previsión es que haya nubes
Igual sí, igual no
Hoy el suelo esta mojado
Pues mejor que lo coja
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 4 / 53
Modelos Probabilistas Introducción
Decisiones Probabilistas
¿Cogerás un paraguas mañana?
Vivo en Barcelona, no llueve nunca
La previsión es que haya nubes
Igual sí, igual no
Hoy el suelo esta mojado
Pues mejor que lo coja
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 4 / 53
Modelos Probabilistas Introducción
Decisiones Probabilistas
¿Cogerás un paraguas mañana?
Vivo en Barcelona, no llueve nunca
La previsión es que haya nubes
Igual sí, igual no
Hoy el suelo esta mojado
Pues mejor que lo coja
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 4 / 53
Modelos Probabilistas Introducción
Decisiones Probabilistas
¿Cogerás un paraguas mañana?
Vivo en Barcelona, no llueve nunca
La previsión es que haya nubes
Igual sí, igual no
Hoy el suelo esta mojado
Pues mejor que lo coja
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 4 / 53
Modelos Probabilistas Introducción
Decisiones Probabilistas
¿Cogerás un paraguas mañana?
Vivo en Barcelona, no llueve nunca
La previsión es que haya nubes
Igual sí, igual no
Hoy el suelo esta mojado
Pues mejor que lo coja
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 4 / 53
Modelos Probabilistas Teoría de probabilidades
Teoría de probabilidades
El elemento básico de teoría de probabilidades es la variable aleatoriaUna variable aleatoria tiene un dominio de valores, podemos tenervariables aleatorias booleanas, discretas o continuas.Definiremos una proposición lógica como cualquier fórmula en lógicade enunciados o predicadosUna proposición lógica tendrá asociada una variable aleatoria queindicará nuestro grado de creencia en ella
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 5 / 53
Modelos Probabilistas Teoría de probabilidades
Teoría de probabilidades
Una variable aleatoria tendrá asociada una distribución deprobabilidadLa forma de expresar esta distribución de probabilidad dependerá deltipo de variable aleatoria (Discretas: Binomial, Multinomial, ...,Continuas: Normal, χ2, ...)Nosotros trabajaremos sólo con variables aleatorias discretasLa unión de variables aleatorias se puede describir mediante unadistribución de probabilidad conjunta
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 6 / 53
Modelos Probabilistas Teoría de probabilidades
Teoría de probabilidades: Notación
Denotaremos como P(a) la probabilidad de que la proposición(variable aleatoria) A tenga el valor a. Por ejemplo, la proposiciónFumar puede tener los valores {fumar ,¬fumar}, P(¬fumar) es laprobabilidad de la proposición Fumar = ¬fumarDenotaremos como P(A) al vector de probabilidades de todos losposibles valores de la proposición A
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 7 / 53
Modelos Probabilistas Teoría de probabilidades
Teoría de probabilidades
Definiremos como probabilidad a priori (P(a)) asociada a unaproposición como el grado de creencia en ella a falta de otrainformaciónDefiniremos como probabilidad a posteriori o condicional (P(a|b))como el grado de creencia en una proposición tras la observación deproposiciones asociadas a ellaLa probabilidad a posteriori se puede definir a partir de probabilidadesa priori como:
P(a|b) = P(a ∧ b)P(b)
Esta fórmula se puede transformar en lo que denominaremos la regladel producto:
P(a ∧ b) = P(a|b)P(b) = P(b|a)P(a)
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 8 / 53
Modelos Probabilistas Teoría de probabilidades
Axiomas de la probabilidad
Los axiomas de la probabilidad serán el marco que restringirá las cosas quepodremos creer y deducir
Toda probabilidad esta en el intervalo [0, 1]
0 ≤ P(a) ≤ 1
La proposición cierto tiene probabilidad 1 y la proposición falso tieneprobabilidad 0
P(cierto) = 1 P(falso) = 0
La probabilidad de la disyunción se obtiene mediante la fórmula
P(a ∨ b) = P(a) + P(b)− P(a ∧ b)
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 9 / 53
Modelos Probabilistas Inferencia probabilística
Inferencia probabilísticaLas leyes de la probabilidad permiten establecer diferentes métodos deinferencia
Marginalización: Probabilidad de una proposición atómica conindependencia de los valores del resto de proposiciones
P(Y ) =∑
zP(Y , z)
Probabilidades condicionadas: Probabilidad de una proposicióndados unos valores para algunas proposiciones e independiente delresto de proposiciones (a partir de la regla del producto)
P(X |e) = α∑
yP(X , e, y)
El valor α es un factor de normalización que corresponde a factorescomunes que hacen que las probabilidades sumen 1cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 10 / 53
Modelos Probabilistas Inferencia probabilística
Inferencia probabilística: ejemplo
Consideremos un problema en el que intervengan las proposicionesFumador = {fumador ,¬fumador}, Sexo = {varon,mujer},Enfisema = {enfisema,¬enfisema}
enfisema ¬enfisemavaron mujer varon mujer
fumador 0.2 0.1 0.05 0.05¬fumador 0.02 0.02 0.23 0.33
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 11 / 53
Modelos Probabilistas Inferencia probabilística
Inferencia probabilística: ejemplo
P(enfisema ∧ varon) = 0,2+ 0,02P(fumador ∨mujer) = 0,2+ 0,1+ 0,05+ 0,05+ 0,02+ 0,33
P(Fumador |enfisema) = 〈P(fumador , enfisema, varon)+P(fumador , enfisema,mujer),P(¬fumador , enfisema, varon)+P(¬fumador , enfisema,mujer)〉
= α〈0,3, 0,04〉= 〈0,88, 0,12〉
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 12 / 53
Modelos Probabilistas Inferencia probabilística
Inferencia probabilística: Problemas
Hacer estos procesos de inferencia requiere almacenar y recorrer ladistribución de probabilidad conjunta de todas las proposicionesSuponiendo proposiciones binarias el coste en espacio y tiempo esO(2n) siendo n el número de proposicionesPara cualquier problema real estas condiciones son impracticablesNecesitamos mecanismos que nos simplifiquen el coste delrazonamiento
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 13 / 53
Modelos Probabilistas Independencia probabilística - Bayes
Independencia probabilística
Por lo general no todas las proposiciones que aparecen en unproblema están relacionadas entre siMuestran la propiedad que denominaremos independenciaprobabilísticaEsto quiere decir que unas proposiciones no influyen en las otras y porlo tanto podemos reescribir sus probabilidades como:
P(X |Y ) = P(X ); P(Y |X ) = P(Y ); P(X ,Y ) = P(X )P(Y )
Dadas estas propiedades podremos reescribir las probabilidadesconjuntas de manera mas compacta reduciendo la complejidad
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 14 / 53
Modelos Probabilistas Independencia probabilística - Bayes
La regla de Bayes
Hemos enunciado la regla del producto como:
P(X ,Y ) = P(X |Y )P(Y ) = P(Y |X )P(X )
Esto nos lleva a lo que denominaremos la regla de Bayes
P(Y |X ) =P(X |Y )P(Y )
P(X )
Esta regla y la propiedad de independencia serán el fundamento delrazonamiento probabilístico y nos permitirá relacionar lasprobabilidades de unas evidencias con otras
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 15 / 53
Modelos Probabilistas Independencia probabilística - Bayes
La regla de Bayes + independencia
Suponiendo que podemos estimar exhaustivamente todas lasprobabilidades que involucran todos los valores de la variable Ypodemos reescribir la formula de Bayes como:
P(Y |X ) = αP(X |Y )P(Y )
Suponiendo independencia condicional entre dos variables podremosescribir:
P(X ,Y |Z ) = P(X |Z )P(Y |Z )
De manera que:
P(Z |X ,Y ) = αP(X ,Y |Z )P(Z ) = αP(X |Z )P(Y |Z )P(Z )
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 16 / 53
Redes Bayesianas Redes Bayesianas
Redes Bayesianas
Si determinamos la independencia entre variables podemos simplificarel cálculo de la combinación de sus probabilidades y su representaciónLas redes bayesianas permiten la representación de las relaciones deindependencia entre variable aleatoriasUna red bayesiana es un grafo dirigido acíclico que tieneinformación probabilística en sus nodos indicando cual es la influenciade sus padres en el grafo sobre el nodo (P(Xi |padres(Xi)))El significado intuitivo de un enlace entre dos nodos X e Y es que lavariable X tiene influencia sobre YEl conjunto de probabilidades representadas en la red describe ladistribución de probabilidad conjunta de todas las variables
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 17 / 53
Redes Bayesianas Redes Bayesianas
Redes Bayesianas: ejemplo (1))
Queremos determinar la probabilidad de que una persona sufra uninfartoSabemos que esta probabilidad está determinada por cuatro variables:La práctica de deporte, lo equilibrada de la alimentación, lapresión sanguínea y si se es fumadorTambién sabemos que la presión sanguínea depende directamente deldeporte y la alimentación, que son variables independientes, y que elser fumador es independiente del resto de variablesEste conocimiento nos permite crear la red de dependencias entre lasvariablesNuestro conocimiento del dominio nos permite estimar la probabilidadque corresponde a cada una de las variables independientes y suinfluencia entre las variables dependientes
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 18 / 53
Redes Bayesianas Redes Bayesianas
Redes Bayesianas: ejemplo (2)
P(I=si) P(I=no)Pr Sang Fum
si
si
no
no
alta
normal
alta
normal
0.8 0.2
0.6 0.4
0.7 0.3
0.3 0.7
DeporteP(D)Deporte
0.9
0.1Alimentacion
P(A)
equilibrada
no equlibrada
0.4
0.6
Alimentacion
FumadorPresion Sanguinea
Infarto
P(F)Fumador
0.40.6
Alim Dep
eq si 0.01 0.99no eq si 0.2 0.8eq no 0.25 0.75
no eq no 0.30.7
no
si
si
no
P(S=alta) P(S=normal)
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 19 / 53
Redes Bayesianas Redes Bayesianas
Redes Bayesianas - Distribución conjunta
En cada nodo de la red aparece la distribución de probabilidad delnodo respecto a sus padresEsto permite factorizar la distribución de probabilidad conjunta,convirtiéndose en el producto de probabilidades condicionalesindependientes
P(x1, x2, . . . , xn) =n∏
i=1P(xi |padres(xi))
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 20 / 53
Redes Bayesianas Redes Bayesianas
Redes Bayesianas - Distribución conjunta - ejemplo
P(Infarto = si ∧ Presion = alta ∧ Fumador = si∧ Deporte = si ∧ Alimentacion = equil)=P(Infarto = si |Presion = alta,Fumador = si)P(Presion = alta|Deporte = si ,Alimentacion = equil)P(Fumador = si)P(Deporte = si)P(Alimentacion = equil)= 0,8× 0,01× 0,4× 0,1× 0,4= 0,000128
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 21 / 53
Redes Bayesianas Redes Bayesianas
Construcción de redes bayesianas
Las propiedades de las redes bayesianas nos dan ciertas ideas sobrecomo construirlas. Si consideramos que (regla del producto):
P(x1, x2, . . . , xn) = P(xn|xn−1, . . . , x1)P(xn−1, . . . , x1)
Iterando el proceso tenemos que:
P(x1, . . . , xn) = P(xn|xn−1, . . . , x1)P(xn−1|xn−2, . . . , x1)
· · ·P(x2|x1)P(x1)
=n∏
i=1P(xi |xi−1, . . . , x1)
Esta es la llamada regla de la cadena
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 22 / 53
Redes Bayesianas Redes Bayesianas
Construcción de redes bayesianas
Dadas estas propiedades, podemos afirmar que sipadres(Xi) ⊆ {Xi−1, . . . ,X1}, entonces:
P(Xi |Xi−1, . . . ,X1) = P(Xi |padres(Xi))
Esto quiere decir que una red bayesiana es una representacióncorrecta de un dominio sólo si cada nodo es condicionalmenteindependiente de sus predecesores en orden, dados sus padresPara lograr esto, los padres de una variable Xi deben ser aquellos deentre las variables X1, . . .Xi−1 que influyan directamente en Xi
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 23 / 53
Redes Bayesianas Redes Bayesianas
Coste de representación
Como comentamos, el coste de representar la distribución deprobabilidad conjunta de n variables binarias es O(2n)
La representación de redes bayesianas nos permite una representaciónmas compacta gracias a la factorización de la distribución conjuntaSuponiendo que cada nodo de la red tenga como máximo k padres(k � n), un nodo necesitará 2k para representar la influencia de suspadres, por lo tanto el espacio necesario será O(n2k).Por ejemplo, con 10 variables y suponiendo 3 padres como máximotenemos 80 frente a 1024, con 100 variables y suponiendo 5 padrestenemos 3200 frente a aproximadamente 1030
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 24 / 53
Redes Bayesianas Inferencia en Redes Bayesianas
Inferencia en Redes Bayesianas
El objetivo de la inferencia probabilística será calcular la distribuciónde probabilidad a posteriori de un conjunto de variables dada laobservación de un evento (valores observados para un subconjunto devariables)Denotaremos como X la variable sobre la que queremos conocer ladistribuciónE será el conjunto de variables de las que conocemos su valorE1, . . . ,En
e el el conjunto de valores observados para las variables de EY será el conjunto de variables que no hemos observado Y1, . . . ,Yn(variables ocultas)De esta manera X = {X} ∪ E ∪ Y será el conjunto completo devariablesNos plantearemos el cálculo de P(X |e)cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 25 / 53
Redes Bayesianas Inferencia en Redes Bayesianas
Inferencia Exacta
Inferencia por enumeración: Cualquier probabilidad condicionada sepuede calcular como la suma de todos los posibles casos a partir de ladistribución de probabilidad conjunta.
P(X |e) = αP(X , e) = α∑
yP(X , e, y)
La red bayesiana nos permite factorizar la distribución de probabilidadconjunta y obtener una expresión mas fácil de evaluarUsando la red bayesiana ejemplo podemos calcular la probabilidad deser fumador si se ha tenido un infarto y no se hace deporte
P(Fumador |Infarto = si ,Deporte = no)
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 26 / 53
Redes Bayesianas Inferencia en Redes Bayesianas
Inferencia Exacta: Ejemplo
La distribución de probabilidad conjunta de la red sería:
P(D,A, S,F , I) = P(I|S,F )P(F )P(S|D,A)P(D)P(A)
Debemos calcular P(F |I = si ,D = no), por lo tanto tenemos
P(F |I = s,D = n) = αP(F , I = s,D = n)= α
∑A∈{e,¬e}
∑S∈{a,n}
P(D = n,A, S,F , I = s)
= αP(D = n)P(F )∑
A∈{e,¬e}P(A)
∑S∈{a,n}
P(S|D = n,A)P(I = s|S,F )
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 27 / 53
Redes Bayesianas Inferencia en Redes Bayesianas
Inferencia Exacta: Ejemplo
Si enumeramos todas las posibilidades y las sumamos de acuerdo con ladistribución de probabilidad conjunta tenemos que:
P(Fumador |Infarto = si ,Deporte = no)= α〈0,9 · 0,4 · (0,4 · (0,25 · 0,8+ 0,75 · 0, 6) + 0,6 · (0,7 · 0,8+ 0,3 · 0,6)),
0,9 · 0,6 · (0,4 · (0,25 · 0,7+ 0, 75 · 0,3) + 0,6 · (0,7 · 0,7+ 0,3 · 0,3)〉= α〈0,253, 0, 274〉= 〈0, 48, 0,52〉
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 28 / 53
Redes Bayesianas Algoritmo de eliminación de variables
Algoritmo de eliminación de variables
El algoritmo de eliminación de variables intenta evitar la repeticiónde cálculos que realiza la inferencia por enumeraciónEl algoritmo utiliza técnicas de programación dinámica de manera quese guardan cálculos intermedios para cada variable para reutilizarlos(factores)El cálculo de la probabilidad de la pregunta se realiza evaluando laexpresión de la distribución de probabilidad conjunta de izquierda aderechaLos factores correspondientes a cada variable se van acumulandosegún se necesitaLa ventaja de este algoritmo es que las variables no relevantesdesaparecen al ser factores constantes
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 29 / 53
Redes Bayesianas Algoritmo de eliminación de variables
Algoritmo de eliminación de variables
Función: Elimination de Variables (X, e, rb)factores ← []vars ← REVERSE(VARS(rb))para cada var ∈ vars hacer
factores ← concatena(factores,CALCULA-FACTOR(var,e))si var es variable oculta entonces
factores ← PRODUCTO-Y-SUMA(var,factores)fin
finretorna NORMALIZA(PRODUCTO(factores))
CALCULA-FACTOR genera el factor correspondiente a la variable enla función de distribución de probabilidad conjuntaPRODUCTO-Y-SUMA multiplica los factores y suma respecto a lavariable ocultaPRODUCTO multiplica un conjunto de factorescbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 30 / 53
Redes Bayesianas Algoritmo de eliminación de variables
Algoritmo de eliminación de variables - Factores
Un factor corresponde a la distribución de probabilidad de unconjunto de variables dadas las variables ocultasSe representa por una tabla que para cada combinación de variablesocultas da la probabilidad de las variables del factor
fX (Y ,Z )=
Y ZC C 0.2C F 0.4F C 0.8F F 0.6
Los factores tienen dos operaciones: suma y producto
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 31 / 53
Redes Bayesianas Algoritmo de eliminación de variables
Suma de Factores
La suma se aplica a un factor y sobre una variable oculta del factor.Como resultado obtenemos una matriz reducida en la que las filas delmismo valor se han acumulado
fXZ (Y ) =∑
Z fX (Y ,Z )=YC 0.6F 1.4
Es igual que una operación de agregación sobre una columna en basesde datos
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 32 / 53
Redes Bayesianas Algoritmo de eliminación de variables
Producto de Factores
El producto de factores permite juntar varios factores utilizando lasvariables ocultas comunes
fX1X2(Y ,W ,Z ) = fX1(Y ,Z )× fX2(Z ,W )=Y Z Z W Y Z WC C 0.2 C C 0.3 C C C 0,2× 0,3C F 0.8 C F 0.7 C C F 0,2× 0,7F C 0.4 F C 0.1 C F C 0,8× 0,1F F 0.6 F F 0.9 C F F 0,8× 0,9
F C C 0,4× 0,3F C F 0,4× 0,7F F C 0,6× 0,1F F F 0,6× 0,9
Es igual que una operación de join en una base de datosmultiplicando los valores de las columnas de datos
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 33 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
A P(A)e 0.4¬ e 0.6
Alimentación
D P(D)si 0.1no 0.9
Deporte
A D P(S=a) P(S=n)e s 0.01 0.99¬e s 0.2 0.8e n 0.25 0.75¬e n 0.7 0.3
Presion
F P(F)s 0.4n 0.6
Fumador S F P(I=s) P(I=n)a s 0.8 0.2a n 0.7 0.3n s 0.6 0.4n n 0.3 0.7
Infarto
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 34 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
Volveremos a calcular P(Fumador |Infarto = si ,Deporte = no) a partir dela distribución de probabilidad conjunta:
P(D,A, S,F , I) = P(I|S,F )P(F )P(S|D,A)P(D)P(A)
Debemos calcular P(F |I = si ,D = no), por lo tanto tenemos
P(F |I = s,D = n) = αP(I = s,F ,D = n)= α
∑A∈{e,¬e}
∑S∈{a,n}
P(D = n,A,S,F , I = s)
En esta ocasión no sacamos factores comunes para seguir el algoritmo
αP(D = n)∑
A∈{e,¬e}P(A)
∑S∈{a,n}
P(S|D = n,A)P(F )P(I = s|S,F )
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 35 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
A P(A)e 0.4¬ e 0.6
Alimentación
D P(D)si 0.1no 0.9
Deporte
A D P(S=a) P(S=n)e s 0.01 0.99¬e s 0.2 0.8e n 0.25 0.75¬e n 0.7 0.3
Presion
F P(F)s 0.4n 0.6
Fumador S F P(I=s) P(I=n)a s 0.8 0.2a n 0.7 0.3n s 0.6 0.4n n 0.3 0.7
Infarto
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 36 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
El algoritmo empieza calculando el factor para la variable Infarto(P(I = s|S,F )), ésta tiene fijo su valor a si, depende de las variablesPresión Sanguinea y Fumador
fI(S,F )=
S Fa s 0.8a n 0.7n s 0.6n n 0.3
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 37 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
A P(A)e 0.4¬ e 0.6
Alimentación
D P(D)si 0.1no 0.9
Deporte
A D P(S=a) P(S=n)e s 0.01 0.99¬e s 0.2 0.8e n 0.25 0.75¬e n 0.7 0.3
Presion
F P(F)s 0.4n 0.6
Fumador S F P(I=s) P(I=n)a s 0.8 0.2a n 0.7 0.3n s 0.6 0.4n n 0.3 0.7
fI(S, F )
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 38 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
La variable fumador (P(F )) no depende de ninguna otra variable, al ser lavariable que preguntamos el factor incluye todos los valores
fF (F )=Fs 0.4n 0.6
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 39 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
A P(A)e 0.4¬ e 0.6
Alimentación
D P(D)si 0.1no 0.9
Deporte
A D P(S=a) P(S=n)e s 0.01 0.99¬e s 0.2 0.8e n 0.25 0.75¬e n 0.7 0.3
Presion
F P(F)s 0.4n 0.6
fF (F ) S F P(I=s) P(I=n)a s 0.8 0.2a n 0.7 0.3n s 0.6 0.4n n 0.3 0.7
fI(S, F )
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 40 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
La variable Presión Sanguinea (P(S|D = n,A)), depende de las variableDeporte que tiene fijo su valor a no y Alimentación. Esta es una variableoculta, por lo que se debe calcular para todos sus valores
fS(S,A)=
S Aa e 0.25a ¬e 0.7n e 0.75n ¬ e 0.3
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 41 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
A P(A)e 0.4¬ e 0.6
Alimentación
D P(D)si 0.1no 0.9
Deporte
A D P(S=a) P(S=n)e s 0.01 0.99¬e s 0.2 0.8e n 0.25 0.75¬e n 0.7 0.3
fS(S, A)
F P(F)s 0.4n 0.6
fF (F ) S F P(I=s) P(I=n)a s 0.8 0.2a n 0.7 0.3n s 0.6 0.4n n 0.3 0.7
fI(S, F )
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 42 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
Al ser la variable Presión Sanguinea una variable oculta debemos acumulartodos los factores que hemos calculado
fS(S,A)× fF (F )× fI(S,F )
fFI(S,F ) = fF (F )× fI(S,F )=
S Fa s 0.8×0.4a n 0.7×0.6n s 0.6×0.4n n 0.3×0.6
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 43 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
fFIS(S,F ,A) = fFI(S,F )× fS(S,A)=
S F Aa s e 0.8×0.4×0.25a s ¬e 0.8×0.4×0.7a n e 0.7×0.6×0.25a n ¬e 0.7×0.6×0.7n s e 0.6×0.4×0.75n s ¬e 0.6×0.4×0.3n n e 0.3×0.6×0.75n n ¬e 0.3×0.6×0.3
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 44 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
Y ahora sumamos sobre todos los valores de la variable S para obtener elfactor correspondiente a la variable Presión Sanguinea
fFIS(F ,A) =∑
S∈{a,n} fFIS(S,F ,A) =F As e 0.8×0.4×0.25 + 0.6×0.4×0.75 = 0.26s ¬e 0.8×0.4×0.7 + 0.6×0.4×0.3 = 0.296n e 0.7×0.6×0.25 + 0.3×0.6×0.75 = 0.24n ¬e 0.7×0.6×0.7 + 0.3×0.6×0.3 = 0.348
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 45 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
A P(A)e 0.4¬ e 0.6
Alimentación
D P(D)si 0.1no 0.9
Deporte
F As e 0.26s ¬e 0.296n e 0.24n ¬e 0.348
fFIS(F , A)
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 46 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
El factor de la variable Alimentación (P(A)) no depende de ningunavariable, al ser una variable oculta generamos todas las posibilidades
fA(A)=Ae 0.4¬e 0.6
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 47 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
A P(A)e 0.4¬ e 0.6
fA(A)
D P(D)si 0.1no 0.9
Deporte
F As e 0.26s ¬e 0.296n e 0.24n ¬e 0.348
fFIS(F , A)
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 48 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
Ahora debemos acumular todos los factores calculados
fAFIS(F ,A) = fA(A)× fFIS(F ,A)=
F As e 0.26×0.4 = 0.104s ¬e 0.296×0.6 = 0.177n e 0.24×0.4 = 0.096n ¬e 0.348×0.6 = 0.208
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 49 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
Y ahora sumamos sobre todos los valores de la variable A para obtener elfactor correspondiente a la variable Alimentación
fAFIS(F ) =∑
A∈{e,¬e} fAFIS(F ,A) =Fs 0.104 + 0.177 = 0.281n 0.096 + 0.208 = 0.304
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 50 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
D P(D)si 0.1no 0.9
Deporte
Fs 0.281n 0.304
fAFIS(F )
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 51 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Algoritmo de eliminación de variables - ejemplo
Y por último la variable Deporte (P(D = n)) tiene el valor fijado a no ydado que no depende de la variable fumador se puede obviar, ya que es unfactor constante.Ahora, si normalizamos a 1
P(F |I = s,D = n) =Fs 0.48n 0.52
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 52 / 53
Redes Bayesianas Algoritmo de eliminación de variables - ejemplo
Complejidad de la inferencia exacta
La complejidad del algoritmo de eliminación de variables depende deltamaño del mayor factor, que depende del orden en el que se evalúanlas variables y la topología de la redEl orden de evaluación que escogeremos será el topológico según elgrafoLa complejidad de la inferencia exacta es NP-hard en el caso generalSi la red bayesiana cumple que para cada par de nodos hay un únicocamino no dirigido (poliárbol) entonces se puede calcular en tiempolinealPara calcular el caso general se recurre a algoritmos aproximadosbasados en técnicas de muestreo
cbea (LSI - FIB) Sistemas Basados en el Conocimiento IA - Curso 2008/2009 53 / 53