L'algorithme de Viterbi est un algorithme de programmation dynamique qui identifie la séquence la plus probable d'états cachés ayant pu produire une séquence donnée d'événements observés. La séquence résultante est souvent appelée le chemin de Viterbi. Il est le plus couramment appliqué aux modèles de Markov cachés (HMM), où les états sous-jacents ne sont pas directement observables mais influencent les observations. Par exemple, un médecin observant les symptômes d'un patient sur plusieurs jours pourrait utiliser l'algorithme pour déduire la séquence la plus probable de conditions de santé sous-jacentes ayant causé ces symptômes.
L'algorithme a trouvé une application universelle dans le décodage des codes convolutifs utilisés dans les réseaux cellulaires numériques CDMA et GSM, les modems à connexion commutée, les communications par satellite et dans l'espace lointain, ainsi que les LAN sans fil 802.11. Il est également largement utilisé dans la reconnaissance vocale, la synthèse vocale, la diarisation des locuteurs, la détection de mots-clés, la linguistique computationnelle et la bioinformatique. Dans les systèmes de transcription vocale, le signal acoustique sert de séquence observée, et la chaîne de texte est la cause cachée ; l'algorithme de Viterbi trouve le texte le plus probable étant donné le signal acoustique.
Historique
L'algorithme de Viterbi est nommé d'après Andrew Viterbi, qui l'a proposé en 1967 comme algorithme de décodage pour les codes convolutifs sur des liaisons de communication numériques bruitées. Il a une histoire d'invention multiple, avec au moins sept découvertes indépendantes, y compris celles de Viterbi, Needleman et Wunsch, et Wagner et Fischer. Il a été introduit dans le traitement du langage naturel comme méthode d'étiquetage morpho-syntaxique dès 1987.
Les termes « chemin de Viterbi » et « algorithme de Viterbi » sont devenus standards pour les approches de programmation dynamique aux problèmes de maximisation impliquant des probabilités. En analyse syntaxique statistique, un algorithme de programmation dynamique peut découvrir la dérivation hors-contexte la plus probable (analyse) d'une chaîne, communément appelée « analyse de Viterbi ». Une autre application est le suivi de cibles, où l'algorithme calcule la piste qui attribue la probabilité maximale à une séquence d'observations.
Aperçu de l'algorithme
Étant donné un modèle de Markov caché avec un ensemble d'états cachés S, un ensemble d'émissions possibles (observations) M, et une séquence de T observations o0, o1, ..., oT-1, l'algorithme de Viterbi trouve la séquence la plus probable d'états cachés ayant pu produire ces observations. À chaque pas de temps t, l'algorithme résout le sous-problème où seules les observations jusqu'à ot sont considérées.
Deux matrices de taille T × |S| sont construites. La matrice Pt,s contient la probabilité maximale de se retrouver à l'état s à l'observation t, parmi toutes les séquences possibles d'états y menant. La matrice Qt,s suit l'état précédent qui a été utilisé avant s dans cette séquence d'états à probabilité maximale.
Soient πs et ar,s les probabilités initiales et de transition respectivement, et bs,o la probabilité d'observer o à l'état s. Alors les valeurs de P sont données par une relation de récurrence. Au temps t = 0, Pt,s est égal à πs multiplié par bs,o0. Pour t > 0, Pt,s est égal au maximum sur tous les états précédents r de (Pt-1,r × ar,s × bs,ot). Après avoir rempli les matrices, l'algorithme effectue un retour en arrière à partir de l'état avec la probabilité la plus élevée au dernier pas de temps en utilisant la matrice Q pour reconstruire la séquence d'états la plus probable.
Applications dans les communications
L'algorithme est une pierre angulaire des communications numériques modernes. Il décode les codes convolutifs, qui sont des codes de correction d'erreurs utilisés dans de nombreux systèmes sans fil et filaires. Dans les réseaux cellulaires CDMA et GSM, l'algorithme de Viterbi aide à récupérer les données transmises malgré le bruit et les interférences. Les modems à connexion commutée, les liaisons par satellite et les systèmes de communication dans l'espace lointain s'appuient également sur lui. La norme LAN sans fil 802.11 intègre le décodage de Viterbi pour une transmission de données fiable.
L'efficacité de l'algorithme provient de sa nature de programmation dynamique : il évite l'énumération exhaustive de toutes les séquences d'états possibles en stockant les probabilités intermédiaires et en utilisant le principe d'optimalité. Cela rend possible le décodage de longues séquences en temps réel, même sur des appareils à ressources limitées.
Applications dans la parole et le langage
En reconnaissance vocale, l'algorithme de Viterbi aligne les caractéristiques acoustiques avec les modèles phonétiques ou de mots. Le signal acoustique est la séquence observée, et la chaîne de texte est la cause cachée. L'algorithme trouve la chaîne de texte la plus probable étant donné le signal acoustique, permettant une transcription précise. Il est également utilisé en synthèse vocale pour sélectionner la séquence la plus naturelle d'unités de parole, et en diarisation des locuteurs pour déterminer qui a parlé quand.
En linguistique computationnelle, l'algorithme est appliqué à l'étiquetage morpho-syntaxique, où les états cachés sont des catégories grammaticales et les observations sont des mots. Il soutient également l'analyse syntaxique statistique, où il trouve l'arbre d'analyse le plus probable pour une phrase. En bioinformatique, il aide à aligner des séquences biologiques et à prédire des structures géniques, traitant les séquences d'ADN ou de protéines comme des observations et les éléments fonctionnels comme des états cachés.
Techniques connexes
L'algorithme de Viterbi est étroitement lié à d'autres méthodes de programmation dynamique, comme l'algorithme forward-backward, qui calcule des probabilités sur toutes les séquences d'états possibles plutôt que seulement la plus probable. Il partage également des fondements conceptuels avec la recherche en faisceau, une technique de recherche heuristique utilisée dans la génération de séquences. Dans les systèmes modernes de apprentissage automatique et d'intelligence artificielle, en particulier ceux impliquant des modèles séquence-à-séquence et des grands modèles de langage, la recherche en faisceau est souvent préférée au décodage exact de Viterbi en raison des grands espaces d'états impliqués.
Malgré l'essor des approches par réseaux de neurones, l'algorithme de Viterbi reste pertinent dans les systèmes hybrides. Par exemple, il peut être utilisé pour décoder les sorties de modèles acoustiques basés sur des réseaux de neurones en reconnaissance vocale, ou pour imposer des contraintes structurelles dans des tâches de traitement du langage naturel. Sa clarté mathématique et son efficacité garantissent son utilisation continue dans des applications classiques et contemporaines.