Curso 2012-2013Juan Domingo Tardós Dpto. Informática e Ingeniería de Sistemas.

Inteligencia Artificial (30223)Lección 13. Razonamiento Probabilista

2

ÍndiceConstrucció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

3

Ejemplo: Alarma Antirrobo

Burglary Earthquake

Alarm

John calls

Mary calls

B P(B)

+b 0.001

b 0.999

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

+b e a 0.06

b +e +a 0.29

b +e a 0.71

b e +a 0.001

b e a 0.999

A J P(J|A)

+a +j 0.9

+a j 0.1

a +j 0.05

a j 0.95

A M P(M|A)

+a +m 0.7

+a m 0.3

a +m 0.01

a m 0.99

4

Semántica de las Redes Bayesianas

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

B E

A

J M

n

iiin XpadresxPxxxP

121 )(|(),,(

5

Correlación no implica CausalidadSi 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

Las tres redes Bayesianas son correctas y permiten hacer inferencias

Sólo la terecera refleja la causalidad real del dominio

Z

D

D

Z

B

Z D

Borrachera

))(|(),,(1

21

n

iiin XpadresXPXXXP

6

Construcción de una Red Bayesiana

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

n

iii

n

iii

nnnn

nnnn

XpadresxP

xxxP

xPxxPxxxPxxxP

xxPxxxPxxxP

1

111

11212111

111121

))(|(

),|(

)()|()|(),|(

),(),|(),,(

7

Causalidad y Correlación

B E

A

J M

J M

A

B E

Orden: {B, E, A, J, M} Orden: {J, M, A, B, E}

8

Causalidad y Correlación

B E

A

J M

M J

E

B A

Orden: {B, E, A, J, M} Orden: {M, J, E, B, A}

9

Inferencia ProbabilistaResponder a preguntas sobre probabilidad a partir

de un Red Bayesiana Para cada pregunta las variables se pueden dividir en 3 grupos:

Probabilidad a posteriori:

Explicación más probable:

B E

A

J M

Q: Nodos Consulta (Query)

H: Nodos Ocultos (Hidden)

E: Nodos Evidencia

10

Inferencia ProbabilistaEn dirección causal:

E: nodo(s) raízQ: nodo(s) hoja

En dirección diagnóstica:E: nodo(s) hojaQ: nodo(s) raíz

EjemploMaría llama, queremos saber la probabilidad de Ladrón

E: {M}Q: {B}H: {E,A,J}

B E

A

J M

Cau

sal

Dia

gnós

tico

11

Inferencia por EnumeraciónCon 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

12

Inferencia por Enumeración

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) =

B E

A

J M

13

Inferencia por EnumeraciónOptimización: sacar términos de los

sumatorios

= 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)

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)

B E

A

J M

14

Inferencia por Enumeración

Problema: Habría que sumar 106 términos

¿Como podemos hacer que la inferencia sea tratable?

15

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)

16

Tipos de “factores”

Distribución conjunta: P(X,Y) Entradas P(x,y) para todas las x, y Suman 1

Conjunta seleccionada: P(x,Y) Una rodaja de la conjunta Entradas P(x,y) para x fijo, todas las

y Suman P(x)

T W P

hot sun 0.4

hot rain 0.1

cold sun 0.2

cold rain 0.3

T W P

cold sun 0.2

cold rain 0.3

17

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)

Condicional simple: P(Y | x) Entradas P(y|x) para x fijo, todas las y Suman 1

T W P

hot sun 0.8

hot rain 0.2

cold sun 0.4

cold rain 0.6

T W P

cold sun 0.4

cold rain 0.6

18

Tipos de “factores”

Familia específica: P(y|X) Entradas P(y|x) para y fijo,

todas las x Suman … ¿quién sabe?

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

T W P

hot rain 0.2

cold rain 0.6

19

Ejemplo: Dominio del TráficoVariables Aleatorias

R: Raining T: Traffic L: Late for class

T

L

R

+r 0.1

-r 0.9

+r +t 0.8

+r -t 0.2

-r +t 0.1

-r -t 0.9

+t +l 0.3

+t -l 0.7

-t +l 0.1

-t -l 0.9

P (L | T )

20

Esquema general de la Eliminación Ir construyendo matrices multi-dimensionales llamadas factores

Factores iniciales: tablas de prob. condicional, una por nodo

Seleccionar los valores conocidos P. ej. Si sabemos que L=+l, los factores iniciales quedan:

EV: Ir alternando: unir factores y eliminar variables

+r 0.1

-r 0.9

+r +t 0.8

+r -t 0.2

-r +t 0.1

-r -t 0.9

+t +l 0.3

+t -l 0.7

-t +l 0.1

-t -l 0.9

+t +l 0.3

-t +l 0.1

+r 0.1

-r 0.9

+r +t 0.8

+r -t 0.2

-r +t 0.1

-r -t 0.9

21

Operación 1: Unir FactoresUnir 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

Para cada entrada: productos punto a punto:

+r 0.1

-r 0.9

+r +t 0.8

+r -t 0.2

-r +t 0.1

-r -t 0.9

+r +t 0.08

+r -t 0.02

-r +t 0.09

-r -t 0.81T

R

R,T

22

Operacióm 2: EliminarSegunda 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 +t 0.08+r -t 0.02-r +t 0.09-r -t 0.81

+t 0.17-t 0.83

23

Ejemplo: Calcular P(L), paso 1

Sum out R

T

L

+r +t 0.08+r -t 0.02-r +t 0.09-r -t 0.81

+t +l 0.3+t -l 0.7-t +l 0.1-t -l 0.9

+t 0.17-t 0.83

+t +l 0.3+t -l 0.7-t +l 0.1-t -l 0.9

T

R

L

+r 0.1-r 0.9

+r +t 0.8+r -t 0.2-r +t 0.1-r -t 0.9

+t +l 0.3+t -l 0.7-t +l 0.1-t -l 0.9

Join R

R, T

L

24

Ejemplo: Calcular P(L), paso 2

Join T Sum out TT, L L

Early marginalización is variable eliminación

T

L

+t 0.17-t 0.83

+t +l 0.3+t -l 0.7-t +l 0.1-t -l 0.9

+t +l 0.051+t -l 0.119-t +l 0.083-t -l 0.747

+l 0.134-l 0.886

25

EvidenciaSi hay evidencia, comenzar con factores que la seleccionen

Si no hay evidencia los factores iniciales son:

Para calcular P(L |+r), los factores iniciales son:

Eliminar todas las variables que no sean query o evidencia

+r 0.1

-r 0.9

+r +t 0.8

+r -t 0.2

-r +t 0.1

-r -t 0.9

+t +l 0.3

+t -l 0.7

-t +l 0.1

-t -l 0.9

+r 0.1 +r +t 0.8

+r -t 0.2

+t +l 0.3

+t -l 0.7

-t +l 0.1

-t -l 0.9

26

Evidencia IIEl resultado será una conjunción seleccionada de query y

evidencia P. ej. para P(L | +r), terminaremos con:

+l 0.26-l 0.74

+r +l 0.026+r -l 0.074

Normalizar

27

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

28

EjemploQueremos obtener:

Factores iniciales instanciados:

Elegimos A

Σ a

B E

A

J M

29

Ejemplo

Elegimos E:

Terminamos con B:

Normalizar

Σ e

30

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 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) 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 Calcular el orden óptimo es intratable Hay buenas heurísticas: eliminar la variable que minimiza el

tamaño del próximo factor a crear

B E

A

J M

S R

W

C

31

Inferencia Aproximada por MuestreoMuestrear / 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

conoceP(“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)

32

Muestreo por PrioriPartimos de una red sin evidencias

Cloudy

Sprinkler Rain

WetGrass

Cloudy

Sprinkler Rain

WetGrass

+c 0.5

-c 0.5

+c+s 0.1

-s 0.9

-c+s 0.5

-s 0.5

+c+r 0.8

-r 0.2

-c+r 0.2

-r 0.8

+s

+r+w 0.99

-w 0.01

-r

+w 0.90

-w 0.10

-s+r

+w 0.90

-w 0.10

-r+w 0.01

-w 0.99

Muestras:

+c, -s, +r, +w-c, +s, -r, +w

…

33

Muestreo por PrioriEste 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

34

EjemploObtenemos un conjunto de muestras de la RB:

+c, -s, +r, +w

+c, +s, +r, +w

-c, +s, +r, -w

+c, -s, +r, +w

-c, -s, -r, +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

Cloudy

Sprinkler Rain

WetGrass

C

S R

W

35

Muestreo por RechazoSupongamos que queremos P(C)

No hace falta mantener todas las muestras Simplemente contar los +c y –c sobre la marcha

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

Cloudy

Sprinkler Rain

WetGrass

C

S R

W

36

EjemploTenemos 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 251 2525 2525 125 251 2525 2525 125 2525 2525 11 251 2525 251 251 2525 2525 11 2525 2525 2525 25

747/1000

37

Ponderación por VerosimilitudProblema 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 Supongamos que queremos P(B|+a)

Idea: fijar la evidencia y muestrear el resto

La distribución de las muestras no es consistente

Solución: ponderar cada muestra con la probabilidad de la evidencia dados los padres

Burglary Alarm

Burglary Alarm

-b, -a -b, -a -b, -a -b, -a+b, +a

-b +a -b, +a -b, +a -b, +a+b, +a

38

EjemploQueremos: P(R|+s,+w)

+c 0.5

-c 0.5

+c+s 0.1

-s 0.9

-c+s 0.5

-s 0.5

+c+r 0.8

-r 0.2

-c+r 0.2

-r 0.8

+s

+r+w 0.99

-w 0.01

-r

+w 0.90

-w 0.10

-s+r

+w 0.90

-w 0.10

-r+w 0.01

-w 0.99

Samples:

+c, +s, +r, +w…

Cloudy

Sprinkler Rain

WetGrass

Cloudy

Sprinkler Rain

WetGrass0.099

39

Ponderación por VerosimilitudSi z son los nodos muestreados y e los nodos evidencia fijos, la

distribución de las muestras es:

Las muestras tienen pesos:

Juntándolo, la distribución de muestras ponderadas es consistente:

Cloudy

R

C

S

W

40

Ponderación por VerosimilitudEs buena

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

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

Cloudy

Rain

C

S R

W

41

Muestreo de GibbsEs 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

42

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

.....

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

Muestreo de Gibbs

Cloudy

Rain

C

S R

W

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