Curso de Inteligencia ArtificialCurso de Inteligencia ArtificialModelos Ocultos de Markov

Gibran Fuentes PinedaIIMAS, UNAM

Redes Bayesianas

● Representación gráfica de relaciones probabilísticas

● Relaciones causales entre variables aleatorias

● Grafo dirigido– Nodos: una o más variables aleatorias

– Vertices: relaciones probabilísticas entre variables

Ejemplo

Tifoidea Gripe

Fiebre DolorDiarrea

Cadena de Markov

● Proceso estocástico discreto– Representa una secuencia de variables

aleatorias

● Propiedad de Markov– El siguiente estado depende únicamente del

estado actual

● Máquina de estados donde las transiciones no son determinístas

Cadenas de Markov

● Primer orden

● Segundo orden

x1 x2 x3 x4

P ( xn∣x1, x2,… , xn−1)=P ( xn∣xn−1)

P ( xn∣x1, x2,… , xn−1)=P (xn∣xn−1 , xn−2)

x1 x2 x3 x4

Modelos Ocultos de Markov

● Modela procesos estocásticos secuenciales

● No todas las variables son observables● Nodos blancos representan variables

ocultas. Nodos obscuros representan variables observadas

z1 z2 zn zn+1

x1 x2 xn xn+1

…

El Problema Versión Alpha

● Una jarra mágica:

– Con 90 canicas rojas y 10 amarillas

● ¿Cuál es la probabilidad de que la siguiente canica sea roja?

El Problema Versión Beta

● Tres jarras mágicas con etiquetas

– Con 90 canicas de un color y 10 de otro color

● ¿Qué secuencia de jarras podrían generar la siguiente secuencia?

A B

C

El Problema Versión 1

● Tres jarra mágicas con etiquetas

– Con 90 canicas de un color y 10 de otro color

● ¿Cuál es la probabilidad de generar la siguiente secuencia? C

A B

C

El Problema Versión 2

● Tres jarra mágicas con etiquetas

– Con 90 canicas de un color y 10 de otro color

● ¿Qué secuencia de jarras tiene mayor probabilidad de generar la siguiente secuencia?

A B

C

El Problema Versión 3

● Tres jarra mágicas con etiquetas

● ¿Qué cantidades debe haber en cada jarra para obtener las secuencias?

A B

C

?? ??

??

Espacio de Muestreo

● Las canicas representan a una variable aleatoria, la cual diremos que la observamos

● Las canicas representan otra variable aleatoria, la cual diremos que está oculta

X ={R=1, A=2,V =3}

Y ={A=1, B=2,C=3}

1 21 3

1 2 3

Elementos del Problema

● Espacio de muestreo

● Probabilidades

● Independencias asumidas ?– La canica únicamente depende de la jarra que se saca

– La jarra de la que se saca depende de la que se saque antesra de la que se saca depende de la que se saque antes

Ω={Ar , Aa , Av , Br , Ba , Bv ,Cr ,Ca ,Cv}

P (r∣A) , P (a∣A) ,…

P (A∣A) , P (A∣B) ,…

P (A) , P (B) , P (C )

Las Probabilidades

P (X∣Z )=Probabilidades de emisión B

P (Z∣Z )=Probabilidades de transición A

P (Z )=Probabilidades de ser estado inicial π

Ω={A , B ,π}

● El conjunto de distribuciones es conocido como el modelo o los parámetros del HMM

● Usualmente los representamos como

Modelando la Secuencia

Ω={Todas las secuencias posibles }x1, x2,… , xn

z1, z2,… , zn

Ψ={z1, z2,… , zn}

Os={x1…xn1 ,… , x1, xnO}

z1 z2 zn

x1 x2 xn

…

Notación

● T = Tamaño de la secuencia de observación● n = Número de estados● m = Número de posibles salidas● Z = Distintos estados del proceso● X = Posibles observaciones● A = Probabilidades de transición● B = Probabilidades de observación● π = Distribución de estado inicial● O = Secuencia de observación

Los Tres Problemas

1.Calcular la probabilidad de una secuencia de observaciones

P (x1, x2,…xn∣θ)

Los Tres Problemas

1.Calcular la probabilidad de una secuencia de observaciones

2. Obtener la secuencia de estados más probable correspondiente a una secuencia de observaciones

P (x1, x2,…xn∣θ)

max P (z1, z2,… zn∣x1, x2,… xn ,θ)

Los Tres Problemas

1.Calcular la probabilidad de una secuencia de observaciones

2. Obtener la secuencia de estados más probable correspondiente a una secuencia de observaciones

3.Dada una secuencia de observaciones, ajustar los parámetros del modelo tal que

P (x1, x2,…xn∣θ)

max P (z1, z2,… zn∣x1, x2,… xn ,θ)

max P (Os∣θ)

Primer Problema

● Necesitamos calcular

Donde ψ representa una secuencia posible de estados

P (x1, x2,…xn∣θ)=∑Z∈ψ

P (x1, x2,… xn∣Ψ ,θ)P (Ψ∣θ)

Complejidad del Problema

● Enumerar todas las secuencias de estados posibles │Z │, esto es, iterar en │Z │n veces

● Calcular P(Z) y P(O │ Z) esto es iterar 2 veces sobre n

● 2n │Z │n

● Exponencial con la longitud de la secuencia!!!!!

Alternativas Más Eficientes

● Podemos utilizar una técnica de programación dinámica

● En HMM se le conoce como el algoritmo forward

● La idea es utilizar un acumulador α para cada estado que lleve la cuenta de la probabilidad de llegar a ese estado

Algoritmo Forward

x1 x2 xn−1 xn

…

…

α11 …

α21

αT1

α12

α22

αT2

α1(n−1)

α2(n−1)

αT (n−1)

α1n

α2n

αTn

z1

z2

zT

αij Probabilidad de llegar a un estado i en j pasos

Algoritmo Forward

x1 x2 xn

…

…

α11 …

α21

αT1

α12

α22

αT2

α1n

α2n

αTn

z1

z2

zT

αi1 P ( z i)P ( x1∣zi)

Algoritmo Forward

x1 x2

…

…

α11 …

α21

αT1

α12

α22

αT2

z1

z2

zT

αij=∑k=1

T

αk ( j−1) P (z i∣zk )P (xi∣z i)

xn

α1n

α2n

αTn

Algoritmo Forward

x1 x2

…

…

α11 …

α21

αT1

α12

α22

αT2

z1

z2

zT

P ( x1, x2,… , xn)=∑k=1

T

αkn

xn

α1n

α2n

αTn

Complejidad del Algoritmo

● Iterar n veces– Iterar en Z para calcular α: |Z| casos

● Iterar en α para calcular: |Z| casos

● T |Z| |Z|● 2T|Z|● Polinomial

Algoritmo Backward

x1 x2 xn−1 xn

…

…

β11…

β21

βT1

β12

β22

βT2

β1(n−1)

β2(n−1)

βT (n−1)

β1n

β2n

βTn

z1

z2

zT

βij Probabilidad de terminar del estado i en n-j pasos

Algoritmo Backward

βi n=1

x1 x2 xn

…

…

β11…

β21

βT1

β12

β22

βT2

β1n

β2n

βTn

z1

z2

zT

Algoritmo Backward

x1 x2

…

…

α11 …

α21

αT1

α12

α22

αT2

z1

z2

zT

βij=∑k=1

T

βk ( j+1) P ( zk∣z i)P ( xi+1∣zk )

xn

α1n

α2n

αTn

Algoritmo Backward

P ( x1, x2,… , xn)=∑k=1

T

βk1 P (x1∣z k)

x1 x2 xn

…

…

β11…

β21

βT1

β12

β22

βT2

β1n

β2n

βTn

z1

z2

zT

Segundo Problema

● Buscamos calcular

● Se usa el algoritmo de Viterbi● Viterbi es similar a Forward o Backward

– Forward: α guarda la probabilidad máxima para llegar a un estado

– Backward: β guarda la probabilidad máxima para a partir de ese estado llegar al final

● El problema se conoce como secuencia óptima

max P (z1, z2,… zn∣x1, x2,… xn ,θ)

Algoritmo Forward

x1 x2 xn−1 xn

…

…

α11 …

α21

αT1

α12

α22

αT2

α1(n−1)

α2(n−1)

αT (n−1)

α1n

α2n

αTn

z1

z2

zT

En lugar de sumar se aplica la operación max

Tercer Problema

● Existe un conjunto de secuencias Os y un número n

de estados y queremos definir θ tal que

– La probabilidad de cada secuencia de Os sea la mayor, es decir,

● En términos prácticos Os se conoce (por ej. La base de datos)

● El problema se le conoce de aprendizaje

max P (Os∣θ)=max∏ P (O i∣θ)

Aprendizaje Automático

● Supervisado: la base de datos contiene secuencia de Xs y Ys asociadas entre sí– {(A,r), (B,r), (C,v)}

– {(A,r), (C,v), (B,a)}

● Sin supervisión: sólo existen secuencias de Xs– r, r, b

– r, v, a

Supervisado

● Fácil● Contar las frecuencias para

– P(Z) = las veces que Z es inicial entre el número de ejemplos en el corpus

– P(Z | Z) = las veces que un estado pasa de un estado a otro, entre las veces que ocurre el primero

– P(X | Ζ) = Las veces que Z produce X entre las veces que ocurre Z

Sin Supervisión

● Un poco más difícil– Ya que no existe método analítico

● Se trata de una optimización

θ*=arg max

θ=∏

i=1

∣Os∣

P (O i∣θ)

Algoritmo Baum-Welch oForward-Backward● Es un método iterativo, no encuentra la mejor

solución pero da un máximo local

● Itera entre dos pasos

– Estimar probabilidades usando θ temporal

– Maximizar parámetros para obtener nuevos θ

● Es equivalente a EM

Esperanza Maximización

● Maximizar la esperanza de que los parámetros actuales generen tanto la secuencia observada como la secuencia oculta dada la secuencia oculta y parámetros anteriores

θ*=arg max

θE [log (P (O ,ψ∣θ))∣O ,θi−1

]

Esperanza

● Esa esperanza se le denomina Q cuando es expandida

● La segunda parte de esa ecuación es el paso E

● Consiste en calcular probabilidad de variables ocultas dado parámetros temporales

Q (θ ,θi−1)=∑Ψ∈ψ

P (O ,Ψ∣θ)P (O∣Ψ ,θ)i−1

Maximización

● Consiste en maximizar Q● En el caso de HMM sustituimos el primer producto

por una expresión analítica

● Y usando la técnica de lagrange y el hecho de las probabilidades suman zero, se maximiza la expresión

P (O , Ψ∣θ)=P ( z1∣θ)∏i=2

n

P (x i∣z i ,θ) P ( z i∣z i−1 ,θ)

EM en Resumen

● Se inicia con ciertos valores (al azar) y se actualizan los valores iterativamente

● Se obtiene un estimador de máxima verosimilitud– Encuentra parametros que maximizan la

probabilidad de generar las observaciones dadas

● No se garantiza un máximo global pero puede encontrar máximos locales

● Relacionado con K-means

Aplicaciones de los HMMs

● En general se aplican a problemas que puedan representarse como una secuencia de observaciones y etiquetas– Reconocedores del habla

– Análisis de DNA

– Robótica

– En procesamiento de lenguaje natural y lingüística computacional