métodos bayesianos - infor.uva.escalonso/mui-tic/mineriadatos/metodosbayesianos.pdf ·...

Métodos Bayesianos

Carlos J. Alonso GonzálezGrupo de Sistemas InteligentesDepartamento de Informática

Universidad de Valladolid

Métodos bayesianos 2

Contenido

1. Motivación2. Teorema de Bayes3. Hipótesis HMAP

4. Teorema de Bayes yaprendizaje de conceptos

5. Clasificador Bayesiano Óptimo6. Clasificador Naive Bayes7. Ejemplo de aplicación: clasificación de texto8. Redes Bayesianas9. Referencias


1. Motivación

Enfoque probabilístico al aprendizaje No basado en el error: las hipótesis

compiten entre si, venciendo la que tenga mayor probabilidad

Inductivo, supervisado: necesitamos conocer la clase de los ejemplos para estimar la probabilidad a posteriori de las observaciones


Razonamiento bayesiano

Supone que Las hipótesis están gobernadas por una

distribución de probabilidad Es posible tomar decisiones óptimas

razonando con estas probabilidades y las observaciones


Proceso de aprendizaje bayesiano

Cada ejemplo de entrenamiento puede modificar el probabilidad de una hipótesis: más flexible que rechazar hipótesis inconsistentes

El conocimiento a priori se combina con las observaciones: probabilidad a priori de cada hipótesis y distribución de probabilidad observada

Las nuevas instancias se clasifican combinando las predicciones de múltiples hipótesis


Interés métodos bayesianos

Algunos métodos bayesianos se encuentran entre los más eficientes

Permiten interpretar el funcionamiento de otros métodos en términos probabilísticos

Incluso cuando no son aplicables, proporcionan un estándar de toma de decisión óptima, frente al que comparar otros métodos


Dificultades

Requiere conocer un elevado número de probabilidades

Elevado coste computacional en el proceso de actualización de probabilidades


2. Teorema de Bayes

Dado un conjunto de entrenamiento D, más conocimiento a priori de la probabilidad de las distintas hipótesis de H, ¿Cuál es la hipótesis más probable?

Teorema de Bayes


Teorema de Bayes

)()()|()|(

DPhPhDPDhP =

P(h) es la probabilidad a priori de la hipótesis h Probabilidad de h sin ninguna observación

P(D) es la probabilidad a priori de D Probabilidad de observar D, sin saber que hipótesis se

verifica P(h|D) es la probabilidad a posteriori de h

Probabilidad de que h sea cierta después de observar D P(D|h) es la probabilidad a posteriori de D

Es la probabilidad de observar el conjunto de entrenamiento D en un universo donde se verifica la hipótesis h.


3. Hipótesis hMAP

Dado espacio de hipótesis H y las observaciones D ¿Cuál es la hipótesis h ∈ Hmás probable?

Hipótesis hMAP: maximun a posteriori

)()|(maxarg)(

)()|(maxarg

)|(maxarg

hPhDPDP

hPdDP

DhPh

Hh

Hh

HhMAP

∈

∈

∈

=

=

≡


Ejemplo

h+: paciente sufre enfermedad Xh-: paciente no padece la enfermedad X

Probabilidad padecer enfermedad X: 0,008

Se dispone de un test para determinar la presencia de la enfermedad X

Si el paciente padece enfermedad X, el test lo detecta en el 98% de los casos

El test da un 97% de casos negativos correctos si el paciente no tiene la enfermedad


hMAP ?

p(h+)=0,008 p(h-)=0,992 P(+/h+)=0,98 p(-/h+)=0,02 p(+/h-)=0.03 p(-/h-)=0.97

Dado que se observa +: p(+/h+) * p(h+)=0,98*0,008= 0,0078 p(+/h-) * p(h-)=0,03*0,992= 0,0298

hMAP: h-


4. Teorema de Bayes yaprendizaje de conceptos

¿Relación entre teorema de Bayes y aprendizaje de conceptos?

Posibilidad: usar Bayes para determinar probabilidad a posteriori de todas las posibles hipótesis, seleccionando la hipótesis hMAP

Aprendizaje de conceptos bayesiano exhaustivo


Clasificador bayesiano exhaustivo

Dado un conjunto de ejemplos D y un espacio de hipótesis H1. Para cada hipótesis h ∈ H calcular la probabilidad a posteriori:

2. Devolver la hipótesis hMAP con la máxima probabilidad a posteriori

)()()|()|(

DPhPhDPDhP =

)|(maxarg DhPhHh

MAP∈

=


Relación con aprendizaje de conceptos

Dados Descripción de Instancias, X, (atributos,

valores) Descripción de las Hipótesis, H Concepto objetivo, c Ejemplos positivos y negativos, D, pares

(<x, c(x)>) Determinar

Hipótesis h de H / h(x) = c(x) para todo xde X


Recordar

Consistente(h,D) Una hipótesis h es consistente con un conjunto de

ejemplos de entrenamiento D, sii h(x) = c(x) para cada ejemplo <x, c(x)> de D

VSH,D El espacio de versiones, VSH,D , respecto al espacio

de hipótesis H y ejemplos de entrenamiento D, es el subconjunto de hipótesis de H consistente con los ejemplos de entrenamiento de DVSH,D = {h∈H / Consistente(h,D)}


¿Qué proporcionaría el clasificador bayesiano exhaustivo?

Elección de p(D/h): 1 si h es consistente con D 0 en otro caso

Elección de p(h), distribución uniforme p(h) = 1/ |H|

P(h/D)= 1/|VSH,D| si h es consistente con D 0 en otro caso


Detalles 1

Hipótesis inconsistentes

Hipótesis consistentes

)()()|()|(

DPhPhDPDhP =

0)(||

10)|( =

⋅=

DPHDhP

||1

||||

||11

)|(,, DHDH VS

HVS

HDhP =⋅

=


Detalles 2

Por teorema de probabilidad total, asumiendo hipótesis mutuamente excluyentes con probabilidad total 1

p(D) = Σhi∈H p(D/hi)*p(hi)= Σhi∈VSHD

1 * 1/|H| + Σhi∉VSHD0 * 1/|H|

= Σhi∈VSHD1 * 1/|H|

= |VSH,D|/|H|


Relación Algoritmo Eliminación Candidatos

Algoritmo de eliminación de candidatos: Encuentra todas las hipótesis de VSH,D

Clasificador bayesiano exhaustivo Como P(h/D)=

1/|VSH,D| si h es consistente con D 0 en otro caso

Todas las hipótesis de VSH,D son hMAP y encuentra todas las hipótesis de VSH,D


Relación Algoritmo Eliminación Candidatos

AlgoritmoEliminaciónCandidatos

Hipótesis salida

ClasificadorBayesianoExhaustivo

Hipótesis salida

D

H

D

Hp(h) uniformeP(D/h)= 1 si consistente

0 si inconsistente


5. Clasificador bayesiano óptimo

hMAP proporciona la hipótesis más probable dado D Interesa más conocer cual es la clasificación más

probable de un nuevo ejemplo, x hMAP(x) no proporciona la clasificación más probable de x

Considerar tres posibles hipótesis:

Que clasifican la nueva instancia como:

¿Cuál es la hipótesis más probable?


Clasificador bayesiano óptimo

Si la clase toma valores vj ∈ V, la probabilidad de que la clasificación correcta sea vj es:

Y la clasificación óptima es:


Ejemplo

Dados:

Se tiene:

Y:


Propiedades Clasificador Bayesiano Óptimo

Maximiza la probabilidad de que una nueva instancia se clasifique correctamente Ningún otro método usando el mismo espacio de hipótesis

y el mismo conocimiento a priori puede obtener mejores tasas de error verdadero

El etiquetado de instancias del clasificador bayesiano óptimo puede no corresponder con ninguna de las hipótesis de H En realidad, el espacio de hipótesis H’ del clasificador es

una combinación lineal de las predicciones de las hipótesis H a las que se aplica el teorema de Bayes


Algoritmo de Gibbs

El clasificador óptimo puede tener un coste elevado probabilidad a posteriori de todas las

hipótesis, combinar las predicciones

Algoritmo de Gibbs Elegir h∈H aleatoriamente, según las

probabilidades a posteriori Asignar la clasificación h(x)


Propiedad algoritmo de Gibbs

Incluso seleccionando h según las probabilidades a priori: E[errorGibs] <= 2*E[errorBayesOptimo]


6. Clasificador Naive Bayes

Dados Descripción de Instancias, X, (atributos, valores) Descripción de las Hipótesis, H Concepto objetivo, c Ejemplos y su clase, D, pares (<x, c(x)>)

Determinar Valor más probable de c(x)

Notación Describimos las instancia como una conjunción de atributos

x=<a1, a2, ... an> siendo ai el valor del atributo i-ésimo c : X V, V finito


Valor más probable

Valor más probable de c(x): vMAP

)()|,...,(maxarg),...,(

)()|,...,(maxarg

),...,|(maxarg

21

21

21

21

jjn

n

jjn

nj

vPvaaaPaaaP

vPvaaaP

aaavPv

Vvj

Vvj

VvjMAP

∈

∈

∈

=

=

=


Estimación de probabilidades

A partir de los datos de entrenamiento p(vj): frecuencia de vj en datos de

entrenamiento p(a1, a2, ... an / vj)

Número de términos a estimar |X|*|V| !!! No es viable salvo conjuntos de

entrenamiento muy grandes, que repitan ejemplos


Aproximación Naive Bayes

Asumir que los valores de los atributo son condicionalmente independientes dado el valor de la clasificación

Clasificador Naive Bayes

∏=i

jijn vaPvaaaP )|()|,...,( 21

∏∈

=i

jij vaPvPVv

vj

nb )|()(maxarg


Estimación probabilidades NB

Nº de términos p(ai/vj) | valores de ai |* |V|


Algoritmo Naive Bayes

Aprendizaje_Bayesiano_Naive(ejemplos)Para cada posible valor del resultado vj

Obtener estimación p’(vj) de la probabilidad p(vj)Para cada valor ai de cada atributo aObtener estimación p’(ai/vj) de la probabilidad P(ai/vj)

Clasificar ejemplo(x)devolver

∏∈

=i

jijNB vaPvPVv

vj

)/()(maxarg


Ejemplo: datos “weather”

Cielo Temp Humedad Viento Jugar

Soleado Alta Alta Falso No

Soleado Alta Alta Cierto No

Cubierto Alta Alta Falso Si

Lluvioso Suave Alta Falso Si

Lluvioso Fría Normal Falso Si

Lluvioso Fría Normal Cierto No

Cubierto Fría Normal Cierto Si

Soleado Suave Alta Falso No

Soleado Fría Normal Falso Si

Lluvioso Suave Normal Falso Si

Soleado Suave Normal Cierto Si

Cubierto Suave Alta Cierto Si

Cubierto Alta Normal Falso Si

Lluvioso Suave Alta Cierto No


Clasificación nueva instancia

<soleado, fría, alta, cierto> Hay que calcular:

)/()/(

)/()/()(maxarg

)/()(maxarg

jj

jjj

ijij

vciertoVientopvaltaHumedadp

vfríaTemppvsoleadoCielopvpVv

vapvpVv

v

j

j

NB

==

==∈

=∈

= ∏



p'(jugar=si) = 9/14 = 0,64p'(jugar=no) = 5/14 = 0,36

p'(Cielo=soleado / jugar=si) = 2/9 = 0,22p'(Cielo=soleado / jugar=no) = 3/5 = 0,6p'(Temp=fría / jugar=si) = 3/9 = 0,33p'(Temp=fría / jugar=no) = 1/5 = 0,2p'(Humedad=alta / jugar=si) = 3/9 = 0,33p'(humedad=alta / jugar=no) = 4/5 = 0,8p'(Viento=cierto / jugar=si) = 3/9 = 0,33p'(Viento=cierto / jugar=no) = 3/5 = 0,6


Clasificación

(0,205) 0,0053)/()/()/()/()( =siciertopsialtapsifríapsisoleadopsip

Por tanto vNB=no

(0,795) 0,0206)/()/()/()/()( =nociertopnoaltapnofríapnosoleadopnop


Hipótesis de independencia

La hipótesis de independencia condicional de los atributos normalmente no se cumple

Pero funciona sorprendentemente bien. El principal argumento es que no es preciso que el cálculo de las probabilidades a posteriori sea correcto, sólo:

∏=i

jijn vaPvaaaP )|()|,...,( 21

)()|,...,(maxarg)|(')('maxarg 21 jjni

jij vpvaaapvapvpVvjVvj ∈∈

∏ =


Estimación probabilidades

Problemas si en el conjunto de entrenamiento no hay ningún ejemplo de clase vj y valor ai

Solución habitual, m-estima:

• n: número de ejemplos de entrenamiento con clase vj• nc: nº ejemplos clase vj con valor ai para el atributo a• p: estimación a priori de p(ai|vj)• m: peso de la estimación a priori (nº de ejemplos

virtuales)

0)/(')('0)/(' == ∏i

jijji vapvpyvap

mnmpnvap c

ji++

=)|('


Discusión Naive Bayes

Uno de los algoritmos de aprendizaje más prácticos, junto a árboles y K-NN

Condiciones de uso Conjunto de entrenamiento grande Atributos razonablemente independientes

Aplicaciones Diagnosis Clasificación de texto


7. Clasificación de texto

Gran cantidad de aplicaciones Clasificación de noticias, según su interés Páginas web, por contenido Correo electrónico, spam Servicios de Inteligencia

Naive Bayes: un algoritmo simple y eficiente


Planteamiento

Tarea de aprendizaje de conceptos, con Espacio de instancias, X: todos los posibles

documentos Descripción de un documento: secuencia ordenada de

atributos, tantos atributos como palabras; valor del atributo: palabra

Concepto objetivo C: X {v1, v2, … vn}

Ejemplos de entrenamiento D, pares (<x, c(x)>)

Clasificación de una nueva instancia, y Valor mas probable de C(y)



Según Naive Bayes

Con wk k-ésima palabra del vocabulario utilizado

p(vj):frecuencia en ejemplos de entrenamiento p(ai=wk/+), p(ai=wk/-) para todas las palabras del

diccionario en cada una de las posibles posiciones Dificultad:

50000 * long(doc) *2 ¡términos a estimar! Suponiendo 50.000 palabras distintas en Ingles

∏=

=−+∈

=)(

1

)|()(},{

maxargdoclong

ijkij vwapvp

vv

j

NB


Suposición adicional

Suponer que la probabilidad de encontrar una palabra es independiente de su posición en el texto p(ai=wk/+) = p(aj=wk/+) = p(wk/+)

Finalmente, para evitar problema probabilidades muy bajas, m-estima

||1)|(

ovocabularinnvwP i

jk+

+=


8. Redes bayesianas: Motivación

Suposición Naive Bayes: Atributos condicionalmente independientes dada la

clase En la práctica, habitualmente:

No se satisface Bajas tasas de error en clasificación

Sin embargo A veces comportamiento mucho peor que, por

ejemplo, árboles de decisión Motivo

NB sólo puede representar distribuciones de probabilidad sencillas

Árboles puede representar distribuciones arbitrarias


Redes bayesianas

Modelo gráfico: Grafo dirigido acíclico Un nodo por atributo

Distribución de probabilidad conjunta factorizada en distribución de sus componentes

Nodos contienen la distribución de los componentes (distribuciones condicionales)

Pueden representar cualquier distribución de probabilidad


Ejemplo: Red Bayesiana Naive

Representación gráfica de Naive Bayes Árbol de profundidad 1

Nodo raíz: clase Nodos hijos (terminales): atributos

Nodo raiz: probabilidad a priori (clase) Nodos hijos: probabilidad a posteriori

(clase dado atributo)


Red bayesiana sencilla

Red Bayesiana Naive (datos weather, cuenta inicial 0.5) [WF05]


Red bayesiana

Grafo dirigido acíclio Un nodo puede tener varios padres

Nodo raíz: clase (probabilidad a priori) Nodos hijos: atributo (probabilidad

condicionada del atributo dados los padres)

Red Bayesiana (datos weather, cuenta inicial 0.5) [WF05]

50Métodos bayesianos


Nodo atributo

Nodo temperature Padres: outlook, play Tabla: probabilidad

condicionada del atributo dados los padres

EjemploPr[(temperature=hot) /(play=yes), (outlook=sunny)]= 0.143


Clasificación nueva instancia

Dos etapas Primero

Seleccionar probabilidad condicionada cada atributo

Multiplicar valores: probabilidad conjunta

Segundo Normalizar: probabilidad condicionada


Ejemplo clasificación

Instancia a clasificar (evidencia, E):outlook=rainy, temperature=cold, humidity=high, windy=true

Probabilidad conjunta Pr[play=no, E]=0.0025 Pr[play=yes, E]=0.0077

Probabilidad condicionada Pr[play=no / E]=0.245 Pr[play=yes / E]=0.755

play=no .367

play=nooutlook=rainy

.385

play=notemperature=cold

.429

play=nohumidity=high

.250

play=nowindy=true

.167

Producto: .0025


Suposición de independencia

La distribución de probabilidad de un nodo solo depende de sus padres:

Pr[nodo/antecesores]=Pr[nodo/padres]

Equivale a suponer independencia de un nodo/atributo respecto a sus antecesores dados sus padres


Obtención probabilidad conjunta (I)

Regla de la cadena:

Pr[a1, a2,… , an]=Πi=1,nPr[ai / ai-1,… , a1]

Descomposición válida para cualquier ordenación de atributos


Obtención probabilidad conjunta (II)

Grafo dirigido acíclico: ordenar nodos para asignar a antecesores

de nodo ai índices menores que i

Suponiendo independencia respecto antecesores dados padres:

Pr[a1, a2,… , an]=Πi=1,nPr[ai / ai-1,… , a1]=Πi=1,nPr[ai / padres de ai]

Redes bayesianas y causalidad (I)

Cuidado con la tentación de interpretar los arcos como una relación causal Un valor de play puede mejorar la probabilidad a

posteriori de algún valor de outlook, pero no lo causa De existir una relación causal, probablemente será

de outlook a play

Se pueden generar redes bayesianas diferentes que representen la misma distribución de probabilidad La red cuyos arcos modelan relaciones causales es

habitualmente las más simple


Redes bayesianas y causalidad (II)

Estructura de la red generada a partir de conocimiento del dominio (experto) Modelar causalidad suele ser beneficioso

Estructura de la red generada con técnicas de aprendizaje Los arcos modelan correlaciones, no

causalidad



Aprendizaje de redes bayesianas

Dos etapas Aprender la estructura de la red

Búsqueda en el espacio de posibles redes (arcos, pues nodos fijos)

Aprender la distribución de probabilidad A partir de los datos, dada la red

Problema: sobreajuste Añadir arcos a la red siempre maximiza la

probabilidad de los datos Es necesario penalizar la complejidad de la

estructura de la red


Aprendizaje de la estructura

Se puede optimizar cada nodo por separado Porque la probabilidad de una instancia es

el producto de las probabilidades individuales de los nodos

Se optimizan los nodos añadiendo/eliminando arcos desde otros nodos

No introducir ciclos


Algoritmos básicos

K2, TAN Sencillos, eficientes K2: cualquier estructura (GDA) TAN: extensión de Naive Bayes


K2

Comienza con una ordenación de los atributos (nodos)

Procesa cada nodo según orden Añade arcos de nodos ya procesados al

actual de forma voraz Cuando el nodo actual no se puede

optimizar más, pasa al siguiente El resultado depende del orden actual


C

A1 A1 A1 A1

C

A1 A1 A1 A1

TAN:tree augmented Naive Bayes

Naive Bayes

Aumentada con un árbol: TAN


Obtencion red TAN

Empezar con estructura Naive Bayes Considerar la posibilidad de añadir 1

padre adicional (salvo a nodo clase) Evitar ciclos

Existen algoritmos eficientes


Ejemplo Weather

P

O T H W


9. Referencias

E. Castillo and J. M. Gutierrez and A. S. Hadi. "Expert systems and probabilistic network models". Springer-Verlag, 1997. A Spanish version is available online for free

F. V. Jensen. "Bayesian Networks and Decision Graphs". Springer. 2001

Tom M. Mitchell. Machine Learning. McGraw-Hill, 1997.

J. T. Palma y R. Marín (edts.). Inteligencia Artificial: métodos, técnicas y aplicaciones. McGraw-Hill, 2008.

J. Pearl. Probabilistic Reasoning in Intelligent Systems: networks of Plausible Inference. Morgan Kaufmann, San Mateo, California, 1988.

I. H. Witten and E. Frank. Data Mining: Practical Machine Learning Tools and Techniques. Morgan Kaufmann, 2nd edition, 2005.

http://personales.unican.es/gutierjm/BookCGH.html�

métodos bayesianos - infor.uva.escalonso/mui-tic/mineriadatos/metodosbayesianos.pdf ·...

Documents