Inteligencia
Artificial (30223)
Lección 13. Razonamiento
Probabilista
Curso 2012-2013
Juan Domingo Tardós
Dpto. Informática e Ingeniería de Sistemas.
Índice
 Construcción de Redes Bayesianas
 Correlación y Causalidad
 Inferencia por Enumeración
 Eliminación de Variables
 Inferencia Aproximada por Muestreo
 Basado en las transparencias de Sebastian Thrun y Peter Norwig,
CS221: Artificial Intelligence, Stanford University, 2011
2
Ejemplo: Alarma Antirrobo
B
P(B)
+b
0.001
b
0.999
Burglary
Earthquake
E
P(E)
+e
0.002
e
0.998
B
E
A
P(A|B,E)
+b
+e
+a
0.95
+b
+e
a
0.05
+b
e
+a
0.94
Alarm
John
calls
Mary
calls
A
J
P(J|A)
A
M
P(M|A)
+b
e
a
0.06
+a
+j
0.9
+a
+m
0.7
b
+e
+a
0.29
+a
j
0.1
+a
m
0.3
b
+e
a
0.71
a
+j
0.05
a
+m
0.01
b
e
+a
0.001
a
j
0.95
a
m
0.99
b
e
a
0.999
3
Semántica de las Redes Bayesianas
B
E
A
J
M
n
P ( x1 , x 2 ,  x n ) 
 P(x
i
| padres ( X i )
i 1
 La topología representa la (in)dependencia condicional
 Puede reflejar la causalidad real del dominio
 La red resultante suele ser más simple de obtener
4
Correlación no implica Causalidad
 Si observamos que existe correlación entre A y B, es decir,
no son independientes:
 ¿A causa B?
 ¿B causa A?
 ¿C causa A y B?
 Ejemplo: quienes duermen con zapatos sufren dolor de
cabeza
Borrachera
Z
D
B
n
P ( X 1 , X 2 , X n ) 
D
 P(X
i
| padres ( X i ) )
i 1
Z
Z
D
 Las tres redes Bayesianas son correctas y permiten hacer inferencias
 Sólo la terecera refleja la causalidad real del dominio
5
Construcción de una Red Bayesiana
P ( x1 , x 2 ,  x n )  P ( x n | x n  1 ,  x1 ) P ( x n  1 ,  x1 )
 P ( x n | x n  1 ,  x1 ) P ( x n  1 | x n  2  x1 )  P ( x 2 | x1 ) P ( x1 )
n

 P(x
i
| x i  1 ,  x1 )
i
| padres ( X i ))
i 1
n

 P(x
i 1

Algoritmo de construcción:
1. Nodos: Determinar el conjunto de variables necesarias para modelar el
problema y ordenarlas {X1, ... Xn}. La red será más compacta si las causas
preceden a los efectos
2. Arcos:
For i = 1 to n do:
Elegir entre {X1, ... Xi-1} un conjunto mínimo de padres para Xi
Para cada padre, insertar un arco del padre a Xi
Escribir la tabla de probabilidades condicionales P(Xi|padres(Xi)
End for
6
Causalidad y Correlación
Orden: {B, E, A, J, M}
B
E
Orden: {J, M, A, B, E}
J
A
J
M
A
M
B
E
7
Causalidad y Correlación
Orden: {B, E, A, J, M}
B
E
Orden: {M, J, E, B, A}
M
J
E
A
J
M
B
A
8
Inferencia Probabilista
 Responder a preguntas sobre probabilidad a partir
de un Red Bayesiana
 Para cada pregunta las variables se pueden dividir en 3 grupos:
B
E
A
J
Q: Nodos Consulta (Query)
H: Nodos Ocultos (Hidden)
M
E: Nodos Evidencia
 Probabilidad a posteriori:
 Explicación más probable:
9
Inferencia Probabilista
 En dirección diagnóstica:
 E: nodo(s) hoja
 Q: nodo(s) raíz
B
Causal
 E: nodo(s) raíz
 Q: nodo(s) hoja
E
Diagnóstico
 En dirección causal:
A
J
M
 Ejemplo
 María llama, queremos saber la probabilidad de Ladrón
 E: {M}
 Q: {B}
 H: {E,A,J}
10
Inferencia por Enumeración
 Con tiempo ilimitado, la inferencia en RB es fácil
 Receta:
 Ver que probabilidades incondicionales se necesitan para
responder a la pregunta
 Enumerar todas las probabilidades atómicas (para todos los
posibles valores de las variables H)
 Calcular suma de productos
 Ejemplo:
B
E
A
J
M
11
Inferencia por Enumeración
B
P(+b, +j, +m)
= ∑e ∑a P(+b, +j, +m, e, a)
= ∑e ∑a P(+b) P(e) P(a|+b,e) P(+j|a) P(+m|a)
E
A
J
M
=
12
Inferencia por Enumeración
 Optimización: sacar términos de los
sumatorios
B
E
A
P(+b, +j, +m)
J
M
= ∑e ∑a P(+b, +j, +m, e, a)
= ∑e ∑a P(+b) P(e) P(a|+b,e) P(+j|a) P(+m|a)
= P(+b) ∑e P(e) ∑a P(a|+b,e) P(+j|a) P(+m|a)
ó
= P(+b) ∑a P(+j|a) P(+m|a) ∑e P(e) P(a|+b,e)
13
Inferencia por Enumeración
 Problema: Habría que sumar 106 términos
 ¿Como podemos hacer que la inferencia sea tratable?
14
Eliminación de Variables
 ¿Por qué es tan lenta la inferencia por
enumeración?
 Se calcula la distribución conjunta completa antes de sumar
(marginalizar) a lo largo de las variables ocultas
( ∑e ∑a P(+b) P(e) P(a|+b,e) P(+j|a) P(+m|a) )
 Se repite un montón de trabajo!
 Idea: entremezclar conjunción y marginalización
 Se denomina “Eliminación de variables”
 Todavía es NP-hard, pero mucho más rápido que enumeración
 Requiere combinar “factores” (arrays multi-dimensionales)
15
Tipos de “factores”
 Distribución conjunta: P(X,Y)
T
W
 Entradas P(x,y) para todas las x, y
hot
sun
0.4
 Suman 1
hot
rain
0.1
cold
sun
0.2
cold
rain
0.3
T
W
cold
sun
0.2
cold
rain
0.3
 Conjunta seleccionada: P(x,Y)
 Una rodaja de la conjunta
 Entradas P(x,y) para x fijo, todas las y
 Suman P(x)
P
P
16
Tipos de “factores”
 Famila de condicionales: P(X|Y)
 Valores condicionales múltiples
 Entradas P(x|y) para todas las x, y
 Suman |Y|
(p.e. si Y es Booleana: 2)
T
W
P
hot
sun
0.8
hot
rain
0.2
cold
sun
0.4
cold
rain
0.6
 Condicional simple: P(Y | x)
 Entradas P(y|x) para x fijo, todas las y
 Suman 1
T
W
P
cold
sun
0.4
cold
rain
0.6
17
Tipos de “factores”
 Familia específica: P(y|X)
T
W
P
 Entradas P(y|x) para y fijo,
todas las x
hot
rain
0.2
 Suman … ¿quién sabe?
cold
rain
0.6
 En general, cuando escribimos P(Y1 … YN | X1 … XM)
 Es un factor, una matriz multi-dimensional
 Sus valores son todas las P(y1 … yN | x1 … xM)
 Cualquier X o Y asignada (valor fijo) es una dimensión que falta en la matriz
18
Ejemplo: Dominio del Tráfico
 Variables Aleatorias
 R: Raining
+r
0.1
 T: Traffic
-r
0.9
 L: Late for class
R
T
L
+r
+t
0.8
+r
-t
0.2
-r
+t
0.1
-r
-t
0.9
P (L | T )
+t
+l
0.3
+t
-l
0.7
-t
+l
0.1
-t
-l
0.9
19
Esquema general de la Eliminación
 Ir construyendo matrices multi-dimensionales llamadas factores
 Factores iniciales: tablas de prob. condicional, una por nodo
+r
0.1
+r
+t
0.8
+t
+l
0.3
-r
0.9
+r
-t
0.2
+t
-l
0.7
-r
+t
0.1
-t
+l
0.1
-r
-t
0.9
-t
-l
0.9
 Seleccionar los valores conocidos
 P. ej. Si sabemos que L=+l, los factores iniciales quedan:
+r
0.1
+r
+t
0.8
+t
+l
0.3
-r
0.9
+r
-t
0.2
-t
+l
0.1
-r
+t
0.1
-r
-t
0.9
 EV: Ir alternando: unir factores y eliminar variables
20
Operación 1: Unir Factores
 Unir factores:
 Parecido a un “join” en una base de datos
 Tomar todos los factores que mencionan la variable a unir
 Construir un nuevo factor con la unión de todas las variables involucradas
 Ejemplo: Unión sobre R
R
T
+r
0.1
+r
+t
0.8
+r
+t
0.08
-r
0.9
+r
-t
0.2
+r
-t
0.02
-r
+t
0.1
-r
+t
0.09
-r
-t
0.9
-r
-t
0.81
R,T
 Para cada entrada: productos punto a punto:
21
Operacióm 2: Eliminar
 Segunda operación básica: marginalización
 Tomar un factor, y sumar sobre una variable, para quitarla
 El factor se reduce de tamaño
 Es una operación de proyección
 Ejemplo:
+r
+r
-r
-r
+t
-t
+t
-t
0.08
0.02
0.09
0.81
+t
-t
0.17
0.83
22
Ejemplo: Calcular P(L), paso 1
+r
-r
R
T
L
0.1
0.9
+r
+r
-r
-r
+t
-t
+t
-t
0.8
0.2
0.1
0.9
+t
+t
-t
-t
+l
-l
+l
-l
0.3
0.7
0.1
0.9
Sum out R
Join R
+r
+r
-r
-r
+t
-t
+t
-t
0.08
0.02
0.09
0.81
+t
-t
0.17
0.83
T
R, T
+t
+t
-t
-t
+l
-l
+l
-l
0.3
0.7
0.1
0.9
L
+t
+t
-t
-t
+l
-l
+l
-l
0.3
0.7
0.1
0.9
L
23
Ejemplo: Calcular P(L), paso 2
T
T, L
Join T
Sum out T
L
L
+t
-t
+t
+t
-t
-t
0.17
0.83
+l
-l
+l
-l
0.3
0.7
0.1
0.9
+t
+t
-t
-t
+l
-l
+l
-l
0.051
0.119
0.083
0.747
+l
-l
0.134
0.886
Early marginalización is variable eliminación24
Evidencia
 Si hay evidencia, comenzar con factores que la seleccionen
 Si no hay evidencia los factores iniciales son:
+r
0.1
+r
+t
0.8
+t
+l
0.3
-r
0.9
+r
-t
0.2
+t
-l
0.7
-r
+t
0.1
-t
+l
0.1
-r
-t
0.9
-t
-l
0.9
 Para calcular P(L |+r), los factores iniciales son:
+r
0.1
+r
+t
0.8
+t
+l
0.3
+r
-t
0.2
+t
-l
0.7
-t
+l
0.1
-t
-l
0.9
 Eliminar todas las variables que no sean query o evidencia
25
Evidencia II
 El resultado será una conjunción seleccionada de query y
evidencia
 P. ej. para P(L | +r), terminaremos con:
Normalizar
+r
+r
+l
-l
0.026
0.074
+l
-l
0.26
0.74
26
Eliminación de Variables General
 Query:
 Empezar con factores iniciales:
 Tablas de Prob. Condicional, instanciadas con la evidencia
 Mientras queden variables ocultas (no Q ni evidencia):
 Elegir una variable oculta H
 Juntar todos los factores que mencionan a H
 Eliminar H (sumando)
 Juntar todos los factores restantes, y normalizar
27
Ejemplo
B
 Queremos obtener:
E
A
 Factores iniciales instanciados:
J
M
 Elegimos A
Σa
28
Ejemplo
 Elegimos E:
Σe
 Terminamos con B:
Normalizar
29
Complejidad de la Eliminación de Variables
 El coste depende del factor intermedio más grande que
se genere, que a su vez depende de:
1. La estructura de la red
B
 Polytrees: si entre dos nodos cualesquiera hay
como máximo un único camino (no-dirigido)
 La complejidad en tiempo y memoria es
lineal con el tamaño de la red (nº de TPC)
A
J
 Si el numero de padres por nodo < k ,
es lineal con el número de nodos
 Redes con conexiones múltiples:
en el peor de los casos el coste es exponencial
2. El orden de eliminación de las variables
E
M
C
S
R
W
 Calcular el orden óptimo es intratable
 Hay buenas heurísticas: eliminar la variable que minimiza el tamaño
del próximo factor a crear
30
Inferencia Aproximada por Muestreo
 Muestrear / Simular / Observar
 Idea básica:
 Extraer N muestras de una distribución de muestreo S
 Calcular una distribución a posteriori aproximada
 De forma que la probabilidad estimada sea consistente: que
converga a la verdadera probabilidad P, cuando el número de
muestras tienda a infinito
 ¿Por qué muestrear?
 Aprendizaje: obtener muestras de una distribución que no se
conoce
P(“Viagra”|SPAM) y P(“Viagra”|¬SPAM)
 Inferencia: en redes complicadas, generar muestras es más rápido
que calcular la respuesta exacta (por ejemplo con eliminación de
variables)
31
Muestreo por Priori
 Partimos de una red sin evidencias
+c
0.5
-c
0.5
Cloudy
+c
-c
+s
+s
0.1
-s
0.9
+s
0.5
-s
0.5
+r
-r
-s
+r
-r
+c
Sprinkler
+w
0.99
-w
0.01
+w
0.90
-w
0.10
+w
0.90
-w
0.10
+w
0.01
-w
0.99
Rain
WetGrass
-c
+r
0.8
-r
0.2
+r
0.2
-r
0.8
Muestras:
+c, -s, +r, +w
-c, +s, -r, +w
…
32
Muestreo por Priori
 Este proceso genera muestras con probabilidad:
…es decir, la probabilidad conjunta de la Red Bayesiana
 Si el número de muestras de un evento es:
 Se cumple:
 Es decir, el procedimiento de muestreo es consistente
33
Ejemplo
 Obtenemos un conjunto de muestras de la RB:
+c, -s, +r, +w
+c, +s, +r, +w
Cloudy
C
-c, +s, +r, -w
+c, -s, +r, +w
Sprinkler
S
-c, -s, -r, +w
Rain
R
WetGrass
W
 Si queremos conocer P(W)
 Tenemos cuentas <+w:4, -w:1>
 Normalizamos para sacar P(W) = <+w:0.8, -w:0.2>
 Se aproximará a la distribución real con más muestras
 Rápido: si tenemos poco tiempo, podemos usar menos muestras, a costa de
la precisión de la aproximación
34
Muestreo por Rechazo
 Supongamos que queremos P(C)
Cloudy
C
 No hace falta mantener todas las muestras
 Simplemente contar los +c y –c sobre la marcha
Sprinkler
S
Rain
R
WetGrass
W
 Supongamos que queremos P(C| +s)
 Contamos los +c y –c, pero ignorando (rechazando)
las muestras que no tienen S=+s
 Se llama muestreo por rechazo
 Es consistente (correcto en el límite)
+c, -s, +r, +w
+c, +s, +r, +w
-c, +s, +r, -w
+c, -s, +r, +w
-c, -s, -r, +w
35
Ejemplo
 Tenemos dos cajas
 Una tiene 1 penny (1c) y 1 quarter (25c)
 La otra tiene 2 quarters
 Elegimos aleatoriamente una de las
cajas y sacamos una moneda de esa
caja. Es un quarter.
¿Cual es la probabilidad de que la otra
moneda de la caja sea también un
quarter?
25 25
1 25
25 25
25 1
25 25
1 25
25 25
25 1
25 25
25 25
25 1
1 25
1 25
25 25
1 25
1 25
25 25
25 1
1 25
25 25
25 25
25 25
747/
1000
36
Ponderación por Verosimilitud
 Problema del muestreo por rechazo:
 Si la evidencia es muy poco probable, tiramos la mayoría de las muestras
 No se aprovecha la evidencia al muestrear
-b, -a
 Supongamos que queremos P(B|+a)
Burglary
Alarm
-b, -a
-b, -a
-b, -a
+b, +a
 Idea: fijar la evidencia y muestrear el resto
Burglary
Alarm
 La distribución de las muestras no es consistente
-b +a
-b, +a
-b, +a
-b, +a
+b, +a
 Solución: ponderar cada muestra con la probabilidad de la
evidencia dados los padres
37
Ejemplo
 Queremos: P(R|+s,+w)
+c
0.5
-c
0.5
Cloudy
+c
-c
+s
+s
0.1
-s
0.9
+s
0.5
-s
0.5
+r
-r
-s
+r
-r
+c
Sprinkler
+w
0.99
-w
0.01
+w
0.90
-w
0.10
+w
0.90
-w
0.10
+w
0.01
-w
0.99
Rain
WetGrass
-c
+r
0.8
-r
0.2
+r
0.2
-r
0.8
Samples:
+c, +s, +r, +w
…
0.099
38
Ponderación por Verosimilitud
 Si z son los nodos muestreados y e los nodos evidencia fijos, la
distribución de las muestras es:
Cloudy
C
 Las muestras tienen pesos:
S
R
W
 Juntándolo, la distribución de muestras ponderadas es consistente:
39
Ponderación por Verosimilitud
 Es buena
Cloudy
C
 Tiene en cuenta la evidencia al generar las
muestras
 En el ejemplo, el valor de W se muestrea teniendo
en cuenta los valores de evidencia de S y R
 Más parte de las muestras reflejan el estado del
universo sugerido por la evidencia
S
Rain
R
W
 Pero no resuelve todos los problemas
 La evidencia influye en la elección de variables
aguas abajo, pero no de las que está aguas
arriba. En el ejemplo, C no ha aumentado su
probabilidad de obtener valores que casen con la
evidencia
 Nos gustaría aprovechar la evidencia al
muestrear todas las variables
40
Muestreo de Gibbs
 Es un algoritmo de tipo Markov Chain Monte Carlo (MCMC)
 Idea: en lugar de generar cada muestra desde cero, crear
muestras que se parecen a la anterior
 Procedimiento:
 Supongamos que el sistema está en un cierto “estado”
 Repetir: Generar un nuevo estado remuestreando aleatoriamente
una de las variable, condicionada por todo el resto, siempre
manteniendo fija la evidencia.
 El conjunto de estados con sus probabilidades de transición forman
una “Cadena de Markov”
 El proceso alcanza un “equilibrio dinámico” en el que la fracción de
tiempo que se pasa en cada estado es proporcional a su
probabilidad a posteriori
 Hace falta que la cadena sea ergódica: todos los estados son
alcanzables desde otro y no hay ciclos períodicos estrictos
41
Muestreo de Gibbs
 Ejemplo: queremos P(c|+s, +w)
+c +s +w +r
Estado inicial
-c +s +w +r
muestreo C
-c +s +w +r
muestreo W
+c +s +w +r
muestreo C
+c +s -w +r
muestreo W
+c +s +w +r
muestreo W
Cloudy
C
S
Rain
R
W
.....
 Propiedades: las muestras no son independientes (de hecho,
las adyacentes son casi iguales), pero las medias muestrales
siguen siendo estimadores consistentes!
 Cual es la gracia: tanto las variables aguas arriba como aguas
abajo están condicionadas por la evidencia
42
Inteligencia
Artificial
(30223) Grado en Ingeniería Informática
Lección 13. Razonamiento Probabililista
AIMA 14.1 a 14.5
Tema 4 de www.ai-class.com
Descargar

L13_Razonamiento_Pro..