Poggi analytics - bayes - 1a

Buenos Aires, marzo de 2016Eduardo Poggi

Aprendizaje Bayesiano

Aproximación probabilística a ML Repaso del cálculo de probabilidades Teorema de Bayes NB ¿IDT + NB? The Joint Distribution

Aprendizaje Bayesiano

Aproximación probabilística a ML Repaso del cálculo de probabilidades Teorema de Bayes NB ¿IDT + NB? The Joint Distribution

Aproximación probabilística a ML

Hasta ahora vimos diferentes técnicas de aprendizaje:

La idea que subyacen en esos métodos es la generalización por particiones del espacio de ejemplos: bordes general-específicos, particiones ortogonales, poliedros convexos, etc.

Aproximación probabilística a ML

El interés del aprendizaje bayesiano es doble: Ofrece un conjunto de técnicas y conceptos prácticos

basados en probabilidades distintos a los aportados por otros métodos y enfoques.

Desde un punto de vista más teórico, ofrece un punto de vista conceptual desde el cual analizar los distintos métodos inductivos. En este sentido es un enfoque complementario al enfoque basado en la resolución de problemas (búsqueda) o al enfoque más “lógico” o “deductivo” de otros métodos.

Aproximación probabilística a ML

Para comprender las técnicas bayesianas es importante comprender el enfoque bayesiano hacia las probabilidades y la estadística.

Probabilidad bayesiana de un suceso es el grado de creencia de una persona en ese suceso.

La probabilidad en la interpretación clásica es una propiedad física del mundo (probabilidad objetiva).

La probabilidad en la interpretación bayesiana es una propiedad de la persona que asigna la probabilidad (probabilidad subjetiva).

Diferencia importante entre la probabilidad objetiva y la subjetiva: para medir la segunda no se necesitan ensayos repetidos.

Aproximación probabilística a ML La probabilidad bayesiana de un suceso

cualquiera es el grado de creencia de una persona en ese evento.

La probabilidad clásica es una propiedad física del mundo (p. ej., la probabilidad de que una moneda arrojada aterrice de cara), mientras que la probabilidad bayesiana es una propiedad de la persona que asigna la probabilidad (p. ej., su grado de creencia de que una moneda arrojada aterrice de cara).

La probabilidad clásica se denomina probabilidad física, objetiva o verdadera, mientras que la probabilidad bayesiana se la suele denominar probabilidad subjetiva.

Para medir la probabilidad objetiva se necesitan múltiples ensayos, para la probabilidad subjetiva no. Esto es muy bueno en los casos de sucesos infrecuentes, difíciles de repetir, medir, etc.

Aproximación probabilística a ML

Importancia del aprendizaje bayesiano Supuesto:

las propiedades están regidas por distribuciones probabilísticas y pueden tomarse buenas decisiones procesando estas probabilidades junto con los datos observados.

Propone un enfoque cuantitativo para ponderar la evidencia que sustenta hipótesis alternativas.

Permite implementar algoritmos muy utilizados y prácticos.

Provee una perspectiva desde la cual interpretar los algoritmos de aprendizaje que no utilizan explícitamente probabilidades.

Aproximación probabilística a ML

Características principales de los métodos bayesianos

Buscar la mejor hipótesis significa buscar la hipótesis más probable dados los datos D y el conocimiento previo.

No hay una búsqueda explícita en el espacio de hipótesis posibles. Cada hipótesis se genera simplemente por conteo de la frecuencia de las diversas combinaciones de valores de los atributos en los ejemplos de entrenamiento.

Cada ejemplo de entrenamiento aumenta o disminuye la probabilidad estimada de que una hipótesis sea correcta.

Aproximación probabilística a ML

Características principales de los métodos bayesianos

El conocimiento previo puede combinarse con los datos observados para determinar la probabilidad final de una hipótesis.

El conocimiento previo está representado por: La probabilidad previa de cada hipótesis candidata (P(h)) Una distribución probabilística sobre los datos observados

(P(D)) Las nuevas instancias pueden clasificarse combinando las

predicción de diversas hipótesis ponderadas por sus respectiva probabilidad.

Aun en los casos en los que los métodos bayesianos puedan resultar computacionalmente intratables, pueden proporcionar un estándar de decisión óptima contra el cual comparar otros métodos.

Aproximación probabilística a ML

Dificultades de los métodos bayesianos Requieren conocimiento inicial previo de muchas

probabilidades. Problema de estimación de probabilidades pequeñas o de

datos no observados. Costo computacional significativo para determinar la

hipótesis bayesiana óptima en el caso general.

Aproximación probabilística a ML

Un estimador de densidad aprende a mapear un conjunto de atributos en una probabilidad.

Aprendizaje Bayesiano

Aproximación probabilística a ML Repaso del cálculo de probabilidades Teorema de Bayes NB ¿IDT + NB? The Joint Distribution

Aproximación probabilística a ML

El mundo es un lugar muy incierto. 40 años de investigación 30 en IA y BD giran sobre

este hecho. Algunos investigadores en IA decidieron retomar

ciertas ideas del siglo XVIII.

Repaso del cálculo de probabilidades

Discrete Random Variables A is a Boolean-valued random variable if A denotes an event,

and there is some degree of uncertainty as to whether A occurs. Examples

A = The US president in 2023 will be male A = You wake up tomorrow with a headache A = You have Ebola

Repaso del cálculo de probabilidades

Probabilidad: Denotamos con P(A) a la “fracción del mundos posibles

en los cuales A es verdadero”

Repaso del cálculo de probabilidades

Base axiomática de la Probabilidad: 0 <= P(A) <= 1 P(True) = 1 P(False) = 0 P(A or B) = P(A) + P(B) - P(A and B)

Repaso del cálculo de probabilidades

Variables Aleatorias Multivaluadas Si A puede tomar más de 2 valores A es una variable con aridad k si solo puede tomar un

valor de {v1 ,v2 , .. vk } Entonces …

Repaso del cálculo de probabilidades

Probabilidad Condicional Probabilidad de que ocurra un evento A, sabiendo que

también sucede otro evento B. Se escribe P(A|B): “la probabilidad de A dado B”. No tiene por qué haber una relación causal o temporal

entre A y B. A puede preceder en el tiempo a B, sucederlo o pueden

ocurrir simultáneamente. A puede causar B, viceversa o pueden no tener relación

causal. Las relaciones causales o temporales son nociones que

no pertenecen al ámbito de la probabilidad.

Repaso del cálculo de probabilidades

H = “Have a headache”F = “Coming down with Flu”

P(H) = 1/10P(F) = 1/40P(H|F) = 1/2

“Headaches are rare and flu is rarer, but if you’re coming down with flu there’s a 50-50 chance you’ll have a headache.”

Repaso del cálculo de probabilidades

P(H|F) = Fraction of flu-inflicted worlds in which you have a Headache= #worlds with flu and headache

#worlds with flu= Area of “H and F” region Area of “F” region= P(H ^ F) P(F)

H = “Have a headache”F = “Coming down with Flu”

P(H) = 1/10P(F) = 1/40P(H|F) = 1/2

Repaso del cálculo de probabilidades

Probabilistic Inference One day you wake up with a headache. You think: “Drat! 50% of flus are associated with headaches so I must have

a 50-50 chance of coming down with flu” Is this reasoning good?

H = “Have a headache”F = “Coming down with Flu”

P(H) = 1/10P(F) = 1/40P(H|F) = 1/2

Aprendizaje Bayesiano

Aproximación probabilística a ML Repaso del cálculo de probabilidades Teorema de Bayes NB ¿IDT + NB? The Joint Distribution

Teorema de Bayes

Bayes Rule

P (B|A) = P(A^B) = P(A|B) P(B)

P(A) P(A)

Bayes, Thomas (1763)

Otras formas:

Teorema de Bayes Provee un método directo para calcular la probabilidad de

las hipótesis: P(h|D) = ( P(D|h) P(h) ) / P(D) P(h): probabilidad inicial (previa, a priori) de h (antes de haber

observado los datos de entrenamiento). Refleja todo el conocimiento general acerca de la probabilidad de que h sea una hipótesis correcta. En caso de que no se tenga conocimiento previo puede suponerse equiprobabilidad de todas las hipótesis

P(D): probabilidad previa de observar los datos de entrenamiento D (sin conocimiento de cuál es la hipótesis vigente)

P(D|h): probabilidad posterior (a posteriori) de observar los datos D cuando h es la hipótesis vigente

P(h|D): probabilidad posterior de la hipótesis h habiendo observado los datos de entrenamiento

D. Refleja nuestra confianza en h habiendo visto D Las probabilidades posteriores (p(h|D); p(D|h)) son

probabilidades condicionales Se puede esperar que P(h|D) aumente con p(h) y con P(D|h)

según el teorema de Bayes. También es razonable ver que P(h|D) disminuye cuando P(D) aumenta, porque cuanto más probable es que D sea observado independientemente de h, menos evidencia D provee en apoyo de h.

Teorema de Bayes Hipótesis más probable

En muchas situaciones de aprendizaje, consideramos algún conjunto H de hipótesis candidatas y estamos interesados en encontrar la hipótesis más probable h (o alguna de las máximamente probables) en H a la luz de un conjunto de datos observados D. Esta hipótesis se denomina de máxima probabilidad a posteriori o hipótesis MAP. Podemos determinarla usando el teorema de Bayes para calcular la probabilidad de cada hipótesis candidata. Como P(D) es constante para toda h, podemos omitirla del cálculo cuando queremos identificar la hipótesis MAP (aunque no cuando queremos determinar exactamente su probabilidad).

Hipótesis ML: Cuando todas las hipótesis h de H son igualmente probables a priori.

P(D|h) se denomina la verosimilitud de los datos D dado h, y cualquier hipótesis que maximiza p(D|h) se denomina hipótesis de máxima verosimilitud. En estadística, el método de máxima verosimilitud produce valores para los parámetros desconocidos que maximizan la probabilidad de obtener el conjunto observado de datos. Para aplicar este método debemos primero construir una función , llamada la función de verosimilitud. Esta función expresa la probabilidad de los datos observados como función de los parámetros desconocidos. Los estimadores de máxima verosimilitud de estos parámetros se eligen como aquellos valores que maximizan esta función. Así, los estimadores resultantes son aquellos que concuerdan más estrechamente con los datos observados.

Teorema de la probabilidad total: Si los sucesos A1,...,An son mutuamente excluyentes con ∑i P(Ai) = 1, entonces P(B) = ∑i P(B|Ai) P(Ai)

Teorema de Bayes – ejemplo

Does patient have cancer or not? A patient takes a lab test and the result comes back positive. It

is known that the test returns a correct positive result in only 98% of the cases and a correct negative result in only 97% of the cases. Furthermore, only 0.008 of the entire population has this disease.

1. What is the probability that this patient has cancer?2. What is the probability that he does not have cancer?3. What is the diagnosis?

Teorema de Bayes – ejemplo

P(cancer) = 0.008, P(-cancer)=0.992 P(+|cancer) = 0.98, P(-|cancer)=0.02 P(+|-cancer)=0.03, P(-|-cancer)=0.97 Si el test da positivo, que deberíamos diagnosticar?

P(+|cancer)*P(cancer) = 0.98*0.008 = 0.0078 P(+|-cancer)*P(-cancer) = 0.03*0.992 = 0.0298

El diagnóstico más probable es que el paciente esté sano. Que se puede afirmar con una probabilidad del:

79% = (0.0298/ (0.0298+0.0078))

Teorema de Bayes – ejemplo

Choosing Hypotheses Maximum Likelihood hypothesis:

Generally we want the most probable hypothesis given training data. This is the maximum a posteriori hypothesis:

Useful observation: it does not depend on the denominator P(d)

)|(maxarg dhPhHh

MAP

)|(maxarg hdPhHh

ML

Teorema de Bayes – ejemplo

Now we compute the diagnosis To find the Maximum Likelihood

hypothesis, we evaluate P(d|h) for the data d, which is the positive lab test and chose the hypothesis (diagnosis) that maximises it:

To find the Maximum A Posteriori hypothesis, we evaluate P(d|h)P(h) for the data d, which is the positive lab test and chose the hypothesis (diagnosis) that maximises it. This is the same as choosing the hypotheses gives the higher posterior probability.

.................:.............)|(............)|(

MLhDiagnosiscancerPcancerP

......................:.............)()|(

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

MAPhDiagnosiscancerPcancerP

cancerPcancerP

Aprendizaje Bayesiano

Aproximación probabilística a ML Repaso del cálculo de probabilidades Teorema de Bayes NB ¿IDT + NB? The Joint Distribution

Naive Bayes

What can we do if our data d has several attributes? Naive Bayes assumption: Attributes that describe data instances

are conditionally independent given the classification hypothesis

it is a simplifying assumption, obviously it may be violated in reality in spite of that, it works well in practice

The naive model generalizes strongly: Assume that each attribute is distributed independently of any of the other attributes.

t

tT haPhaaPhP )|()|,...,()|( 1d

Naive Bayes

Independently Distributed Data Let x[i]denote the i ’th field of record x. The independently distributed assumption says that for

any i,v, u1 u2… ui-1 ui+1…uM

Or in other words, x[i]is independent of {x[1],x[2],..x[i-1], x[i+1],…x[M]}

This is often written as:

Naive Bayes

Some eqs, assume P(A|B) = P(A) then P(A^B) = P(A) P(B) and P(~A|B) = P(~A) and P(B|A) = P(B) and P(A|~B) = P(A)

Multivalued Independence:

Naive Bayes Se aplica a tareas de aprendizaje que usan un lenguaje conjuntivo

de representación de instancias y la función objetivo puede tomar cualquier valor v de un conjunto finito V.

Los términos P(vj) son fáciles de estimar, pero no los términos P(a1,a2,...,an|vj) a menos que se tenga un conjunto de datos de entrenamiento muy grande. El problema es que el número de estos términos es igual al número de instancias posibles por el número de valores objetivo posibles. Necesitamos ver cada instancia en el espacio de instancias muchas veces para obtener estimaciones confiables.

El clasificador naive Bayes se basa en el supuesto simplificador de que los valores de los atributos son condicionalmente independientes dado el valor objetivo. Esto es, dado el valor objetivo de la instancia, la probabilidad de observar la conjunción a1, a2,...,an es solo el producto de las probabilidades de los atributos individuales: P(a1,a2,...,an|vj) = ∏i P(ai|vj).

El número de términos P(ai|vj) que deben estimarse a partir de los datos de entrenamiento es solo el número de valores de atributos distintos por el número de valores objetivo distintos.

El método de naive Bayes involucra un paso de aprendizaje en el cual se estiman los diversos P(vj) y P(ai|vj), en base a su frecuencia sobre los datos de entrenamiento. El conjunto de estas estimaciones corresponden a la hipótesis aprendida. Esta hipótesis es usada luego para clasificar las nuevas instancias. Cuando el supuesto bayesiano ingenuo de independencia condicional se satisface, la clasificación bayesiana ingenua es idéntica a la clasificación MAP.

Naive Bayes

Etapa de entrenamiento: Compilar una tabla (unidimensional) de estimaciones de

la probabilidad de la clase P(vj) Compilar una tabla (bidimensional) indizada por la clase y

pares atributo-valor de las estimaciones condicionales P(ai|vj)

Etapa de clasificación: Para cada instancia no clasificada calcular argmaxvj P(vj)

Πi P(ai|vj)

Naive Bayes

Características: Es un clasificador “global” y no puede hacer predicciones

locales como K-NN o los árboles de decisión. Usualmente tiene baja varianza ya que perturbaciones de

los conjuntos de entrenamiento raramente causarán grandes cambios en sus predicciones, que se basan en probabilidades.

Naive Bayes Suavizamiento:

La estimación “directa” de P(ai|vj) es Frecuencia(ai,vj) / frecuencia(vj) en la muestra de entrenamiento D

Problema: cuando en D no ocurre alguna combinación (ai,vj), ya sea debido a las idiosincrasias de D y/o porque esa combinación es muy poco frecuente (aunque no imposible) y |D| es pequeño, la estimación sería P(ai|vj) = 0, lo que anula toda la productoria ∏K

Solución: suavizar las estimaciones para que sean menos extremas:

Enfoque “no match”: reemplazar las frecuencias 0 por un factor sobre el número de instancias (m) del conjunto de entrenamiento.

Enfoque de Laplace: estimar todas las probabilidades P(ai/vj) mediante (frec(ai,vj) + f) / (m + k.f), donde f es un factor y k el número de clases.

Estimación-m: estimar todas las probabilidades P(ai|vj) mediante (frec(ai,vj) + m.p) / (frec(vj) + m), donde p: estimación previa de la probabilidad que deseamos determinar y m: constante llamada tamaño de muestra equivalente que determina cuánto ponderar p en relación con los datos observados

Naive Bayes - Ejemplo

Example “PlayTennis”

Naive Bayes - Ejemplo

Classifing Classify any new datum instance x=(a1,…aT) as:

In the case of the naive Bayes Classifier this can be simplified:

Technical Hint:If you have 10,000 input attributes that product will underflow in floating

point math. You should use logs:

Naive Bayes - Ejemplo

x = <Outlook=Sunny, Temp=Cool, Hum=High, Wind=Strong>hNB = argmax P(h) P(x|h) = argmax P(h) P(ai | h) = argmax P(h) P(Outlook=Sunny | h) P(Temp=Cool | h)

P (Hum=High | h) P(Wind=Strong | h)Aproximando las probabilidades por la frecuencia:P (PlayTennis = yes) = 9/14 = 0.64P (PlayTennis = no) = 5/14 = 0.36P (Wind = Strong | PlayTennis = yes) = 3/9 = 0.33P (Wind = Strong | PlayTennis = no) = 3/5 = 0.60Aplicandolo a las fórmulas:P(yes) P(Sunny|yes) P(Cool|yes) P(High|yes) P(String|yes) = 0.0053P(no) P(Sunny|no) P(Cool|no) P(High|no) P(String|no) = 0.0206 Answer: PlayTennis = no Con 79.5% de certeza

Aprendizaje Bayesiano

Aproximación probabilística a ML Repaso del cálculo de probabilidades Teorema de Bayes NB ¿IDT + NB? The Joint Distribution

¿IDT + NB?

Árbol bayesiano ingenuo (NBTree) Es un enfoque híbrido que combina un clasificador

bayesiano ingenuo con un árbol de decisión. NBTree usa una estructura de árbol para dividir el espacio de instancias en subespacios y genera un clasificador bayesiano ingenuo en cada subespacio.

Los nodos de decisión contienen tests univariados típicos. Cada hoja contiene un clasificador bayesiano ingenuo

local que no incluye las variables involucradas en los tests sobre el camino que lleva a la hoja.

¿IDT + NB?

Árbol bayesiano ingenuo (NBTree) La debilidad principal de NB es el supuesto de

independencia condicional de los atributos. Cuando existen atributos interdependientes la performance de este método puede deteriorarse mucho. La mayoría de las modificaciones de NB surgen para aliviar este problema tratando de tomar en cuenta la interdependencia en un modelo global o generando modelos NB más locales que estén más o menos libres de esa interdependencia. Este último es el caso de los NBTree.

Una selección apropiada de tests puede permitir a los árboles eliminar interdependencias dañinas (para NB) entre atributos. Los atributos en las ramas no son utilizados por los NB en las hojas, disminuyendo así la probabilidad de construir modelos con atributos interdependientes.

Aprendizaje Bayesiano

Aproximación probabilística a ML Repaso del cálculo de probabilidades Teorema de Bayes NB ¿IDT + NB? The Joint Distribution

The Joint Distribution

Recipe for making a joint distribution of M variables:

1. Make a truth table listing all combinations of values of your variables (if there are M Boolean variables then the table will have 2M rows).

2. For each combination of values, say how probable it is.

3. If you subscribe to the axioms of probability, those numbers must sum to 1.

The Joint Distribution

Using the Joint

One you have the JD you can ask for the probability of any logical expression involving your attribute

P(Poor Male) = 0.4654 P(Poor) = 0.7604 P(Male | Poor) = 0.4654

0.7604 = 0.612

The Joint Distribution

Log Probabilities Since probabilities of datasets get so small we usually use log

probabilities

Bad news ….Density estimators can overfit. And the full joint density

estimator is the overfittiest of them all! We need Density Estimators that are less prone to overfitting

The Joint Distribution

Contrast

Aprendizaje Bayesiano - Resumen

Density estimation can be performed with real-valued inputs Bayes Classifiers can be built with real-valued inputs Rather Technical Complaint: Bayes Classifiers don’t try to be

maximally discriminative---they merely try to honestly model what’s going on

Zero probabilities are painful for Joint and Naïve. Naïve Bayes is wonderfully cheap. And survives 10,000

attributes cheerfully!

eduardopoggi@yahoo.com.ar

eduardo-poggi

http://ar.linkedin.com/in/eduardoapoggi

https://www.facebook.com/eduardo.poggi

@eduardoapoggi

Bibliografía

Álvarez, José: Notas de cátedra. Universidad Austral. Mitchell Cap 6