9 de Noviembre de 2016

1

APRENDIZAJE PROBABILÍSTICONAIVE BAYES

Bases de Datos Masivas

2

Razonamiento Probabilístico● Es una herramienta de aprendizaje estadístico.

● Se trata de razonar en un contexto incierto; y la mejor forma de representar la incertidumbre es a través de probabilidades.

Como vimos en temas previos vamos a trabajar en aprendizaje a partir de observaciones.

● Dado un conjunto de entrenamiento d y con un conjunto de hipótesis H, candidatas a ser aprendidas

● El conjunto de datos d representa una serie de evidencias observadas

● Las hipótesis de H son modelos probabilísticos de cómo funciona el dominio

Instancias de una variable aleatoria D

Una distribución de probabilidad

3

Ejemplo Partimos de un dataset como evidencia

Variables aleatorias que describen el dominio

Las hipótesis serán teorías probabilísticas de cómo funciona el dominio.

Nuestros caramelos preferidos tienen un envoltorio donde no es posible determinar el sabor

Cereza

Limón

Los caramelos se guardan en 5 bolsas

diferentes

h1 : 100% Cereza

h2 : 75% Cereza + 25% Limón

h3 : 50% Cereza + 50% Limón

h4 : 25% Cereza + 75% Limón

h5 : 100% Limón

[ Russell et al. 1996 ]

Dada una nueva bolsa

v.a. H denota una nueva bolsa que

puede ser de h1 a h

5

H no es directamente observable

Cuando se abre e inspecciona una bolsa se

revelan los datos D

1, D

2,..,D

n

Di es una en una

v.a. con valores posibles cereza y

limón

El objetivo de este sistema es predecir el sabor

del siguiente caramelo

4

Teorema de Bayes

Sea X una muestra de datos (evidencia): se desconoce su clase

Sea H la hipótesis de que X pertenece a la clase C

La clasificación es para determinar P(H|X): la probabilidad de que la hipótesis se sostenga dada una muestra de las observaciones X

P(H) es la probabilidad a priori, es decir la probabilidad inicial.

X va a comer un caramelo, independientemente del sabor, etc.

P(X): Probabilidad de observación de una muestra

P(X|H) probabilidad a posteriori, la probabilidad de observar la muestra dado que la hipótesis se sostiene.

Dado que X va a comer un caramelo cuál es la probabilidad que sea de Cereza

5

Teorema de BayesTeniendo en cuenta los datos de entrenamiento X, la probabilidad a posteriori de la hipótesis H, P(H|X), el Teorema de Bayes se denota cómo:

)()()|()|(

XXXP

HPHPHP

Así podemos saber, cuál es la probabilidad de pertenencia de una instancia X a una clase C

i si y sólo si la probabilidad P(C

i | X)

es la más alta entre todas las P(Ck | X) para todas las clases de k

Dificultad práctica: requiere conocimientos iniciales de muchas probabilidades, costo computacional significativo

Verosimilitud de los datos dada cada una de las hipótesis

Probabilidad a priori

6

Clasificación: Naïve Bayes

Sea D un conjunto de tuplas de entrenamiento y sus etiquetas de clase asociados, y cada tupla se representada mediante un vector de atributos n-D

X = (x1, x

2, ..., x

n)

Supongamos que hay m clases C1, C2, …, Cm.La clasificación la haremos a partir de la hipótesis más probable.

Máximo a posteriori o hipótesis MAP. Máximo( P(Ci|X) )

Esto se puede derivar de teorema de Bayes:

Puesto que P(X) es constante para todas las clases, sólo se busca maximizar:

)()()|(

)|(X

XX

PiCPiCP

iCP

)()|()|( iCPiCPiCP XX Principio de independencia condicional

7

Clasificación: Naïve Bayes

Calcular P(X|Ci) si el dataset tiene muchos atributos el costo

computacional es muy alto.

Independencia condicional con respecto a la clase C. Ese es el supuesto naive que se adopta. Los valores de los atributos son independientes dada la clase.

xk es el valor del atributo A

k en X

Esto reduce considerablemente el costo de cálculo: sólo cuenta la distribución de clases

)|(...)|()|(1

)|()|(21

CixPCixPCixPn

kCixPCiP

nk

X

8

Clasificación: Naïve Bayes

Si Ak es categórica, P(xk|Ci) es el nro # de tuplas en Ci que tienen valor xk para Ak dividido |Ci, D| (# de tuplas of Ci in D)

Si Ak es un valor continuo, P(xk|Ci) se calcula utilizando una distribución Gausiana con media μ desviación estándar σ

2

2

2

)(

2

1),,(

x

exg

y P(xk|Ci) es:

),,()|(ii CCkxgCiP X

9

Clasificador Naïve Bayesian: Ejemploedad ingreso estudiante calificación_crediticia compra_computadora

<=30 alto no buena no<=30 alto no excelente no31…40 alto no buena si>40 medio no buena si>40 bajo si buena si>40 bajo si excelente no31…40 bajo si excelente si<=30 medio no buena no<=30 bajo si buena si>40 medio si buena si<=30 medio si excelente si31…40 medio no excelente si31…40 alto si buena si>40 medio no excelente no

Clase:C1:compra_computadora =‘si’

C2:compra_computadora = ‘no’

MuestraX = (edad <=30, ingresos = medio, estudiante = si, calif_credit. = buena)

10

Ejemplo

P(X|Ci) : P(X|compra_computadora = “si”) = 0.222 x 0.444 x 0.667 x 0.667 = 0.044 P(X|compra_computadora = “no”) = 0.6 x 0.4 x 0.2 x 0.4 = 0.019P(X|Ci)*P(Ci) : P(X|compra_computadora = “si”) * P(compra_computadora = “si”) = 0.028

P(X|compra_computadora = “no”) * P(compra_computadora = “no”) = 0.007

De esta manera, X pertenece a la clase (“compra_computadora = si”)

P(Ci): P(compra_computadora = “si”) = 9/14 = 0.643       P(compra_computadora = “no”) = 5/14 = 0.357

Calcular P(X|Ci) para cada una de las clases:  P(age = “<=30” | compra_computadora = “si”) = 2/9 = 0.222  P(age = “<= 30” | compra_computadora = “no”) = 3/5 = 0.6  P(ingresos = “medio” | compra_computadora = “si”) = 4/9 = 0.444  P(ingresos = “medio” | compra_computadora = “no”) = 2/5 = 0.4  P(estudiante = “si” | compra_computadora = “si) = 6/9 = 0.667  P(estudiante = “si” | compra_computadora = “no”) = 1/5 = 0.2  P(calificación_crediticia = “buena” | compra_computadora = “si”) = 6/9 = 0.667  P(calificación_crediticia = “buena” | compra_computadora = “no”) = 2/5 = 0.4

Muestra: X = (age <= 30 , ingresos = medio, estudiante = si, calificación_crediticia = buena)

11

Evitar el problema de 0-PrLa predicción con Naïve Bayes requiere que cada una de las probabilidades condicionales no sea cero. De lo contrario la probabilidad predicha será cero:

n

kCixkPCiXP

1)|()|(

● Por ejemplo, tenemos un dataset de 1000 tuplas, ingresos=bajo (0), ingresos= medio (990), ingresos = alto (10),

● Se puede usar Laplacian correction (o estimador Laplaciano)– Agrega 1 a cada caso

Prob(ingresos = bajo) = 1/1003Prob(ingresos = medio) = 991/1003Prob(ingresos = alto) = 11/1003

– Las estimaciones de probabilidad "corregidas" están próximas a sus contrapartes "no corregidas"

12

Comentarios Ventajas

– Fácil de implementar– Buenos resultados obtenidos en la mayoría de los casos

Desventajas– Asumir class conditional independence, y por lo tanto la

perdida de precisión.– En la práctica, existen dependencias entre las variables

● Por ejemplo, los hospitales: pacientes: Perfil: edad, antecedentes familiares, etc.

● Síntomas: fiebre, tos, etc., enfermedades: cáncer de pulmón, diabetes, etc.

Dependencias entre estos no pueden ser modeladas por un clasificador Naïve Bayes ● ¿Cómo manejar las dependencias?

– Redes Bayesianas

20

Referencias

● Russell, S. J., & Norvig, P. (2004). Inteligencia Artificial: un enfoque moderno. Seguenda Edición. Cap. 20: Métodos estadísticos de aprendizaje.

● Jiawei Han,Micheline Kamber.Data Mining,Concepts and Techniques- 2 da edición- The Morgan Kaufmann Series in Data Management Systems