BIOINFORMÁTICA

Algoritmo de avance-retroceso

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 ${\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 probabilidad 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[editar]

Cálculo de ${\displaystyle \alpha _{t}(i)}$[editar]

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)}$[editar]

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[editar]

Cálculo de ${\displaystyle \beta _{t}(i)}$[editar]

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)}$[editar]

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[editar]

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).

MODELOS OCULTOS DE MARKOV

Consideraciones Importantes: 

Se cumple la probabilidad de Markov:

• Si la probabilidad de cada estado depende únicamente del estado anterior (propiedad de Markov)
  
• Axioma de probabilidad:
  
  Usos de los Modelos Ocultos de Markov:
  Existen tres problemas canónicos asociados con HMM:
  Dados los parámetros del modelo, compútese la probabilidad de una secuencia de salida en particular. Este problema se resuelve con el algoritmo de avance-retroceso.
  Dados los parámetros del modelo, encuéntrese la secuencia más probable de estados ocultos que puedan haber generado una secuencia de salida dada. Este problema se resuelve con el algoritmo de Viterbi.
  Dada una secuencia de salida o un conjunto de tales secuencias, encuéntrese el conjunto de estados de transición y probabilidades de salida más probables. En otras palabras, entrénense a los parámetros del HMM dada una secuencia de datos. Este problema se resuelve con el algoritmo de Baum-Welch.
  Algoritmo de Forward – Backward:
  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 la Probabilidad de una secuencia de estados. Se divide en 2 pasos:

  • Forward: Se busca cada αt de forma iterativa
  • Backward: Se busca cada βt de forma iterativa
    La probabilidad de la secuencia es proporcional a αt βt

  Algoritmo de Viterbi:

  El algoritmo de Viterbi es un algoritmo de programación dinámica que permite hallar la secuencia mas probable de estados ocultos que produce una secuencia observada de sucesos, especialmente en el contexto de fuentes de información de Markov y Modelos ocultos de Markov.

  Algoritmo de Baum – Welch:

  Uno de los problemas relacionados con los Modelos Ocultos de Márkov (MOM) es el de encontrar un modelo que maximice la probabilidad de una secuencia, 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.cia de observaciones.

  Caso de uso: Viterbi