O algoritmo forward-backward é uma técnica fundamental de programação dinâmica utilizada no contexto de modelos ocultos de Markov (HMMs) e em modelos probabilísticos de sequências relacionados. Ele calcula a distribuição marginal a posteriori de cada estado oculto dada uma sequência de observações, permitindo inferência eficiente e estimativa de parâmetros. O algoritmo é uma pedra angular do aprendizado de máquina clássico e permanece relevante em aplicações modernas como reconhecimento de fala, bioinformática e processamento de linguagem natural.
Desenvolvido no final da década de 1960 e início da década de 1970, o algoritmo foi formalizado por Leonard Baum e seus colegas em uma série de artigos sobre estimação estatística para funções probabilísticas de cadeias de Markov. Ele é frequentemente apresentado em conjunto com o algoritmo de Viterbi, que encontra a sequência mais provável de estados ocultos, enquanto o algoritmo forward-backward calcula probabilidades para cada estado individual em cada etapa de tempo. O algoritmo opera em duas passagens: uma passagem direta que calcula a probabilidade de observar a sequência até um determinado ponto no tempo e terminar em um estado particular, e uma passagem reversa que calcula a probabilidade de observar o restante da sequência dado um estado inicial. A combinação desses dois conjuntos de probabilidades produz as marginais a posteriori desejadas.
Formulação Matemática
Considere um HMM com estados ocultos \( S = \{s_1, s_2, \ldots, s_N\} \), probabilidades de transição \( a_{ij} = P(s_j | s_i) \), probabilidades de emissão \( b_j(o_t) = P(o_t | s_j) \), e distribuição inicial de estados \( \pi_i = P(s_i) \). Para uma sequência de observações \( O = (o_1, o_2, \ldots, o_T) \), a variável direta \( \alpha_t(i) \) é definida como a probabilidade da sequência de observações parcial até o tempo \( t \) e de estar no estado \( s_i \) no tempo \( t \): \( \alpha_t(i) = P(o_1, o_2, \ldots, o_t, q_t = s_i | \lambda) \), onde \( \lambda \) denota os parâmetros do modelo. A passagem direta inicializa \( \alpha_1(i) = \pi_i b_i(o_1) \) e recursivamente calcula \( \alpha_{t+1}(j) = b_j(o_{t+1}) \sum_{i=1}^N \alpha_t(i) a_{ij} \).
A variável reversa \( \beta_t(i) \) é definida como a probabilidade da sequência de observações do tempo \( t+1 \) até \( T \) dado que o estado no tempo \( t \) é \( s_i \): \( \beta_t(i) = P(o_{t+1}, o_{t+2}, \ldots, o_T | q_t = s_i, \lambda) \). A passagem reversa inicializa \( \beta_T(i) = 1 \) para todo \( i \) e recursivamente calcula \( \beta_t(i) = \sum_{j=1}^N a_{ij} b_j(o_{t+1}) \beta_{t+1}(j) \). A probabilidade posterior de estar no estado \( s_i \) no tempo \( t \) é então dada por \( \gamma_t(i) = \frac{\alpha_t(i) \beta_t(i)}{\sum_{j=1}^N \alpha_t(j) \beta_t(j)} \).
Aplicações em Modelagem de Sequências
O algoritmo é amplamente utilizado para treinar HMMs via o algoritmo de Baum-Welch, uma instância de esperança-maximização. Na etapa E, o algoritmo de forward-backward calcula estatísticas suficientes esperadas, como o número esperado de transições entre estados e o número esperado de emissões de cada símbolo de observação. Essas estatísticas são então usadas na etapa M para atualizar os parâmetros do modelo. Este procedimento iterativo converge para um máximo local da função de verossimilhança.
No reconhecimento de fala, HMMs com treinamento forward-backward foram a abordagem dominante para modelagem acústica dos anos 1970 até o início dos anos 2000, antes de serem amplamente superados por métodos de deep learning. Em bioinformática, o algoritmo é usado para predição de genes e para analisar sequências de proteínas, onde HMMs modelam motivos conservados. Em processamento de linguagem natural, ele aparece na etiquetagem de partes do discurso e no treinamento de modelos sequence-to-sequence quando usados com camadas de saída estruturada.
Relação com Machine Learning Moderno
Embora o algoritmo forward-backward seja uma técnica clássica, seus princípios persistem no Machine learning moderno. A passagem direta é análoga à propagação de informações em redes neurais recorrentes, e a passagem reversa se assemelha à retropropagação de sinais de erro, embora os objetivos matemáticos sejam distintos. Em redes neurais usadas para rotulação de sequências, como LSTMs bidirecionais, os estados ocultos diretos e reversos são combinados para capturar contexto de ambas as direções, espelhando as variáveis diretas e reversas do algoritmo. Além disso, o uso eficiente de programação dinâmica no algoritmo inspirou técnicas semelhantes em modelos baseados em Transformer (architecture), como o algoritmo forward-backward usado em algumas formas de predição estruturada e no treinamento de grandes modelos de linguagem para tarefas como reconhecimento de entidades nomeadas.
O algoritmo também está relacionado ao conceito de Beam Search em que ambos gerenciam complexidade computacional em problemas de sequência, mas servem a propósitos diferentes: a busca em feixe aproxima a sequência mais provável, enquanto o forward-backward calcula probabilidades marginais exatas. Em modelos gráficos probabilísticos, o algoritmo forward-backward é um caso especial do algoritmo soma de-produto em um grafo de cadeia e que generaliza para gralha externa por modelo em árvore via de crença em propagação.
Complexidade Computacional e Variantes
O algoritmo forward-backward executa em tempo \( O(T N^2) \) e espaço \( O(T N) \), onde é \( T \) o comprimento da sequência e \( N \) o número de está oculto. Essa eficiência torna viável para sequências de milhares de etapas de tempo com centenas de estados. Para espaços de estados grande, aproximações como o algoritmo de amostragem de filtragem-de-radiação de volta são usadas em filtragem de partícula e métodos de Monte Carlo. Em configurações online, o algoritmo direto sozinho pode ser usado para filtragem, enquanto a passagem reversa requer a sequência inteira, tornando-a offline. Variantes incluem o algoritmo forward-backward escalado para problema comum de underflow numérico, especialmente com sequências de análise e baixas probabilidades.
Ver Também
- hidden-argus
- Viterbi Algorithm
- Baum-Welch Algorithm
- dynamic-programming
- sequence-modeling