PDF de programación - Razonamiento con Incertidumbre

Razonamiento con Incertidumbre

c b e a

CS - FIB - UPC

Curso 2013/2014

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

1 / 56

Razonamiento con incertidumbre

1 Razonamiento con incertidumbre

2 Modelos Probabilistas

3 Redes Bayesianas

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

2 / 56

Razonamiento con incertidumbre

Introducción

Incertidumbre y conocimiento

Todos los mecanismos de representación de conocimiento vistos están
basados en la lógica bajo estos supuestos:

Todo hecho sobre el que razonemos debe poder ser evaluado como
cierto o falso

Para poder razonar necesitamos tener todos los hechos a nuestra
disposición

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

3 / 56

Razonamiento con incertidumbre

Introducción

Incertidumbre y conocimiento

Pero en la práctica nos encontramos con estos problemas

Representar el conocimiento para cubrir todos los hechos que son
relevantes para un problema es difícil

Existen dominios en los que se desconocen todos los hechos y reglas
necesarias para resolver el problema

Existen problemas en los que aún teniendo las reglas para resolverlos no
disponemos de toda la información necesaria o no tenemos confianza
absoluta en ellas

En otros problemas la reglas no se aplican siempre o su confianza
cambia con la confianza que tenemos en los hechos

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

4 / 56

Modelos Probabilistas

1 Razonamiento con incertidumbre

2 Modelos Probabilistas

3 Redes Bayesianas

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

5 / 56

Modelos Probabilistas

Introducción

Modelos Probabilistas

Los modelos probabilistas se basan en la teoría de la probabilidad

Las probabilidades se utilizan para modelizar nuestra creencia sobre
los posibles valores que pueden tomar los hechos

Cada hecho tendrá una distribución de probabilidad asociada que nos
permitirá tomar decisiones

La probabilidad de un hecho podrá ser modificada por nuestra
creencia en otros hechos que estén relacionados

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

6 / 56

Modelos Probabilistas

Introducción

Decisiones Probabilistas

¿Cogerás un paraguas mañana?

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

7 / 56

Modelos Probabilistas

Introducción

Decisiones Probabilistas

¿Cogerás un paraguas mañana?

Vivo en Barcelona, no llueve nunca

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

7 / 56

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

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

7 / 56

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

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

7 / 56

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

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

7 / 56

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

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

7 / 56

Modelos Probabilistas

Teoría de probabilidades

Teoría de probabilidades

El elemento básico de teoría de probabilidades es la variable aleatoria

Una variable aleatoria tiene un dominio de valores, podemos tener
variables aleatorias booleanas, discretas o continuas.

Definiremos una proposición lógica como cualquier fórmula en lógica
de enunciados o predicados

Una proposición lógica tendrá asociada una variable aleatoria que
indicará nuestro grado de creencia en ella

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

8 / 56

Modelos Probabilistas

Teoría de probabilidades

Teoría de probabilidades

Una variable aleatoria tendrá asociada una distribución de
probabilidad

La forma de expresar esta distribución de probabilidad dependerá del
tipo de variable aleatoria (Discretas: Binomial, Multinomial, ...,
Continuas: Normal, χ2, ...)

Nosotros trabajaremos sólo con variables aleatorias discretas

La unión de variables aleatorias se puede describir mediante una
distribución de probabilidad conjunta

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

9 / 56

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ón Fumar puede tener los valores
{fumar ,¬fumar}, P(¬fumar) es la probabilidad de la proposición
Fumar = ¬fumar

Denotaremos como P(A) al vector de probabilidades de todos los
posibles valores de la proposición A

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

10 / 56

Modelos Probabilistas

Teoría de probabilidades

Teoría de probabilidades

Definiremos como probabilidad a priori (P(a)) asociada a una
proposición como el grado de creencia en ella a falta de otra
información
Definiremos como probabilidad a posteriori o condicional (P(a|b))
como el grado de creencia en una proposición tras la observación de
proposiciones asociadas a ella
La probabilidad a posteriori se puede definir a partir de probabilidades
a priori como:

P(a|b) = P(a ∧ b)
P(b)

Esta fórmula transforma en la regla del producto:

P(a ∧ b) = P(a|b)P(b) = P(b|a)P(a)

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

11 / 56

Modelos Probabilistas

Teoría de probabilidades

Axiomas de la probabilidad

Los axiomas de la probabilidad serán el marco que restringirá las cosas que
podremos 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 tiene
probabilidad 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)

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

12 / 56

Modelos Probabilistas

Inferencia probabilística

Inferencia probabilística

Marginalización: Probabilidad de una proposición atómica con
independencia de los valores del resto de proposiciones

P(Y ) =X

z

P(Y , z)

Probabilidades condicionadas: Probabilidad de una proposición
dados unos valores para algunas proposiciones e independiente del
resto de proposiciones (a partir de la regla del producto)

P(X|e) = α

P(X , e, y)

X

y

El valor α es un factor de normalización que corresponde a factores
comunes que hacen que las probabilidades sumen 1

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

13 / 56

Modelos Probabilistas

Inferencia probabilística

Inferencia probabilística: ejemplo

Consideremos un problema en el que intervengan las proposiciones:
Fumador = {fumador ,¬fumador}
Sexo = {varon, mujer}
Enfisema = {enfisema,¬enfisema}

enfisema

varon mujer
0.1
0.2
0.02
0.02

¬enfisema
varon mujer
0.05
0.05
0.23
0.33

fumador
¬fumador

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

14 / 56

Modelos Probabilistas

Inferencia probabilística

Inferencia probabilística: ejemplo

P(enfisema ∧ varon) = 0,2 + 0,02

P(fumador ∨ mujer) = 0,2 + 0,1 + 0,05 + 0,05 + 0,02 + 0,33

P(Fumador|enfisema) = hP(fumador , enfisema, varon)
+P(fumador , enfisema, mujer),
P(¬fumador , enfisema, varon)
+P(¬fumador , enfisema, mujer)i

= αh0,3, 0,04i
= h0,88, 0,12i

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

15 / 56

Modelos Probabilistas

Inferencia probabilística

Inferencia probabilística: Problema

Hacer estos procesos de inferencia requiere almacenar y recorrer la
distribución de probabilidad conjunta de todas las proposiciones
Suponiendo proposiciones binarias el coste en espacio y tiempo es
O(2n) siendo n el número de proposiciones
Para cualquier problema real estas condiciones son impracticables
Necesitamos mecanismos que nos simplifiquen el coste del
razonamiento

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

16 / 56

Modelos Probabilistas

Independencia probabilística - Bayes

Independencia probabilística

Por lo general no todas las proposiciones que aparecen en un
problema están relacionadas entre si
Muestran la propiedad que denominaremos independencia
probabilística
Esto quiere decir que unas proposiciones no influyen en las otras y por
lo 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 probabilidades
conjuntas de manera mas compacta reduciendo la complejidad

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

17 / 56

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 del
razonamiento probabilístico y nos permitirá relacionar las
probabilidades de unas evidencias con otras

c b e a (CS - FIB - UPC)

Razonamiento con Incertidumbre

Curso 2013/2014

18 / 56

Modelos Probabilistas

Independencia probabilística - Bayes

La regla de Bayes + Independencia condicional

Suponiendo que podemos estimar exhaustivamente todas las
probabilidades que involucran todos los valores de la variable Y
podemos reescribir la formula de Bayes