Algoritmo de avance-retroceso

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 α₄(3)

3 Cálculo hacia atrás

3.1 Cálculo de β_t(i)

3.2 Ejemplo de cálculo de β₂(3)

4 Complejidad computacional

5 Véase también

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 (o t | q t,μ)$ 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) = π 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 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

Modelos Ocultos de Márkov

Algoritmo de Viterbi

Algoritmo de Baum-Welch

Categorías:
Algoritmos
Bioinformática

Игры ⚽ Поможем сделать НИР

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

Los diccionarios y las enciclopedias sobre el Académico

Algoritmo de avance-retroceso

Contenido

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

Mira otros diccionarios:

Compartir el artículo y extractos

Los diccionarios y las enciclopedias sobre el Académico

Wikipedia Español

Algoritmo de avance-retroceso

Contenido

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

Mira otros diccionarios:

Compartir el artículo y extractos

Link directo

Cálculo de $α t (i)$

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

Cálculo de $β t (i)$

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