El algoritmo forward-backward es una técnica fundamental de programación dinámica utilizada en el contexto de los modelos ocultos de Markov (HMM) y modelos de secuencias probabilísticas relacionados. Calcula la distribución marginal posterior de cada estado oculto dada una secuencia de observaciones, lo que permite una inferencia eficiente y la estimación de parámetros. El algoritmo es una piedra angular del aprendizaje automático clásico y sigue siendo relevante en aplicaciones modernas como el reconocimiento de voz, la bioinformática y el procesamiento del lenguaje natural.
Desarrollado a finales de la década de 1960 y principios de la de 1970, el algoritmo fue formalizado por Leonard Baum y sus colegas en una serie de artículos sobre estimación estadística para funciones probabilísticas de cadenas de Markov. A menudo se presenta junto con el algoritmo de Viterbi, que encuentra la secuencia más probable de estados ocultos, mientras que el algoritmo forward-backward calcula probabilidades para cada estado individual en cada paso de tiempo. El algoritmo opera en dos pasadas: una pasada forward que calcula la probabilidad de observar la secuencia hasta un punto de tiempo dado y terminar en un estado particular, y una pasada backward que calcula la probabilidad de observar el resto de la secuencia dado un estado inicial. La combinación de estos dos conjuntos de probabilidades produce las marginales posteriores deseadas.
Formulación Matemática
Considere un HMM con estados ocultos \( S = \{s_1, s_2, \ldots, s_N\} \), probabilidades de transición \( a_{ij} = P(s_j | s_i) \), probabilidades de emisión \( b_j(o_t) = P(o_t | s_j) \), y distribución inicial de estados \( \pi_i = P(s_i) \). Para una secuencia de observaciones \( O = (o_1, o_2, \ldots, o_T) \), la variable forward \( \alpha_t(i) \) se define como la probabilidad de la secuencia de observaciones parcial hasta el tiempo \( t \) y de estar en el estado \( s_i \) en el tiempo \( t \): \( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \), donde \( \lambda \) denota los parámetros del modelo. La pasada forward inicializa \( \alpha_1(i) = \pi_i b_i(o_1) \) y calcula recursivamente \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \).
La variable backward \( \beta_t(i) \) se define como la probabilidad de la secuencia de observaciones desde el tiempo \( t+1 \) hasta \( T \) dado que el estado en el tiempo \( t \) es \( s_i \): \( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \). La pasada backward inicializa \( \beta_T(i) = 1 \) para todo \( i \) y calcula recursivamente \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \). La probabilidad posterior de estar en el estado \( s_i \) en el tiempo \( t \) viene dada entonces por \( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \).
Aplicaciones en Modelado de Secuencias
El algoritmo se utiliza ampliamente para entrenar HMM mediante el algoritmo de Baum-Welch, una instancia de maximización de expectativas. En el paso E, el algoritmo forward-backward calcula estadísticas suficientes esperadas, como el número esperado de transiciones entre estados y el número esperado de emisiones de cada símbolo de observación. Estas estadísticas se utilizan luego en el paso M para actualizar los parámetros del modelo. Este procedimiento iterativo converge a un máximo local de la función de verosimilitud.
En el reconocimiento de voz, los HMM con entrenamiento forward-backward fueron el enfoque dominante para el modelado acústico desde la década de 1970 hasta principios de la de 2000, antes de ser en gran medida reemplazados por métodos de aprendizaje profundo. En bioinformática, el algoritmo se utiliza para la predicción de genes y para el análisis de secuencias de proteínas, donde los HMM modelan motivos conservados. En el procesamiento del lenguaje natural, aparece en el etiquetado de partes del discurso y en el entrenamiento de modelos secuencia a secuencia cuando se utilizan con capas de salida estructuradas.
Relación con el Aprendizaje Automático Moderno
Aunque el algoritmo forward-backward es una técnica clásica, sus principios persisten en el aprendizaje automático moderno. La pasada forward es análoga a la propagación de información en redes neuronales recurrentes, y la pasada backward se asemeja a la retropropagación de señales de error, aunque los objetivos matemáticos difieren. En redes neuronales utilizadas para el etiquetado de secuencias, como las LSTMs bidireccionales, los estados ocultos forward y backward se combinan para capturar el contexto desde ambas direcciones, reflejando las variables forward y backward del algoritmo. Además, el uso eficiente de la programación dinámica por parte del algoritmo ha inspirado técnicas similares en modelos basados en transformers, como el algoritmo forward-backward utilizado en algunas formas de predicción estructurada y en el entrenamiento de grandes modelos de lenguaje para tareas como el reconocimiento de entidades nombradas.
El algoritmo también está relacionado con el concepto de búsqueda en haz en el sentido de que ambos gestionan la complejidad computacional en problemas de secuencias, pero sirven para propósitos diferentes: la búsqueda en haz aproxima la secuencia más probable, mientras que forward-backward calcula probabilidades marginales exactas. En los modelos gráficos probabilísticos, el algoritmo forward-backward es un caso especial del algoritmo de suma-producto en un gráfico de cadena, y se generaliza a modelos con estructura de árbol mediante la propagación de creencias.
Complejidad Computacional y Variantes
El algoritmo forward-backward se ejecuta en \( O(T N^2) \) tiempo y \( O(T N) \) espacio, donde \( T \) es la longitud de la secuencia y \( N \) es el número de estados ocultos. Esta eficiencia lo hace factible para secuencias de miles de pasos de tiempo con cientos de estados. Para espacios de estados grandes, se utilizan aproximaciones como el algoritmo de filtrado forward y muestreo backward en el filtrado de partículas y métodos de Monte Carlo. En entornos en línea, el algoritmo forward por sí solo se puede usar para el filtrado, mientras que la pasada backward requiere la secuencia completa, lo que lo hace fuera de línea. Las variantes incluyen el algoritmo forward-backward escalado para evitar el subdesbordamiento numérico, que es común al tratar con secuencias largas y probabilidades pequeñas.
Véase También
- hidden-markov-model
- algoritmo de Viterbi
- algoritmo de Baum-Welch
- dynamic-programming
- sequence-modeling