Algoritmo de avance-retroceso

El algoritmo de avance-retroceso es un algoritmo de inferencia para modelos ocultos de Markov que calcula las distribuciones marginales posteriores de todas las variables de estado ocultas dada una secuencia de observaciones/emisiones.${\displaystyle o_{1:T}:=o_{1},\dots ,o_{T}}$, es decir, calcula, para todas las variables de estado ocultas${\displaystyle X_{t}\in \{X_{1},\dots ,X_{T}\}}$la distribución${\displaystyle P(X_{t}\ |\ o_{1:T})}$Esta tarea de inferencia se suele denominar suavizado . El algoritmo utiliza el principio de programación dinámica para calcular eficientemente los valores necesarios para obtener las distribuciones marginales posteriores en dos pasadas. La primera pasada avanza en el tiempo, mientras que la segunda retrocede; de ​​ahí el nombre de algoritmo de avance-retroceso .

El término algoritmo de avance-retroceso también se utiliza para referirse a cualquier algoritmo perteneciente a la clase general de algoritmos que operan sobre modelos de secuencia de manera bidireccional. En este sentido, las descripciones que se presentan en el resto de este artículo se refieren únicamente a un caso específico de esta clase.

En la primera pasada, el algoritmo hacia adelante-hacia atrás calcula un conjunto de probabilidades hacia adelante que proporcionan, para todo${\displaystyle t\in \{1,\dots ,T\}}$, la probabilidad de terminar en cualquier estado particular dado el primero${\displaystyle t}$observaciones en la secuencia, es decir${\displaystyle P(X_{t}\ |\ o_{1:t})}$En la segunda pasada, el algoritmo calcula un conjunto de probabilidades hacia atrás que proporcionan la probabilidad de observar las observaciones restantes dado cualquier punto de partida.${\displaystyle t}$, es decir${\displaystyle P(o_{t+1:T}\ |\ X_{t})}$Estos dos conjuntos de distribuciones de probabilidad se pueden combinar para obtener la distribución sobre los estados en cualquier momento específico, dada toda la secuencia de observaciones:

${\displaystyle P(X_{t}\ |\ o_{1:T})=P(X_{t}\ |\ o_{1:t},o_{t+1:T})\propto P(o_{t+1:T}\ |\ X_{t})P(X_{t}|o_{1:t})}$

El último paso se deriva de una aplicación de la regla de Bayes y la independencia condicional de${\displaystyle o_{t+1:T}}$y${\displaystyle o_{1:t}}$dado${\displaystyle X_{t}}$.

Como se ha descrito anteriormente, el algoritmo consta de tres pasos:

1. cálculo de probabilidades futuras
2. cálculo de probabilidades hacia atrás
3. Calculando valores suavizados.

Los pasos hacia adelante y hacia atrás también se denominan "paso de mensaje hacia adelante" y "paso de mensaje hacia atrás", términos que se deben al método de propagación de creencias utilizado en general . En cada observación de la secuencia, se calculan las probabilidades que se utilizarán para los cálculos de la siguiente observación. El paso de suavizado se puede calcular simultáneamente durante el paso hacia atrás. Este paso permite que el algoritmo tenga en cuenta las observaciones anteriores de la salida para obtener resultados más precisos.

El algoritmo de avance-retroceso puede utilizarse para encontrar el estado más probable en cualquier momento. Sin embargo, no puede utilizarse para encontrar la secuencia de estados más probable (véase el algoritmo de Viterbi ).

La siguiente descripción utilizará matrices de valores de probabilidad en lugar de distribuciones de probabilidad. Sin embargo, el algoritmo de avance-retroceso puede aplicarse, en general, tanto a modelos de probabilidad continuos como discretos.

Transformamos las distribuciones de probabilidad relacionadas con un modelo oculto de Markov dado en notación matricial de la siguiente manera. Las probabilidades de transición${\displaystyle \mathbf {P} (X_{t}\mid X_{t-1})}$de una variable aleatoria dada${\displaystyle X_{t}}$La matriz representa todos los estados posibles en el modelo oculto de Markov.${\displaystyle \mathbf {T} }$donde el índice de la columna${\displaystyle j}$representará el estado objetivo y el índice de fila.${\displaystyle i}$representa el estado inicial. Una transición desde el estado de vector fila${\displaystyle \mathbf {\pi _{t}} }$al estado incremental de vector fila${\displaystyle \mathbf {\pi _{t+1}} }$se escribe como${\displaystyle \mathbf {\pi _ {t+1}} =\mathbf {\pi _ {t}} \mathbf {T} }$El siguiente ejemplo representa un sistema donde la probabilidad de permanecer en el mismo estado después de cada paso es del 70% y la probabilidad de transición al otro estado es del 30%. La matriz de transición es entonces:

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}}$

En un modelo de Markov típico, multiplicaríamos un vector de estado por esta matriz para obtener las probabilidades del estado subsiguiente. En un modelo oculto de Markov, el estado es desconocido y, en su lugar, observamos eventos asociados con los posibles estados. Una matriz de eventos de la forma:

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

proporciona las probabilidades de observar eventos dado un estado particular. En el ejemplo anterior, el evento 1 se observará el 90% de las veces si estamos en el estado 1, mientras que el evento 2 tiene una probabilidad del 10% de ocurrir en este estado. Por el contrario, el evento 1 solo se observará el 20% de las veces si estamos en el estado 2 y el evento 2 tiene una probabilidad del 80% de ocurrir. Dado un vector fila arbitrario que describe el estado del sistema (${\displaystyle \mathbf {\pi } }$), la probabilidad de observar el evento j es entonces:

${\displaystyle \mathbf {P} (O=j)=\sum _{i}\pi _{i}B_{i,j}}$

La probabilidad de que un estado dado conduzca al evento observado j se puede representar en forma matricial multiplicando el vector fila del estado (${\displaystyle \mathbf {\pi } }$) con una matriz de observación (${\displaystyle \mathbf {O_{j}} =\mathrm {diag} (B_{*,o_{j}})}$) que contiene únicamente entradas diagonales. Siguiendo con el ejemplo anterior, la matriz de observación para el evento 1 sería:

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

Esto nos permite calcular el nuevo vector de estado de probabilidades no normalizadas.${\displaystyle \mathbf {\pi '} }$mediante la regla de Bayes, ponderando por la probabilidad de que cada elemento de${\displaystyle \mathbf {\pi } }$evento generado 1 como:

${\displaystyle \mathbf {\pi '} =\mathbf {\pi } \mathbf {O_{1}} }$

Ahora podemos hacer que este procedimiento general sea específico para nuestra serie de observaciones. Suponiendo un vector de estado inicial${\displaystyle \mathbf {\pi } _{0}}$, (que puede optimizarse como un parámetro mediante repeticiones del procedimiento hacia adelante-hacia atrás), comenzamos con${\displaystyle \mathbf {f_{0:0}} =\mathbf {\pi } _{0}}$, luego actualizando la distribución del estado y ponderando por la probabilidad de la primera observación:

${\displaystyle \mathbf {f_{0:1}} =\mathbf {\pi } _{0}\mathbf {T} \mathbf {O_{o_{1}}} }$

Este proceso puede continuarse con observaciones adicionales utilizando:

${\displaystyle \mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}} }$

Este valor es el vector de probabilidad no normalizado hacia adelante . La i-ésima entrada de este vector proporciona:

${\displaystyle \mathbf {f_{0:t}} (i)=\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}$

Normalmente, normalizaremos el vector de probabilidad en cada paso de modo que la suma de sus entradas sea igual a 1. Por lo tanto, en cada paso se introduce un factor de escala tal que:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\ \mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{o_{t}}} }$

dónde${\displaystyle \mathbf {{\hat {f}}_{0:t-1}} }$representa el vector escalado del paso anterior y${\displaystyle c_{t}}$representa el factor de escala que hace que la suma de las entradas del vector resultante sea igual a 1. El producto de los factores de escala es la probabilidad total de observar los eventos dados, independientemente de los estados finales:

${\displaystyle \mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})=\prod _{s=1}^{t}c_{s}}$

Esto nos permite interpretar el vector de probabilidad escalado como:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} (i)={\frac {\mathbf {f_{0:t}} (i)}{\prod _{s=1}^{t}c_{s}}}={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{t},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{t}|\mathbf {\pi } _{0})}}=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{t},\mathbf {\pi } _{0})}$

Así, encontramos que el producto de los factores de escala nos proporciona la probabilidad total de observar la secuencia dada hasta el tiempo t y que el vector de probabilidad escalada nos proporciona la probabilidad de estar en cada estado en ese momento.

Se puede construir un procedimiento similar para encontrar probabilidades hacia atrás. Estos pretenden proporcionar las siguientes probabilidades:

${\displaystyle \mathbf {b_{t:T}} (i)=\mathbf {P} (o_{t+1},o_{t+2},\dots ,o_{T}|X_{t}=x_{i})}$

Es decir, ahora queremos suponer que comenzamos en un estado particular (${\displaystyle X_{t}=x_{i}}$), y ahora nos interesa la probabilidad de observar todos los eventos futuros desde este estado. Dado que el estado inicial se asume como dado (es decir, la probabilidad previa de este estado = 100%), comenzamos con:

${\displaystyle \mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}}$

Observe que ahora estamos utilizando un vector columna, mientras que las probabilidades directas utilizaban vectores fila. A continuación, podemos trabajar hacia atrás utilizando:

${\displaystyle \mathbf {b_{t-1:T}} =\mathbf {T} \mathbf {O_{t}} \mathbf {b_{t:T}} }$

Si bien podríamos normalizar este vector para que la suma de sus entradas sea igual a uno, esto no se suele hacer. Teniendo en cuenta que cada entrada contiene la probabilidad de la secuencia de eventos futuros dado un estado inicial particular, normalizar este vector sería equivalente a aplicar el teorema de Bayes para hallar la probabilidad de cada estado inicial dados los eventos futuros (suponiendo distribuciones a priori uniformes para el vector de estado final). Sin embargo, es más común escalar este vector utilizando el mismo método.${\displaystyle c_{t}}$constantes utilizadas en los cálculos de probabilidad directa. ${\displaystyle \mathbf {b_{T:T}} }$no está escalado, pero las operaciones posteriores utilizan:

${\displaystyle \mathbf {{\hat {b}}_{t-1:T}} =c_{t}^{-1}\mathbf {T} \mathbf {O_{t}} \mathbf {{\hat {b}}_{t:T}} }$

dónde${\displaystyle \mathbf {{\hat {b}}_{t:T}} }$representa el vector anterior escalado. Este resultado indica que el vector de probabilidad escalado está relacionado con las probabilidades hacia atrás mediante:

${\displaystyle \mathbf {{\hat {b}}_{t:T}} (i)={\frac {\mathbf {b_{t:T}} (i)}{\prod _{s=t+1}^{T}c_{s}}}}$

Esto es útil porque nos permite hallar la probabilidad total de estar en cada estado en un momento dado, t, multiplicando estos valores:

${\displaystyle \mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=x_{i}|o_{1},o_{2},\dots ,o_{T},\mathbf {\pi } _{0})={\frac {\mathbf {P} (o_{1},o_{2},\dots ,o_{T},X_{t}=x_{i}|\mathbf {\pi } _{0})}{\mathbf {P} (o_{1},o_{2},\dots ,o_{T}|\mathbf {\pi } _{0})}}={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{\prod _{s=1}^{T}c_{s}}}=\mathbf {{\hat {f}}_{0:t}} (i)\cdot \mathbf {{\hat {b}}_{t:T}} (i)}$

Para entender esto, observamos que${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}$proporciona la probabilidad de observar los eventos dados de una manera que pase por el estado${\displaystyle x_{i}}$en el tiempo t. Esta probabilidad incluye las probabilidades hacia adelante que cubren todos los eventos hasta el tiempo t, así como las probabilidades hacia atrás que incluyen todos los eventos futuros. Este es el numerador que buscamos en nuestra ecuación, y dividimos por la probabilidad total de la secuencia de observación para normalizar este valor y extraer solo la probabilidad de que${\displaystyle X_{t}=x_{i}}$Estos valores a veces se denominan "valores suavizados", ya que combinan las probabilidades hacia adelante y hacia atrás para calcular una probabilidad final.

Los valores${\displaystyle \mathbf {\gamma _{t}} (i)}$De esta forma, proporcionan la probabilidad de estar en cada estado en el instante t. Por lo tanto, son útiles para determinar el estado más probable en cualquier momento. El término "estado más probable" es algo ambiguo. Si bien el estado más probable es el que tiene más probabilidades de ser correcto en un punto dado, la secuencia de estados individualmente probables no tiene muchas probabilidades de ser la secuencia más probable. Esto se debe a que las probabilidades para cada punto se calculan independientemente unas de otras. No tienen en cuenta las probabilidades de transición entre estados, y por lo tanto es posible obtener estados en dos momentos (t y t+1) que son ambos los más probables en esos instantes, pero que tienen muy poca probabilidad de ocurrir juntos, es decir${\displaystyle \mathbf {P} (X_{t}=x_{i},X_{t+1}=x_{j})\neq \mathbf {P} (X_{t}=x_{i})\mathbf {P} (X_{t+1}=x_{j})}$La secuencia de estados más probable que produjo una secuencia de observación se puede encontrar utilizando el algoritmo de Viterbi .

Este ejemplo se basa en el mundo de los paraguas descrito en Russell y Norvig (2010), capítulo 15, pág. 567, donde se pretende inferir el tiempo a partir de la observación de una persona que lleva o no un paraguas. Suponemos dos estados posibles para el tiempo: estado 1 = lluvia, estado 2 = ausencia de lluvia. Suponemos que el tiempo tiene un 70 % de probabilidad de permanecer igual cada día y un 30 % de probabilidad de cambiar. Las probabilidades de transición son, por lo tanto:

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}}$

También asumimos que cada estado genera uno de dos posibles eventos: evento 1 = paraguas, evento 2 = sin paraguas. Las probabilidades condicionales de que estos ocurran en cada estado vienen dadas por la matriz de probabilidad:

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

A continuación, observamos la siguiente secuencia de eventos: {paraguas, paraguas, sin paraguas, paraguas, paraguas} que representaremos en nuestros cálculos como:

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{2}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{3}} ={\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}~~\mathbf {O_{4}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}~~\mathbf {O_{5}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

Tenga en cuenta que${\displaystyle \mathbf {O_{3}} }$Se diferencia de los demás por la observación de que "no lleva paraguas".

Para calcular las probabilidades a futuro, comenzamos con:

${\displaystyle \mathbf {f_{0:0}} ={\begin{pmatrix}0.5&0.5\end{pmatrix}}}$

que es nuestro vector de estado previo, lo que indica que no sabemos en qué estado se encuentra el clima antes de nuestras observaciones. Si bien un vector de estado debería darse como un vector fila, utilizaremos la transpuesta de la matriz para que los cálculos que siguen sean más fáciles de leer. Nuestros cálculos se escriben entonces de la siguiente forma:

${\displaystyle (\mathbf {{\hat {f}}_{0:t}} )^{T}=c_{t}^{-1}\mathbf {O_{t}} (\mathbf {T} )^{T}(\mathbf {{\hat {f}}_{0:t-1}} )^{T}}$

en lugar de:

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}} }$

Nótese que la matriz de transformación también se transpone, pero en nuestro ejemplo la transpuesta es igual a la matriz original. Al realizar estos cálculos y normalizar los resultados, obtenemos:

${\displaystyle (\mathbf {{\hat {f}}_{0:1}} )^{T}=c_{1}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}=c_{1}^{-1}{\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:2}} )^{T}=c_{2}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}=c_{2}^{-1}{\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:3}} )^{T}=c_{3}^{-1}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}=c_{3}^{-1}{\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:4}} )^{T}=c_{4}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}=c_{4}^{-1}{\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}}$

${\displaystyle (\mathbf {{\hat {f}}_{0:5}} )^{T}=c_{5}^{-1}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}=c_{5}^{-1}{\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

Para las probabilidades hacia atrás, comenzamos con:

${\displaystyle \mathbf {b_{5:5}} ={\begin{pmatrix}1.0\\1.0\end{pmatrix}}}$

Entonces podemos calcular (utilizando las observaciones en orden inverso y normalizando con diferentes constantes):

${\displaystyle \mathbf {{\hat {b}}_{4:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.6900\\0.4100\end{pmatrix}}={\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{3:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4175\\0.2215\end{pmatrix}}={\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{2:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.1&0.0\\0.0&0.8\end{pmatrix}}{\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1289\\0.2138\end{pmatrix}}={\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{1:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.2745\\0.1889\end{pmatrix}}={\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}}$

${\displaystyle \mathbf {{\hat {b}}_{0:5}} =\alpha {\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}{\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}{\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.3976\\0.2170\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}}$

Finalmente, calcularemos los valores de probabilidad suavizados. Estos resultados también deben escalarse de modo que sus entradas sumen 1 porque no escalamos las probabilidades hacia atrás con la${\displaystyle c_{t}}$Se encontró anteriormente. Los vectores de probabilidad hacia atrás anteriores representan, por lo tanto, la probabilidad de cada estado en el instante t dadas las observaciones futuras. Dado que estos vectores son proporcionales a las probabilidades reales hacia atrás, el resultado debe escalarse un factor adicional.

${\displaystyle (\mathbf {\gamma _{0}} )^{T}=\alpha {\begin{pmatrix}0.5000\\0.5000\end{pmatrix}}\circ {\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}=\alpha {\begin{pmatrix}0.3235\\0.1765\end{pmatrix}}={\begin{pmatrix}0.6469\\0.3531\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{1}} )^{T}=\alpha {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}\circ {\begin{pmatrix}0.5923\\0.4077\end{pmatrix}}=\alpha {\begin{pmatrix}0.4846\\0.0741\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{2}} )^{T}=\alpha {\begin{pmatrix}0.8834\\0.1166\end{pmatrix}}\circ {\begin{pmatrix}0.3763\\0.6237\end{pmatrix}}=\alpha {\begin{pmatrix}0.3324\\0.0728\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{3}} )^{T}=\alpha {\begin{pmatrix}0.1907\\0.8093\end{pmatrix}}\circ {\begin{pmatrix}0.6533\\0.3467\end{pmatrix}}=\alpha {\begin{pmatrix}0.1246\\0.2806\end{pmatrix}}={\begin{pmatrix}0.3075\\0.6925\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{4}} )^{T}=\alpha {\begin{pmatrix}0.7308\\0.2692\end{pmatrix}}\circ {\begin{pmatrix}0.6273\\0.3727\end{pmatrix}}=\alpha {\begin{pmatrix}0.4584\\0.1003\end{pmatrix}}={\begin{pmatrix}0.8204\\0.1796\end{pmatrix}}}$

${\displaystyle (\mathbf {\gamma _{5}} )^{T}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}\circ {\begin{pmatrix}1.0000\\1.0000\end{pmatrix}}=\alpha {\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1327\end{pmatrix}}}$

Observe que el valor de${\displaystyle \mathbf {\gamma _{0}} }$es igual a${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$y eso${\displaystyle \mathbf {\gamma _{5}} }$es igual a${\displaystyle \mathbf {{\hat {f}}_{0:5}} }$Esto se deduce naturalmente porque ambos${\displaystyle \mathbf {{\hat {f}}_{0:5}} }$y${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$comenzar con distribuciones a priori uniformes sobre los vectores de estado inicial y final (respectivamente) y tener en cuenta todas las observaciones. Sin embargo,${\displaystyle \mathbf {\gamma _{0}} }$será igual a${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$cuando nuestro vector de estado inicial representa una distribución a priori uniforme (es decir, todas las entradas son iguales). Cuando este no es el caso${\displaystyle \mathbf {{\hat {b}}_{0:5}} }$Es necesario combinar las probabilidades hacia adelante con el vector de estado inicial para hallar el estado inicial más probable. De este modo, concluimos que las probabilidades hacia adelante son suficientes para calcular el estado final más probable. Del mismo modo, las probabilidades hacia atrás pueden combinarse con el vector de estado inicial para obtener el estado inicial más probable a partir de las observaciones. Las probabilidades hacia adelante y hacia atrás solo necesitan combinarse para inferir los estados más probables entre los puntos inicial y final.

Los cálculos anteriores revelan que el estado meteorológico más probable en todos los días excepto en el tercero fue "lluvia". Sin embargo, nos dicen más que esto, ya que ahora proporcionan una forma de cuantificar las probabilidades de cada estado en diferentes momentos. Quizás lo más importante sea nuestro valor en${\displaystyle \mathbf {\gamma _{5}} }$Cuantifica nuestro conocimiento del vector de estado al final de la secuencia de observación. Podemos usarlo para predecir la probabilidad de los distintos estados meteorológicos de mañana, así como la probabilidad de observar un paraguas.

El algoritmo de avance-retroceso se ejecuta con complejidad temporal${\displaystyle O(S^{2}T)}$en el espacio${\displaystyle O(ST)}$, dónde${\displaystyle T}$es la duración de la secuencia de tiempo y${\displaystyle S}$es el número de símbolos en el alfabeto del estado. ^{[ 1 ]} El algoritmo también puede ejecutarse en espacio constante con complejidad temporal.${\displaystyle O(S^{2}T^{2})}$recalculando valores en cada paso. ^{[ 2 ]} En comparación, un procedimiento de fuerza bruta generaría todos los posibles${\displaystyle S^{T}}$secuencias de estados y calcular la probabilidad conjunta de cada secuencia de estados con la serie de eventos observados, lo que tendría una complejidad temporal.${\displaystyle O(T\cdot S^{T})}$El método de fuerza bruta resulta intratable para problemas realistas, ya que el número de posibles secuencias de nodos ocultos suele ser extremadamente alto.

Una mejora del algoritmo general de avance-retroceso, llamado algoritmo de la isla , intercambia un menor uso de memoria por un mayor tiempo de ejecución, tomando${\displaystyle O(S^{2}T\log T)}$tiempo y${\displaystyle O(S\log T)}$memoria. Además, es posible invertir el modelo de proceso para obtener un${\displaystyle O(S)}$espacio,${\displaystyle O(S^{2}T)}$algoritmo de tiempo, aunque el proceso invertido puede no existir o estar mal condicionado . ^{[ 3 ]}

Además, se han desarrollado algoritmos para calcular${\displaystyle \mathbf {f_{0:t+1}} }$eficientemente a través de suavizado en línea como el algoritmo de suavizado de retardo fijo (FLS). ^{[ 4 ]}

El algoritmo forward_backward es la entrada: guessState Salida de int sequenceIndex : resultadoSi sequenceIndex está más allá del final de la secuencia , entonces devuelve 1. Si ( guessState , sequenceIndex ) ya se ha visto antes, entonces devuelve el resultado guardado . resultado := 0 para cada estado vecino n: resultado := resultado + (probabilidad de transición de guessState a n elemento de observación dado en sequenceIndex ) × Hacia atrás(n, índice de secuencia + 1) guardar resultado para ( guessState , sequenceIndex ) devolver resultado

Dado el HMM (al igual que en el algoritmo de Viterbi ) representado en el lenguaje de programación Python :

estados = ( "Sano" , "Fiebre" ) ​​estado_final = "E"observaciones = ( "normal" , "frío" , "mareado" )probabilidad_inicial = { "Sano" : 0.6 , "Fiebre" : 0.4 }probabilidad_de_transición = { "Saludable" : { "Saludable" : 0.69 , "Fiebre" : 0.3 , "E" : 0.01 }, "Fiebre" : { "Saludable" : 0.4 , "Fiebre" : 0.59 , "E" : 0.01 }, }probabilidad_de_emisión = { "Saludable" : { "normal" : 0.5 , "frío" : 0.4 , "mareado" : 0.1 }, "Fiebre" : { "normal" : 0.1 , "frío" : 0.3 , "mareado" : 0.6 }, }

Podemos escribir la implementación del algoritmo de avance-retroceso de esta manera:

def fwd_bkw ( observaciones , estados , start_prob , trans_prob , emm_prob , end_st ): """Algoritmo hacia adelante-hacia atrás.""" # Parte hacia adelante del algoritmo fwd = [] for i , observation_i in enumerate ( observaciones ): f_curr = {} for st in estados : if i == 0 : # caso base para la parte hacia adelante prev_f_sum = start_prob [ st ] else : prev_f_sum = sum ( f_prev [ k ] * trans_prob [ k ][ st ] for k in estados )f_curr [ st ] = emm_prob [ st ][ observation_i ] * prev_f_sumfwd.append ( f_curr ) f_prev = f_curr​​p_fwd = suma ( f_curr [ k ] * trans_prob [ k ][ end_st ] para k en estados )# Parte inversa del algoritmo bkw = [] para i , observation_i_plus en enumerate ( reversed ( observations [ 1 :] + ( None ,))): b_curr = {} para st en states : si i == 0 : # caso base para la parte inversa b_curr [ st ] = trans_prob [ st ][ end_st ] else : b_curr [ st ] = sum ( trans_prob [ st ][ l ] * emm_prob [ l ][ observation_i_plus ] * b_prev [ l ] para l en states )bkw.insertar ( 0 , b_curr ) b_prev = b_curr​​p_bkw = suma ( start_prob [ l ] * emm_prob [ l ][ observations [ 0 ]] * b_curr [ l ] para l en estados )# Fusionando las dos partes posterior = [] para i en rango ( len ( observaciones )): posterior . append ({ st : fwd [ i ][ st ] * bkw [ i ][ st ] / p_fwd para st en estados })assert p_fwd == p_bkw return fwd , bkw , posterior

La función fwd_bkwtoma los siguientes argumentos: xes la secuencia de observaciones, por ejemplo ['normal', 'cold', 'dizzy']; stateses el conjunto de estados ocultos; a_0es la probabilidad de inicio; ason las probabilidades de transición; y eson las probabilidades de emisión.

Para simplificar el código, asumimos que la secuencia de observación xno está vacía y que a[i][j]y e[i][j]está definida para todos los estados i,j.

En el ejemplo que se está ejecutando, el algoritmo de avance-retroceso se utiliza de la siguiente manera:

def ejemplo (): return fwd_bkw ( observaciones , estados , probabilidad_inicio , probabilidad_transición , probabilidad_emisión , estado_final , )

>>> para línea en ejemplo (): ... imprimir ( * línea ) ... {'Saludable': 0.3, 'Fiebre': 0.04000000000000001} {'Saludable': 0.0892, 'Fiebre': 0.03408} {'Saludable': 0.007518, 'Fiebre': 0.028120319999999997} {'Saludable': 0.0010418399999999998, 'Fiebre': 0.00109578} {'Saludable': 0.00249, 'Fiebre': 0.00394} {'Saludable': 0.01, 'Fiebre': 0.01} {'Saludable': 0,8770110375573259, 'Fiebre': 0,1229889624426741} {'Saludable': 0,623228030950954, 'Fiebre': 0,3767719690490461} {'Saludable': 0,2109527048413057, 'Fiebre': 0,7890472951586943}

• Algoritmo de Baum-Welch
• Algoritmo de Viterbi
• Algoritmo BCJR

• Lawrence R. Rabiner , Tutorial sobre modelos ocultos de Markov y aplicaciones seleccionadas en el reconocimiento de voz. Actas del IEEE , 77 (2), págs.  257-286, febrero de 1989. 10.1109/5.18626
• Lawrence R. Rabiner, BH Juang (enero de 1986). "Una introducción a los modelos ocultos de Markov". Revista IEEE ASSP : 4– 15.
• Eugene Charniak (1993). Aprendizaje estadístico del lenguaje . Cambridge, Massachusetts: MIT Press. ISBN 978-0-262-53141-2.
• Stuart Russell y Peter Norvig (2010). Inteligencia artificial: Un enfoque moderno, 3.ª edición . Upper Saddle River, Nueva Jersey: Pearson Education/Prentice-Hall. ISBN 978-0-13-604259-4.

• Una hoja de cálculo interactiva para enseñar el algoritmo de avance-retroceso (hoja de cálculo y artículo con instrucciones paso a paso).
• Tutorial de modelos ocultos de Markov, incluyendo el algoritmo de avance-retroceso.
• Colección de algoritmos de IA implementados en Java (incluidos HMM y el algoritmo de avance-retroceso).