Suposiciones hechas por modelos ocultos de Markov
Fundamentos de los modelos ocultos de Markov
Resumen
- ¿Hay alguna diferencia entre el modelado de temas y el clúster?
- ¿Por qué el artículo de DeepMind sobre el aprendizaje de refuerzo (jugar juegos de atari) ganó popularidad estelar?
- ¿Cuáles son los mejores métodos para recopilar datos de entrenamiento para el algoritmo Naive Bayes?
- ¿Hay alguna universidad en la India que ofrezca cursos a corto plazo sobre aprendizaje automático / ciencia de datos?
- ¿Cómo se aplica el aprendizaje profundo en la industria?
¿Cómo podemos aplicar el aprendizaje automático a los datos que se representan como una secuencia de observaciones a lo largo del tiempo? Por ejemplo, podríamos estar interesados en descubrir la secuencia de palabras que alguien habló en base a una grabación de audio de su discurso. O podríamos estar interesados en anotar una secuencia de palabras con sus etiquetas de parte del discurso. Estas notas proporcionan una introducción matemática exhaustiva al concepto de modelos de Markov
un formalismo para razonar sobre estados a lo largo del tiempo y modelos ocultos de Markov donde deseamos recuperar una serie de estados a partir de una serie de observaciones. La sección final incluye algunos consejos sobre recursos que presentan este material desde otras perspectivas.
Modelos Markov
Dado un conjunto de estados S – {.SISI} podemos observar una serie a lo largo del tiempo, es decir, S
T
. Por ejemplo, podríamos tener los estados de un sistema meteorológico S – {sol, nubes, lluvia} con ISI = 3 y observar el clima durante unos días {Zl – Ssun
7 7
+2 = Scloud ‘Z3 = Scloud’ Z4 rain ‘7 + 5 = * fuerte} con T = 5.
Los estados observados de nuestro ejemplo meteorológico representan la salida de un proceso aleatorio a lo largo del tiempo. Sin algunos supuestos adicionales, el estado sj en el tiempo t podría ser una función de cualquier número de variables, incluidos todos los estados desde los tiempos 1 a t – 1 y posiblemente muchos otros que ni siquiera modelamos. Sin embargo, haremos dos SUPUESTOS DE MARKOV que nos permitirán razonar de manera manejable sobre series de tiempo.
La ASUNCIÓN LIMITADA DEL HORIZONTE es que la probabilidad de estar en un estado en el tiempo t depende solo del estado en el tiempo t— 1. La intuición subyacente a esta suposición es que el estado en el tiempo t representa un resumen “suficiente” del pasado para predecir razonablemente el futuro. Formalmente:
P (ztlzt-l,…, Zl) P (ztlzt-l
La ASUNCIÓN DE PROCESO ESTACIONARIO es que la distribución condicional en el siguiente estado dado el estado actual no cambia con el tiempo. Formalmente:
P (zt zt-l) = P (Z2 Zl); te 2 … T
Como convención, también asumiremos que hay un estado inicial y una observación inicial zo – so, donde representa la distribución de probabilidad inicial sobre los estados en el tiempo 0. Esta conveniencia de notación nos permite codificar nuestra creencia sobre la probabilidad previa de ver el primer estado real Zl como P (Zl Izo). Tenga en cuenta que
. , Zl) = P (ztlzt-l, …, Zl, zo) porque hemos definido zo = so para cualquier secuencia de estado. (Otras presentaciones de HMM a veces representan estas creencias previas con un vector T e IR
Soy yo
. )
Parametrizamos estas transiciones definiendo una matriz de transición de estado A e
El valor AiJ es la probabilidad de pasar del estado i al estado j en cualquier momento t. Para nuestro ejemplo de sol y lluvia, podríamos tener la siguiente matriz de transición:
S cloud Srain
SO o .33 .33 .33
o .8 .1 .1 S cl ou, do .2 .6 .2 srain o .1 .2
Tenga en cuenta que estos números (que inventé) representan la intuición de que el clima está auto correlacionado: si hace sol, tenderá a mantenerse soleado, nublado permanecerá nublado, etc. Este patrón es común en muchos modelos de Markov y puede observarse como una diagonal fuerte en la matriz de transición. Tenga en cuenta que en este ejemplo, nuestro estado inicial muestra una probabilidad uniforme de transición a cada uno de los tres estados de nuestro sistema meteorológico.
Dos preguntas de un modelo de Markov
Combinando los supuestos de Markov con nuestra parametrización de transición de estado A, podemos responder dos preguntas básicas sobre una secuencia de estados en una cadena de Markov. ¿Cuál es la probabilidad de una secuencia particular de estados 2? ¿Y cómo estimamos los parámetros de nuestro modelo A para maximizar la probabilidad de una secuencia observada?
Probabilidad de una secuencia de estados.
Podemos calcular la probabilidad de una serie particular de estados i mediante el uso de la regla de la cadena de probabilidad:
P (zt, zt
P (zt, zt_
P (zt zt
P (zt zt_l;
zo; UNA)
P (ZtIZt-1; A) t = l
Zt-l zt
En la segunda línea, introducimos zo en nuestra probabilidad conjunta, que está permitida por la definición de zo anterior. La tercera línea es cierta para cualquier distribución conjunta por la regla de la cadena de probabilidades o la aplicación repetida de la regla de Bayes. La cuarta línea se desprende de los supuestos de Markov y la última línea representa estos términos como sus elementos en nuestra matriz de transición A.
Calculemos la probabilidad de nuestra secuencia de tiempo de ejemplo de antes. Queremos P (Zl sol ‘Z2 = Scloud’ Z3 rain ‘Z4 rain’ 5 = scioud) que puede factorizarse como P (ssun
S
sol P (S lluvia ratn S lluvia) P (S nube Srain
.33 x .1 x .2 x .7 x .2
Asignación de parámetros de máxima verosimilitud
Desde una perspectiva de aprendizaje, podríamos buscar encontrar los parámetros A que maximicen la probabilidad logarítmica de la secuencia de observaciones E. Esto corresponde a encontrar las probabilidades de transición de soleado a nublado versus soleado a soleado, etc., que forman un conjunto de observaciones más probables. Definamos la probabilidad logarítmica de un modelo de Markov.
log P (i; A)
log LIAZt — l zt t = l
sol
t = l
ISI ISI T
= sj} log Aij
En la última línea, usamos una función de indicador cuyo valor es uno cuando la condición se cumple y cero de lo contrario para seleccionar la transición observada en cada paso de tiempo. Al resolver este problema de optimización, es importante asegurarse de que los parámetros resueltos A sigan formando una matriz de transición válida. En particular, debemos hacer cumplir que la distribución de probabilidad saliente del estado i siempre se suma a 1 y que todos los elementos de A no son negativos. Podemos resolver este problema de optimización utilizando el método de multiplicadores de Lagrange.
max I (A)
ISI
S t
Este problema de optimización restringida puede resolverse en forma cerrada utilizando el método de multiplicadores de Lagrange. Introduciremos la restricción de igualdad en el lagrangiano, pero la restricción de desigualdad puede ignorarse con seguridad, la solución óptima producirá valores positivos para Aij de todos modos. Por lo tanto, construimos el lagrangiano como:
ISI ISI T ISI ISI
– EEE 1 {zt – 1
sj} log Aij + en (l – Atj)
Tomando derivadas parciales y poniéndolas iguales a cero obtenemos:
DC (A, a)
Sustituyendo nuevamente y estableciendo el parcial con respecto a un igual a cero:
ISI
DC (A, 0)
Avena
LO ES
EE l {zt-l
A zt –
j = l
E l {Zt-l
Sustituyendo en este valor por ai en la expresión que derivamos para Ai] obtenemos nuestro valor de parámetro de máxima verosimilitud final para.
EtT
Esta fórmula codifica una intuición simple: la probabilidad de probabilidad máxima de transición del estado i al estado j es solo el número de veces que hacemos la transición de i a j dividido por el número total de veces que estamos en i. En otras palabras, el parámetro de máxima verosimilitud corresponde a la fracción de tiempo cuando estábamos en el estado i que hicimos la transición a j.
Modelos ocultos de Markov
Los modelos de Markov son una abstracción poderosa para datos de series temporales, pero no pueden limitar
Es un escenario muy común. ¿Cómo podemos razonar sobre una serie de estados si no podemos observar los estados mismos, sino más bien solo alguna función probabilística de esos estados? Este es el escenario para el etiquetado de parte del discurso donde las palabras se observan pero las etiquetas de partes del discurso no lo son, y para el reconocimiento de voz
ción donde se observa la secuencia de sonido pero no las palabras que la generaron. Para un ejemplo simple, tomemos prestada la configuración propuesta por Jason Eisner en 2002 [1], “Ice Cream Climatology”.
La situación: eres climatólogo en el año 2799, estudias la historia del calentamiento global. No puede encontrar ningún registro del clima de Baltimore, pero sí encuentra mi diario (de Jason Eisner), en el que grabé asiduamente la cantidad de helado que comía cada día. ¿Qué se puede deducir de esto sobre el clima ese verano?
Se puede usar un modelo de Markov oculto (HMM) para explorar este escenario. no podemos observar la secuencia real de estados (el clima en cada día). Por el contrario, solo podemos observar algunos resultados generados por cada estado (cuántos helados se comieron ese día).
Formalmente, un HMM es un modelo de Markov para el que tenemos una serie de resultados observados x Xl, X2, …, XT} extraídos de un alfabeto de salida V = {VI, c’2, …, VIVI},
es decir, e V, t = I..T. Como en la sección anterior, también postulamos la existencia de se
Riesgos de estados z – …, ZT} extraídos de un alfabeto de estado S = {Sl, s2, ..
zt e S, t = I..T pero en este escenario los valores de los estados no son observados. La transición entre los estados i y j nuevamente estará representada por el valor correspondiente en nuestra matriz de transición de estado AtJ
También modelamos la probabilidad de generar una observación de salida en función de nuestro estado oculto. Para hacerlo, hacemos la ASUNCIÓN DE INDEPENDENCIA DE SALIDA y definimos = Vklzt = sj) = P (Xt = Vk lX1,.
Bjk. La matriz B codifica la probabilidad de que nuestro estado oculto genere salida Uk dado que el estado en el momento correspondiente era s,
Volviendo al ejemplo del clima, imagine que tiene registros de consumo de helado durante un período de cuatro días: = V3, X2 = U’2, X3 VI, X4 = V’2
donde nuestro alfabeto solo codifica la cantidad de helados consumidos, es decir, V –
– 1 helado, – 2 helados, 3 helados}. ¿Qué preguntas puede responder un HMM?
Tres preguntas de un modelo oculto de Markov
Hay tres preguntas fundamentales que podríamos hacerle a un HMM. ¿Cuál es la probabilidad de una secuencia observada (qué tan probable es que veamos 3, 2, 1, 2 helados consumidos)? ¿Cuál es la serie de estados más probable para generar las observaciones (cuál fue el clima durante esos cuatro días)? ¿Y cómo podemos aprender valores para los parámetros A y B del HMM dados algunos datos?
Probabilidad de una secuencia observada: procedimiento directo
En un HMM, suponemos que nuestros datos fueron generados por el siguiente proceso: postulamos la existencia de una serie de estados a lo largo de nuestra serie de tiempo. Esta secuencia de estado es generada por un modelo de Markov parametrizado por una matriz de transición de estado A. En cada paso de tiempo t, seleccionamos una salida en función del estado zt. Por lo tanto, para obtener la probabilidad de una secuencia de observaciones, necesitamos sumar la probabilidad de los datos dados cada serie posible de estados.
A, B)
Las fórmulas anteriores son verdaderas para cualquier distribución de probabilidad. Sin embargo, los supuestos de HMM nos permiten simplificar aún más la expresión:
P (xt zt; B)) (HP (zt 0-1; A))
Bzt (M Azt 1 zt) t = l
La buena noticia es que esta es una expresión simple en términos de nuestros parámetros. La derivación sigue los supuestos de HMM: el supuesto de independencia de salida, el supuesto de Markov y el supuesto de proceso estacionario se utilizan para derivar la segunda línea. La mala noticia es que la suma supera todas las asignaciones posibles a E. Debido a que zt puede tomar uno de los valores posibles de ISI en cada paso de tiempo, evaluar esta suma directamente requerirá operaciones O (ISI T).
Algoritmo 1 Procedimiento directo para calcular en, (t)
1)
Caso base: = 240 i, i I..IS
2)
Recursión: aj (t) = ISI1 – 1) AtjBjxt, J – 1 .. Sl, t = I..T
Afortunadamente, un medio más rápido de calcular P (i; A, B) es posible a través de un dy
algoritmo de programación namic llamado PROCEDIMIENTO ADELANTE. Primero, definamos una cantidad = P (Xl, x2, • •., Xt, zt st ••, A, B). at (t) representa la probabilidad total de todas las observaciones hasta el tiempo t (por cualquier asignación de estado) y que estamos en el estado Si en el tiempo t. Si tuviéramos tal cantidad, la probabilidad de nuestro conjunto completo de observaciones P (F) podría representarse como:
PDI, xo,. . . , XT •, A, B)
ISI
mi
PAGS
(
X
l, X2, …, XT, 70T
i = l
ISI
Comer (T)
El algoritmo 2.2 presenta una forma eficiente de calcular en, (t). En cada paso de tiempo solo debemos realizar operaciones O (ISI), lo que resulta en una complejidad de algoritmo final de O (ISI • T) para calcular la probabilidad total de una secuencia de estado observada
Se puede usar un algoritmo similar conocido como PROCEDIMIENTO HACIA ATRÁS para calcular una probabilidad análoga ßi (t) = P (XT, XT — I, .., xt + l, zt
Asignación de estado de máxima verosimilitud: el algoritmo de Viterbi
Una de las consultas más comunes de un modelo oculto de Markov es preguntar cuál fue la serie de estados más probable, es decir, ST dada una serie observada de resultados
e VT. Formalmente, buscamos:
arg P (Eli; A, B) arg max
arg myx P (i, E; A, B)
La primera simplificación se deriva de la regla de Bayes y la segunda de la observación de que el denominador no depende directamente de E. Ingenuamente, podríamos intentar cada asignación posible a E y tomar la que tenga la mayor probabilidad conjunta asignada por nuestro modelo. Sin embargo, esto requeriría O (ISI
T
) operaciones solo para enumerar el conjunto de asignaciones posibles. En este punto, podría pensar que una solución de programación dinámica como el algoritmo de avance podría salvar el día, y estaría en lo cierto. Tenga en cuenta que si reemplazó el argumento max: con
nuestra tarea actual es exactamente análoga a la expresión que motivó el procedimiento de avance.
Algoritmo 2 Aplicación ingenua de EM a HMM
Repita hasta la convergencia
(E-Step) Para cada etiquetado posible, es decir, S
T
establecer
(M-Step) Set
arg max
ISI
p (ilö; A, B)
Q (E) log
S t
IVI
1, yo
I..IS Aij 2 0, i, j
I..IS
E Bik
1
yo
1 .. SI • 2 0, i
1 .. Sl, k
l..lvl
El ALGORITMO VITERBI es como el procedimiento directo, excepto que en lugar de rastrear la probabilidad total de generar las observaciones vistas hasta ahora, solo necesitamos rastrear la probabilidad máxima y registrar su secuencia de estado correspondiente.
Aprendizaje de parámetros: EM para HMM
La última pregunta que debe hacerse a un HMM es: dado un conjunto de observaciones, ¿cuáles son los valores de las probabilidades de transición de estado A y las probabilidades de emisión de salida B que hacen que los datos sean más probables? Por ejemplo, resolver los parámetros de máxima verosimilitud basados en un conjunto de datos de reconocimiento de voz nos permitirá entrenar eficazmente el HMM antes de solicitar la asignación del estado de máxima verosimilitud de una señal de voz candidata.
En esta sección, presentamos una derivación del algoritmo de maximización de expectativas para los modelos ocultos de Markov.
Haremos uso de los algoritmos de avance y retroceso mencionados anteriormente para calcular un conjunto de estadísticas suficientes para nuestro E-Step y M-Step de manera manejable.
Primero, reescribamos la función objetivo usando nuestros supuestos de Markov.
ISI ISI IVI T
l {zt = sy A = ’11k} log Bjk +
sj} log Aij
En la primera línea dividimos la división logarítmica en una resta y observamos que el término del denominador no depende de los parámetros A, B. Las suposiciones de Markov se aplican en la línea 3. La línea 5 usa funciones de indicador para indexar A y B por estado.
Al igual que para los parámetros de máxima verosimilitud para un modelo de Markov visible, es seguro ignorar las restricciones de desigualdad porque la forma de la solución naturalmente da como resultado solo soluciones positivas. Construyendo el lagrangiano:
ISI ISI IVI T
– SJ A Xt = Uk} log Bj k 1 {Zt — l
sj} log Aij
Tomando derivadas parciales y poniéndolas iguales a cero:
DC (A, B, 5, e)
DC (A, B, ö, e) Q (i) 1
E El {zt = sj A xt = Vk}
DBjk Bjk t-1
Bjk
= sj A xt = t’k}
Tomando derivadas parciales con respecto a los multiplicadores de Lagrange y sustituyendo nuestros valores de Ai9 y Bjk arriba:
DC (A, B, D, e)
Punto
DC (A, B, D, e)
ISI
1
IVI 1
k = l
IVI
= sj A xt = Reino Unido}
’11k}
l
{
z
t = Y.}
t = l
Sustituyendo de nuevo en nuestras expresiones anteriores, encontramos que los parámetros A y B que maximizan nuestros recuentos predichos con respecto al conjunto de datos son:
Bjk
Desafortunadamente, cada una de estas sumas está sobre todos los trabajos posibles, es decir, S
T
. Pero recuerde que Q (i) se definió en el paso E como P (Eli; A, B) para los parámetros A y B en el último paso de tiempo. Consideremos cómo representar primero el numerador de At) en términos de nuestras probabilidades hacia adelante y hacia atrás, y ßj (t).
1
t = l
En los primeros dos pasos, reorganizamos los términos y los sustituimos por nuestra definición de Q. Luego, usamos la regla de Bayes para derivar la línea cuatro, seguida de las definiciones de a, [3, A y B, en la línea cinco. Del mismo modo, el denominador se puede representar sumando sobre j el valor del numerador.
LO ES
Combinando estas expresiones, podemos caracterizar completamente nuestras transiciones de estado de máxima verosimilitud en] sin necesidad de enumerar todos los posibles etiquetados como:
Del mismo modo, podemos representar el numerador de Bjk como:
LO ES
1
Algoritmo 3 Algoritmo de avance / retroceso para el aprendizaje de parámetros HMM
Inicialización: establezca A y B como matrices de probabilidad válidas al azar donde Ato = 0 y BOk = 0 para i – I..ISI yk = 1 .. V.
Repita hasta la convergencia
(E-Step) Ejecute los algoritmos de avance y retroceso para calcular ai y para i I..ISI. Luego establezca:
(Paso M) Vuelva a estimar los parámetros de máxima verosimilitud como:
LO ES
1
l
{xt =
Y el denominador de Bjk como:
ISI T 1
LO ES
1
Combinando estas expresiones, tenemos la siguiente forma para nuestras probabilidades de emisión de máxima verosimilitud como:
El algoritmo 2.4 muestra una variante del ALGORITMO HACIA ADELANTE o ALGORITMO BAUM-WELCH para el aprendizaje de parámetros en HMM. En el
E-Step, en lugar de evaluar explícitamente Q (i) para todos, es decir, S
T
, calculamos una estadística suficiente
en (t) At9B, Xtßj (t + 1) que es proporcional a la probabilidad de transición entre sate Si y sj en el tiempo t dadas todas nuestras observaciones i. Las expresiones derivadas para Aij y Bjk son intuitivamente atractivas. Atj se calcula como el número esperado de transiciones de Si a sj dividido por el número esperado de apariciones de st. De manera similar, Bjk se calcula como el número esperado de emisiones de Uk de sj dividido por el número esperado de apariciones de s
Como muchas aplicaciones de EM, el aprendizaje de parámetros para HM Ms es un problema no convexo con muchos máximos locales. EM convergerá al máximo en función de sus parámetros iniciales, por lo que es posible que se realicen varias ejecuciones. Además, a menudo es importante suavizar las distribuciones de probabilidad representadas por A y B para que no se asigne ninguna probabilidad de transición o emisión.
