Upload
others
View
14
Download
0
Embed Size (px)
Citation preview
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Bases Formales de la Computacion:Sesion 4. Modelos Ocultos de Markov
Prof. Gloria Ines Alvarez V.
Departamento de Ciencias e Ingenierıa de la ComputacionPontificia Universidad Javeriana Cali
Periodo 2008-2
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Contenido
1 Modelos Ocultos de markov
Problema 3
2 Tipos de Modelos Ocultos de Markov
Variaciones sobre la Estructura del Modelo
Variaciones sobre la Funcion de probabilidad de Emision
Variaciones sobre el Lugar de Emision
Otras Variaciones
3 Aplicaciones
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Evaluacion de la segunda parte del curso
Cada persona debe elegir un artıculo cientıfico de las bases dedatos IEEE Explorer o Science Direct the Elsevier, que reportela aplicacion de Modelos Ocultos de Markov a un temaespecıfico. Deben ponerse de acuerdo para que cada personapresente una aplicacion diferente.
Deben preparar una presentacion de 15 minutos dondeexpliquen el mencionado artıculo.
El dia 31 de octubre tendremos una evaluacion escrita de unahora y las presentaciones de los artıculos.
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Problema 3
El Problema 3 consiste en estimar los parametros del modelo demanera que se maximice la probabilidad de una secuencia deobservaciones dado el modelo. es decir: ajustar M para maximizarP(O|M)
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Problema de Estimacion del modelo
Este es sin duda el mas difıcil de resolver de los tres problemas
Dada una secuencia de observaciones de entrenamiento, nohay una manera optima de estimar los parametros del modelo:A,B ,Π
Se puede elegir M = (A,B ,Π) tal que P(O|M) se maximizalocalmente.
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Definicion de γt(i)
Definicion
La variable γt(i) representa la probabilidad de estar en el estado ien el tiempo t dadas la secuencia de observaciones O y el modeloM.
γt(i) = P(Xt = si |O,M)
γt(i) = P(Xt = si |O,M)
=αt(i)βt(i)
P(O|M)
=αt(i)βt(i)
∑Ni=1 αt(i)βt(i)
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Procedimiento de Reestimacion de Parametros
Es un proceso iterativo que aplica la estrategia EM(expectation-maximization)
La estrategia se conoce como el algoritmo de Baum-Welch
Definicion
Sea ξt(i , j) la probabilidad de estar en el estado si en el tiempo t yen el estado sj en el tiempo t + 1 dada una secuencia deobservaciones O y el modelo M. Es decir:
ξt(i , j) = P(Xt = si ,Xt+1 = sj |O,M)
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Explicacion Intuitiva
α t(i) β t(i)
A[i,j]B[j,O t+1]
t−1 t t+1 t+2
is sj
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Definicion precisa de ξt(i , j)
Definicion
ξt(i , j) =αt(i)A[i , j]B [j ,Ot+1]βt+1(j)
P(O|M)
=αt(i)A[i , j]B [j ,Ot+1]βt+1(j)
∑Ni=1
∑Nj=1 αt(i)A[i , j]B [j ,Ot+1]βt+1(j)
Se puede calcular γt(i) a partir de ξt(i , j):
Definicion
γt(i) =
N∑
j=1
ξt(i , j)
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Valores esperados de paso por un estado y por unatransicion
Definicion
El valor esperado (en el tiempo) del numero de veces que se visitael estado si es:
∑T−1t1
γt(i)
Definicion
El valor esperado (en el tiempo) del numero de veces que setransita desde el estado si hasta el estado sj es:
∑T−1t1
ξt(i , j)
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Reestimacion de Valores
Utilizando las variables previamente definidas y el concepto deconteo de ocurrencias de eventos, se propone una forma de ajustarlos valores de los parametros del modelo:
π[i ] es el numero de veces en el estado si en el tiempo t = 1
A[i , j] numero esperado de transiciones desde si hasta sj /numero esperado de transiciones desde si
B[j , k] es el numero esperado de veces que en el estado sj seobserva el evento vk / el numero esperado de veces en elestado sj
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Reestimacion de Valores
Definicion
Π[i ] = γ1(i)
A[i , j] =
∑T−1t=1 ξt(i , j)
∑T−1t=1 γt(i)
B[j , k] =
∑T−1t=1 γt(j),Ot = vk
∑T−1t=1 γt(j)
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Reestimacion de Valores
Baum y sus colegas demostraron que si se parte de un modeloM = (A,B ,Π), se calculan las reestimaciones anteriores y seobtiene un nuevo modelo M = (A, B , Π). Pueden ocurrir doscosas:
M = MM es mas probable que el modelo M , en el sentido queP(O|M) > P(O|M)
El proceso de reestimacion opera iterativamente hasta unpunto
Cuando se detiene se ha calculado el estimado de maximaverosimilitud del modelo oculto de Markov
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Modelos Ocultos de markov
Problema 3
Algoritmo BaumWelch(O1, O2, . . . )
Select arbitrary model parameters M ′ = (A′, B ′, Π′)
score =P
dP(Od |M ′)
repeat{
M = M’
for each sequence Od do{
Calculate αt(i)Calculate βt(i)Calculate newA, contribution of Od to A
Calculate newB, contribution of Od to B
}
A[i , j] = newA[i,j ]P
l A[i,l ]
B[j , k] = newB[j,k]P
l B[j,l ]
score =P
d P(Od |A, B)} until (the change in score is less than some predefined threshold)
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Variaciones sobre la Estructura del Modelo
Variaciones sobre la Estructura del Modelo
Modelo ergodico
Modelo de izquierda a derecha
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Variaciones sobre la Estructura del Modelo
Modelo Ergodico
Cada estado se comunica con cualquier otro en un numero finitode pasos. La matriz de probabilidades es de la forma:
1 2
3 4
A =
a11 a12 a13 a14
a21 a22 a23 a24
a31 a32 a33 a34
a41 a42 a43 a44
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Variaciones sobre la Estructura del Modelo
Modelo Izquierda a derecha
1 2 3 4
A =
a11 a12 a13 a14
0 a22 a23 a24
0 0 a33 a34
0 0 0 a44
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Variaciones sobre la Estructura del Modelo
Modelo Izquierda a derecha
El modelo empieza siempre por el primer estado (Π[1] = 1 y elresto valen cero)
Todas las transiciones apuntan a un estado que esta masadelante en la secuencia (A[i , j] = 0 si i > j)
Notar que las modificaciones en la arquitectura del modelo notienen impacto sobre el proceso de reestimacion, pues si unaprobabilidad esta en cero desde el principio seguira siendo ceroluego de la reestimacion.
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Variaciones sobre la Funcion de probabilidad de Emision
Variaciones sobre la Funcion de probabilidad de Emision
Funcion de densidad de probabilidad discreta
Funcion de densidad de probabilidad continua
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Variaciones sobre la Funcion de probabilidad de Emision
Densidades de Observacion Continuas
Si la naturaleza de las emisiones es continua, forzar sudiscretizacion causa degradacion en la informacion querepresenta
Se deben establecer algunas restricciones sobre la funcioncontinua para garantizar que la reestimacion sea consistente
La representacion mas general de una funcion de distribucionde probabilidad continua que se puede reestimar es unamixtura finita de la forma:
B [j ,O] =∑M
m=1 CjmN[O, µjm,Ujm]
En el caso continuo, se deben reestimar los parametros de lafuncion que comunmente es una Gaussiana
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Variaciones sobre la Funcion de probabilidad de Emision
Densidades de Observacion Continuas
Definicion
Cjk =
∑Tt=1 γt(j , k)
∑Tt=1
∑Mk=1 γt(j , k)
µjk =
∑Tt=1 γt(j , k)Ot
∑Tt=1 γt(j , k)
Ujk =
∑Tt=1 γt(j , k)(Ot − µjk)(Ot − µjk)′
∑Tt=1 γt(j , k)
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Variaciones sobre el Lugar de Emision
Variaciones sobre el Lugar de Emision
Emision en el estado
Emision en la transicion
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Tipos de Modelos Ocultos de Markov
Otras Variaciones
Otras Variaciones
Uso de estados nulos
Tiempo de permanencia en un estado
Bases Formales de la Computacion: Sesion 4. Modelos Ocultos de Markov
Aplicaciones
Campos de Aplicacion de los HMM
Para detectar la familia estructural a la que pertenece unaproteina desconocida
En reconocimiento de texto manuscrito
En reconocimiento automatico de habla
En deteccion y filtrado de spam
En recuperacion de informacion no estructurada
En etiquetamiento sintactico
En reconocimiento de imagenes, aplicado a reconocimiento derostros, gestos u objetos
En robotica