Modelo Oculto de Markov

Modelo Oculto de Markov, HMM (Hidden Markov Model)El Modelo Oculto de Markov (MOM) o HMM (Hidden Markov Model), es una cadena de Markov donde cada estado, que no es observable y está asociado con una distribución de probabilidad, genera una observación que sí es observable. La información sobre el pasado se transmite a través de una única variable discreta que es el estado oculto. El objetivo del modelo es inferir la secuencia de estados oculta. Su origen se debe a una serie de artículos publicados por Leonard E. Baum desde 1.960 en el IDA (Otro organismo bélico de EE.UU.).

Leonard Esau Baum
Baum

 

Modelo Oculto de Markov, HMM (Hidden Markov Model)
Modelo Oculto de Markov

 

 

De otra forma, el modelo trata de relacionar una secuencia de observaciones con una secuencia de estados ocultos que explican las observaciones. El proceso asigna una etiqueta a cada estado (palabras, valor, etc.) y calcula una distribución de probabilidad sobre las posibles secuencias de etiquetas eligiendo la mejor de ellas. El proceso de descubrir la secuencia de estados, dada una secuencia de observaciones, se conoce como decodificación o inferencia.

 

Otras definiciones del modelo:

  • B. H. Juang y L. R. Rabiner: «Un HMM es un proceso doblemente estocástico con un proceso estocástico subyacente que no es observable (está oculto), pero solo puede observarse a través de otro conjunto de procesos estocásticos que producen la secuencia de símbolos observados».
  • L. R. Rabiner. HMM es una máquina estocástica de estados finitos capaz de producir a su salida una secuencia de símbolos observables.

HMM se utiliza como método estadístico y aplicable en el entrenamiento no supervisado de redes neuronales, además de en otros sistemas de reconocimiento de patrones que necesitan modelar las correlaciones entre símbolos o eventos adyacentes através de patrones de secuencia de tiempo.

 

Se usó como técnica base para los sistemas de reconocimiento de voz y de escritura desarrollados a finales de los años 1.960, pero es a partir de 1.980 cuando verdaderamente empieza a aplicarse, aunque es inapropiado para el análisis de la visión y otras aplicaciones que se componen de múltiples procesos de interacción. En la actualidad se utiliza en una amplia gama de problemas en el análisis de secuencias biológicas, reconocimiento de texto manuscrito y hasta en los mercados financieros como una herramienta de análisis por los grandes fondos de inversión, fondos buitres y entidades relacionadas.

 

 

Descripción del modelo.

Para describir el modelo se utiliza la siguiente notación y elementos, Φ = (A,B,π) y N, M, O, donde:

 

Φ = (A,B,π) es el modelo.

 

N y M: Son parámetros.

N: Número de estados.

Estados individuales: E = {e1, …, eN }, en el tiempo t.

qt estado en el que se encuentra el modelo en el instante t.

Q = (q1, q2, … qT).  Secuencia de estados.

Existen Nt posibles secuencias de estado.

M: Es el conjunto finito de posibles observaciones, O = {o1,… , oM }. Por ejemplo: Las seis caras de un dado, las dos caras de una moneda o las 27 letras del alfabeto español.

 

A,B,π:  Son medidas de probabilidad.

A: Una matriz de probabilidades de transición de estados, A={aij}. Distribución de probabilidad (p) en la transición de estado (e).

aij = P [ qt + 1 = ej | qt = ei]

donde: 1 ≤ i, j ≤ N

B: Matriz de probabilidades de la observación en un estado (emisión), para observaciones discretas, aunque se puede generalizar para estado continuos.

B = bj(k)

donde :  bj(k) = P(Ot = vk | qt = ej )
y donde: 1 ≤  j ≤ N

1 ≤  k ≤ M

vk   representa el valor de la observación

 

π = {πi}:  El conjunto de probabilidades de los estados iniciales.

πi = P[q1 = ei],

donde: 1 ≤  i ≤ N

 

O: Observaciones.

Con N, M, A, B, π,  el HMM puede generar la secuencia real de observaciones O = {o1,… , ot }. ot es la variable aleatoria que denota la observación en el tiempo t (variable de salida).

 

Evolución temporal.

El modelo transita (evoluciona) de acuerdo con dos reglas:

  1. Puede moverse del estado actual al siguiente, donde este puede ser el mismo. El movimiento (paso, transición) se realiza mediante alguna distribución de probabilidad que depende solo del estado actual:
    • Es decir p (et | e1) = p (et | et ,…, e1) que se conoce como la propiedad de Markov.
  2. Después de cada transición, el modelo emite una observación cuya distribución depende solo del estado actual, es decir p (ot | o1) = p (ot | ot, et, … , o1, e1). A los estados que generan las observaciones, que son desconocidos para el observador, son los estados ocultos.

Ejemplo.

Suponemos que Mari Cruz sólo puede estar trabajando o en día de descanso. Después de trabajar o cuando está de descanso, puede ir de tiendas, ver a su familia o directamente duerme plácidamente. Con estos datos y alguno más, armamos un ejemplo:

 

π = {0,70, 0,30}

N: 2

E = {Laboral, Festivo}

M: 3

O = {Tiendas, Dormir, Familia}

Ejemplo Modelo Oculto de Markov, HMM (Hidden Markov Model)
Ejemplo HMM

A: Matriz Probabilidades de Transición

A Laboral Festivo
Laboral 0,85 0,15
Festivo 0,75 0,25

 

 

 

 

B: Matriz Probabilidad de Observación dado un estado

 B Tiendas Dormir Familia
Laboral 0,1 0,7 0,2
Festivo 0,55 0,15 0,3

Continuamos, ahora consideramos la siguiente secuencia de observaciones que ha realizado Mari Cruz durante tres días:

O = {oTiendas, oDormir, oFamilia}.

 

Lawrence R. Rabiner
Rabiner

Para revelar lo que esconde el ejemplo debemos conocer los tres tipos fundamentales de problemas que aborda el HMM y que fueron propuestos por John D. Ferguson en 1.980 y Lawrence R. Rabiner en 1.989. Cada pregunta (problema) tiene uno o varios algoritmos para su solución, estos pueden ser seguidos en los enlaces para terminar el ejemplo.

Problemas del modelo.

1. Probabilidad.  ¿Cuál es la probabilidad  P (O | Φ) de que el modelo Φ = (A, B, π) genere las observaciones (O = o1,… , ot) ?.  Para calcularla debemos tratar todas las rutas posibles y realizar una evaluación para verificar el grado de coincidencia de cada secuencia de observación y el modelo. Para resolver el problema se utilizan dos algoritmos:

Forward o algoritmo de Avance.

Backward o algoritmo de Retroceso

Estos algoritmos, de forma conjunta, permiten encontrar el estado más probable en cualquier instante t (paso en el tiempo) en la secuencia.

 

2. Decodificación.  ¿Cuál es la secuencia de estado (Q = q1, q2, … qt) más probable en el modelo  Φ = (A, B, π) que produjo las observaciones (O = o1,… , ot) ?, es decir, la explicación más verosímil. No nos rompamos la cabeza, no vamos a encontrar la secuencia «correcta», pero sí una de las mejores rutas a través de ese modelo. Para resolver el problema se utiliza el algoritmo de Viterbi.

 

3. Aprendizaje.  Este es el problema más importante y difícil. ¿Cómo ajustamos los parámetros del modelo Φ = (A, B, π)  para que tengan una alta probabilidad de generar esas secuencias (O = o1,… , ot) , es decir, maximizar P (O | Φ)?. En redes neuronales es aprender de los datos de entrenamiento. Para responder a la pregunta tenemos el algoritmo más conocido, el de Baum-Welch.

 

 

Algoritmos.

Existe un amplio abanico de algoritmos, muchos de ellos relacionados (ver en POMDP), y que dan soporte al modelo y sus problemáticas:

 

  • ACO (Ant Colony Optimization).
  • EM (Expectation-Maximization).
  • GEM (Generalized Expectation Maximization)
  • K-Means.
  • Kullback-Leibler.
  • MCMC (Markov Chain Monte Carlo (MCMC).
  • Métodos de Gradiente.
    • Transición de Probabilidades.
    • Observación de Probabilidades.
  • MAP (Maximum a Posteriori).
  • MLE (Maximum Likelihood Estimate). Criterio de máxima verosimilitud.
  • MMI (Maximum Mutual Information). Criterio de información mutua máxima.
  • SVI (Stochastic Variational Inference).
  • Tabú (TS-Tabu Search).

Los métodos basados en gradientes, también el algoritmo Baum-Welch, generalmente solo producen un óptimo local (ver gradiente descendente) y este sí que es un problema. Una de las soluciones para mejorar esa búsqueda es Tabú, este algoritmo puede retroceder desde un óptimo local y seguir buscando otros que puedan ser óptimos.

 

Modelos derivados de HMM.

A lo largo del tiempo, HMM, se ha ido adaptando a distintas áreas científicas y cada una de ellas lo ha modelado para obtener de él las mejores repuestas. A continuación algunos de ellos:

 

CHMM.

CHMM (Coupled Hidden Markov Model) fue descrito por Matthew Brand, Nuria Oliver y Alex Pentland en 1.996-7. Surge para resolver el inconveniente que tiene HMM respecto del uso de un solo proceso con un pequeño número de estados y una memoria de estado limitada. CHMM utiliza múltiples variables de estado que se acoplan temporalmente a través de matrices de probabilidades condicionales, de tal forma que se pueden modelar aplicaciones multimedia que integran múltiples flujos de datos, haciendo que el modelo sea un grupo de modelos HMM.

 

Alex Pentland. CHMM (Coupled Hidden Markov Model)
Pentland
Nuria Oliver. CHMM (Coupled Hidden Markov Model)
N. Oliver
Matthew-Brand
M. Brand
Coupled Hidden Markov Model (CHMM) 2 cadenas
(CHMM) 2 cadenas

 

 

 

 

 

 

 

 

 

 

Una aplicación práctica ha sido en el entorno financiero, el objetivo es comparar los valores de dos activos al mismo tiempo, estuviesen o no dentro del mismo mercado, por ejemplo:

Comparar la constructora Acciona en la bolsa de Madrid en Europa, respecto de la dinámica del activo CEMEX en la bolsa de México DF en América.

Los resultados empíricos corroboraron que lo idóneo era modelar dos activos en sus extremos: fuertemente relacionados o nada relacionados.

 

FHMM.

El Factorial Hidden Markov Model fue propuesto en 1.997 por Zoubin Ghahramani y Michael I. Jordan. Se usa para representar una combinación de múltiples datos producidos de forma independientemente y representados por cadenas de Markov distintas. No se recomienda utilizar el modelo en entrenamiento de redes neuronales o en sistemas donde el número de cadenas sea grande.

Michael I. Jordan
Jordan
Zoubin Ghahramani
Ghahramani

 

Factorial Hidden Markov Model (FHMM) dos cadenas
(FHMM) dos cadenas

 

 

 

 

 

 

 

 

GCHMM

Graph-Coupled Hidden Markov Models es una extensión de los modelos ocultos acoplados de Markov (CHMM) propuesto en 2.012 por  Katherine A. Heller, Alex Pentland y Wen Dong. Su objetivo es predecir, a nivel individual, cómo se produce la propagación de una infección, evaluar el estado de salud de cada individuo y seguir las vías de transmisión de la enfermedad a través de los integrantes de una red social.

Katherine Heller. GCHMM Graph-Coupled Hidden Markov Models
K. Heller
Alex Pentland. GCHMM Graph-Coupled Hidden Markov Models
Pentland
Wen Dong. GCHMM Graph-Coupled Hidden Markov Models
W. Dong
Graph-Coupled Hidden Markov Models (GCHMM) 3 Cadenas
(GCHMM) 3 Cadenas

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

HSMM.

El modelo Hidden Semi-Markov Model (HSMM) fue propuesto en 1.980 por John D. Ferguson, tiene distintas denominaciones en función de dónde se le utilice, «HMM con duración variable», «HMM con duración explícita», «HMM con segmentación», etc. En el modelo cada estado tiene una duración aleatoria variable y se producen varias observaciones mientras se encuentra en un estado. El número de observaciones producidas, en un estado, está determinado por el tiempo que se pasa en ese estado, es decir, la duración (D) y la duración en un estado (actual) es independiente del estado anterior.

 

Hidden Semi-Markov Model (HSMM) Semioculto
Hidden Semi-Markov Model (HSMM) Semioculto

Desde principios de este siglo ha sido el modelo de «moda» más aplicado en: La fabricación de semiconductores, seguimiento de redes de tefonía móvil, modelado de tráfico de Internet, síntesis de voz, aprendizaje semántico en autómatas móviles, clasificación musical, etc.

 

Debido a que su complejidad computacional es alta, los procesos basados en HSMM no son apropiados para aplicarse cuando D es grande. Para salvar esta problemática se han propuesto distintos tipos de algoritmos, el de Stephen E. Levinson o el de Martin J. Russell.