Algorithme de Viterbi | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

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.

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (8)

Personnes associées (5)

Concepts associés (17)

Cours associés (18)

Séances de cours associées (63)

Analysis of the BIKE post-quantum cryptographic protocols and the Legendre pseudorandom function

Dusan Kostic

The field of post-quantum cryptography studies cryptographic systems that are secure against an adversary in possession of a quantum computer. In 2017, the National Institute of Standards and Technolo

EPFL2020

Gaussian channel transmission of images and audio files using cryptcoding

Vladimir Ilievski

Random codes based on quasigroups (RCBQ) are cryptcodes, i.e. they are error-correcting codes, which provide information security. Cut-Decoding and 4-Sets-Cut-Decoding algorithms for these codes are d

2019

Fixed-wing drones for communication networks

Maja Varga

In the last decade, drones became frequently used to provide eye-in-the-sky overview in the outdoor environment. Their main advantage compared to the other types of robots is that they can fly above o

EPFL2016

COM-302: Principles of digital communications

This course is on the foundations of digital communication. The focus is on the transmission problem (rather than being on source coding).

FIN-417: Quantitative risk management

This course is an introduction to quantitative risk management that covers standard statistical methods, multivariate risk factor models, non-linear dependence structures (copula models), as well as p

EE-554: Automatic speech processing

The goal of this course is to provide the students with the main formalisms, models and algorithms required for the implementation of advanced speech processing applications (involving, among others,

Hidden Markov Modèles: Primer

Introduit des modèles de Markov cachés, expliquant les problèmes de base et les algorithmes comme Forward-Backward, Viterbi et Baum-Welch, en mettant laccent sur lattente-Maximisation.

Théorie du MCMC

Couvre la théorie de l'échantillonnage de Markov Chain Monte Carlo (MCMC) et discute des conditions de convergence, du choix de la matrice de transition et de l'évolution de la distribution cible.

Risque global : Mesures de risque cohérentes

Examine l'importance des risques globaux et des mesures cohérentes des risques, y compris leur interprétation et leurs implications.

Modèle de Markov caché

Un modèle de Markov caché (MMC, terme et définition normalisés par l’ISO/CÉI [ISO/IEC 2382-29:1999]) — (HMM)—, ou plus correctement (mais non employé) automate de Markov à états cachés, est un modèle statistique dans lequel le système modélisé est supposé être un processus markovien de paramètres inconnus. Contrairement à une chaîne de Markov classique, où les transitions prises sont inconnues de l'utilisateur mais où les états d'une exécution sont connus, dans un modèle de Markov caché, les états d'une exécution sont inconnus de l'utilisateur (seuls certains paramètres, comme la température, etc.

Algorithme de Viterbi

Probabilistic context-free grammar

Grammar theory to model symbol strings originated from work in computational linguistics aiming to understand the structure of natural languages. Probabilistic context free grammars (PCFGs) have been applied in probabilistic modeling of RNA structures almost 40 years after they were introduced in computational linguistics. PCFGs extend context-free grammars similar to how hidden Markov models extend regular grammars. Each production is assigned a probability.