7-bayesiano

Aprendizaje Bayesiano

ndiceIntroduccin Teorema de Bayes Hiptesis MAP y ML Algoritmos MAP Principio MDL Clasificador ptimo

! ! ! ! ! !

Mtodos de Aprendizaje Automtico - InCo

2

Introduccin!

Por qu estudiar mtodos bayesianos?!

Tienen gran aplicacin prctica Son competitivos con otros mtodos conocidos [redes neuronales, rboles de decisin, etc.] Permiten caracterizar otros mtodos que no utilizan la probabilidad de forma explcita

!

!


3

Introduccin!

Caractersiticas de los mtodos bayesianos:!

Cada caso de entrenamiento cambia la probabilidad estimada de que una hiptesis sea correcta. El conocimiento previo puede ser utilizado para determinar la probabilidad de una hiptesis. Pueden dar predicciones probabilsticas. Pueden clasificar nuevas instancias combinando probabilsticamente distintas hiptesis. Se precisa conocer varias probabilidades Los algoritmos tienen un costo alto4

!

!

!

!

!


Teorema de Bayes!

Podemos caracterizar la mejor hiptesis como la hiptesis ms probable dados los datos. Esto es, buscamos obtener las hiptesis de H que maximizan P(h|D). Las hiptesis que cumplen esto son llamadas Maximum A Posteriori [hiptesis MAP]

!

!


5

Teorema de Bayes!

El teorema de Bayes nos permite obtener la probabilidad a posteriori de una hiptesis: P(h|D) * P(D)= P(D|h) * P(h)

!

Aplicndolo a nuestro problema: hMAP! argmaxh"HP(h|D) ! argmaxh"HP(D|h) * P(h) / P(D) ! argmaxh"HP(D|h) * P(h) Si las hiptesis son equiprobables: hML ! argmaxh"HP(D|h)6

!


Teorema de Bayes!

Por ejemplo:P(cancer) = 0.008 P(test # | cancer) = 0.98 P(test # | cancer) = 0.03 P(cancer)=0.992 P(test $ | cancer) =0.02 P(test $ | cancer) =0.97

!

Si el test da positivo: qu deberamos diagnosticar?P(test #| cancer) * P(cancer) = 0.98 * 0.008 = 0.0078 P(test #|cancer) * P(cancer) = 0.03 * 0.992 = 0.0298

! !

El diagnstico ms probable es que el paciente est sano. Esto lo puedo afirmar con una seguridad del 79% [0.0298/ (0.0298+0.0078)]7


Algoritmos MAP! !

Cul es la aplicacin del teorema de Bayes al Aprendizaje Conceptual? Podemos buscar hMAP en H.

!

Algoritmo Fuerza-Bruta ! Para cada hiptesis h de H, calculamos: P(h|D)= P(D|h) * P(h) / P(D) ! Damos como salida hMAP! argmaxh"HP(h|D)

!

No es una buena opcin cuando H es grande.8


Algoritmos MAP!

Para aplicar el algoritmo debemos calcular las probabilidades P(D|h) y P(h) Estas probabilidades se pueden elegir de acuerdo a los conocimientos previos que tengamos sobre el espacio de bsqueda Por ejemplo, supongamos que: ! El conjunto D no tiene ruido. ! El concepto objetivo est en nuestro espacio H. ! En principio, todas las hiptesis son equiprobables: P(h)= |H|-1

!

!


9

Algoritmos MAP!

Cmo estimamos P(D|h)? P(D|h) = 1 0 si di=h(xi) %di en D en caso contrario

!

En otras palabras: evaluamos en 1 si la hiptesis es consistente con D y 0 en caso contrario (no hay datos con ruido).


10

Algoritmos MAP!

Cul es la probabilidad a posteriori de las hiptesis? Si considero una hiptesis inconsistente con los datos, su probabilidad es nula P(h|D) = 0 * P(h) / P(D) = 0

!

!

En cambio, si es consistente: P(h|D) = 1 * |H|-1 / (|VSH,D|/|H|) = |VSH,D| -1


11

Algoritmos MAP!

Por lo tanto, toda hiptesis consistente con el conjunto de entrenamiento es MAP.


12

Algoritmos MAP!

Todo algoritmo [consistente] da como resultado una hiptesis MAP, si asumimos una distribucin a priori uniforme sobre H. Find-S y Candidate-Elimination no manejan ningn tipo de probabilidad y sin embargo son algoritmos MAP. Existen otras condiciones bajo las cuales Find-S sea un algoritmo MAP? S. Cuando la distribucin sobre H asigna ms probabilidad a las hiptesis ms especficas y no hay ruido en la entrada.13

!

!

!


Algoritmos MAP!

En definitiva, podemos caracterizar los algoritmos aun cuando estos no utilizan explcitamente probabilidades. Para esto, basta encontrar P(h) y P(D|h) bajo las cuales los algoritmos dan hiptesis MAP. Esta es una alternativa al sesgo para caracterizar los supuestos bajo los cuales un algoritmo aprende.

!

!


14

Principio MDL!

Veamos la Navaja de Occam desde un punto de vista bayesiano. Para esto, vamos a definir el Principio del Largo Mnimo de Descripcin [MDL] Volviendo a la def. de hMAP : hMAP! argmaxh"H P(D|h) * P(h) ! argminh"H-log P(D|h) - log P(h)

!

!

!

Esto se puede interpretar como que se debe preferir las hiptesis ms cortas.15


Principio MDL!

Para minimizar un cdigo se debe elegir para el mensaje isimo el largo -(log pi) siendo pi la probabilidad de aparicin de este mensaje Entonces: LCH(h)=-log P(h) : es el largo de la descripcin de h dentro del codificacin ptima de H (CH). LCD/h(D|h)=-log P(D|h): es el largo de la codificacin del conjunto de entrenamiento si vale h, bajo la mejor codificacin (CD|h). hMAP = argminh LCH(h) + LCD/h(D|h)

!

!


16

Principio MDL!

Pero en la prctica la codificacin ya est determinada [C1=codif.hip,C2=codif.Dat]. Principio MDL: hMAP = argminh LC1(h) + LC2(D|h)

!

!

Apliqumoslo a los rboles de decisin...


17

Principio MDL!

Para C1 elegimos una codificacin que asigne cdigos ms largos a rboles con ms nodos. Qu codificacin elegimos para C2 dada C1? Supongamos que los ejemplos son conocidos por un emisor y su receptor, y lo nico que se debe transmitir son Si la hiptesis clasifica perfectamente los ejemplos, no hay nada para transmitir, pero con seguridad el rbol sea ms grande.

!

!

!


18

Principio MDL!

En cambio, cuando algn ejemplo es clasificado errneamente hay que transmitir un mensaje donde se identifica el error y su valor correcto. El principio MDL nos permite balancear la complejidad del rbol vs. los errores que se cometen Las aplicaciones de este principio, dieron resultados similares a los algoritmos clsicos. Podemos afirmar entonces que Occam tena razn?

!

!

!


19

Principio MDL!

La respuesta es negativa, ya que la justificacin bayesiana slo es vlida cuando estamos ante las codificaciones ptimas.

Para determinar estas codificaciones precisamos saber P(h) y P(D|h).! !

Por lo general se busca una especificacin que nos parezca mejor... y aplicamos el algoritmo


20

Clasificador bayesiano ptimo!

Sabemos determinar la(s) hiptesis ms probable(s) dado un conjunto de entrenamiento. Pero, es la hiptesis ms probable las que nos da la clasificacin ms probable de una nueva instancia?

!


21


La respuesta es negativa. ejemplo: P(h2|D)=0.3

! or P

P(h1|D) = 0.4 P(h3|D) = 0.3 h1(x)=#

h2(x)=

$

h3(x)=

$

!

Uno tiende a pensar que el valor ms probables es 60% de seguridad]

$

[con


22


En general, el valor ms probable se obtiene combinando los resultados de todas las hiptesis P(v|D)=&h"HP(v|h) P(h|D)

!

Clasificacin bayesiana ptima: argmaxv"V&h"HP(v|h) P(h|D)


23


Por ejemplo:P(h1|D) = 0.4 P(h2|D) = 0.3 P(h3|D) = 0.3 P(#|D) = P($|D) = P(#|h1) = 1 P(#|h2) = 0 P(#|h3) = 0 P($|h1) = 0 P($|h1) = 1 P($|h1) = 1

&h"HP(#|h)

P(h|D) = 0.4 &h"HP($|h) P(h|D) = 0.6&h"HP(v|h)

argmaxv"{# ,$}

P(h|D) =

$


24


Un Clasificador bayesiano ptimo es cualquier sistema que clasifique las instancias de esta manera. Estos sistemas maximizan la probabilidad de clasificar correctamente nuevas instancias dado el conjunto de entrenamiento y las probabilidades a priori de las hiptesis.

!


25


Un clasificador ptimo es, por ejemplo, tomar el resultado de la votacin entre las hiptesis del espacio de versiones resultante del Candidate-Elimination Esto lleva a que la clasificacin obtenida no tenga porque tener una hiptesis que la represente dentro del espacio H. La desventaja es que calcular las prioridad a posteriori con cada hiptesis puede ser muy costoso.

!

!


26

Algoritmo de Gibbs!

Algoritmo de Gibbs: ! Elija una hiptesis h al azar segn la distribucin a posteriori que gobierna H ! Use h para predecir el valor de la instancia Se puede probar que, si se toma h segn la distribucin a priori, el error del clasificador de Gibbs es a lo sumo el doble que el ptimo. Si supongo hiptesis equiprobables, y tomo una hiptesis del VS al azar, el resultado tiene a lo sumo el doble de error que el clasificador ptimo!

!

!


27

Clasificador sencillo!

Consideremos instancias de la forma , y una funcin objetivo f que toma valores sobre un conjunto finito V. Buscamos: v = argmaxvj"V P(vj| a1...an) = argmaxvj"V P(a1...an | vj)*P(vj)/ P(a1...an) = argmaxvj"V P(a1...an | vj)*P(vj) Cmo estimamos estos valores a partir del conjunto de entrenamiento?

!

!


28


Podemos utilizar la frecuencia de aparicin en el conjunto de entrenamiento para P(vj) Calcular P(a1...an|vj) no siempre es posible Suponiendo que los atributos son independientes entre s. vNB= argmaxvj"V'iP(ai|vj)*P(vj)

! !

!

Notar que no hay bsqueda en H.


29


Por ejemplo:

!

Buscamos clasificar la instancia: 30



Utilizando el calsificador: = argmaxvj"V'iP(ai|vj)*P(vj) = = argmaxvj"{s,no} P(cielo=soleado|vj) * P(temp=fro|vj) * P(hum=alta|vj) * P(viento=fuerte |vj) *P(vj)

vNB

!

Ahora, aproximamos las 10 probabilidades que precisamos utilizando la frecuencia de aparicin en la tabla


31


Haciendo cuentas: P(jugar=s) = 9/14 = 0.64 P(jugar=no) = 5/14 = 0.36 P(Viento=fuerte|jugar=s) = 3/9 = 0.33 P(Viento=fuerte|jugar=no) = 3/5 = 0.60 ... P(soleado|s) * P(fro|s) * P(fuerte|s) * P(s) =0.0053 P(soleado|no) * P(fro|no) * P(fuerte|no) * P(no)=0.0206

!

Con un 79.5% de seguridad puedo afirmar que la respuesta es negativa.32



No siempre es buena la aproximacin utilizando la frecuencia e/n [e=nmero de veces que ocurre el evento, n=nmero de oportunidades] Cuando no hay ejemplos para algunos casos, la probabilidad asignada es cero [con lo cual anula todo el trmino del clasificador] m-estimador [e + m*p] / [n + m]

!

!

p es la estimacin a priori de la probabilidad buscada y m es el tamao equivalente de muestra.!

La frmula puede verse como aumentar la muestra con m ejemplos, distribuidos segn p (si equiprobables, p=1/k)33


Resumiendo...!

Los mtodos bayesianos me permiten obtener la hiptesis ptima [probabilsticamente] El clasificador ptimo me permite determinar el valor ms probable de una nueva instancia a partir de las probabilidades de TODAS las hiptesis El clasificador sencillo me ahorra el clculo de todas las probabilidades a cambio de supuestos de independencia

!

!


34

Resumiendo...!

Puedo caracterizar algoritmos que no usan explcitamente probabilidades aplicando un razonamiento bayesiano El principio MDL recomienda seleccionar la hiptesis que minimiza el largo de su descripcin ms los datos si ella se cumple.

!


35

7-bayesiano

Documents