Algorithme de Viterbi et modèles de Markov cachés

Introduction

Contexte :

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 : à partir d'une séquence de données altérées que l'on reçoit, comment retrouver la séquence d'informations d'origine ayant été émise ?

Origine de l'algorithme :

En 1960, on commence à inventer des algorithmes qui permettent d’encoder des messages afin de pouvoir retrouver le message original en dépit d’altérations. Cependant, 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.

Usage :

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 le wifi, les disques durs etc… Et continue de servir dans la génétique et les objets connectés (bluetooth) notamment.
Mais avant de comprendre comment fonctionne l'algorithme de Viterbi, il nous faut d'abord introduire deux outils mathématiques sur lesquels il repose : les chaînes de Markov et les modèles de Markov cachés.

1 - les chaînes de Markov et les modèles de Markov cachés

Une chaîne de Markov est un moyen de représenter les probabilités de passer d'un état à un autre. La propriété fondamentale de ces chaînes est que la probabilité d'aller vers un état futur ne dépend que de l'état présent, et non de tout ce qui s'est passé avant.

Prenons comme exemple la météo : en observant le temps qu'il fait jour après jour, on peut estimer la probabilité qu'il pleuve après une journée ensoleillée, ou inversement, et ainsi obtenir un graphe probabiliste qui représentera notre chaîne de Markov.

Cependant, dans des conditions réelles, si l’on veut estimer la météo à un endroit où l’on ne se trouve pas, on va plutôt se baser sur des relevés météorologiques comme l’humidité, la pression atmosphérique ou la température.
C'est ce que l'on appelle le modèle de Markov caché : le principe est de se baser sur nos observations pour en déduire l'état réel. Dans notre exemple, la météo réelle (beau temps ou pluie) est « cachée ». On dispose seulement d'indices comme l'humidité, la pression, la température qui nous permettent de l'estimer.
Un modèle de Markov caché repose donc sur deux types de probabilités, les probabilités qui décrivent comment le système passe d'un état caché à un autre, et les probabilités qui décrivent la chance qu'un état donné produise une observation particulière.

2 - L'algorithme 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éthodes :

1. Nous avons d'abord créé une fonction qui génère toutes les combinaisons possibles en fonction du nombre de jours observés.

1. 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.
2. 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 jours, la fonction doit calculer Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 3^n} chemins. En effet, pour le jour 1, nous avons 3 climats possibles, pour le jour 2, chaque climat s'ouvre sur 3 nouvelles branches, etc... Au bout d'un mois, l'ordinateur doit calculer Échec de l’analyse (SVG (MathML peut être activé via une extension du navigateur) : réponse non valide(« Math extension cannot connect to Restbase. ») du serveur « https://wikimedia.org/api/rest_v1/ » :): {\displaystyle 3^{30}} chemins soit plus de 200 mille 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.

Sur cette image, nous pouvons voir l'explosivité du nombre de chemins à calculer en fonction du nombre de jours (en abscisse).

3 - L'algorithme de Viterbi

C'est dans ce contexte, qu'Andrew Viterbi a une idée de génie. Plutôt que de tout devoir calculer à chaque fois, pourquoi ne pas éliminer les chemins les plus aberrants ?

Une petite analogie pour mieux comprendre

Imaginons que nous ayons la folle idée de quitter la Savoie pour aller à Paris et que nous cherchons le meilleur itinéraire pour y aller.
Si notre gps suivait un algorithme naïf, il calculerait tous les chemins possibles pour y aller, incluant des chemins totalement incohérents comme un chemin qui passerait par Marseille par exemple.

Si notre gps utilisait Viterbi, il ne calculerait pas d'itinéraire par Marseille car il se rendrait directement compte que cela n'a aucun sens. Si nous comparons cette analogie à notre système de météo où nous observerions une série discontinue d'un climat très sec, il n'y aurait pas de sens de calculer la probabilité qu'il ait plu tous les jours.

Notre implémentation

L'algorithme avance de jour en jour. Imaginons que nous soyons au jour 2 et qu'on regarde l'état Soleil. Pour y arriver, il n'y a que trois provenances possibles, soit Soleil soit nuage, soit pluie. On calcule le score partiel de ces trois routes, on le compare et on garde la meilleure en l'inscrivant sur le dictionnaire. On répète cela pour chaque jour jusqu'à la fin en ayant gardé que 3 chemins en mémoire à chaque fois.
Une fois qu'on arrive au bout des jours, nous avons 3 chemins, nous choisissons le meilleur des 3 et nous remontons pour calculer la séquence complète.//// //////METTRE PHOTO

4 - Le fonctionnement du code de Convolution

Dans l'espace, des radiations peuvent frapper le signal radio et inverser certains bits. Ce phénomène existe aussi sur terre lié à de nombreuses interférences. C'est dans ce contexte qu'apparait le code de Convolution. Son but est de rajouter des bits supplémentaires au message afin de pouvoir retrouver le message original si des bits ont été touchés. Comme mentionné en introduction, il n'est pas très compliqué d'encoder des messages à l'aide du code de convolution. En revanche, avant Viterbi, il était complexe de le déchiffrer. Nous allons donc voir comment Viterbi intervient ici.

Avant de vouloir utiliser Viterbi pour décoder un message, il est nécessaire de savoir encoder des messages. Nous avons donc créé une fonction qui permet d'encoder des messages. Mais alors comment est-ce que ça marche ?

1. L'état initial. La machine possède 3 sortes de boites (boite1, boite2 et boite3) qui sont initialisées à 0.
2. La machine lit chaque bit du message un par un. A chaque fois qu'un bit arrive, les anciens bits sont décalés (le bit qui était dans la boite2 passe dans la boite 3, l'ancien bit de la boite 1 passe dans la boite 2 et le nouveau bit entre dans la boite1.
3. Deux sorties (sortie A et sortie B) sont reliées aux boites. La sortie A réalise un XOR entre la boite 3, 2 et 1 et la sortie B réalise un XOR entre les boites 1 et 2.
4. Pour chaque bit qui rentre, l'algorithme crée deux bits de sortie (sortie A et sortie B), le message doublera donc de taille.

Nous avons donc couvert le fonctionnement global de cet encodage. Ce qui le rend puissant c'est sa "mémoire". Du fait que ces boites existent, un bit qui rentre va influencer les xor sur trois tours (entre son entrée en boite1 et sa sortie de la boite3) ce qui permet de retrouver le message original en cas de détérioration du message.

5.1 Décryptage à l'aide de Viterbi (version Antoine) :

Maintenant que nous savons comment encoder un message à l'aide du code de convolution, nous allons tenter de le décoder à l'aide de Viterbi. A la différence de la météo, ici nous n'avons pas de probabilité. En revanche, nous avons des états possibles. Pour un état de mémoire donné et un bit entrant donné, les bits sortants (calculés par les deux xor) sont figés. Grâce à cela, il est possible de dresser une liste exhaustive de tous les états autorisés par la machine que l'on donne en dessous.

  [{'depart': '00', 'arrivee': '00', 'bits_emis': [0, 0], 'bit_arrivant': 0},
   {'depart': '00', 'arrivee': '10', 'bits_emis': [1, 1], 'bit_arrivant': 1},
   
   {'depart': '01', 'arrivee': '00', 'bits_emis': [1, 0], 'bit_arrivant': 0},
   {'depart': '01', 'arrivee': '10', 'bits_emis': [0, 1], 'bit_arrivant': 1},
   
   {'depart': '10', 'arrivee': '01', 'bits_emis': [1, 1], 'bit_arrivant': 0},
   {'depart': '10', 'arrivee': '11', 'bits_emis': [0, 0], 'bit_arrivant': 1},
   
   {'depart': '11', 'arrivee': '01', 'bits_emis': [0, 1], 'bit_arrivant': 0},
   {'depart': '11', 'arrivee': '11', 'bits_emis': [1, 0], 'bit_arrivant': 1}]

Par exemple, si la machine est dans l'état '00' (indiqué par 'depart'), il n'existe que deux possibilités, l'algorithme ne peut émettre que [0, 0] ou [1, 1] (lu dans 'bits_emis'). Ainsi, dans ce cas, si l'on reçoit [1, 0] on sait tout de suite qu'il y a un problème.

Grâce à cette liste, l'algorithme peut parcourir les différentes possibilités en ne sélectionnant que celles qui ont le minimum d'erreurs. Une fois qu'il a trouvé la meilleure "branche", il lui suffit de tout remonter en lisant les "bit_arrivant" (inscrits dans la liste) pour reconstituer le message.

Un exemple :

Pour illustrer le fonctionnement final du code, on peut observer la capture d'écran du code ci-dessus. On commence par créer un message que l'on souhaite envoyer ('message_original'). Ensuite on lui fait subir l'encodage de convolution et on altère un bit. A la fin on observe bien que le message d'origine a été retrouvé en dépit de cette dégradation.

5.2 Décryptage à l'aide de Viterbi (version Gaspard) :

Ecrire ici

Ouverture :

Le code de convolution que nous avons implémenté possède 3 boites, un bit influence donc les sorties sur 3 tours. Ce code a donc une résilience assez limitée (si on change plusieurs bits collés, le code ne fonctionne plus). Dans l'exemple de la nasa cité en introduction, ils utilisaient un code de convolution à 7 boites de mémoire ayant ainsi une très grande résilience.

Conclusion :

A travers ce projet, nous avons pu découvrir l'algorithme de Viterbi, un outil aux multiples applications encore largement utilisé aujourd'hui. Nous avons d'abord pu tester l'approche naïve, intuitive mais très peu optimisée. De là nous avons pu résoudre ce défaut grâce à l'algorithme de Viterbi.

Travailler sur cet algorithme qui fait partie de notre vie de tous les jours mais aussi de l'exploration spatiale, a été passionnant pour nous deux. Nous souhaitons donc remercier sincèrement notre tuteur, M. Sebastien Tavenas, qui a nous permis de réaliser ce projet.

Merci pour cette lecture,

Antoine Garcia, Gaspard Perrin