Algorithme de Viterbi et modèles de Markov cachés
Introduction
A la fin des années 1970, la course à l’espace prend une nouvelle tournure. La compétition ne porte plus sur qui atteindra la lune en premier mais sur l’exploration du reste du système solaire, bien plus lointain. Les sondes sont équipées d’émetteurs très faibles et la distance qui sépare les sondes des antennes terrestres est très grande induisant des messages très parasités.
Une question se pose alors : comment arriver à décrypter ces messages totalement bruités ?
En 1960, on commence à inventer des algorithmes qui permettent d’encoder des messages dans le but de pouvoir retrouver le message original en dépit d’altérations mais il est très ardu de les décoder. L’attention se porte alors sur un algorithme créé en 1967 par un Américain, Andrew Viterbi. Son algorithme permet de décoder ces messages bien plus rapidement et de retrouver les messages d'origine bien qu’ils aient été altérés. Cet algorithme que nous allons vous présenter a donc eu un usage dans la conquête spatiale, dans les réseaux 2G/3G, dans la wifi, les disques durs etc… Et continue de servir dans la génétique et les objets connectés (bluetooth) notamment.
2 - Le décodage Naïf
Une fois notre modèle de Markov posé, on se demande comment est-ce qu'il est possible de retrouver la séquence cachée la plus probable.
Une première approche, sans doute la plus intuitive, consisterait à employer la force brute. Puisque nous cherchons le meilleur chemin, il "suffit" de tous les parcourir, calculer leur probabilité individuelle et retenir celui avec la plus grosse probabilité.
C'est exactement ce que nous avons implémenté en Python. Pour y parvenir nous avons utilisé plusieurs méthode :
- Nous avons d'abord créé une fonction qui génère toutes les combinaisons possibles en fonction du nombre de jours observés.
- Pour chaque chemin qui a été créé, la fonction calcule la probabilité en tenant compte de la probabilité de transition d'un jour à l'autre et de la probabilité d'observation.
- La fonction renvoie le chemin ayant obtenu le score maximal.
Dans la théorie cette méthode marche parfaitement. Pourtant elle a un problème majeur, si n est un nombre de jour, la fonction doit calculer 3 puissance n chemins. Au bout d'un mois, l'ordinateur doit calculer plus de 200 mile milliards de chemins ce qui est problématique si l'on souhaite calculer des séquences contenant de nombreux jours, au-delà d'un gros problème d'optimisation.
Mettre photo ???????????////////////