Home
Enciclopedia
Algoritmo_de_avance-retroceso

Algoritmo de avance-retroceso

Conocimientos adicionales recomendados

Procedimientos normalizados de trabajo (PNT) para la comprobación de balanzas

8 pasos para limpiar una balanza y 5 soluciones para mantenerla limpia

Guía de técnicas básicas de medición en el laboratorio

Tabla de contenidos

1 Introducción
2 Procedimiento hacia adelante
- 2.1 Cálculo de αt(i)
- 2.2 Ejemplo de cálculo de α4(3)
3 Cálculo hacia atrás
- 3.1 Cálculo de βt(i)
- 3.2 Ejemplo de cálculo de β2(3)
4 Complejidad computacional
5 Véase también

Introducción

Uno de los problemas básicos de los Modelos Ocultos de Markov 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 observación $O$ dada una secuencia de estado $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 (o t | q t,μ)$ corresponde con el valor de $b_{q_t}(o_t)$

Probabilidad de una observación $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 Markov 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 hasta 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) = π i b i (o 1),$

$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)$ :

$\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.

$\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 $N 2 T$ operaciones; muy inferior a $2 T N T - 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 Markov:

¿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

Categoría: Bioinformática

Este articulo se basa en el articulo Algoritmo_de_avance-retroceso publicado en la enciclopedia libre de Wikipedia. El contenido está disponible bajo los términos de la Licencia de GNU Free Documentation License. Véase también en Wikipedia para obtener una lista de autores.

Algoritmo de avance-retroceso

Conocimientos adicionales recomendados

Procedimientos normalizados de trabajo (PNT) para la comprobación de balanzas

8 pasos para limpiar una balanza y 5 soluciones para mantenerla limpia

Guía de técnicas básicas de medición en el laboratorio

Tabla de contenidos

Introducción

Procedimiento hacia adelante

Cálculo de $α t (i)$

Ejemplo de cálculo de $α 4 (3)$

Cálculo hacia atrás

Cálculo de $β t (i)$

Ejemplo de cálculo de $β 2 (3)$

Complejidad computacional

Véase también

Acerca de quimica.es

Acerca de LUMITOS

Anunciarse en LUMITOS

Algoritmo de avance-retroceso

Conocimientos adicionales recomendados

Procedimientos normalizados de trabajo (PNT) para la comprobación de balanzas

8 pasos para limpiar una balanza y 5 soluciones para mantenerla limpia

Guía de técnicas básicas de medición en el laboratorio

Tabla de contenidos

Introducción

Procedimiento hacia adelante

Cálculo de αt(i)

Ejemplo de cálculo de α4(3)

Cálculo hacia atrás

Cálculo de βt(i)

Ejemplo de cálculo de β2(3)

Complejidad computacional

Véase también

Acerca de quimica.es

Acerca de LUMITOS

Anunciarse en LUMITOS

Cálculo de $α t (i)$

Ejemplo de cálculo de $α 4 (3)$

Cálculo de $β t (i)$

Ejemplo de cálculo de $β 2 (3)$