eBabylone
.com
|
Un article de Wikipedia.y-project.com.L'algorithme de Viterbi, de Andrew Viterbi, permet de corriger les erreurs survenues lors d'une transmission à travers un canal bruité (dans une certaine mesure).
Cet algorithme a pour but de trouver la séquence d'états la plus probable ayant produit la séquence mesurée. [] PrincipeSoit 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 conséquente, 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 <math>a^n</math> (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. [] ApplicationsL'application la plus courante est évidemment la restauration de transmissions numériques (détériorées à travers des vecteurs non fiables par exemple) en s'appuyant sur la distance de Hamming afin de faire ressortir la plus faible métrique entre les différentes valeurs probables. En général, 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). [] ExempleImaginons un canal bruité qui supprime tous les accents d'un texte. À partir du message m : « Université » on observe le message o : « Universite ». Plusieurs messages ont pu conduire à cette observation :
On peut connaître la probabilité de chaque lettre en s'intéressant à sa probabilité d'apparition dans la langue française et l'on peut affiner cette probabilité en cherchant la probabilité qu'une lettre apparaisse alors 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 que l'on a eu X -- cf image).
Image:Viterbi-grand.png 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 l'on obtient pour chaque n?ud la valeur <math>\lambda_1 P(X) + \lambda_2 P(Y/X) + \lambda_3 P(Z/XY) + ...</math> avec <math> \lambda_0 + \lambda_1 + \lambda_2 + ... + \lambda_n = 1</math> (n correspondant au degré de n-gramme désiré), puisque l'on s'intéresse à une probabilité, donc comprise entre zéro et un (pour l'exemple, les valeurs <math>\lambda_1 = 0.9</math> et <math>\lambda_2 = 0.1</math> semblent optimale). En regardant l'arbre, on se rend compte rapidement que les probabilités du troisième étage (pour le caractère observé « i ») sont identiques et ne dépendent que de l'étage précédent. De même, les sous-arbres de ces n?uds seront identiques, il est donc inutile de dérouler les sous-arbres sous les branches de plus faible probabilité puisque l'on est sûr que la probabilité totale des branches engendrées sera plus faible. Par 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 donc 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 donc élaguer l'arbre en les supprimant et continuer le calcul sur les branches restantes (suppression de la moitié des possibilités à chaque étape). DernierMirror La source est wikipedia http://fr.wikipedia.org/wiki/ algorithme de Viterbi |
Revue de presse algorithme_de_Viterbi
Server 2.0