Introducción[editar]
Uno de los problemas básicos de los Modelos Ocultos de Márkov es el cálculo de la probabilidad de una secuencia de observables
dado un modelo
. El objetivo es por tanto calcular eficientemente
.
Probabilidad de una secuencia
de estados
Supongamos una secuencia de estados
. La probabilidad de esta secuencia es:
Probabilidad de una secuencia de observables
dada una secuencia de estados
La probabilidad de observar
cuando se da precisamente esta secuencia de estados
es:
Cada
corresponde con el valor de
Probabilidad de una secuencia de observables
dado un modelo
Por tanto, para obtener la probabilidad de una secuencia
de observables dado un modelo
, deberíamos calcular la probabilidad de
para cada una de las secuencias posibles
.
El cálculo de
tal y como se muestra es impracticable; sólo para
estados y
observaciones sería necesario realizar del orden de
operaciones. Para reducir esta complejidad se emplean estrategias de programación dinámica como los algoritmos forward y backward.
Se recomienda revisar la formalización habitual de un Modelo Oculto de Márkov para comprender cada uno de los elementos en la formulación de estos dos procedimientos.
Procedimiento hacia adelante[editar]
Cálculo de
[editar]
Consideramos la variable
como:
Dado el modelo
,
es la probabilidad de observar
y estar en el instante de tiempo
en el estado
.
Cálculo hacia adelante de la probabilidad de una secuencia de observaciones.
Inicialización
Recurrencia
,
Terminación
Ejemplo de cálculo de
[editar]
El esquema muestra los estados y probabilidades necesarias para el cálculo de
:
Cálculo hacia atrás[editar]
Cálculo de
[editar]
Consideramos la variable
.
Dado el modelo
,
es la probabilidad de la secuencia de observación desde el instante de tiempo
hasta el final, cuando el estado en el instante de tiempo
es
.
Inicialización
,
Recurrencia
,
,
Terminación
Ejemplo de cálculo de
[editar]
El esquema muestra los estados y probabilidades necesarios para el cálculo de
para un modelo de 5 estados y una secuencia de observaciones de longitud 5.
Complejidad computacional[editar]
Tanto el procedimiento hacia adelante como el algoritmo backward, requieren del orden de
operaciones; muy inferior a
operaciones (
es el número de estados y
es la longitud de la secuencia de observaciones) que son necesarias si se calcula
para todas las posibles secuencias
del modelo.
El cálculo de los
servirán - junto a los
- para contestar las otras dos preguntas fundamentales de los Modelos Ocultos de Márkov:
- ¿Cuál es la secuencia óptima
de estados dado una secuencia de observaciones
? (algoritmo de Viterbi)
- Dada una secuencia de observaciones
, ¿cómo podemos estimar los parámetros del modelo
para maximizar
. En este caso el objetivo es encontrar el modelo que mejor explica la secuencia observada (algoritmo de Baum-Welch).
Véase también[editar]
Referencias[editar]