Modelo oculto de Márkov

Modelo oculto de Márkov
Ejemplo de transición de estados en un modelo oculto de Márkov
x — estados ocultos
y — salidas observables
a — probabilidades de transición
b — probabilidades de salida

Un modelo oculto de Márkov o HMM (por sus siglas del inglés, Hidden Markov Model) es un modelo estadístico en el que se asume que el sistema a modelar es un proceso de Márkov de parámetros desconocidos. El objetivo es determinar los parámetros desconocidos (u ocultos, de ahí el nombre) de dicha cadena a partir de los parámetros observables. Los parámetros extraídos se pueden emplear para llevar a cabo sucesivos análisis, por ejemplo en aplicaciones de reconocimiento de patrones. Un HMM se puede considerar como la red bayesiana dinámica más simple.

En un modelo de Márkov normal, el estado es visible directamente para el observador, por lo que las probabilidades de transición entre estados son los únicos parámetros. En un modelo oculto de Márkov, el estado no es visible directamente, sino que sólo lo son las variables influidas por el estado. Cada estado tiene una distribución de probabilidad sobre los posibles símbolos de salida. Consecuentemente, la secuencia de símbolos generada por un HMM proporciona cierta información acerca de la secuencia de estados.

Los modelos ocultos de Márkov son especialmente aplicados a reconocimiento de formas temporales, como reconocimiento del habla, de escritura manual, de gestos, etiquetado gramatical o en bioinformática. En el reconocimiento de voz se emplea para modelar una frase completa, una palabra, un fonema o trifonema en el modelo acústico. Por ejemplo la palabra "gato" puede estar formada por dos HMM(Hidden Markov Model) para los dos trifonemas que la componen /gat/ y /ato/

Contenido

Historia

Los modelos ocultos de Márkov fueron descritos por primera vez en una serie de artículos estadísticos por Leonard E. Baum y otros autores en la segunda mitad de la década de 1960. Una de las primeras aplicaciones de HMMs fue reconocimiento del habla, comenzando en la mitad de la década de 1970.[1]

En la segunda mitad de la década de 1980, los HMMs comenzaron a ser aplicados al análisis de secuencias biológicas, en particular de DNA. Desde entonces, se han hecho ubicuos en el campo de la bioinformática.[2]

Arquitectura de un modelo oculto de Márkov

El diagrama que se encuentra más abajo muestra la arquitectura general de un HMM. Cada óvalo representa una variable aleatoria que puede tomar determinados valores. La variable aleatoria x(t) es el valor de la variable oculta en el instante de tiempo t. La variable aleatoria y(t) es el valor de la variable observada en el mismo instante de tiempo t. Las flechas indican dependencias condicionales.

Del diagrama queda claro que el valor de la variable oculta x(t) (en el instante t) solo depende del valor de la variable oculta x(t − 1) (en el instante t − 1). A esto se le llama propiedad de Márkov. De forma similar, el valor de la variable observada y(t) solo depende del valor de la variable oculta x(t) (ambas en el instante t).

Evolución en el tiempo de un modelo oculta de Márkov

Probabilidad de una secuencia observada

La probabilidad de observar la secuencia Y=y(0), y(1),\dots,y(L-1) de longitud L está dada por

P(Y)=\sum_{X}P(Y\mid X)P(X),

donde la sumatoria se extiende sobre todas las secuencias de nodos ocultos X=x(0), x(1), \dots, x(L-1).\, El cálculo por fuerza bruta de P(Y) es impráctico para la mayoría de los problemas reales, dado que el número de secuencias de nodos ocultos será extremadamente alto en tal caso. Sin embargo, el cálculo puede acelerarse notoriamente usando un algoritmo conocido como el procedimiento de avance-retroceso.[3]

Definición formal de un Modelo Oculto de Márkov

Una notación habitual de un MOM es la representación como una tupla (Q,V,π,A,B):

  • El conjunto de estados Q = \{1,2,\dots,N\}. El estado inicial se denota como qt. En el caso de la etiquetación categorial, cada valor de t hace referencia a la posición de la palabra en la oración.
  • El conjunto V de posibles valores \{v_1,v_2,\dots,v_M\} observables en cada estado. M es el número de palabras posibles y cada vk hace referencia a una palabra diferente.
  • Las probabilidades iniciales π = {πi}, donde πi es la probabilidad de que el primer estado sea el estado Qi.
  • El conjunto de probabilidades A = {aij} de transiciones entre estados.
    • aij = P(qt = j | qt − 1 = i), es decir, aij es la probabilidad de estar en el estado j en el instante t si en el instante anterior t − 1 se estaba en el estado i.
  • El conjunto de probabilidades B = {bj(vk)} de las observaciones.
    • bj(vk) = P(ot = vk | qt = j), es decir, la probabilidad de observar vk cuando se está en el estado j en el instante t.

La secuencia de observables se denota como un conjunto O=(o_1,o_2,\dots,o_T).

Uso de modelos ocultos de Márkov

Existen tres problemas canónicos asociados con HMMs:

  • Dados los parámetros del modelo, compútese la probabilidad de una secuencia de salida en particular. Este problema se resuelve con el algoritmo de avance-retroceso.
  • Dados los parámetros del modelo, encuéntrese la secuencia más probable de estados ocultos que puedan haber generado una secuencia de salida dada. Este problema se resuelve con el algoritmo de Viterbi.
  • Dada una secuencia de salida o un conjunto de tales secuencias, encuéntrese el conjunto de estados de transición y probabilidades de salida más probables. En otras palabras, entrénense a los parámetros del HMM dada una secuencia de datos. Este problema se resuelve con el algoritmo de Baum-Welch.

Ejemplo de utilización

Imagínese que tiene un amigo que vive lejos y con quien habla a diario por teléfono acerca de lo que hizo durante el día. A su amigo le interesan tres actividades: caminar por la plaza, salir de compras y limpiar su departamento. Lo que su amigo hace depende exclusivamente del estado del tiempo en ese día. Usted no tiene información clara acerca del estado del tiempo donde su amigo vive, pero conoce tendencias generales. Basándose en lo que su amigo le dice que hizo en el día, usted intenta adivinar el estado del tiempo.

Supóngase que el estado del tiempo se comporta como una cadena de Márkov discreta. Existen dos estados, "Lluvioso" y "Soleado", pero usted no los puede observar directamente, es decir, están ocultos. Existe también una cierta posibilidad de que su amigo haga una de sus actividades cada día, dependiendo del estado del tiempo: "caminar", "comprar" o "limpiar". Dado que su amigo le cuenta sus actividades del día, esas son las observaciones. El sistema completo es un modelo oculto de Márkov.

Usted conoce las tendencias generales del tiempo en el área y lo que a su amigo le gusta hacer. En otras palabras, los parámetros del HMM son conocidos. Pueden escribirse usando el lenguaje de programación Python:

estados = ('Lluvioso', 'Soleado')
 
observaciones = ('caminar', 'comprar', 'limpiar')
 
probabilidad_inicial = {'Lluvioso': 0.6, 'Soleado': 0.4}
 
probabilidad_transicion = {
   'Lluvioso' : {'Lluvioso': 0.7, 'Soleado': 0.3},
   'Soleado'  : {'Lluvioso': 0.4, 'Soleado': 0.6},
   }
 
probabilidad_emision = {
   'Lluvioso' : {'caminar': 0.1, 'comprar': 0.4, 'limpiar': 0.5},
   'Soleado'  : {'caminar': 0.6, 'comprar': 0.3, 'limpiar': 0.1},
   }

En esta porción de código se tiene:

La probabilidad_inicial que representa el estado en el que usted cree que se encuentra el HMM la primera vez que su amigo lo llama (es decir, sabe que es un poco más probable que esté lluvioso). La distribución de probabilidades que se usó aquí no es la de equilibrio, que es (dadas las probabilidades de transición) aproximadamente {'Lluvioso': 0.571, 'Soleado': 0.429}.

La probabilidad_transicion representa el cambio del tiempo en la cadena de Márkov por detrás del modelo. En este ejemplo, hay un 30% de probabilidad de que mañana esté soleado si hoy llovió.

La probabilidad_emision representa con cuanta probabilidad su amigo realiza una actividad determinada cada día. Si llueve, hay un 50% de probabilidad de que esté limpiando su departamento; si hay sol, hay un 60% de probabilidades de que haya salido a caminar.

Aplicaciones de modelos ocultos de Márkov

Notas

  1. Rabiner, p. 258
  2. Durbin et al.
  3. Rabiner, p. 262
  4. Pardo et al.

Véase también

Enlaces externos


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать курсовую

Mira otros diccionarios:

  • Andréi Márkov — Andréi Márkov. Andréi Andréyevich Márkov (Андрей Андреевич Марков) (14 de junio de 1856 20 de julio de 1922) fue un matemático ruso conocido por sus trabajos en la teoría de los números y la teoría de probabilidades. Márkov nació en Riazán, Rusia …   Wikipedia Español

  • Anexo:Episodios de Numb3rs — La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada (2005 2006) …   Wikipedia Español

  • Algoritmo de Viterbi — Contenido 1 Introducción 2 Algoritmo 2.1 Inicialización 2.2 Recursión 2.3 Terminación …   Wikipedia Español

  • Algoritmo de avance-retroceso — Contenido 1 Introducción 2 Procedimiento hacia adelante 2.1 Cálculo de αt(i) 2.2 Ejemplo de cálculo de α4(3) …   Wikipedia Español

  • Algoritmo de Baum-Welch — Contenido 1 Introducción 2 El algoritmo de Baum y Welch 2.1 Valores esperados 2.2 Reestimación …   Wikipedia Español

  • N-grama — Un n grama es una subsecuencia de n elementos de una secuencia dada. Los n gramas se emplean en varias áreas del procesamiento estadístico del lenguaje natural, así como en algunos métodos de predicción o descubrimiento de genes. Un n grama de… …   Wikipedia Español

  • Episodios de Numb3rs — Anexo:Episodios de Numb3rs Saltar a navegación, búsqueda La siguiente es una lista de episodios de la serie norteamericana NUMB3RS. Contenido 1 Estrenos y Lanzamientos en DVD 2 Primera temporada (2005) 3 Segunda temporada ( …   Wikipedia Español

  • Alineamiento múltiple de secuencias — Un alineamiento múltiple de secuencias (MSA, por sus siglas en inglés) es un alineamiento de tres o más secuencias biológicas, generalmente proteínas, ADN o ARN. En general, se asume que el conjunto de secuencias de consulta que se ingresa como… …   Wikipedia Español

  • Hopfield (RNA) — Una red de Hopfield es una forma de red neuronal artificial recurrente inventada por John Hopfield. Las redes de Hopfield se usan como sistemas de Memoria asociativa con unidades binarias. Están diseñadas para converger a un mínimo local, pero la …   Wikipedia Español

  • Bioinformática — Saltar a navegación, búsqueda La bioinformática, según una de sus definiciones más sencillas, es la aplicación de tecnología de computadores a la gestión y análisis de datos biológicos.[1] Los términos bioinformática, biología computacional y, en …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”