Algorithme de Viterbi

L'algorithme de Viterbi, d'Andrew Viterbi, permet de corriger, dans une certaine mesure, les erreurs survenues lors d'une transmission à travers un canal bruité. Son utilisation s'appuie sur la connaissance du canal bruité, c'est-à-dire la probabilité qu'une information ait été modifiée en une autre, et permet de simplifier radicalement la complexité de la recherche du message d'origine le plus probable. D'exponentielle, cette complexité devient linéaire. Cet algorithme a pour but de trouver la séquence d'états la plus probable ayant produit la séquence mesurée. Soit un message m diffusé à travers un canal bruité connu (par exemple, qui supprime tous les accents d'un texte) et le message o observé en sortie du canal. Pour retrouver le message d'origine, on cherche, à partir de o le message le plus probable. La méthode brute consiste à tester, pour chaque lettre de o la lettre la plus probable dans m en émettant l'hypothèse que le canal bruité n'a pas ajouté ni supprimé d'information. On obtient un arbre de taille importante, si n est la taille du message et a le nombre de modifications possibles pour chaque unité (chaque lettre par exemple), la complexité du traitement est de (ce qui rend le problème incalculable pour de grandes quantités de données). L'algorithme de Viterbi propose de simplifier l'arbre au fur et à mesure de sa construction. En effet, lors de son déroulement on se retrouve rapidement avec des branches proposant les mêmes substitutions, mais avec des probabilités différentes : il n'est pas nécessaire de dérouler celles de plus faible probabilité puisqu'elles ne peuvent plus être candidates pour décrire le message le plus probable. Ce principe simple est connu sous le nom de programmation dynamique. De manière plus générale, l'algorithme de Viterbi est utilisé dans les cas où le processus sous-jacent est modélisable comme une chaîne de Markov discrète à états finis. Le problème est alors, étant donné une séquence d'observation , de trouver la séquence d'états pour laquelle la probabilité a posteriori est maximale.