Algoritmo de Viterbi

Visão geral

O algoritmo de Viterbi é um método clássico de programação dinâmica (dynamic programming) para decodificar sequências em Modelos Ocultos de Markov (Hidden Markov Models, HMMs) e outros modelos probabilísticos de estado finito (finite-state). Dada uma sequência observada (por exemplo, características acústicas, palavras, bases de DNA), ele encontra a única sequência mais provável de estados ocultos — também chamada de caminho MAP (MAP path) (sequência de estados maximum a posteriori):

[ \hat{z}{1:T}=\arg\max{z_{1:T}} p(z_{1:T}\mid x_{1:T}) ]

Como (p(z_{1:T}\mid x_{1:T}) \propto p(z_{1:T}, x_{1:T})), o Viterbi é tipicamente apresentado como a maximização da probabilidade conjunta (p(z_{1:T}, x_{1:T})). A ideia-chave é que, embora o número de possíveis sequências de estados cresça exponencialmente com o comprimento da sequência, a estrutura de Markov permite que um caminho ótimo seja computado em tempo polinomial reutilizando sub-resultados.

O Viterbi é uma ferramenta central em Modelos Ocultos de Markov, amplamente usada em reconhecimento de fala, rotulagem em PLN, biologia computacional e decodificação em modelos gráficos (é essencialmente uma forma máx-produto (max-product) de propagação de crenças em uma cadeia).

Configuração do problema: notação de HMM

Um HMM tipicamente especifica:

• Um conjunto de estados ocultos (z_t \in {1,\dots,N})
• Observações (x_t) (símbolos discretos ou vetores de características contínuos)
• Distribuição inicial de estados: (\pi_i = p(z_1=i))
• Probabilidades de transição: (a_{ij} = p(z_t=j \mid z_{t-1}=i))
• Verossimilhanças de emissão: (b_j(x_t) = p(x_t \mid z_t=j))

A probabilidade conjunta se fatoriza como:

[ p(z_{1:T}, x_{1:T}) = \pi_{z_1} b_{z_1}(x_1) \prod_{t=2}^{T} a_{z_{t-1}, z_t} , b_{z_t}(x_t) ]

O objetivo de decodificação (Viterbi) é:

[ \hat{z}{1:T} = \arg\max{z_{1:T}} p(z_{1:T}, x_{1:T}) ]

Isso difere de computar marginais (p(z_t \mid x_{1:T})), o que é tratado pelo Algoritmo Forward-Backward.

A ideia de programação dinâmica (o “treliça”)

Considere o melhor caminho que termina no estado (i) no tempo (t). Se você conhecesse o melhor caminho para cada estado anterior (j) no tempo (t-1), então a melhor forma de chegar a (i) no tempo (t) deve vir do melhor predecessor (j) mais uma transição (j\to i).

Isso é a marca registrada da programação dinâmica: subestrutura ótima.

Definimos uma tabela de PD:

• (\delta_t(i)): pontuação (probabilidade) do caminho mais provável que termina no estado (i) no tempo (t)
• (\psi_t(i)): ponteiro de retorno (backpointer), o índice do estado predecessor (j) que atingiu o máximo

O cálculo ao longo do tempo forma uma grade frequentemente chamada de treliça (trellis) (tempo em um eixo, estados no outro).

Recorrência de Viterbi (equações centrais)

Inicialização (\(t=1\))

[ \delta_1(i) = \pi_i , b_i(x_1), \quad \psi_1(i) = 0 ]

Recursão (\(t=2,\dots,T\))

[ \delta_t(i) = b_i(x_t), \max_{j \in {1,\dots,N}} \left[\delta_{t-1}(j), a_{j i}\right] ]

[ \psi_t(i) = \arg\max_{j \in {1,\dots,N}} \left[\delta_{t-1}(j), a_{j i}\right] ]

Terminação

[ \hat{z}_T = \arg\max_i \delta_T(i) ]

(Se o modelo incluir probabilidades explícitas de estado final, incorpore-as aqui de forma semelhante.)

Retrotraçado (recuperando o caminho MAP)

Para (t=T-1,\dots,1):

[ \hat{z}t = \psi{t+1}(\hat{z}_{t+1}) ]

Os ponteiros de retorno são o que convertem “melhor pontuação por estado final” na sequência de estados globalmente ótima.

Mini-exemplo trabalhado (HMM discreto)

Suponha dois estados ocultos:

• (1=) Rainy, (2=) Sunny
  Observações: (x_t \in {\text{walk}, \text{shop}, \text{clean}})

Parâmetros:

• (\pi = [0.6, 0.4])

• (A = \begin{bmatrix} 0.7 & 0.3 \ 0.4 & 0.6 \end{bmatrix})

• Emissões (b_i(x)):

  • Rainy: walk 0.1, shop 0.4, clean 0.5
  • Sunny: walk 0.6, shop 0.3, clean 0.1

Sequência de observações: (x_{1:3} = [\text{walk}, \text{shop}, \text{clean}])

\(t=1\)

• (\delta_1(\text{Rainy}) = 0.6 \cdot 0.1 = 0.06)
• (\delta_1(\text{Sunny}) = 0.4 \cdot 0.6 = 0.24)

\(t=2\), observação “shop”

Para Rainy (estado 1):

• de Rainy: (0.06 \cdot 0.7 = 0.042)
• de Sunny: (0.24 \cdot 0.4 = 0.096) (máx)

Então:

• (\delta_2(1) = 0.4 \cdot 0.096 = 0.0384)
• (\psi_2(1) = \text{Sunny})

Para Sunny (estado 2):

• de Rainy: (0.06 \cdot 0.3 = 0.018)
• de Sunny: (0.24 \cdot 0.6 = 0.144) (máx)

Então:

• (\delta_2(2) = 0.3 \cdot 0.144 = 0.0432)
• (\psi_2(2) = \text{Sunny})

\(t=3\), observação “clean”

Para Rainy:

• de Rainy: (0.0384 \cdot 0.7 = 0.02688)
• de Sunny: (0.0432 \cdot 0.4 = 0.01728) (máx é de Rainy)

(\delta_3(1) = 0.5 \cdot 0.02688 = 0.01344), (\psi_3(1)=\text{Rainy})

Para Sunny:

• de Rainy: (0.0384 \cdot 0.3 = 0.01152)
• de Sunny: (0.0432 \cdot 0.6 = 0.02592) (máx de Sunny)

(\delta_3(2)=0.1 \cdot 0.02592 = 0.002592), (\psi_3(2)=\text{Sunny})

Terminação e retrotraçado

• Melhor estado final: Rainy ((0.01344) vs (0.002592))
• (\hat{z}_3 = \text{Rainy})
• (\hat{z}_2 = \psi_3(\text{Rainy}) = \text{Rainy})
• (\hat{z}_1 = \psi_2(\text{Rainy}) = \text{Sunny})

Sequência de estados decodificada: Sunny → Rainy → Rainy

Isso ilustra o comportamento essencial: o Viterbi faz escolhas de predecessor localmente ótimas que são globalmente ótimas porque o estado da PD resume todo o histórico necessário.

Pseudocódigo (domínio de probabilidade)

Inputs: pi[1..N], a[1..N,1..N], emission b_i(x), observations x[1..T]

delta[1..T,1..N]
psi[1..T,1..N]

# init
for i in 1..N:
    delta[1,i] = pi[i] * b_i(x[1])
    psi[1,i] = 0

# recurse
for t in 2..T:
    for i in 1..N:
        best_val = -inf
        best_arg = 1
        for j in 1..N:
            val = delta[t-1,j] * a[j,i]
            if val > best_val:
                best_val = val
                best_arg = j
        delta[t,i] = b_i(x[t]) * best_val
        psi[t,i] = best_arg

# terminate
z[T] = argmax_i delta[T,i]

# backtrace
for t in T-1 down to 1:
    z[t] = psi[t+1, z[t+1]]

return z[1..T]

Na prática, você quase sempre executa o Viterbi em espaço logarítmico (log-space) para evitar subfluxo numérico.

Viterbi em espaço logarítmico (recomendado)

Probabilidades ao longo de um caminho multiplicam ao longo do tempo, rapidamente sofrendo subfluxo para 0 em ponto flutuante quando (T) é grande. A correção padrão é tomar logaritmos e transformar produtos em somas:

Defina (\Delta_t(i) = \log \delta_t(i)). Então:

Inicialização

[ \Delta_1(i) = \log \pi_i + \log b_i(x_1) ]

Recursão

[ \Delta_t(i) = \log b_i(x_t) + \max_j \left[\Delta_{t-1}(j) + \log a_{j i}\right] ]

Os ponteiros de retorno (\psi_t(i)) não mudam (eles armazenam o argmax).

Observações práticas para espaço logarítmico

• Use (-\infty) para transições/emissões impossíveis ((\log 0)).
• Pré-calcule (\log A), (\log \pi) e (se discreto) (\log B) para velocidade.
• Para emissões contínuas (por exemplo, Gaussianas), compute log-verossimilhanças (log-likelihoods) diretamente.

Complexidade de tempo e espaço

Seja:

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

Complexidade de tempo

A recorrência direta computa, para cada tempo (t) e estado (i), um máximo sobre todos os estados predecessores (j):

• Tempo: (\mathcal{O}(T N^2))

Isso frequentemente é aceitável para (N) pequeno a médio, mas pode ser caro para espaços de estados grandes.

Acelerações comuns (dependentes do modelo):

• Transições esparsas: se cada estado tem apenas (k) transições de saída, a complexidade se torna (\mathcal{O}(T N k)).
• Transições estruturadas: certas estruturas em banda ou convolucionais podem ser aceleradas.
• Busca em feixe (beam search) (aproximada): mantém apenas os top-(K) estados por passo de tempo.

Complexidade de espaço

Se você armazenar a tabela inteira de PD e os ponteiros de retorno:

• (\delta): (\mathcal{O}(T N))
• (\psi): (\mathcal{O}(T N))

Total: memória (\mathcal{O}(T N)) (as constantes dependem dos tamanhos de dtype).

Se você só precisa da melhor pontuação (não do caminho), pode manter apenas a coluna anterior:

• Pontuações: (\mathcal{O}(N))

Mas para reconstruir o caminho, tipicamente você armazena ponteiros de retorno. Opções para economizar memória incluem:

• Checkpointing: armazenar ponteiros de retorno em intervalos e recomputar segmentos.
• Variantes online / streaming: consolidar partes do caminho quando o melhor prefixo se torna estável (comum em decodificação de fala).

Variantes de decodificação e objetivos relacionados

“Decodificação” pode significar coisas diferentes dependendo do que você quer otimizar.

Decodificação Viterbi (caminho MAP)

• Saída: uma única sequência (\hat{z}_{1:T})
• Objetivo: maximizar a probabilidade conjunta (ou a posteriori do caminho inteiro)

Isso é o que “o algoritmo de Viterbi” geralmente significa.

Decodificação posterior (MAP por passo de tempo)

Às vezes você quer o estado mais provável em cada tempo:

[ \hat{z}t = \arg\max_i p(z_t=i \mid x{1:T}) ]

Isso usa marginais do Algoritmo Forward-Backward, não o Viterbi. A decodificação posterior pode produzir uma sequência que não é um caminho válido de alta probabilidade sob restrições de transição, pois otimiza cada posição de forma independente.

Viterbi N-melhores (múltiplos melhores caminhos)

Em vez de um melhor caminho, você pode querer os top (K) caminhos. Isso é útil para reordenamento (reranking) ou restrições a jusante. Abordagens comuns:

• Manter (K) melhores hipóteses por estado/tempo (contabilidade mais complexa).
• Usar métodos de treliça / grafo em autômatos ponderados.

Busca em feixe / poda (Viterbi aproximado)

Em modelos grandes (por exemplo, reconhecimento de fala), a decodificação exata (\mathcal{O}(T N^2)) pode ser lenta demais. A busca em feixe:

• Mantém apenas estados cuja pontuação está dentro de um limiar do melhor atual (ou os top (K) estados).
• Troca exatidão por velocidade.

Viterbi em CRFs e outros modelos de estado finito

A recorrência de Viterbi se generaliza para qualquer modelo estruturado em cadeia onde a pontuação se decompõe em termos locais:

• Campos Aleatórios Condicionais (Conditional Random Fields, CRFs) de cadeia linear (substitua probabilidades por log-potenciais)
• Caminhos de pontuação máxima em grafos de fatores (máx-soma)

Nesses contextos, “Viterbi” frequentemente é descrito como programação dinâmica máx-soma (max-sum).

Variantes segmentais e semi-Markov

Se estados podem persistir por segmentos de comprimento variável (modelos semi-Markov), a recorrência tipicamente inclui um máximo sobre possíveis comprimentos de segmento, aumentando a complexidade a menos que seja otimizada.

Interpretando o Viterbi como caminho mais curto/mais longo em um grafo

A treliça pode ser vista como um grafo acíclico dirigido (DAG):

• Nós: ((t,i))
• Peso da aresta: (\log a_{ji} + \log b_i(x_t)) (mais inicialização)
• Objetivo: encontrar o caminho de peso máximo do início até qualquer nó final

Essa perspectiva conecta o Viterbi a:

• Caminho mais longo em um DAG (resolvível por PD)
• Transdutores de estado finito ponderados (WFSTs) usados em fala e OCR

Notas práticas de implementação

Lidando com zeros e suavização

Se algumas transições ou emissões são zero, o espaço logarítmico usa (-\infty). Isso está correto se esses eventos são realmente impossíveis, mas frequentemente zeros vêm de dados limitados. Correções típicas:

• Suavização aditiva para emissões/transições discretas
• Backoff ou interpolação
• Estimação de parâmetros com regularização (veja Expectation-Maximization para treinamento de HMM via Baum–Welch)

Emissões contínuas

Para HMMs Gaussianos, você calcula:

[ \log b_i(x_t) = \log \mathcal{N}(x_t; \mu_i, \Sigma_i) ]

e insere no Viterbi em espaço logarítmico. Certifique-se de usar rotinas numericamente estáveis de logpdf Gaussiana.

Desempate e determinismo

Se múltiplos estados predecessores produzem o mesmo máximo, (\arg\max) é ambíguo. Para saídas reprodutíveis:

• Escolha o menor índice em empates, ou
• Escolha com base em uma heurística secundária (por exemplo, preferir auto-transições)

Restrições e transições mascaradas

Muitas aplicações impõem restrições:

• Transições de estado proibidas
• Rótulos conhecidos em certos tempos (“forced alignment”)
• Estados de início/fim

Elas são facilmente tratadas definindo as pontuações logarítmicas correspondentes de transição/emissão como (-\infty).

Vetorização e processamento em lote

Para (N) moderado, você pode acelerar com álgebra linear:

• Para cada tempo (t), compute uma matriz de pontuações candidatas: (\Delta_{t-1}[:,None] + \log A)
• Tome máximos por linha/coluna dependendo do layout

Isso é comum em implementações NumPy/PyTorch, embora um gerenciamento cuidadoso de memória importe quando (N) é grande.

Implementação de referência em Python (espaço logarítmico)

A seguir está uma implementação compacta para um HMM de emissões discretas. Ela assume que você consegue consultar (\log b_i(x_t)) para cada estado e tempo.

import numpy as np

def viterbi_log(pi_log, A_log, emit_log):
    """
    Log-space Viterbi.

    Args:
      pi_log:  (N,) log initial probabilities
      A_log:   (N, N) log transition probs, A_log[j, i] = log p(i|j)
      emit_log:(T, N) log emission likelihoods, emit_log[t, i] = log p(x_t|i)

    Returns:
      path: (T,) int state indices
      best_logp: log probability of best path
    """
    T, N = emit_log.shape
    delta = np.full((T, N), -np.inf, dtype=np.float64)
    psi = np.zeros((T, N), dtype=np.int32)

    # init
    delta[0] = pi_log + emit_log[0]
    psi[0] = -1

    # recursion
    for t in range(1, T):
        # scores[j, i] = delta[t-1, j] + A_log[j, i]
        scores = delta[t - 1][:, None] + A_log
        psi[t] = np.argmax(scores, axis=0)
        delta[t] = emit_log[t] + np.max(scores, axis=0)

    # termination
    last = int(np.argmax(delta[T - 1]))
    best_logp = float(delta[T - 1, last])

    # backtrace
    path = np.zeros(T, dtype=np.int32)
    path[T - 1] = last
    for t in range(T - 2, -1, -1):
        path[t] = psi[t + 1, path[t + 1]]

    return path, best_logp

Em sistemas reais você pode precisar de:

• (A) esparsa (armazenar listas de adjacência)
• poda por feixe
• processar múltiplas sequências em lote com padding/máscaras

Aplicações

A decodificação de Viterbi aparece em qualquer lugar em que uma sequência é gerada por um processo de Markov latente:

• Rotulagem em PLN: rotulagem morfossintática (part-of-speech tagging), reconhecimento de entidades nomeadas (HMMs historicamente; CRFs comumente)
• Reconhecimento de fala: decodificação de sequências de estados ou fones; frequentemente integrado a decodificadores WFST com poda
• Biologia computacional: identificação de genes, anotação de domínios de proteínas
• Robótica / rastreamento: estimação de modo discreto em modelos de espaço de estados com comutação
• Correção de erros / comunicações: códigos convolucionais (o Viterbi originalmente ficou famoso aqui)

Equívocos comuns e armadilhas

• “O Viterbi retorna o estado mais provável em cada tempo.”
  Não necessariamente. Ele retorna a sequência inteira mais provável. O estado mais provável no tempo (t) é uma questão marginal resolvida por forward-backward.

• Subfluxo no espaço de probabilidade.
  Para sequências longas, multiplicações de probabilidades brutas viram zero. Use espaço logarítmico.

• Comparar probabilidades entre sequências de comprimentos diferentes.
  Se você decodifica sequências de comprimentos variados, log-probabilidades conjuntas brutas escalam com (T). Considere log-probabilidade média por passo se você precisar de pontuações comparáveis.

• Caminhos excessivamente confiantes com parâmetros mal estimados.
  Se transições/emissões forem “pontiagudas” demais devido a dados limitados, o Viterbi pode travar em caminhos irreais. Suavização/regularização ajuda.

Relação com treinamento e inferência em HMMs

• Treinamento (aprender (A, B, \pi)) é comumente feito com Expectation-Maximization (Baum–Welch), que usa marginais do forward-backward.
• Decodificação (encontrar a melhor sequência de estados ocultos) é o que o Viterbi fornece após os parâmetros serem conhecidos.
• Um conceito relacionado é o treinamento de Viterbi (Viterbi training) (EM duro), que alterna entre decodificação de Viterbi e atualização de parâmetros com base no único melhor caminho — mais rápido, porém menos robusto estatisticamente do que o EM completo.

Resumo

• O algoritmo de Viterbi computa a sequência MAP de estados ocultos em um HMM via programação dinâmica.
• Ele mantém:
  • (\delta_t(i)): melhor pontuação de caminho terminando no estado (i) no tempo (t)
  • (\psi_t(i)): ponteiros de retorno para reconstruir o caminho
• A complexidade é tipicamente (\mathcal{O}(T N^2)) em tempo e (\mathcal{O}(T N)) em espaço, com muitas otimizações práticas (esparsidade, poda, checkpointing).
• Cálculo em espaço logarítmico é a abordagem prática padrão para estabilidade numérica.
• Variantes como decodificação posterior, decodificação N-melhores e busca em feixe atendem a objetivos diferentes ou necessidades de escalabilidade.

Para uma inferência complementar que computa marginais de estado em vez de um único melhor caminho, veja o Algoritmo Forward-Backward.

---