Bioinformática

Algoritmo de avance-retroceso

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

Probabilidad de una secuencia ${\displaystyle S}$ de estados

Supongamos una secuencia de estados ${\displaystyle S=(q_{1},q_{2},\dots ,q_{T})}$. La probabildad de esta secuencia es:

${\displaystyle 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 ${\displaystyle O}$ dada una secuencia de estados ${\displaystyle S}$

La probabilidad de observar ${\displaystyle O=(o_{1},o_{2},\dots ,o_{T})}$ cuando se da precisamente esta secuencia de estados ${\displaystyle S}$ es:

${\displaystyle P(O|S,\mu )=\displaystyle \prod _{t=1}^{T}{P(o_{t}|q_{t},\mu )}}$

Cada ${\displaystyle P(o_{t}|q_{t},\mu )}$ corresponde con el valor de ${\displaystyle b_{q_{t}}(o_{t})}$

Probabilidad de una secuencia de observables ${\displaystyle O}$ dado un modelo ${\displaystyle \mu }$

Por tanto, para obtener la probabilidad de una secuencia ${\displaystyle O}$ de observables dado un modelo ${\displaystyle \mu }$, deberíamos calcular la probabilidad de ${\displaystyle O}$ para cada una de las secuencias posibles ${\displaystyle S}$.

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

El cálculo de ${\displaystyle P(O|\mu )}$ tal y como se muestra es impracticable; sólo para ${\displaystyle 10}$ estados y ${\displaystyle 10}$ observaciones sería necesario realizar del orden de ${\displaystyle 10^{11}}$ 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 ${\displaystyle \alpha _{t}(i)}$

Consideramos la variable ${\displaystyle \alpha _{t}(i)}$ como:

${\displaystyle \alpha _{t}(i)=P(o_{1},o_{2},\ldots ,o_{t},q_{t}=i|\mu )}$

Dado el modelo ${\displaystyle \mu }$, ${\displaystyle \alpha _{t}(i)}$ es la probabilidad de observar ${\displaystyle o_{1},o_{2},\ldots ,o_{t}}$ y estar en el instante de tiempo ${\displaystyle t}$ en el estado ${\displaystyle i}$.

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

Inicialización

${\displaystyle \alpha _{1}(i)=\pi _{i}b_{i}(o_{1}),}$

${\displaystyle 1\leq i\leq N}$

Recurrencia

${\displaystyle \alpha _{t+1}(j)={\biggl [}\displaystyle \sum _{i=1}^{N}{\alpha _{t}(i)a_{ij}}{\biggr ]}b_{j}(o_{t+1})}$

${\displaystyle t=1,2,\ldots ,T-1}$, ${\displaystyle 1\leq j\leq N}$

Terminación

${\displaystyle P(O|\mu )=\displaystyle \sum _{i=1}^{N}{\alpha _{T}(i)}}$

Ejemplo de cálculo de ${\displaystyle \alpha _{4}(3)}$

El esquema muestra los estados y probabilidades necesarias para el cálculo de ${\displaystyle \alpha _{4}(3)}$:

${\displaystyle \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 ${\displaystyle \beta _{t}(i)}$

Consideramos la variable ${\displaystyle \beta _{t}(i)}$.

${\displaystyle \beta _{t}(i)=P(o_{t+1}o_{t+2},\ldots ,o_{T}|q_{t}=i,\mu )}$

Dado el modelo ${\displaystyle \mu }$, ${\displaystyle \beta _{t}(i)}$ es la probabilidad de la secuencia de observación desde el instante de tiempo ${\displaystyle t+1}$ hasta el final, cuando el estado en el instante de tiempo ${\displaystyle t}$ es${\displaystyle i}$.

Inicialización

${\displaystyle \beta _{T}(i)=1}$,

${\displaystyle 1\leq i\leq N}$

Recurrencia

${\displaystyle \beta _{t}(i)=\displaystyle \sum _{j=1}^{N}{a_{ij}\beta _{t+1}(j)b_{j}(o_{t+1})}}$,

${\displaystyle t=T-1,T-2,\ldots ,1}$, ${\displaystyle 1\leq i\leq N}$

Terminación

${\displaystyle P(O|\mu )=\displaystyle \sum _{i=1}^{N}{\beta _{1}(i)\pi _{i}b_{i}(o_{1})}}$

Ejemplo de cálculo de ${\displaystyle \beta _{2}(3)}$

El esquema muestra los estados y probabilidades necesarios para el cálculo de ${\displaystyle \beta _{2}(3)}$ para un modelo de 5 estados y una secuencia de observaciones de longitud 5.

${\displaystyle \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 ${\displaystyle N^{2}T}$ operaciones; muy inferior a ${\displaystyle 2TN^{T}-1}$ operaciones (${\displaystyle N}$ es el número de estados y ${\displaystyle T}$ es la longitud de la secuencia de observaciones) que son necesarias si se calcula ${\displaystyle P(O,S|\mu )}$ para todas las posibles secuencias ${\displaystyle S}$ del modelo.

El cálculo de los ${\displaystyle \beta _{t}(i)}$ servirán - junto a los ${\displaystyle \alpha _{t}(i)}$ - para contestar las otras dos preguntas fundamentales de los Modelos Ocultos de Márkov:

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

Algoritmo de Baum-Welch

Introducción

Uno de los problemas relacionados con los Modelos Ocultos de Márkov (MOM) es el de encontrar un modelo ${\displaystyle \mu }$ que maximice la probabilidad de una secuencia de observaciones ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$, es decir, determinar el modelo que mejor explica tal secuencia. El problema es que no es posible encontrar tal modelo analíticamente y por ello es necesario un algoritmo iterativo como el de Baum y Welch, que permite estimar los parámetros de un modelo que hacen máxima la probabilidad de una secuencia de observables.

El algoritmo de Baum y Welch

Dada una secuencia de observaciones ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$, el algoritmo de Baum y Welch permite estimar los parámetros ${\displaystyle \mu }$ de un Modelo oculto de Márkov (MOM) que maximizan la probabilidad de dicha secuencia, es decir, ${\displaystyle P(O|\mu )}$.

Valores esperados

Antes de describir el proceso de estimación, necesitamos conocer:

• el número esperado de transiciones desde el estado ${\displaystyle i}$ en ${\displaystyle O}$ y
• el número esperado de transiciones desde el estado ${\displaystyle i}$ al estado ${\displaystyle j}$ en ${\displaystyle O}$

Para ello definimos previamente ${\displaystyle \xi _{t}{(i,j)}}$ como la probabilidad de estar en el estado ${\displaystyle i}$ en el instante ${\displaystyle t}$ y en el estado ${\displaystyle j}$ en el instante ${\displaystyle t+1}$, dado una observación ${\displaystyle O}$ y el modelo ${\displaystyle \mu }$.

${\displaystyle \xi _{t}{(i,j)}=P(q_{t}=i,q_{t+1}=j|O,\mu )}$

${\displaystyle \xi _{t}{(i,j)}={\frac {P(q_{t}=i,q_{t+1}=j,O|\mu )}{P(O|\mu )}}={\frac {\alpha _{t}{(i)}a_{ij}b_{j}(o_{t+1})\beta _{t+1}(j)}{P(O|\mu )}}}$

${\displaystyle \xi _{t}{(i,j)}={\frac {\alpha _{t}{(i)}a_{ij}b_{j}(o_{t+1})\beta _{t+1}(j)}{\displaystyle \sum _{k=1}^{N}\displaystyle \sum _{l=1}^{N}{\alpha _{t}(k)a_{kl}b_{l}(o_{t+1})\beta _{t+1}(l)}}}}$

donde los valores ${\displaystyle \alpha _{t}(i)}$ y ${\displaystyle \beta _{t}(i)}$ se pueden calcular eficientemente con el algoritmo de avance-retroceso.

${\displaystyle \alpha _{t}(i)=P(o_{1},o_{2},\ldots ,o_{t},q_{t}=i|\mu )}$

${\displaystyle \beta _{t}(i)=P(o_{t+1},o_{t+2},\ldots ,o_{T}|q_{t}=i,\mu )}$

La figura muestra un esquema parcial de los elementos necesarios para el cálculo de ${\displaystyle \xi (i,j)}$.

Definimos también ${\displaystyle \gamma _{t}(i)}$ como la probabilidad de estar en el estado ${\displaystyle i}$ en el instante ${\displaystyle t}$,

${\displaystyle \gamma _{t}(i)=\displaystyle \sum _{j=1}^{N}{\xi _{t}(i,j)}}$

Sumando cada ${\displaystyle \gamma _{t}(i)}$ en cada instante de tiempo, obtenemos:

• el número esperado de transiciones desde el estado ${\displaystyle i}$ en la observación ${\displaystyle O}$

${\displaystyle \displaystyle \sum _{t=1}^{T-1}{\gamma _{t}(i)}}$

y haciendo lo mismo con cada ${\displaystyle \xi _{t}(i,j)}$, obtenemos:

• el número esperado de transiciones desde el estado ${\displaystyle i}$ al estado ${\displaystyle j}$ en la observación ${\displaystyle O}$

${\displaystyle \displaystyle \sum _{t=1}^{T-1}{\xi _{t}(i,j)}}$

Reestimación

El funcionamiento del procedimiento iterativo es básicamente el siguiente:

1. Se parte de un modelo inicial que se puede seleccionar aleatoriamente.
2. Se realiza el cálculo de las transiciones y símbolos de emisión que son más probables según el modelo inicial escogido.
3. Se construye un nuevo modelo en el que se incrementa la probabilidad de las transiciones y símbolos determinados en el paso anterior. Para la secuencia de observables en cuestión, el modelo tendrá ahora una probabilidad mayor que el modelo anterior.

Este proceso de entrenamiento se repite varias veces hasta que no exista mejora entre un modelo y el siguiente revisado.

Probabilidad de estar en el estado ${\displaystyle i}$ en el instante de tiempo ${\displaystyle t=1}$:

${\displaystyle {\bar {\pi }}_{i}=\gamma _{1}(i)}$

${\displaystyle 1\leq i\leq N}$

Reestimación de las probabilidades de transición. El numerador representa el número esperado de transiciones de ${\displaystyle i}$ a ${\displaystyle j}$, y el denominador representa el número esperado de transiciones desde ${\displaystyle i}$:

${\displaystyle {\bar {a}}_{ij}={\frac {\displaystyle \sum _{t=1}^{T-1}{\xi _{t}(i,j)}}{\displaystyle \sum _{t=1}^{T-1}{\gamma _{t}(i)}}}}$

${\displaystyle 1\leq i\leq N}$, ${\displaystyle 1\leq j\leq N}$

Reestimación de las probabilidades de emisión. El numerador representa el número esperado de veces que se pasa por el estado ${\displaystyle j}$ y se observa ${\displaystyle o_{k}}$, y el denominador representa el número esperado de veces que se pasa por el estado ${\displaystyle j}$:

${\displaystyle {\bar {b}}_{j}(o_{k})={\frac {\displaystyle \sum _{t=1:o_{t}=o_{k}}^{T}{\gamma _{t}(j)}}{\displaystyle \sum _{t=1}^{T}{\gamma _{t}(j)}}}}$

${\displaystyle 1\leq j\leq N}$, ${\displaystyle 1\leq k\leq N}$

Otras preguntas fundamentales

Otros dos problemas que es importante saber resolver para utilizar los MOM son:

1. ¿Cuál es la secuencia óptima ${\displaystyle S}$ de estados, dada una secuencia de observaciones ${\displaystyle O}$? (algoritmo de Viterbi)
2. ¿Cuál es la probabilidad de una secuencia de observaciones ${\displaystyle O=(o_{1},o_{2},\ldots ,o_{T})}$ dado un modelo ${\displaystyle \mu =(\pi ,A,B)}$? Es decir, ¿cómo podemos calcular de forma eficiente ${\displaystyle P(O|\mu )}$? (cálculo hacia adelante y hacia atrás).

El algoritmo de Baum-Welch y el Modelo oculto de Markov

Leonard Baum y Welch Lloyd diseñaron un algoritmo de modelado probabilístico para detectar patrones en elmodelo oculto de Markov. Se basan en la teoría de funciones de probabilidad de una Cadena de Markov y elalgoritmo esperanza-maximización (algortimo EM) – un método iterativo para encontrar la máxima verosimilitud de los parámetros en los modelos estadísticos, en los que el modelo depende de variables latentes no observables.

Fuente Data Science Central

El algoritmo de Baum-Welch demostró inicialmente ser una herramienta de notable reconocimiento a la hora de descifrar códigos y el lenguaje, pero también tiene aplicaciones para negocios, finanzas, ciencias y otros. El algoritmo encuentra parámetros desconocidos de un modelo oculto de Markov.

El algoritmo consta de dos fases:

1 . Calcular las probabilidades a posteriori para un determinado modelo , y
2 . volver a estimar los parámetros del modelo .

El modelo de un proceso de Markov es una secuencia de eventos que no tienen una relación directa. Un modelo oculto de Markov es un modelo probabilístico de una colección de variables aleatorias y el cual proporciona un marco sencillo y eficaz para el modelado de las secuencias del vector espectral para variables del tiempo .

El algoritmo de Baum- Welch y el modelo oculto de Markov se utilizan con éxito para los sistemas de comercio financiero, predicción de las tendencias del mercado, la detección de fraudes, optimización de cadenas, previsión de la oferta y la demanda, predicción de series de tiempo financieras y la detección de anomalías en la actividad de tráfico de red.

Con suficientes datos y potencia de computación, los modelos de algoritmo de Baum- Welch y el modelo oculto de Markov pueden calcular las probabilidades de que un  proceso ocurra y predecir eventos futuros.