Algoritmo de avance-retroceso


Algoritmo de avance-retroceso

Contenido

Introducción

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 O=(o_{1},o_{2},\ldots,o_{T}) dado un modelo μ = (π,A,B). El objetivo es por tanto calcular eficientemente P(O | μ).

Probabilidad de una secuencia S de estados

Supongamos una secuencia de estado S = (q_1,q_2, \dots, q_T). La probabildad de esta secuencia es:


P(S|\mu) = \pi_{q_1} a_{q_{1}q_{2}} a_{q_{2}q_{3}} \dots a_{q_{T-1}q_{T}}

Probabilidad de una secuencia de observables O dada una secuencia de estados S

La probabilidad de observar O=(o_1,o_2,\dots,o_T) cuando se da precisamente esta secuencia de estados S es:


P(O|S,\mu) = \displaystyle\prod_{t=1}^{T}{P(o_t|q_t,\mu)}

Cada P(ot | qt,μ) corresponde con el valor de b_{q_t}(o_t)

Probabilidad de una secuencia de observables O dado un modelo μ

Por tanto, para obtener la probabilidad de una secuencia O de observables dado un modelo μ, deberíamos calcular la probabilidad de O para cada una de las secuencias posibles S.


P(O|\mu) = \displaystyle\sum^{S}{P(S|\mu)P(O|S,\mu)}

El cálculo de P(O | μ) tal y como se muestra es impracticable; sólo para 10 estados y 10 observaciones sería necesario realizar del orden de 1011 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

Cálculo de αt(i)

Consideramos la variable αt(i) como:

\alpha_{t}(i)=P(o_{1},o_{2},\ldots,o_{t},q_{t}=i|\mu)

Dado el modelo μ, αt(i) es la probabilidad de observar o_{1},o_{2},\ldots,o_{t} y estar en el instante de tiempo t en el estado i.

Cálculo hacia adelante de la probabilidad de una secuencia de observaciones.

Inicialización

α1(i) = πibi(o1),

1 \leq i \leq N

Recurrencia

\alpha_{t+1}(j)=\biggl[\displaystyle\sum_{i=1}^{N}{\alpha_{t}(i)a_{ij}}\biggr]b_{j}(o_{t+1})

t=1,2,\ldots,T-1, 1 \leq j \leq N

Terminación

P(O|\mu)=\displaystyle\sum_{i=1}^{N}{\alpha_{T}(i)}

Ejemplo de cálculo de α4(3)

El esquema muestra los estados y probabilidades necesarias para el cálculo de α4(3):

Algoritmo forward


\alpha_{4}(3)=\biggl[\displaystyle\sum_{i=1}^{5}{\alpha_{3}(i)a_{i3}}\biggr]b_{3}(o_{4})

Cálculo hacia atrás

Cálculo de βt(i)

Consideramos la variable βt(i).

\beta_{t}(i)=P(o_{t+1}o_{t+2},\ldots,o_{T}|q_{t}=i,\mu)

Dado el modelo μ, βt(i) es la probabilidad de la secuencia de observación desde el instante de tiempo t + 1 hasta el final, cuando el estado en el instante de tiempo t es i.

Inicialización

βT(i) = 1,

1 \leq i \leq N

Recurrencia

\beta_{t}(i)=\displaystyle\sum_{j=1}^{N}{a_{ij}\beta_{t+1}(j)b_{j}(o_{t+1})},

t=T-1,T-2,\ldots,1, 1 \leq i \leq N

Terminación

P(O|\mu)=\displaystyle\sum_{i=1}^{N}{\beta_{1}(i)\pi_{i}b_{i}(o_{1})}

Ejemplo de cálculo de β2(3)

El esquema muestra los estados y probabilidades necesarios para el cálculo de β2(3) para un modelo de 5 estados y una secuencia de observaciones de longitud 5.

Algoritmo backward


\beta_{2}(3)=\displaystyle\sum_{j=1}^{5}{a_{3j}\beta_{3}(j)b_{j}(o_{3})},

Complejidad computacional

Tanto el procedimiento hacia adelante como el algoritmo backward, requieren del orden de N2T operaciones; muy inferior a 2TNT − 1 operaciones (N es el número de estados y T es la longitud de la secuencia de observaciones) que son necesarias si se calcula P(O,S | μ) para todas las posibles secuencias S del modelo.

El cálculo de los βt(i) servirán - junto a los αt(i) - para contestar las otras dos preguntas fundamentales de los Modelos Ocultos de Márkov:

  • ¿Cuál es la secuencia óptima S de estados dado una secuencia de observaciones O? (algoritmo de Viterbi)
  • Dada una secuencia de observaciones O=(o_{1},o_{2},\ldots,o_{T}), ¿cómo podemos estimar los parámetros del modelo μ = (π,A,B) para maximizar P(O | μ). En este caso el objetivo es encontrar el modelo que mejor explica la secuencia observada (algoritmo de Baum-Welch).

Véase también


Wikimedia foundation. 2010.

Mira otros diccionarios:

  • 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 Baum-Welch — Contenido 1 Introducción 2 El algoritmo de Baum y Welch 2.1 Valores esperados 2.2 Reestimación …   Wikipedia Español

  • Algoritmo de Levinson — El algoritmo de Levinson o de Levinson Durbin es un algoritmo del álgebra lineal para calcular en forma recursiva la solución de una ecuación que involucra una matriz de Toeplitz. El costo computacional es de Θ(n2), una mejora considerable frente …   Wikipedia Español

  • 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… …   Wikipedia Español

  • Gramática libre de contexto probabilística — Una gramática libre de contexto probabilística (GLCP) es una gramática libre de contexto en la cual cada regla tiene asignada una probabilidad. La probabilidad de un análisis sintáctico es el producto de las probabilidades de cada una de las… …   Wikipedia Español

  • Recursión de Levinson — Saltar a navegación, búsqueda La recursión de Levinson o de Levinson Durbin es un algoritmo del álgebra lineal para calcular en forma recursiva la solución de una ecuación que involucra una matriz de Toeplitz. El costo computacional es de Θ(n2),… …   Wikipedia Español

  • C Sharp — Saltar a navegación, búsqueda El título de este artículo se muestra incorrectamente debido a limitaciones técnicas. El título correcto es C#. C Sharp Paradigma: Orientado a objetos Apareció en: 2001 Diseñado por: Microsoft Corporation Última… …   Wikipedia Español

  • Tecnologías de la información y la comunicación — «TIC» redirige aquí. Para el término médico, véase Tic. Torre de telecomunicaciones de Collserola, (Barcelona). Las tecnologías de la información y la comunicación (TIC o bien NTIC para Nuevas Tecnologías de la Información y de la Comunicación o… …   Wikipedia Español

  • Módem — Para otros usos de este término, véase Modem (desambiguación). Un módem (Modulador Demodulador) es un dispositivo que sirve para enviar una señal llamada moduladora mediante otra señal llamada portadora. Se han usado módems desde los años 60,… …   Wikipedia Español