Algoritmo de Baum-Welch

En ingeniería eléctrica, informática estadística y bioinformática, el algoritmo de Baum-Welch es un caso especial del algoritmo de expectativa-maximización utilizado para encontrar los parámetros desconocidos de un modelo oculto de Markov (HMM). Utiliza el algoritmo de avance-retroceso para calcular las estadísticas del paso de expectativa.

Historia

El algoritmo Baum-Welch lleva el nombre de sus inventores Leonard E. Baum y Lloyd R. Welch. El algoritmo y los modelos ocultos de Markov se describieron por primera vez en una serie de artículos de Baum y sus colegas en el Centro IDA para la Investigación de las Comunicaciones de Princeton a finales de los años sesenta y principios de los setenta. Una de las primeras aplicaciones importantes de los HMM fue en el campo del procesamiento del habla. En la década de 1980, los HMM emergieron como una herramienta útil en el análisis de información y sistemas biológicos, y en particular de información genética. Desde entonces se han convertido en una herramienta importante en el modelado probabilístico de secuencias genómicas.

Descripción

Un modelo de Markov oculto describe la probabilidad conjunta de una colección de datos "ocultos" y variables aleatorias discretas observadas. Se basa en el supuesto de que la i-ésima variable oculta dada la (i − 1)-ésima variable oculta es independiente de las variables ocultas anteriores, y las variables de observación actuales dependen sólo en el estado oculto actual.

El algoritmo de Baum-Welch utiliza el conocido algoritmo EM para encontrar la estimación de máxima verosimilitud de los parámetros de un modelo oculto de Markov dado un conjunto de vectores de características observados.

Vamos. ${displaystyle X_{t}$ ser una variable discreta oculta al azar con ${displaystyle N}$ valores posibles (es decir, suponemos que hay ${displaystyle N}$ estados en total). Asumimos el ${displaystyle P(X_{t}mid X_{t-1}$ es independiente del tiempo ${displaystyle t}$, que conduce a la definición de la matriz de transición estocástica independiente del tiempo

${displaystyle A={a_{ij}=P(X_{t}=jmid X_{t-1}=i).}$

La distribución inicial del estado (es decir, cuando ${displaystyle t=1}$) es dado por

${displaystyle pi _{i}=P(X_{1}=i).$

Las variables de observación ${displaystyle Y...$ puede tomar uno ${displaystyle K}$ valores posibles. También suponemos que la observación dada el estado "hidden" es tiempo independiente. La probabilidad de cierta observación ${displaystyle Y...$ a la vez ${displaystyle t}$ para el estado ${displaystyle X.$ es dado por

${displaystyle ¿Qué? X_{t}=j).}$

Teniendo en cuenta todos los valores posibles ${displaystyle Y...$ y ${displaystyle X_{t}$, obtenemos el ${displaystyle Ntimes K}$ matriz ${displaystyle B={b_{j}$ Donde ${displaystyle B_{j}$ pertenece a todos los estados posibles y ${displaystyle Y...$ pertenece a todas las observaciones.

Una secuencia de observación es dada por ${displaystyle Y=(Y_{1}=y_{1},Y_{2}=y_{2},ldotsY_{T}=y_{T}}$.

Así podemos describir una cadena oculta de Markov ${displaystyle theta = (A,B,pi)}$. El algoritmo Baum-Welch encuentra un máximo local para ${displaystyle theta ^{*}=operatorname {arg,max} _{theta }P(Ymid theta)}$ (es decir, los parámetros HMM ${displaystyle theta }$ que maximice la probabilidad de la observación).

Algoritmo

Set ${displaystyle theta = (A,B,pi)}$ con condiciones iniciales al azar. También se pueden configurar utilizando información previa sobre los parámetros si está disponible; esto puede acelerar el algoritmo y dirigirlo hacia el máximo local deseado.

Procedimiento directo

Vamos. ${displaystyle alpha _{i}(t)=P(Y_{1}=y_{1},ldotsY_{t}=y_{t},X_{t}=imid theta)}$, la probabilidad de ver las observaciones ${displaystyle Y...$ y estar en estado ${displaystyle i}$ a la vez ${displaystyle t}$. Esto se encuentra recursivamente:

1. ${displaystyle alpha _{i}(1)=pi _{i}b_{i}(y_{1}),}$
2. ${displaystyle alpha _{i}(t+1)=b_{i}(y_{t+1})sum ¿Por qué?$

Dado que esta serie converge exponencialmente a cero, el algoritmo se desbordará numéricamente para secuencias más largas. Sin embargo, esto se puede evitar en un algoritmo ligeramente modificado escalando ${displaystyle alpha }$ en el futuro ${displaystyle beta }$ en el procedimiento atrasado a continuación.

Procedimiento inverso

Vamos. ${displaystyle beta _{i}(t)=P(Y_{t+1}=y_{t+1},ldotsY_{T}=y_{T}midt ¿Qué?$ que es la probabilidad de la secuencia parcial final ${displaystyle y_{t+1},ldotsy_{T}$ dado estado inicial ${displaystyle i}$ a la vez ${displaystyle t}$. Calculamos ${displaystyle beta _{i}(t)}$ como,

1. ${displaystyle beta _{i}(T)=1,}$
2. ${displaystyle beta _{i}(t)=sum _{j=1}beta _{j}(t+1)a_{j}b_{j}(y_{t+1}).}$

Actualizar

Ahora podemos calcular las variables temporales, según Bayes' teorema:

${} {} {} {} {} {} {} {} {}} {}} {}} {}} {}} {f} {fn} {fn0}} {fn}}} {fn0}} {fn0}} {f}} {fn0}} {fn0}}} {f} {f}}}} {f}}}}} {f}}}}}} {f}}}}}}} {f} {f} {f}}}}}}}}}} {f} {f}}} {f}}}}}}}}} {f} {f} {f}}}}}}}}}}}}}}} {f} {f} {f}} {f}}}}}}}}}}}} {f} {f}} {f}}}}}}}}}} {f}}}}}}}$

que es la probabilidad de estar en estado ${displaystyle i}$ a la vez ${displaystyle t}$ dada la secuencia observada ${displaystyle Sí.$ y los parámetros ${displaystyle theta }$

${fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {f} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fnMicrosoft ] {fnMicrosoft ] {fnMicrosoft ] {f} {f} {f} {f} {f} {f} {fnMicrob} {f}fnMicrob} {f} {f} {fnMicrotfnMicrosoft}fnMicrosoft}fnMicrob} {fnMicrob} {f} {fnMicrotfnMicrosoft}fnMicrosoft} {f} {fnMicrosoft}fnMicrosoft}}f}fnMicrosoft}fnMicrosoft}f}fnMi ¿Qué? ¿Por qué?$

que es la probabilidad de estar en estado ${displaystyle i}$ y ${displaystyle j}$ a veces ${displaystyle t}$ y ${displaystyle t+1}$ respectivamente dada la secuencia observada ${displaystyle Sí.$ y parámetros ${displaystyle theta }$.

Los denominadores ${displaystyle gamma _{i}(t)}$ y ${displaystyle xi _{ij}(t)}$ son los mismos; representan la probabilidad de hacer la observación ${displaystyle Sí.$ dados los parámetros ${displaystyle theta }$.

Los parámetros del modelo oculto Markov ${displaystyle theta }$ ahora se puede actualizar:

• ${displaystyle pi _{i}{*}=gamma _{i}(1),}$

que es la frecuencia esperada gastada en estado ${displaystyle i}$ a la vez ${displaystyle 1}$.

• ${displaystyle a_{ij}{*}={frac {sum _{t=1}{T-1}xi _{ij}(t)}{sum ¿Qué?$

que es el número esperado de transiciones del estado i al estado j en comparación con el número total esperado de transiciones fuera del estado i. Para aclarar, el número de transiciones fuera del estado i no significa transiciones a un estado diferente j, sino a cualquier estado incluido él mismo. Esto equivale al número de veces que se observa el estado i en la secuencia de t = 1 a t = T − 1.

• ${displaystyle ¿Qué? ¿Por qué? ¿Qué?$

dónde

${displaystyle 1_{y_{t}=v_{k}={begin{cases}1 {text{if} - Sí.$

es una función indicadora, y ${displaystyle ¿Qué?$ es el número esperado de veces que las observaciones de salida han sido iguales ${displaystyle V_{k}$ mientras que en estado ${displaystyle i}$ sobre el número total esperado de veces en estado ${displaystyle i}$.

Estos pasos ahora se repiten iterativamente hasta alcanzar el nivel deseado de convergencia.

Nota: Es posible superar un conjunto de datos en particular. Eso es, ${displaystyle P(Ymid theta _{text{final}}} P(Ymid theta _{text{true})}$. El algoritmo también lo hace no garantizar un máximo global.

Múltiples secuencias

El algoritmo descrito hasta ahora asume una única secuencia observada ${displaystyle Y=y_{1},ldotsy_{N}$. Sin embargo, en muchas situaciones, se observan varias secuencias: ${displaystyle Y_{1},ldotsY_{R}$. En este caso, la información de todas las secuencias observadas debe utilizarse en la actualización de los parámetros ${displaystyle A}$, ${displaystyle pi}$, y ${displaystyle b}$. Suponiendo que hayas computado ${displaystyle gamma _{ir}(t)}$ y ${displaystyle xi _{ijr}(t)}$ para cada secuencia ${displaystyle y_{1,r},ldotsy_{N_{r}r}$, los parámetros se pueden actualizar ahora:

• ${displaystyle pi _{i} {f} {fnK} {fn0} {fn0}gn0}} {cH00}}}$
• ${displaystyle a_{ij}{*}={frac {sum _{r=1}{R}sum _{t=1}{T-1}xi _{ijr}(t)}{sum _{r=1}^{R}sum ¿Qué? }$
• ${displaystyle ¿Qué? ¿Qué? ¿Por qué? ¿Qué? ¿Qué? }$

dónde

${displaystyle 1_{y_{tr}=v_{k}={begin{cases}1 {text{if} }y_{t,r}=v_{k},$