Algoritmo Forward–Backward

Visão geral

O algoritmo forward–backward (forward–backward algorithm) é um método de programação dinâmica (dynamic programming) para Modelos Ocultos de Markov (Hidden Markov Models, HMMs) que calcula probabilidades posteriores marginais (marginal posterior probabilities) dos estados ocultos dado uma sequência de observações. Ele também é conhecido como o algoritmo soma–produto (sum–product algorithm) para grafos em cadeia de HMM (um caso especial de Propagação de Crenças (Belief Propagation) em Modelos Gráficos Probabilísticos (Probabilistic Graphical Models)).

Dadas observações (x_{1:T} = (x_1, \dots, x_T)) e estados ocultos (z_{1:T} = (z_1, \dots, z_T)), o forward–backward computa eficientemente:

  • Marginais de estado (suavização (smoothing)): [ p(z_t = i \mid x_{1:T}) \quad \text{para todo } t, i ]
  • Marginais de pares de transição (posteriores de dois cortes (two-slice posteriors)): [ p(z_t = i, z_{t+1} = j \mid x_{1:T}) \quad \text{para todo } t, i, j ]

Essas quantidades são essenciais para:

  • Suavização (estimativa de estados passados dado todas as observações)
  • Filtragem (filtering) (estimativa do estado atual dado as observações até o momento; usa apenas a passagem forward)
  • Aprendizado de parâmetros de HMM via Expectação–Maximização (Expectation–Maximization), especificamente o procedimento de Baum–Welch (Baum–Welch) (EM especializada para HMMs)

O forward–backward é o complemento probabilístico do Algoritmo de Viterbi (Viterbi Algorithm), que encontra a única sequência de estados ocultos mais provável (trajetória MAP (MAP path)) em vez de probabilidades marginais.

Configuração e notação do HMM

Um HMM com (N) estados ocultos é parametrizado por:

  • Distribuição inicial de estados: (\pi_i = p(z_1 = i))
  • Probabilidades de transição: (A_{ij} = p(z_{t+1}=j \mid z_t=i))
  • Modelo de emissão: (B_j(x_t) = p(x_t \mid z_t=j))

A distribuição conjunta fatora como: [ p(z_{1:T}, x_{1:T}) = p(z_1)\prod_{t=1}^{T-1} p(z_{t+1}\mid z_t)\prod_{t=1}^{T} p(x_t\mid z_t) ] ou, em parâmetros do HMM: [ p(z_{1:T}, x_{1:T}) = \pi_{z_1}\left(\prod_{t=1}^{T-1} A_{z_t z_{t+1}}\right)\left(\prod_{t=1}^{T} B_{z_t}(x_t)\right) ]

O desafio computacional é que, de forma ingênua, somar sobre todas as sequências de estados exige (O(N^T)) operações. O forward–backward reduz isso para (O(TN^2)) com programação dinâmica.

Recorrência forward (a “passagem forward (forward pass)”)

Definição da variável forward

Defina a mensagem forward (forward message) (frequentemente chamada de (\alpha)):

[ \alpha_t(i) ;=; p(x_{1:t}, z_t=i) ]

Interpretação: a probabilidade de observar as primeiras (t) observações e estar no estado (i) no tempo (t).

Inicialização

[ \alpha_1(i) = \pi_i , B_i(x_1) ]

Recorrência

Para (t = 2,\dots,T): [ \alpha_t(j) = B_j(x_t)\sum_{i=1}^{N} \alpha_{t-1}(i) A_{ij} ]

Este é um passo “prever e depois atualizar”:

  1. Predizer o estado (j) a partir de todos os estados anteriores via transições.
  2. Ponderar pela verossimilhança da observação atual sob o estado (j).

Verossimilhança da sequência a partir da passagem forward

A verossimilhança (likelihood) da sequência de observações é: [ p(x_{1:T}) = \sum_{i=1}^{N} \alpha_T(i) ]

Essa quantidade também é usada em treinamento e comparação de modelos.

Recorrência backward (a “passagem backward (backward pass)”)

Definição da variável backward

Defina a mensagem backward (backward message) (frequentemente chamada de (\beta)):

[ \beta_t(i) ;=; p(x_{t+1:T} \mid z_t=i) ]

Interpretação: se você está no estado (i) no tempo (t), (\beta_t(i)) é a probabilidade de gerar todas as observações futuras (x_{t+1}, \dots, x_T).

Inicialização

[ \beta_T(i) = 1 \quad \text{para todo } i ]

(Não há observações futuras após o tempo (T).)

Recorrência

Para (t = T-1, \dots, 1): [ \beta_t(i) = \sum_{j=1}^{N} A_{ij} , B_j(x_{t+1}) , \beta_{t+1}(j) ]

Isto diz: a partir do estado (i) no tempo (t), some sobre o próximo estado (j), a probabilidade de transição, a probabilidade de emissão da próxima observação e a probabilidade de gerar o restante do futuro.

Cálculo dos posteriores marginais (suavização)

Uma vez que você tenha (\alpha) e (\beta), é possível calcular marginais posteriores sobre estados e transições.

Marginais de estado: \(p(z_t=i \mid x_{1:T})\)

Defina: [ \gamma_t(i) ;=; p(z_t=i \mid x_{1:T}) ]

Usando a regra de Bayes e as definições acima: [ \gamma_t(i) = \frac{\alpha_t(i)\beta_t(i)}{p(x_{1:T})} ] onde (p(x_{1:T}) = \sum_k \alpha_T(k)).

Na prática, você frequentemente computa um valor não normalizado e então normaliza sobre (i): [ \gamma_t(i) \propto \alpha_t(i)\beta_t(i), \quad \sum_i \gamma_t(i)=1 ]

Marginais de pares de transição: \(p(z_t=i, z_{t+1}=j \mid x_{1:T})\)

Defina a marginal de dois cortes: [ \xi_t(i,j) ;=; p(z_t=i, z_{t+1}=j \mid x_{1:T}) ] para (t=1,\dots,T-1).

Ela pode ser computada como: [ \xi_t(i,j) = \frac{\alpha_t(i),A_{ij},B_j(x_{t+1}),\beta_{t+1}(j)}{p(x_{1:T})} ]

Assim como em (\gamma), você pode computar (\xi_t) até proporcionalidade e então normalizar em todos os ((i,j)).

Estabilidade numérica: escalonamento e espaço logarítmico

O forward–backward envolve multiplicar muitas probabilidades, o que rapidamente sofre underflow para zero em aritmética de ponto flutuante para (T) moderado. Duas soluções padrão são:

  1. Escalonamento (scaling) (normalizar a cada passo de tempo)
  2. Cálculo em espaço logarítmico (log-space computation) (usar log-sum-exp)

Abordagem de escalonamento (comum na prática)

Calcule valores forward escalonados (\hat{\alpha}_t(i)) e fatores de escalonamento (c_t):

  1. Calcule (\alpha_t) não escalonado via a recorrência forward.
  2. Defina: [ c_t = \sum_i \alpha_t(i), \quad \hat{\alpha}_t(i) = \frac{\alpha_t(i)}{c_t} ] Isso força (\sum_i \hat{\alpha}_t(i)=1).

A log-verossimilhança (log-likelihood) é então: [ \log p(x_{1:T}) = \sum_{t=1}^{T} \log c_t ] (Com ressalvas sobre convenções de sinal, dependendo de você armazenar (c_t) como normalizador ou seu recíproco; seja consistente.)

Para a passagem backward, use um escalonamento compatível para que (\gamma_t(i) \propto \hat{\alpha}_t(i)\hat{\beta}_t(i)) permaneça válido. Um esquema comum:

  • Inicialize (\hat{\beta}_T(i)=1)
  • Para (t=T-1,\dots,1): [ \hat{\beta}t(i)=\frac{\sum_j A{ij} B_j(x_{t+1}) \hat{\beta}{t+1}(j)}{c{t+1}} ]

Então (\gamma_t(i)) pode ser computado normalizando (\hat{\alpha}_t(i)\hat{\beta}_t(i)).

O escalonamento é rápido, estável e mantém valores em ([0,1]).

Abordagem em espaço logarítmico (conceitualmente simples e robusta)

Defina: [ \ell\alpha_t(i)=\log \alpha_t(i),\quad \ell\beta_t(i)=\log \beta_t(i) ]

Então a recorrência forward se torna: [ \ell\alpha_t(j) = \log B_j(x_t) + \log\sum_i \exp(\ell\alpha_{t-1}(i) + \log A_{ij}) ]

O termo interno é computado com a operação log-sum-exp (log-sum-exp) para estabilidade: [ \log\sum_i e^{u_i} = m + \log\sum_i e^{u_i - m},\quad m=\max_i u_i ]

O espaço logarítmico é particularmente conveniente quando probabilidades são extremamente pequenas, transições são esparsas, ou você já trabalha na forma de energia/potenciais logarítmicos (log-potential).

Complexidade e memória

Seja:

  • (T) = comprimento da sequência
  • (N) = número de estados ocultos

Complexidade de tempo (time complexity)

  • Passagem forward: (O(TN^2)) para (A) denso
  • Passagem backward: (O(TN^2))
  • Total: (O(TN^2))

Se a matriz de transição é esparsa com (E) transições não nulas, você pode reduzir para (O(TE)).

Complexidade de espaço (space complexity)

  • Armazenar todos os (\alpha_t(i)) e (\beta_t(i)): (O(TN))
  • Se você só precisa da verossimilhança (p(x_{1:T})), pode computar mensagens forward com (O(N)) de memória (mantendo apenas o passo de tempo anterior).
  • Para (\gamma_t) e (\xi_t) em todos os passos de tempo (como em EM), você tipicamente armazena todos os (\alpha_t) (e então computa (\beta) de trás para frente e combina) ou armazena ambos, se for conveniente.

Um pequeno exemplo resolvido (HMM de dois estados)

Considere um HMM com dois estados ocultos:

  • (z_t \in {R, S}) significando “Chuvoso” vs “Ensolarado”
  • Observações (x_t \in {\text{Guarda-chuva}, \text{SemGuarda-chuva}})

Parâmetros:

  • (\pi = [p(R)=0.6,, p(S)=0.4])
  • Matriz de transição (A):
    • (p(R\to R)=0.7,; p(R\to S)=0.3)
    • (p(S\to R)=0.4,; p(S\to S)=0.6)
  • Emissões (B):
    • (p(\text{Guarda-chuva}\mid R)=0.9,; p(\text{Guarda-chuva}\mid S)=0.2)
    • (p(\text{SemGuarda-chuva}\mid R)=0.1,; p(\text{SemGuarda-chuva}\mid S)=0.8)

Suponha que observamos (x_{1:3} = (\text{Guarda-chuva}, \text{Guarda-chuva}, \text{SemGuarda-chuva})).

Forward (não escalonado, conceitualmente)

Em (t=1):

  • (\alpha_1(R)=0.6\cdot 0.9=0.54)
  • (\alpha_1(S)=0.4\cdot 0.2=0.08)

Em (t=2):

  • (\alpha_2(R)=0.9\cdot(\alpha_1(R)\cdot 0.7+\alpha_1(S)\cdot 0.4))
  • (\alpha_2(S)=0.2\cdot(\alpha_1(R)\cdot 0.3+\alpha_1(S)\cdot 0.6))

Em (t=3) (SemGuarda-chuva):

  • (\alpha_3(R)=0.1\cdot(\alpha_2(R)\cdot 0.7+\alpha_2(S)\cdot 0.4))
  • (\alpha_3(S)=0.8\cdot(\alpha_2(R)\cdot 0.3+\alpha_2(S)\cdot 0.6))

Por fim (p(x_{1:3})=\alpha_3(R)+\alpha_3(S)).

Intuição do backward e da suavização

A passagem backward incorpora evidência do futuro. Por exemplo, observar SemGuarda-chuva no tempo 3 aumenta a crença em Ensolarado no tempo 3, o que “puxa” a crença no tempo 2 um pouco em direção a Ensolarado também, dependendo das probabilidades de transição. O posterior suavizado (\gamma_2) combina:

  • quão provável cada estado explica as observações até o tempo 2 ((\alpha_2))
  • quão consistente cada estado é com as observações após o tempo 2 ((\beta_2))

Isto é exatamente o que o forward–backward formaliza.

Aplicações práticas

1) Suavização, filtragem e predição

  • Filtragem: (p(z_t \mid x_{1:t})) pode ser obtida apenas de (\alpha_t) normalizado.
  • Suavização: (p(z_t \mid x_{1:T})) usa (\alpha_t) e (\beta_t) (forward–backward completo).
  • Predição de um passo (one-step prediction): (p(z_{t+1}\mid x_{1:t}) = \sum_i p(z_t=i\mid x_{1:t})A_{ij})

Em sistemas reais (por exemplo, atividade de usuário, fala, fusão de sensores), a filtragem é útil para inferência online (online inference), enquanto a suavização é frequentemente usada offline quando a sequência inteira está disponível.

2) Treinamento por EM / Baum–Welch (contagens esperadas)

Quando os parâmetros do HMM são desconhecidos, eles podem ser aprendidos a partir de dados via EM. O forward–backward é o motor de inferência dentro de EM:

  • Etapa E: computar (\gamma_t(i)) e (\xi_t(i,j))
  • Etapa M: atualizar parâmetros usando contagens esperadas

Para um HMM com emissões discretas, atualizações típicas são:

  • Distribuição inicial: [ \pi_i \leftarrow \gamma_1(i) ]
  • Transições: [ A_{ij} \leftarrow \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_t(i)} ]
  • Emissões (para símbolos discretos (v)): [ B_i(v) \leftarrow \frac{\sum_{t=1}^{T} \mathbf{1}[x_t=v]\gamma_t(i)}{\sum_{t=1}^{T}\gamma_t(i)} ]

Com múltiplas sequências, as somas se estendem também pelas sequências.

Este é o núcleo do Baum–Welch, e ele se generaliza para emissões contínuas (por exemplo, HMMs Gaussianos) em que a etapa M atualiza média/covariância usando (\gamma_t(i)) como atribuições suaves (soft assignments).

3) Decodificação posterior vs decodificação de Viterbi

O forward–backward permite decodificação posterior (posterior decoding): [ \hat{z}_t = \arg\max_i \gamma_t(i) ] Isso escolhe o estado mais provável em cada tempo de forma independente.

Em contraste, o Algoritmo de Viterbi encontra: [ \hat{z}{1:T} = \arg\max{z_{1:T}} p(z_{1:T}\mid x_{1:T}) ] o que produz um caminho globalmente consistente (mas não fornece marginais).

A decodificação posterior pode produzir transições inadmissíveis se algumas transições forem impossíveis; o Viterbi respeitará as restrições de transição.

Pseudocódigo de referência (forward–backward escalonado (scaled forward–backward))

Abaixo está um esboço comum de implementação escalonada. Ele assume um HMM em tempo discreto com verossimilhanças de emissão (B[:, t] = p(x_t\mid z_t=i)) já computadas.

Inputs:
  A[N,N] transition matrix
  pi[N] initial distribution
  B[N,T] emission likelihoods for each state and time

Forward (scaled):
  alpha[:,1] = pi * B[:,1]
  c[1] = sum(alpha[:,1])
  alpha[:,1] /= c[1]

  for t = 2..T:
    alpha[:,t] = B[:,t] * (alpha[:,t-1]^T * A)      # size N
    c[t] = sum(alpha[:,t])
    alpha[:,t] /= c[t]

Backward (scaled):
  beta[:,T] = 1
  for t = T-1..1:
    beta[:,t] = A * (B[:,t+1] * beta[:,t+1])        # matrix-vector
    beta[:,t] /= c[t+1]

Marginals:
  for t = 1..T:
    gamma[:,t] = normalize(alpha[:,t] * beta[:,t])

  for t = 1..T-1:
    xi[:,:,t] ∝ alpha[:,t][:,None] * A * (B[:,t+1] * beta[:,t+1])[None,:]
    xi[:,:,t] = xi[:,:,t] / sum_{i,j} xi[i,j,t]

Log-likelihood:
  log p(x_1:T) = sum_{t=1..T} log c[t]

Notas:

  • normalize(v) divide por sum(v) para tornar o vetor uma distribuição de probabilidade.
  • A orientação exata das multiplicações matriz-vetor depende da sua convenção (matriz estocástica por linhas vs estocástica por colunas). As fórmulas neste artigo assumem (A_{ij}=p(z_{t+1}=j\mid z_t=i)).

Dicas de implementação e armadilhas comuns

  • Pré-calcule as verossimilhanças de emissão (emission likelihoods) (B_i(x_t)) para todos os estados e passos de tempo. Para emissões complexas (por exemplo, Gaussianas), calcule log-verossimilhanças e então exponencie com cuidado — ou permaneça no espaço logarítmico.
  • Lide com zeros: se algumas transições/emissões são estruturalmente impossíveis, mantenha-as como zeros exatos. No espaço logarítmico, represente (\log 0) como (-\infty).
  • Use escalonamento ou espaço logarítmico, não probabilidades brutas, para qualquer (T) não trivial.
  • Vetorização: em NumPy/PyTorch/JAX, use multiplicações de matrizes em vez de loops explícitos sobre estados para reduzir overhead.
  • Planejamento de memória: se você só precisa de (\gamma_t) online, pode fazer filtragem apenas com mensagens forward. Para EM, você tipicamente precisa das marginais de todos os passos de tempo.

Principal conclusão conceitual

O forward–backward funciona porque um HMM é uma cadeia (chain), então o posterior sobre um estado no tempo (t) pode ser decomposto em:

  • informação do passado: (\alpha_t(i)=p(x_{1:t}, z_t=i))
  • informação do futuro: (\beta_t(i)=p(x_{t+1:T}\mid z_t=i))

Multiplicar essas quantidades (e normalizar) produz o posterior suavizado (p(z_t\mid x_{1:T})). Estender a mesma ideia para pares adjacentes produz (p(z_t, z_{t+1}\mid x_{1:T})), que fornece as estatísticas suficientes esperadas (expected sufficient statistics) necessárias para treinar HMMs via EM/Baum–Welch.

Em resumo: o Viterbi encontra a melhor explicação única; o forward–backward soma sobre todas as explicações para computar crenças.