O algoritmo de Viterbi é um algoritmo de programação dinâmica que identifica a sequência mais provável de estados ocultos que poderia ter produzido uma determinada sequência de eventos observados. A sequência resultante é frequentemente chamada de caminho de Viterbi. Ele é mais comumente aplicado a modelos ocultos de Markov (HMMs), onde os estados subjacentes não são diretamente observáveis, mas influenciam as observações. Por exemplo, um médico observando os sintomas de um paciente ao longo de vários dias poderia usar o algoritmo para inferir a sequência mais provável de condições de saúde subjacentes que causaram esses sintomas.
O algoritmo encontrou aplicação universal na decodificação de códigos convolucionais usados em redes celulares digitais CDMA e GSM, modems dial-up, comunicações via satélite e de espaço profundo, e LANs sem fio 802.11. Ele também é amplamente utilizado em reconhecimento de fala, síntese de fala, diarização de locutores, detecção de palavras-chave, linguística computacional e bioinformática. Em sistemas de conversão de fala em texto, o sinal acústico serve como a sequência observada, e a string de texto é a causa oculta; o algoritmo de Viterbi encontra o texto mais provável dado o sinal acústico.
História
O algoritmo de Viterbi recebeu esse nome em homenagem a Andrew Viterbi, que o propôs em 1967 como um algoritmo de decodificação para códigos convolucionais em links de comunicação digital ruidosos. Ele tem um histórico de múltiplas invenções, com pelo menos sete descobertas independentes, incluindo as de Viterbi, Needleman e Wunsch, e Wagner e Fischer. Foi introduzido no processamento de linguagem natural como um método para etiquetagem de classes gramaticais já em 1987.
Os termos "caminho de Viterbi" e "algoritmo de Viterbi" tornaram-se padrão para abordagens de programação dinâmica a problemas de maximização envolvendo probabilidades. Na análise sintática estatística, um algoritmo de programação dinâmica pode descobrir a única derivação livre de contexto mais provável (análise sintática) de uma string, comumente chamada de "análise sintática de Viterbi". Outra aplicação é o rastreamento de alvos, onde o algoritmo calcula a trajetória que atribui máxima verossimilhança a uma sequência de observações.
Visão Geral do Algoritmo
Dado um modelo oculto de Markov com um conjunto de estados ocultos S, um conjunto de possíveis emissões (observações) M, e uma sequência de T observações o0, o1, ..., oT-1, o algoritmo de Viterbi encontra a sequência mais provável de estados ocultos que poderia ter produzido essas observações. Em cada passo de tempo t, o algoritmo resolve o subproblema onde apenas observações até ot são consideradas.
Duas matrizes de tamanho T × |S| são construídas. A matriz Pt,s contém a probabilidade máxima de terminar no estado s na observação t, entre todas as sequências possíveis de estados que levam a ele. A matriz Qt,s rastreia o estado anterior que foi usado antes de s nesta sequência de estados de probabilidade máxima.
Sejam πs e ar,s as probabilidades inicial e de transição, respectivamente, e seja bs,o a probabilidade de observar o no estado s. Então os valores de P são dados por uma relação de recorrência. No tempo t = 0, Pt,s é igual a πs multiplicado por bs,o0. Para t > 0, Pt,s é igual ao máximo sobre todos os estados anteriores r de (Pt-1,r × ar,s × bs,ot). Após preencher as matrizes, o algoritmo retrocede a partir do estado com a maior probabilidade no passo de tempo final usando a matriz Q para reconstruir a sequência de estados mais provável.
Aplicações em Comunicações
O algoritmo é uma pedra angular das comunicações digitais modernas. Ele decodifica códigos convolucionais, que são códigos de correção de erros usados em muitos sistemas sem fio e com fio. Em redes celulares CDMA e GSM, o algoritmo de Viterbi ajuda a recuperar dados transmitidos apesar de ruído e interferência. Modems dial-up, links via satélite e sistemas de comunicação de espaço profundo também dependem dele. O padrão de LAN sem fio 802.11 incorpora decodificação de Viterbi para transmissão confiável de dados.
A eficiência do algoritmo vem de sua natureza de programação dinâmica: ele evita a enumeração exaustiva de todas as sequências possíveis de estados armazenando probabilidades intermediárias e usando o princípio da otimalidade. Isso torna viável decodificar sequências longas em tempo real, mesmo em dispositivos com recursos limitados.
Aplicações em Fala e Linguagem
No reconhecimento de fala, o algoritmo de Viterbi alinha características acústicas com modelos fonéticos ou de palavras. O sinal acústico é a sequência observada, e a string de texto é a causa oculta. O algoritmo encontra a string de texto mais provável dado o sinal acústico, permitindo transcrição precisa. Ele também é usado na síntese de fala para selecionar a sequência mais natural de unidades de fala, e na diarização de locutores para determinar quem falou quando.
Na linguística computacional, o algoritmo é aplicado à etiquetagem de classes gramaticais, onde os estados ocultos são categorias gramaticais e as observações são palavras. Ele também suporta análise sintática estatística, onde encontra a árvore de análise sintática mais provável para uma frase. Na bioinformática, ele ajuda a alinhar sequências biológicas e prever estruturas de genes, tratando sequências de DNA ou proteínas como observações e elementos funcionais como estados ocultos.
Técnicas Relacionadas
O algoritmo de Viterbi está intimamente relacionado a outros métodos de programação dinâmica, como o algoritmo forward-backward, que calcula probabilidades sobre todas as sequências possíveis de estados em vez de apenas a mais provável. Ele também compartilha fundamentos conceituais com Beam Search, uma técnica de busca heurística usada na geração de sequências. Em sistemas modernos de Machine learning e Artificial intelligence, especialmente aqueles que envolvem modelos Sequence-to-Sequence (Seq2Seq) e Large language models, a busca em feixe é frequentemente preferida à decodificação exata de Viterbi devido aos grandes espaços de estados envolvidos.
Apesar do aumento de abordagens baseadas em Neural network, o algoritmo de Viterbi permanece relevante em sistemas híbridos. Por exemplo, ele pode ser usado para decodificar saídas de modelos acústicos baseados em Neural network no reconhecimento de fala, ou para impor restrições estruturais em tarefas de Natural language processing. Sua clareza matemática e eficiência garantem seu uso contínuo em aplicações clássicas e contemporâneas.