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

Introduction

Mise en situation :

Nous sommes à 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 bases : 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.

Image illustrant les chaines de Markov dans le cas de la météo.

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 (Soleil, Nuage 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.
Dans notre exemple, la météo réelle correspond à la séquence cachée, nous ne pouvons l'observer directement. La seule chose que nous connaissions c'est le taux d'humidité que l'on nomme observations. Le but du modèle de Markov est donc de deviner la séquence cachée (la météo : Soleil, Nuage ou Pluie) uniquement à partir de la séquence d'observations (humidité).

2 - L'impasse : 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.

Image illustrant le fonctionnement de l'algorithme naïf.

2. 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.
3. 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 $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 rend la tache techniquement très compliquée. Le temps de calcul et la mémoire requise croissent de manière exponentielle avec le nombre de jours observés.

Modélisation de la courbe associée à É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} .
Sur cette image, nous pouvons voir l'explosivité du nombre de chemins à calculer en fonction du nombre de jours (en abscisse).

3 - La solution, l'algorithme de Viterbi

C'est dans ce contexte, qu'Andrew Viterbi a une idée brillante. En algorithmique, éliminer les chemins "aberrants" pour gagner du temps est une technique classique. Ici, le principe de Viterbi repose sur la conservation d'un petit nombre de chemins suffisant pour être certain que le chemin optimal s'y trouve.

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. Pour illustrer ce qui a été dit précédemment, voici des images qui illustrent un exemple.

Image illustrant l'initialisation de l'algorithme de Viterbi sur la météo.

Image illustrant le début de la récurrence de l'algorithme de Viterbi sur la météo.

Image illustrant la fin de la récurrence de l'algorithme de Viterbi sur la météo.

Image illustrant la remontée de l'algorithme de Viterbi sur la météo.

4 - L'application en communications : Le 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 boite3, l'ancien bit de la boite1 passe dans la boite2 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 boite3, boite2 et boite1 et la sortie B réalise un XOR entre la boite1 et la boite2.
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.

Image illustrant le fonctionnement du code de convolution.

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 - La réparation du message par Viterbi

Pour réparer un message bruité, nous avons eu deux approches différentes que nous allons vous présenter :

5.1 - Viterbi via un dictionnaire

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}]

Modélisation de cette liste en Python.
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 :

Capture d'écran depuis un terminal exécutant le code python de notre projet.
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 - Viterbi via des tableau de probabilité

Une autre méthode pour retrouver un message après qu’il y ait eu des perturbations consiste à constituer des tableaux de probabilités, de la même manière que nous l’avons fait avec la météo. Pour cela, on prend comme états cachés les blocs de trois bits sur lesquels on va utiliser le code de convolution, et comme observations les deux bits de sortie du code de convolution.

Comme on peut le voir sur ce tableau, il y a une chance sur deux que le bloc suivant à partir de 000 soit 100 ou 000. Cela est logique, car en se décalant vers la gauche, le bloc ne peut recevoir qu’un nouveau bit, qui peut être soit 1, soit 0.

Dans ce deuxième tableau, on voit les probabilités qu’une paire de bits provienne d’un bloc de trois bits, en prenant en compte les changements possibles d’un ou plusieurs bits lors du transfert du message.

Ensuite, il suffit d’utiliser l’algorithme de Viterbi avec ces tableaux de probabilités pour trouver le message le plus probable.

Un exemple :

Comme on peut le voir sur cette capture d’écran, même avec des perturbations(changements de bits) sur les bits encadrés en rouge, on arrive quand même à retrouver le message initial

Limites :

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 essentiel à la conquête spatiale et toujours au coeur de nos technologie modernes, 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