curso 2012-2013 juan domingo tardós dpto. informática e ingeniería de sistemas. inteligencia...

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

Inteligencia Artificial (30223)Lección 12. Probabilidad y Redes Bayesianas

2

ÍndiceProbabilidad. Conceptos básicos

Regla de Bayes

Independencia .vs. Independencia Condicional

Redes Bayesianas

D-Separación

Basado en las transparencias de Sebastian Thrun y Peter Norwig, CS221: Artificial Intelligence, Stanford University, 2011

3

El Problema de Monty HallConcurso de la tele (“Let’s make a deal”)

Hay tres puertas cerradas, tras una hay un coche y tras las otras, sendas cabras

El concursante elige una puerta, por ejemplo la 1 El presentador (Monty Hall) abre una de las otras dos puertas

Él sabe dónde está el coche y nunca lo muestra Da al concursante la opción de mantener su elección o cambiar

¿Cual es la decisión más racional? ¿Mantener la elección? ¿Cambiar de puerta? ¿Da igual?

Los creadores de “1,2,3 responda otra vez” ¿sabían cálculo de probabilidades?

4

Objetivo de este TemaRepresentación estructurada de la incertidumbre

bateríasin carga

el cocheno arranca

batería no se recarga

alternadorroto

correa alternador

rota

bateríamuerta

batería vieja

indicadorde la batería

lucesluz delaceite

indicador dela gasolina

varilla delaceite

sinaceite

singasolina

manguitogasolinaobstruído

motor dearranqueaveriado

5

ProbabilidadRepresenta la incertidumbre

Grado de creencia de un agente en una afirmación

Tiene fundamento matemático sólido

Aparece en todos los campos de la Inteligencia Artificial Aprendizaje Recuperación de información Visión por Computador Robótica

Ejemplo: vamos al dentistadolor_de_muelas caries

dolor_de_muelas caries problema_encías flemón ....caries dolor_de_muelas

P( dolor_de_muelas | caries ) = 0.8

?

?

?

6

RecordatorioX: variable aleatoria

x: un valor específico

Probabilidad condicional:

Tma Probabilidad Total:

Regla de Bayes:

X e Y son independientes si:

1)( x

xP0)()( xXPxP

)(

),()|(

yP

yxPyxP

)()|(),()( yPyxPyxPxPyy

'

)'()'|(

)()|(

)(

)()|()|(

y

yPyxP

yPyxP

xP

yPyxPxyP

YX

Distribución discreta

)()|(

)()|(

)()(),(:,

yPxyP

xPyxP

yPxPyxPyx

7

ProbabilidadProbabilidad incondicional o a priori:

Probabilidad condicional o a posteriori (dada una cierta evidencia):

5.0)()( caraPcaraMonedaP 5.0)( cruzP

2.0)( cariesP 8.0)( cariesP

01.0)(

29.0)(

1.0)(

6.0)(

nieveTiempoP

nubesTiempoP

lluviaTiempoP

solTiempoP

4.0)(

6.0)(

elasolor_de_mucaries | dP

elasolor_de_mucaries | dP

1)( x

xP

1)|( x

yxP

8

Probabilidad ConjuntaEventos múltiples: cancer, resultado de un test

Problema: para N variables binarias, hacen falta 2N-1 valores para especificar la distribución conjunta

)PositivoTest Cancer,(PTiene Cancer? Test Positivo? P(C,TP)

si si 0.018

si no 0.002

no si 0.196

no no 0.784

1),(,

yx

yxP

9

Probabilidades MarginalesPueden obtenerse a partir de la conjunta

Marginalizar:

Tiene Cancer? Test Positivo? P(C,TP)

si si 0.018

si no 0.002

no si 0.196

no no 0.784

y

yxPxP ),()(

C P(C)

si 0.02

no 0.98

TP P(TP)

si 0.214

no 0.786

10

Probabilidad CondicionalCaracterísticas del test:

Probabilidad a priori:

Podemos calcular la distribución conjunta:

9.0)( tp | cP

2.0)( ctp | P

02.0)( cP

1.0)( tp | cP

8.0)( ctp | P

98.0)( cP

Tiene Cancer? Test Positivo? P(C,TP)

si si 0.018

si no 0.002

no si 0.196

no no 0.784

)()|(),( yPyxPyxP

11

Probabilidad CondicionalPregunta de diagnóstico: ¿Como de probable es que

tenga cancer si ha dado test positivo?

Siendo un test relativamente bueno, porque sale tan baja? Porque la probabilidad a priori era muy baja:

084.0196.0018.0

018.0

)(

)()(

tpP

c, tpPc | tpP

Tiene Cancer? Test Positivo? P(C,TP)

si si 0.018

si no 0.002

no si 0.196

no no 0.784

02.0)( cP

12

Regla de Bayes

Ejemplo:

084.0196.0018.0

018.0

98.02.002.09.0

02.09.0

)()|()()|(

)()|(

)'()'|(

)()|(

)(

)()|()(

'

cPctpPcPctpP

cPctpP

cPctpP

cPctpP

tpP

cPctpPc | tpP

c

9.0)( tp | cP

2.0)( ctp | P

02.0)( cP1.0)( tp | cP

8.0)( ctp | P

98.0)( cP

916.0)()|()()|(

)()|(

)(

)()|()(

cPctpPcPctpP

cPctpP

tpP

cPctpPc | tpP

1)|( x

yxP

C

TP

'

)'()'|(

)()|(

)(

)()|()|(

y

yPyxP

yPyxP

xP

yPyxPxyP

13

Red Bayesiana (Bayes Network)Nuestra primera red Bayesiana:

La flecha indica que existe dependencia entre la v.a. Test_positivo y la v.a. Cancer

Cancer

Test positivo

P(Cancer) y P(Test positivo | Cancer) constituyen el “modelo”

A calcular P(Test positivo) se le llama “predicción”

A calcular P(Cancer | Test positivo) se le llama “razonamiendo diagnóstico”

14

Red BayesianaQue significan estas dos redes Bayesianas?:

Cancer

Test positiv

o

Cancer

Test positiv

o

versus

)()(

)()()(

CPC|TPP

CPTPPC,TPP

)()()( CPTP|CPC,TPP

Son v.a. Independientes:el test no aporta ninguna información sobre el cancer !!

El resultado del test depende del valor de la v.a. cancer

15

Bayes con Normalización Retrasada

Podemos hacer el cálculo sin normalizar:

Y después normalizar:

)()|()()|()()|(

)()|(

)(

)()|()|(

)()|()()|()()|(

)()|(

)(

)()|()|(

yPyxPyPyxPyPyxP

yPyxP

xP

yPyxPxyP

yPyxPyPyxPyPyxP

yPyxP

xP

yPyxPxyP

)()|()|('

)()|()|('

yPyxPxyP

yPyxPxyP

1)|(' y

xyP

)|(')|(

)|(')|(

)|(')|(' 1

yxPxyP

yxPxyP

xyPxyP

NO son probabilidades

1)|( y

xyP

16

Ejemplo: Cancer con dos tests

Cálculo normalizando al final:

9.0)( | cP

2.0)( c | P

02.0)( cP1.0)( | cP

8.0)( c | P

98.0)( cPC

T1 T2

P(C) P(T1+|C) P’(C|+) P(T2+|C) P’(C|++) P(C|++)

c 0.02 0.9 0.018 0.9 0.0162 0.2924

-c 0.98 0.2 0.196 0.2 0.0392 0.7076

0.0554 1.0000

17

IndependenciaDos variables aleatorias X e Y son independientes si:

Su distrubución conjunta se puede factorizar como el producto de dos distribuciones más simples

X no da información sobre Y, ni Y sobre X

Se denota mediante :

La independencia suele ser una suposición simplificadora del modelado Las distribuciones conjuntas empíricas en el mejor de los casos

son “cercanas” a ser independientes

YX

)()|(

)()|(

)()(),(:,

yPxyP

xPyxP

yPxPyxPyx

Son condiciones equivalentes

18

Ejemplo: IndependenciaN lanzamientos independientes de monedas:

c 0.5

x 0.5

c 0.5

x 0.5

c 0.5

x 0.5

19

Ejemplo: ¿Independencia?

y

yxPxP ),()(

x

yxPyP ),()(

T W P

warm sun 0.4

warm rain 0.1

cold sun 0.2

cold rain 0.3

T W P

warm sun 0.3

warm rain 0.2

cold sun 0.3

cold rain 0.2

T P

warm 0.5

cold 0.5

W P

sun 0.6

rain 0.4

Si fueran independientes:P(T,W) = P(T) P(W)

P(T)

P(T,W)

P(W)

Marginalizar

20

Independencia Condicional P(Dolor, Caries, Infección)

Si tengo caries, la sonda del dentista puede infectarme la muela Si tengo caries, es probable que tenga dolor de muelas

Luego dolor e infección no son independientes, si tengo dolor de muelas, es más probable que se infecte

P(Infección | Dolor) ≠ P(Infección)

Pero: si tengo una caries, la probabilidad de que la sonda infecte no depende de si tengo o no dolor de muelas:

P(Infección | Dolor, Caries) = P(Infección | Caries)

Infección y Dolor son Condicionalmente Independientes dado Caries

21

Independencia Condicional Condiciones equivalentes:

Lo denotamos mediante:

Atención:

)|(),|(

)|(),|(

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

zyPzxyP

zxPzyxP

zyPzxPzyxPzyx

ZYX |

Conocido Z, Y no da información adicional sobre X, ni X sobre Y

YXZYX

YXZYX

|

|ej: Dolor e Infeción son C.I. perono son Independientes

Luego veremos un ejemplo

22

Representación con Red BayesianaP(Dolor, Caries, Infección) requeriría 23-1 = 7 parámetros

Caries

Infección Dolor

P(Caries)p(+c)

P(Infección | Caries)P(+i|+c)P(+i|-c)

P(Dolor | Caries) P(+d|+c)P(+d|-c)

1 parámetro

2 parámetros 2 parámetros

Basta con 5 parámetros

CDI |

)()|()|(

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

CPCIPCDP

CPCIPCIDPCIDP

DI

23

Notación del GrafoNodos: variables (con sus

dominios) Pueden ser observadas o no

Arcos: interacciones Indican “influencia directa”

entre variables Formalmente: codifican la

independencia condicional

Podemos pensar que representan relación causal (aunque no es necesario)

Caries

Infección

Dolor

Tiempo

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

|;;;

CDPCIPCPTPDICTP

CDIDTITCT

24

Ejemplos

X1 X2 Xn

N lanzamientos de moneda independientes

No hay interacción entre las variables: independencia absoluta

La lluvia y el tráfico Modelo 1: independencia

Modelo 2: la lluvia causa tráfico

Un agente que use el modelo 2 se comportará mejor

LL T

LL T

25

Ejemplo: Sol o Ascenso?S: Sol, A: Ascenso, C: Contento

S A

C01.0)()|()|( aPsaPsaPAS

5254.0

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

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

aPsPascPaPsPascPaPsPascPaPsPascP

asPascPasPascPasPascPasPascPcP

97.0)(),|()(),|()|( sPsacPsPsacPacP

01.0)(

7.0)(

aP

sP

1.0),|(

7.0),|(

9.0),|(

1),|(

ascP

ascP

ascP

ascP

Razonamiento predictivo:

26

Independencia pero no Ind.Condic.S: Sol, A: Ascenso, C: Contento

S A

C

0185.0)(

)()|()|(

cP

aPacPcaP

01.0)(

7.0)(

aP

sP

1.0),|(

7.0),|(

9.0),|(

1),|(

ascP

ascP

ascP

ascP

0142.099.07.001.01

01.01

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

)(),|(

)|(

)|(),|(),|(

aPsacPaPsacP

aPsacP

scP

saPsacPscaP

Razonamiento diagnóstico:

0833.099.01.001.09.0

01.09.0

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

)(),|(

)|(

)|(),|(),|(

aPsacPaPsacP

aPsacP

scP

saPsacPscaP

AS

0833.0),|(

0142.0),|(

0185.0)|(

scaP

scaP

caP Si viene contento y no sabemos qué tiempo hace

Si hace sol, eso puede explicar la alegría

Si no hace sol, es más probable que sea por el ascenso

CASCAPSCAP |)|(),|(

27

Semántica de las Redes BayesianasUn conjunto de nodos, uno por cada

variable X

Un grafo dirigido acíclico (DAG)

Una distribución condicional por cada nodo Una colección de distribuciones sobre X, una por

cada combinación de los valores de los nodos padre

CPT: tabla de probabilidades condicionales Representación de un proceso “causal” con ruido

A1

X

An

Red Bayesiana = Topología (grafo) + Prob. Condicionales Locales

28

Probabilidades en Redes BayesianasUna red Bayesiana representa implícitamente las

distribuciones conjuntas Como un producto de distribuciones condicionales locales As a product of local conditional distributions Para calcular la probabilidad de una asignación concreta, se multiplican

todas la condiciones relevantes:

Ejemplo:

Permite reconstruir cualquier entrada de la tabla de probabilidades conjunta

No todas las RB pueden representar todas las distribuciones conjuntas La topología define qué condiciones de independencia se cumplen

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

Caries

Infección Dolor

n

iiin XpadresxPxxxP

121 )(|(),,(

29

Ejemplo: Lanzamiento de monedas

h 0.5

t 0.5

h 0.5

t 0.5

h 0.5

t 0.5

X1 X2 Xn

Solo las distribuciones cuyas variables son absolutamente independientes pueden modelarse mediante una red Bayesiana sin arcos.

30

Ejemplo: Tráfico

LL

T

+ll 1/4

ll 3/4

+ll +t 3/4

t 1/4

ll +t 1/2

t 1/2

LL T P(LL,T)

+ll +t 3/16

+ll -t 1/16

-ll +t 3/8

-ll -t 3/8

P(T | LL)

P(LL)

31

Ejemplo: Alarma AntirroboVariables

L: Ha entrado un Ladrón A: La Alarma se dispara M: María llama a avisar J: Juan llama a avisar T: Terremoto!

Ladrón Terremoto

Alarma

Juan llam

a

María llama

32

Ejemplo: Alarma Antirrobo

¿Número de parámetros?

1 1

4

2 2

10

Ladrón Terremoto

Alarma

Juan llam

a

María llama

En lugar de 25-1 = 31

33

Ejemplo: Alarma Antirrobo

Ladrón Terremoto

Alarma

Juan llam

a

María llama

L P(L)

+l 0.001

l 0.999

T P(T)

+t 0.002

t 0.998

L T A P(A|L,T)

+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

34

Ejemplo: Alarma Antirrobo

Ladrón Terremoto

Alarma

Juan llam

a

María llama

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

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

AMPAJPTLAPTPLP

XpadresXPMJATLPn

iii

)(LP )(TP

),|( TLAP

)|( AMP)|( AJP

35

Red BayesianaUn RB es una codificación

eficiente de un modelo probabilístico de un dominio

Preguntas que podemos hacer: Inferencia: dada una RB, ¿cual es P(X | e)? Representación: dado el grafo de una RB, ¿qué tipos de distribuciones

puede codificar? Modelado: ¿qué RB es más apropiada para representar un cierto dominio?

BN is most appropriate for a given domain?

36

Red Bayesiana del seguro del coche

37

Ejemplo: El coche que no arranca

Representación ingénua: 216-1 = 65535 parámetros Representación estructurada con RB: 47 parámetros

bateríasin carga

el cocheno arranca

batería no se recarga

alternadorroto

correa alternador

rota

bateríamuerta

batería vieja

indicadorde la batería

lucesluz delaceite

indicador dela gasolina

varilla delaceite

sinaceite

singasolina

manguitogasolinaobstruído

motor dearranqueaveriado

Ejercicio: Calcúlalo

38

D-separaciónObjetivo: Encontrar (In)Dependencias Condicionales en

una red Bayesiana Pregunta general: ¿son dos variables independientes dada una

cierta evidencia?

Solución: analizar el grafo Concepto de “d-separación”

Cualquier ejemplo complejo se puede analizar usando tres casos básicos:

Cadena causal Causa común Efecto común

39

Cadena CausalEsta configuración es una “cadena causal”

¿Es X independiente de Z dado Y?

La evidencia en una cadena “bloquea” la influencia

X Y Z

¡si!

X: Bajas Presiones

Y: Lluvia

Z: Tráfico

40

Causa ComúnDos efectos de la misma causa

¿Son X y Z independientes?

¿Son X y Z independientes dado Y?

Observar la causa bloquea la influencia entre los efectos

X

Y

Z

¡si!

Y: Alarma

X: Juan llama

Z: María Llama

¡no!

41

Efecto ComúnDos causas de un mismo efecto

(estructura en v) ¿Son X y Z independentes?

el partido de futbol y la lluvia causan tráfico, pero futbol y lluvia no están relacionados

¿Son X y Z independientes dado Y? si hay tráfico, la lluvia y el fútbol entran en

competencia como explicación

Al revés que en los casos anteriores: Observar un efecto activa la influencia

entre las posibles causas

X

Y

Z

X: Lluvia

Z: Fútbol

Y: Tráfico

¡si!

¡no!

42

Alcanzabilidad (D-Separación) Pregunta: ¿cuándo son X e Y

condicionalmente independentes dadas las variables de evidencia {Z}? Cuando X e Y están d-separados por

Z Cuando no hay ningún camino activo

de X a Y

Un camino es activo si todos sus tripletes son activos: Cadena causal A B C donde B no es

observada (en ambas direcciones) Causa común A B C donde B no es

observada Efecto común (estructura en v)

A B C donde B o uno de sus descendientes es observado

Un solo triplete inactivo bloquea un camino

Tripletes Activos Tripletes Inactivos

Sombreamos las variables de evidencia

43

Ejemplos¿Cuales de estas propiedades se cumplen?

R

T

B

T’

si

no

no

44

Ejemplo ¿Cuales de estas propiedades se cumplen?

R

T

B

D

L

T’

si

si

si

no

no

45

EjemploVariables:

R: Raining T: Traffic D: Roof drips S: I’m sad

¿Cuales se cumplen?

T

S

D

R

si

no

no

46

¿Causalidad?Cuando una Red Bayesiana refleja la causalidad real del

dominio:Suele ser más simple (los nodos tienen menos padres)Suele ser más fácil razonar con ellaSuele ser más fácil de obtener a partir de expertos

Pero las Redes Bayesianas no necesitan ser causalesA veces no existe una red causal para el dominioLa red acaba teniendo flechas que reflejan correlación, no

relación causal

Entonces, ¿qué significan exactamente las flechas?La topología puede que represente la estructura causal La topología siempre representa la independencia

condicional

47

ResumenRed Bayesiana:

Captura las dependencias dispersas entre variables No todas dependen de todas, sólo suele haber unas pocas

relaciones Representación eficiente de distribuciones conjuntas Reduce el número de parámetros de exponencial a lineal (en

muchos casos)

Próximo tema: Inferencia en redes Bayesianas

Inteligencia Artificial

(30223) Grado en Ingeniería Informática

Lección 12. Probabilidad y Redes BayesianasAIMA-3ed 13.1 a 13.5 (AIMA-2ed 13.1 a 13.6)

Tema 3 de www.ai-class.com