Algoritmo de avance-retroceso

El algoritmo de avance-retroceso es un algoritmo para calcular las probabilidades posteriores de una secuencia de estados en presencia de una secuencia de observaciones. En otras palabras, un algoritmo que calcula la probabilidad de una secuencia particular de observaciones. El algoritmo se aplica en tres algoritmos de modelos ocultos de Markov .

Resumen

El algoritmo incluye tres pasos:

cálculo de probabilidades directas
cálculo de probabilidades inversas
cálculo de valores suavizados

Los pasos hacia adelante y hacia atrás a menudo se denominan "paso de mensaje hacia adelante" y "paso de mensaje hacia atrás", donde los mensajes son una serie de observaciones sucesivas. La formulación proviene de la forma en que el algoritmo procesa una secuencia dada de observaciones. Primero, el algoritmo avanza, comenzando en la primera observación de la secuencia y yendo a la última, y luego de regreso a la primera. En cada observación, se calculan las probabilidades de secuencia que se utilizarán para los cálculos en la siguiente observación. Durante el paso hacia atrás, el algoritmo realiza simultáneamente un paso de suavizado. El suavizado es el proceso de calcular la distribución de probabilidad de los valores de las variables en estados pasados, dada la evidencia, hasta el estado presente. Este paso permite que el algoritmo tenga en cuenta todas las observaciones anteriores para calcular resultados más precisos.

Descripción formal

Además, consideraremos la matriz empírica de valores probabilísticos, y no la distribución de probabilidad, como matriz base. Transformamos las distribuciones de probabilidad asociadas con un modelo oculto de Markov dado en forma de matriz de la siguiente manera. La matriz de probabilidad de transición (para) una variable aleatoria dada , que representa todos los estados posibles en el modelo oculto de Markov, estará representada por una matriz . En esta matriz, el índice de fila i denota el estado inicial y el índice de columna j denota el estado final. Por ejemplo, a continuación se muestra un sistema para el cual la probabilidad de permanecer en el mismo estado después de cada paso es del 70 % y la probabilidad de pasar a otro estado es del 30 %. Entonces la matriz de probabilidad de transición se ve así: $P({\mbox{X}}_{\mathrm {t} }|{\mbox{X}}_{\mathrm {t-1} })$ ${\mbox{X}}_{\mathrm{t}} }$ $T$ $T={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

De manera similar, representaremos las probabilidades de nuevos estados para estados observados dados, dados como evidencia, en una matriz de observación , donde cada elemento de la diagonal contiene la probabilidad de un nuevo estado, dado el estado observado en el tiempo t. Tenga en cuenta que t indica una observación particular en una secuencia de observaciones. Todos los demás elementos de la matriz serán cero. En el siguiente ejemplo, la primera evidencia observada es el "paraguas". Por lo tanto se definiría como: ${\mbox{O}}_{\mathrm{t} }$ ${\ estilo de visualización (t = 1)}$ ${\mbox{O}}_{\mathrm{1} }$ $O_{1}={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}$

Con base en esta descripción, podemos calcular la siguiente probabilidad directa. Deje que el conjunto de probabilidades directas se almacene en otra matriz . Aquí indica que las probabilidades calculadas dependen de todas las probabilidades directas desde hasta , incluida la matriz de probabilidad actual, que describiremos como . Por lo tanto, es igual al producto de la matriz transpuesta con las probabilidades directas actuales y la matriz de observación para la próxima evidencia en el flujo de observación. Después de eso, se obtiene una matriz que requiere normalización, es decir, los valores obtenidos se deben dividir por la suma de todos los valores de la matriz. El factor de normalización se especifica mediante α . El cálculo de probabilidades directas se describe mediante la fórmula: ${\mbox{f}}_{\mathrm{1:t+1}} }$ ${\ estilo de visualización 1: t + 1}$ $una$ $t+1$ ${\mbox{f}}_{\mathrm{1:t} }$ ${\mbox{f}}_{\mathrm{1:t+1}} }$ ${\mbox{f}}_{\mathrm {1:t+1} }=\alpha {\mbox{O}}_{\mathrm {t+1} }T^{T}{\mbox {f}}_{\mathrm {1:t} }$

Podemos imaginarnos calcular la probabilidad inversa , que comienza desde el final de la secuencia de manera similar. Deje que el final de la secuencia se describa mediante un índice que comienza en 0. Por lo tanto, correr de a y calcular cada probabilidad recíproca se puede describir mediante la siguiente fórmula: ${\mbox{b}}_{\mathrm {k+1:t} }$ $k$ $k$ $t=0$ ${\mbox{b}}_{\mathrm {k+1:t} }=T{\mbox{O}}_{\mathrm {k+1} }{\mbox{b}}_{ \mathrm {k+2:t} }$

Tenga en cuenta que estamos usando una matriz no transpuesta y que el valor de los elementos ha cambiado. También tenga en cuenta que, como resultado final, no usamos el producto de matriz habitual, sino puntualmente. Esta operación multiplica cada variable en una matriz con la variable correspondiente en otra. El tercer y último paso es el cálculo de las probabilidades suavizadas . Probabilidades suavizadas obtenidas por el producto escalar La fórmula se define como El siguiente ejemplo se muestra a continuación. $T$ ${\displaystyle {\mbox{sv))_{\mathrm {k} ))$ ${\mbox{sv))_{\mathrm {k} }=\alpha {\mbox{b))_{\mathrm {k+1:t} }{\mbox{f))_{\ matemática {1:k} }$

Ejemplo

Basado en un ejemplo de Russel & Norvig 2003, página 540. Considere la siguiente secuencia de observaciones (paraguas, paraguas, sin paraguas, paraguas, paraguas). Suponga que la probabilidad de lluvia es del 90% si se observa el paraguas y del 10% si no se observa el paraguas. La probabilidad de que no llueva es del 20% y 80%, respectivamente. Además, suponga que hay un 70 % de probabilidad de que el clima se mantenga igual y un 30 % de probabilidad de que cambie. Las siguientes matrices tomadas del "mundo" de los paraguas describen numéricamente las observaciones anteriores ${\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}}~~{\mathbf {T}}={\begin{pmatrix}0.7&0.3\\0.3&0.7\ end{pmatrix}}~~{\mathbf {T^{T}}}={\begin{pmatrix}0.7&0.3\\0.3&0.7\end{pmatrix}}$

Antes de comenzar a calcular las probabilidades directas, debemos describir dos variables especiales, la primera probabilidad directa y la k+2 probabilidad inversa. La primera probabilidad directa en t=0 está determinada por el antecedente de la variable aleatoria. k+2 la probabilidad inversa está determinada por la matriz "verdadera". Por lo tanto sigue:

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

${\mathbf {b_{{k+2:t}}}}={\begin{pmatrix}1.0\\1.0\end{pmatrix}}$

Ahora iteraremos a través de todos los valores de t y calcularemos las probabilidades directas. Obtenemos las siguientes matrices a partir de la fórmula de probabilidad directa descrita anteriormente. Algunos cálculos pueden ser menos precisos debido al número limitado de lugares decimales utilizados en este ejemplo.

${\mathbf {f_{{1:1}}}}=\alpha {\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}}=\alpha {\begin{pmatrix}0.4500\\0.1000\end{pmatrix}}={\begin {pmatrix}0.8182\\0.1818\end{pmatrix}}$

${\mathbf {f_{{1:2}}}}=\alpha {\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}}=\alpha {\begin{pmatrix}0.5645\\0.0745\end{pmatrix}}={\begin {pmatrix}0.8834\\0.1165\end{pmatrix}}$

${\mathbf {f_{{1:3}}}}=\alpha {\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.1165\end{pmatrix}}=\alpha {\begin{pmatrix}0.0653\\0.2772\end{pmatrix}}={\begin {pmatrix}0.1906\\0.8093\end{pmatrix}}$

${\mathbf {f_{{1:4}}}}=\alpha {\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.1906\\0.8093\end{pmatrix}}=\alpha {\begin{pmatrix}0.3386\\0.1247\end{pmatrix}}={\begin {pmatrix}0.7308\\0.2691\end{pmatrix}}$

${\mathbf {f_{{1:5}}}}=\alpha {\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.2691\end{pmatrix}}=\alpha {\begin{pmatrix}0.5331\\0.0815\end{pmatrix}}={\begin {pmatrix}0.8673\\0.1326\end{pmatrix}}$

Ahora que hemos determinado las probabilidades directas, continuamos calculando las probabilidades inversas. Obtenemos las matrices descritas a continuación a partir de la fórmula para encontrar la probabilidad inversa descrita anteriormente.

${\mathbf {b_{{5:5}}}}={\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}}={\begin{pmatrix}0.5984\\0.0543\end{pmatrix}}={\begin{pmatrix}0.9168 \\0.0831\end{matrix}}$

${\mathbf {b_{{4:5}}}}={\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.9168\\0.0831\end{pmatrix}}={\begin{pmatrix}0.7308\\0.2691\end{pmatrix}}={\begin{pmatrix}0.8593 \\0.1407\end{matrix}}$

${\mathbf {b_{{3:5}}}}={\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.8593\\0.1407\end{pmatrix}}={\begin{pmatrix}0.0178\\0.0845\end{pmatrix}}={\begin{pmatrix}0.1739 \\0.8260\end{matrix}}$

${\mathbf {b_{{2:5}}}}={\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.1739\\0.8260\end{pmatrix}}={\begin{pmatrix}0.1405\\0.0189\end{pmatrix}}={\begin{pmatrix}0.8814 \\0.1185\end{matrix}}$

${\mathbf {b_{{1:5}}}}={\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.8814\\0.1185\end{pmatrix}}={\begin{pmatrix}0.4600\\0.0462\end{pmatrix}}={\begin{pmatrix}0.9087 \\0.0912\end{matrix}}$

Finalmente, calculamos los valores de probabilidad suavizados. El orden de la matriz sigue la fórmula para calcular los valores suavizados anteriores.

${\mathbf {sv_{{5}}}}=\alpha {\begin{pmatrix}1,0000\\1,0000\end{pmatrix}}\times {\begin{pmatrix}0,8673\\0,1326\end{pmatrix}}= \alpha {\begin{pmatrix}0.8673\\0.1326\end{pmatrix}}={\begin{pmatrix}0.8673\\0.1326\end{pmatrix}}$

$\mathbf {sv_{4}} =\alpha {\begin{pmatrix}0.9168\\0.0831\end{pmatrix}}\times {\begin{pmatrix}0.7308\\0.2691\end{pmatrix}}=\ alfa {\begin{pmatrix}0.6699\\0.0223\end{pmatrix}}={\begin{pmatrix}0.9677\\0.0322\end{pmatrix}}$

${\mathbf {sv_{{3}}}}=\alpha {\begin{pmatrix}0.8593\\0.1407\end{pmatrix}}\times {\begin{pmatrix}0.1906\\0.8093\end{pmatrix}}= \alpha {\begin{pmatrix}0.1637\\0.1138\end{pmatrix}}={\begin{pmatrix}0.5899\\0.4101\end{pmatrix}}$

${\mathbf {sv_{{2}}}}=\alpha {\begin{pmatrix}0.1739\\0.8260\end{pmatrix}}\times {\begin{pmatrix}0.8834\\0.1165\end{pmatrix}}= \alpha {\begin{pmatrix}0.1536\\0.0962\end{pmatrix}}={\begin{pmatrix}0.6148\\0.3852\end{pmatrix}}$

${\mathbf {sv_{{1}}}}=\alpha {\begin{pmatrix}0.8814\\0.1185\end{pmatrix}}\times {\begin{pmatrix}0.8182\\0.1818\end{pmatrix}}= \alpha {\begin{pmatrix}0.7211\\0.0215\end{pmatrix}}={\begin{pmatrix}0.9710\\0.0289\end{pmatrix}}$

Una solución más simple a este problema es enumerar todas las secuencias posibles de eventos observados y estados ocultos con sus probabilidades utilizando dos matrices de transición. La probabilidad conjunta de dos secuencias se calcula multiplicando las respectivas probabilidades. Este algoritmo tiene complejidad temporal donde T es la longitud de las secuencias y N es el número de símbolos en el alfabeto estatal. Esto es difícil porque el número de posibles secuencias de nudos ocultos suele ser extremadamente alto. El algoritmo adelante-atrás tiene una complejidad de tiempo de . Hay mejoras en el algoritmo que permiten realizar cálculos en una región de memoria de tamaño constante. Además, para aumentar t, se han desarrollado algoritmos para calcular de manera eficiente utilizando el suavizado en línea de retraso fijo, como el algoritmo de suavizado ( FLS ) Russel & Norvig 2003 página 552 $O(TN^{T})$ $O(N^{2}T)$ ${\mbox{f}}_{\mathrm{1:t+1}} }$

Aplicación

El algoritmo de ida y vuelta es la base de los métodos computacionales utilizados en muchas de estas aplicaciones, que se ocupan de secuencias de observaciones ruidosas que van desde el reconocimiento de voz hasta el seguimiento de aeronaves por radar.

Pseudocódigo

AdelanteAtrás(estado de adivinanza, índice de secuencia): si el índice de secuencia ha pasado el final de la secuencia, devuelve 1 si (guessState, secuenciaIndex) se ha visto antes, devuelve el resultado guardado resultado = 0 para cada estado vecino n: resultado = resultado + (probabilidad de transición de adivinarEstado a n elemento de observación dado en el índice de secuencia)*AdelanteAtrás(n, índice de secuencia+1) guardar resultado para (guessState, índice de secuencia) resultado devuelto

Véase también

Enlaces

Una hoja de cálculo interactiva para enseñar el algoritmo adelante-atrás (hoja de cálculo y artículo con guía paso a paso)
Tutorial de Modelos Ocultos de Markov incluyendo el algoritmo adelante-atrás
Colección de algoritmos de IA implementados en Java (incluidos HMM y el algoritmo de avance hacia atrás)
Suavizado (enlace descendente)
Modelos ocultos de Markov