Lecci on 6: Modelos de cadenas de Markov oculto

Leccion 6:Modelos de cadenas de Markov oculto

Dr. Jesus SavageDr. Carlos Rivera

23 de abril de 2020

Dr. Jesus Savage Dr. Carlos Rivera Leccion 6: Modelos de cadenas de Markov oculto 23 de abril de 2020 1 / 24

Indice

1 Modelos de cadenas de Markov

2 Procesos de Markov discretos en el tiempo

3 Modelos de cadenas de Markov Ocultos


Modelos de cadenas de Markov

La teorıa de cadenas de Markov ha sido extensivamente utilizada pararesolver problemas de reconocimiento de patrones. La asumpcion principales que senales de una, dos y tres dimensiones pueden ser caracterizadascomo un proceso aleatorio parametrico, y que los parametros del procesoestocastico pueden ser determinados (estimados) en una manera precisa ybien definida Se utilizan principalmente para el tipo de procesos que varianen el tiempo.


Procesos de Markov discretos en el tiempo

Una cadena de Markov esta formado por un conjunto de estados unidospor ligas. La transicion de un estado a otro esta determinado porprobabilidades.


Procesos de Markov discretos en el tiempo

Los cambios de estados se denominan qt en el tiempo t. Probabilidad deque la cadena de Markov se encuentre en un estado determinado j

P[qt = j∣∣ qt−1 = i , qt−2 = k , ...] = P[qt = j

∣∣ qt−1 = i ]

aij = P[qt = j∣∣ qt−1 = i ], 1 ≤ i j ≤ N

0 ≤ aij ≤ 1 ∀ i , j

N∑j=1

aij = 1 ∀i

Este modelo es observable puesto que la salida es un conjunto de estadosen cada instante donde cada estado representa un evento observable.


Ejemplo

Supongase que tenemos un modelo del tiempo como se describe acontinuacion:

Donde: S1 = Lluvia; S2 = Nublado; S3 = SoleadoEl tiempo t es tomado a las 12:00 en el dıa.Dr. Jesus Savage Dr. Carlos Rivera Leccion 6: Modelos de cadenas de Markov oculto 23 de abril de 2020 6 / 24

Ejemplo

A = {aij} =

0. 4 0. 3 0. 30. 2 0. 6 0. 20. 1 0. 1 0. 8

Problema: ¿Cual es la probabilidad que el clima en 8 dıas consecutivos sea:soleado, soleado, soleado, lluvioso, lluvioso, soleado, nublado, soleado?Definiendo la secuencia de observacion O, como

O = (Soleado, Soleado, Soleado, Lluvioso,

Lluvioso,Soleado,Nublado,Soleado)

O = (S3,S3, S3,S1, S1, S3,S2, S3)

P(O|modelo) = Probabilidad de observar la secuencia O,

dado el modelo del clima


Ejemplo

= P(S3,S3, S3,S1, S1,S3,S2, S3|modelo)

= P(S3)P [S3|S3]2 P [S1|S3]P [S1|S1]P [S3|S1]P [S2|S3]P [S3|S2]

= π3(a33)2 a31 a11 a13 a32 a23

= (1. 0)(0. 8)2(0. 1)(0. 4)(0. 3)(0. 1)(0. 2) = 1. 536x10−4

Donde se usa la notacion:

π3 = P [q1 = 3] = 1

πi son las probabilidades iniciales, en este ejemplo cuando se inicio elexperimento era ya un dıa soleado, por lo tanto π3 = 1.


Problema

¿Cual es la probabilidad que el sistema se quede en un estado especıfico ipor d dıas?Secuencia de observaciones:

O = (i , i , i , ..., i , j 6= i)

dias = (1, 2, 3, ..., d , d + 1)

¿ P(O|modelo, q1 = i) ?Recordar la definicion de probabilidades condicionales:

P(A|B) =P(A · B)

P(B)

P(B|A) =P(A · B)

P(A)


Problema

P(O|modelo, q1 = i) =P(O,modelo, q1 = i)

P(modelo, q1 = i)=

P(O,modelo, q1 = i)

P(modelo)P(q1 = i)

P(O, q1 = i |modelo) =P(O, q1 = i ,modelo)

P(modelo)

P(O, q1 = i |modelo)P(modelo) = P(O, q1 = i ,modelo)

Substituyendo esta expresion en la primera ecuacion:

P(O|modelo, q1 = i) =P(O, q1 = i |modelo)P(model)

P(modelo)P(q1 = i)

⇒ P(O|modelo) =P(O, q1 = i |modelo)

P(q1 = i)

= πi ad−1ii · (1− aii )/πi


Problema

= ad−1ii (1− aii ) = Pi (d)

Pi (d) es la funcion de probabilidad de estar en el estado i d vecescontinuas.

Pi (d) = P [qt = j |qt−1 = i ] ...P [q1 = i |q0 = i ]

Se puede calcular el numero esperado de durar en el estado i

di =∞∑d=1

d pi (d)


Problema

=∞∑d=1

dad−1ii (1− aii )

= (1− aii )∞∑d=1

dad−1ii = (1− aii )

δ

δaii

∞∑d=1

adii

Por otra parte:

∞∑d=1

adii =∞∑d=1

adii + 1− 1 =∞∑d=0

adii − 1 =1

1− aii− 1

=1− 1 + aii

1− aii=

aii1− aii

= (1− aii )δ

δaii

(aii

1− aii

)Dr. Jesus Savage Dr. Carlos Rivera Leccion 6: Modelos de cadenas de Markov oculto 23 de abril de 2020 12 / 24

Problema

δ

δaiiaii (1− aii )

−1 = (1− aii )−1 − aii (−1)(1− aii )

−2

=1

1− aii+

aii(1− aii )2

=1− aii + aii

(1− aii )2=

1

(1− aii )2

Finalmente

di = (1− aii ) ·1

(1− aii )2=

1

(1− aii )


Modelos de Markov Ocultos

Ejemplos de repaso:Dada una moneda normal P(sol) = P(aguila) = 0. 5

1 ¿Cual es la probabilidad que los proximos diez volados den la siguientesecuencia, con S = sol y A = aguila?(S , S ,A,S ,A,A,S ,A,A, S)Para una moneda normal haciendo 10 volados independientes hay 210

secuencias probables, y como cada una tiene la misma probabilidad deocurrir, entonces:

P(SSASAASAAS) =

(1

2

)10


Modelos de Markov

2 ¿Cual es la probabilidad de que los proximos 10 volados generen unasecuencia (SSSSSSSSSS)?

P(SSSSSSSSSS) =

(1

2

)10

3 ¿Cual es la probabilidad de que 5 de los 10 proximos volados sean soles?Esta probabilidad es igual al numero de secuencias observadas con 5soles y 5 aguilas (en cualquier orden).

P(5S , 5A) =

(10

5

)(1

2

)10

=252

1024≈ 0. 25

Ya que hay(10

5

)formas de tener 5 soles y 5 aguilas en 10 volados, y

cada secuencia tiene una probabilidad de(

12

)10



4 ¿Cual es el numero esperado de soles en 10 volados?

E (S en 10 volados) =10∑d=0

d

(10

d

)(1

2

)10

= 5


Ejemplo

Supongamos que una persona esta echando volados detras de una cortina,con diferentes monedas cargadas.La persona solamente dice el resultado obtenido sin decir de que monedauso. ¿Como se construirıa un modelo de cadenas de Markov Ocultos talque explicara la recurrencia de aguilas y soles obtenidos?

O = (O1,O2,O3, ...,OT )

= (AASSA...S)


Modelo con una sola moneda

Observaciones = AASSASASSEstados = 112212122Los estados correspoden a las observaciones.


Modelo con dos monedas

Observaciones = AASSASASSEstados = 211122211


Modelo con tres monedas

Observaciones = O = SSAASASAASSA

Estados = q = 312331111313

P1(A) = P1; P2(A) = P2; P3(A) = P3

P1(S) = 1− P1; P2(S) = 1− P2; P3(S) = 1− P3

Las ai s representan las probabilidades de cambiar las monedas cuando sehacen los volados.Dr. Jesus Savage Dr. Carlos Rivera Leccion 6: Modelos de cadenas de Markov oculto 23 de abril de 2020 20 / 24

Modelo de las urnas con pelotas

Se tienen N urnas con M bolas de diferentes colores. Se tiene una personaque aleatoriamente escoge una pelota de alguna de las urnas y la muestra,repitiendo esta operacion varias veces. El proceso completo corresponde auna salida observable de un HMM.



O = {Verde,Verde,Azul ,Rojo,Amarillo, ...,Azul}

Elementos de un HMM para observaciones de sımbolos discretos.

1 N numero de estados del modelo.A pesar que los estados son ocultos, para muchas aplicaciones practicashay evidancia fısica para cada uno de los estados. Cada estado esdenominado como {1, 2, ...,N}, y el tiempo en el estado como qt

2 M, el numero de observaciones distintas en cada estado, es decir, elalfabeto de tamano discreto.Las observaciones corresponden a las salidas fısicas del sistema queesta siendo modelado. Se representan los sımbolos individuales comoV = {V 1,V2, ...,VM}



3 La distribucion de probabilidad es de cambio de estado A = {aij} donde

aij = P{qt+1 = j |qt = i}, 1 ≤ i , j ≤ N;

0 ≤ aij ≤ 1; ∀i , j

4 La distribucion de probabilidad del sımbolo observado, B = {bj(k)}

bj(k) = P[Ot = Vk |qt = j ], 1 ≤ k ≤ M

5 La distribucion del estado inicial π = πj

πi = P[q1 = i ], 1 ≤ i ≤ N



Entonces el modelo de Markov oculto (en ingles Hidden Markov Model,HMM), completo requiere los valores de N,M, los sımbolos de salida V yuna especificacion de las probabilidades A,B y π. Por conveniencia se usala siguiente notacion:

λ = (A,B, π)


Documents

Lecci on 6: Modelos de cadenas de Markov oculto