Algorithme de Viterbi

L'algorithme de Viterbi, d'Andrew Viterbi, sert à corriger les erreurs survenues lors d'une transmission à travers un canal bruité.



Catégories :

Algorithme - Théorie de l'information - Traitement numérique du signal - Détection et correction d'erreur

Page(s) en rapport avec ce sujet :

  • Le critère du maximum de probabilité a poste- riori est adopté comme critère de décision : le déco-... dement dans l'arbre. Par contre, le volume de calcul, ... thme de pile et l'algorithme de Viterbi est que dans ... (source : documents.irevues.inist)
  • de decodage sous-optimal, avec une probabilite de bit en erreur qui augmente considerablement quand le canal... En effet, I'algorithme de Viterbi est un dtcodeur h... utilise une structure en arbre ou en treillis avec un nombre M... (source : ieeexplore.ieee)

L'algorithme de Viterbi, d'Andrew Viterbi, sert à corriger les erreurs survenues lors d'une transmission à travers un canal bruité (dans une certaine mesure).

Son utilisation s'appuie sur la connaissance du canal bruité (la probabilité qu'une information ait été modifiée en une autre) et sert à simplifier radicalement la complexité de la recherche du plus probable message d'origine (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.

Principe

Soit un message m diffusé à travers un canal bruité connu (par exemple, qui supprime l'ensemble des 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 envisageables pour chaque unité (chaque lettre par exemple), la complexité du traitement est de an (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 indispensable de dérouler celles de plus faible probabilité dans la mesure où 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 ou 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 z, de trouver la séquence d'états x pour laquelle la probabilité a posteriori P (x | z) est maximale. L'algorithme de Viterbi donne la solution de ce problème d'estimation par maximum a posteriori.

Applications

L'application la plus courante est certainement la restauration de transmissions numériques, détériorées à travers un canal non fiable (transmission hertzienne par exemple) en s'appuyant sur la distance de Hamming pour faire ressortir la plus faible métrique entre les différentes valeurs probables. Généralement, cette méthode s'applique à de nombreux problèmes basés sur des évaluations statistiques de la pertinence des résultats (abondamment utilisé en traitement automatique des langues par exemple, cf exemple suivant).

Une des applications phares de l'algorithme est aussi l'estimation de la séquence d'états (cachés) la plus probable ayant été générée par un modèle de Markov caché (problème de décodage). La reconnaissance de la parole et la bio-informatique utilisent abondamment les modèles de Markov cachés et sont par conséquent aussi des domaines où l'algorithme de Viterbi trouve une application.

Exemple

Imaginons un canal bruité qui supprime l'ensemble des accents d'un texte. À partir du message m : «Université» on observe le message o : «Universite».

Plusieurs messages ont pu conduire à cette observation :

  • Ùnîvêrsîtê
  • Ùnîvêrsîtè
  • Ùnîvêrsîté
  • ...
  • Université
  • ...

On peut connaître la probabilité de chaque lettre en s'intéressant à sa probabilité d'apparition dans la langue française et on peut affiner cette probabilité en cherchant la probabilité qu'une lettre apparaisse tandis qu'elle est précédée d'une autre (et ainsi de suite), on parle d'unigrammes, de bigrammes, trigrammes...

On construit l'arbre suivant (avec les bigrammes, P (X) correspond à la probabilité de voir apparaître X, P (Y/X) est la probabilité d'avoir Y sachant qu'on a eu X -- cf image).

Déroulement de l'algorithme de Viterbi sur un exemple

La probabilité d'une branche est le produit de la probabilité de tous ses nœuds. À chaque nœud, on considère la probabilité de l'unigramme (P (X) ) et du bigramme (P (X/Y) ). Dans la pratique ces probabilités sont pondérées et normalisées et on obtient pour chaque nœud la valeur λ1P (X) + λ2P (Y / X) + λ3P (Z / XY) +... avec λ0 + λ1 + λ2 +... + λn = 1 (n correspondant au degré de n-gramme désiré), puisque on s'intéresse à une probabilité, par conséquent comprise entre zéro et un (pour l'exemple, les valeurs λ1 = 0.9 et λ2 = 0.1 semblent optimales).

En regardant l'arbre, on se rend compte rapidement que les probabilités du troisième étage (pour le caractère observé «i») sont semblables et ne dépendent que de l'étage précédent. De même, les sous-arbres de ces nœuds seront semblables, il est par conséquent inutile de dérouler les sous-arbres sous les branches de plus faible probabilité puisque on est sûr que la probabilité totale des branches génèrées sera plus faible.

A titre d'exemple, supposons que nous ayons obtenu comme probabilités au troisième étage de notre arbre :

Les sous-arbres en dessous du I de UNI et en dessous du I de ÙNI sont strictement équivalents, de même pour les sous-arbres en dessous du Î de UNÎ et du Î de ÙNÎ. On aura par conséquent les probabilités suivantes :

et

Quelle que soit la probabilité de chacun des sous-arbres, on se rend compte que certains seront plus faibles que d'autres rapidement, par exemple la branche (4) sera inférieure à la branche (2) et la branche (3) inférieure à la branche (1) . On peut par conséquent élaguer l'arbre en les supprimant et continuer le calcul sur les branches restantes (suppression de la moitié des possibilités à chaque étape).

Références

Liens externes

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Algorithme_de_Viterbi.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu