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.
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 - 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é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.
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 jour, la fonction doit calculer 3 puissance n chemins. Au bout d'un mois, l'ordinateur doit calculer 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.

Mettre photo ???????????////////////

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 qu'il 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 des 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 - Une application de Viterbi, 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.

Fonctionnement du code de Convolution.

Avant de vouloir utiliser Viterbi pour décoder un message, il était 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 1, 2 et 3 et la sortie B réalise un XOR entre les boites 1 et 2.
4. Pour chaque bit qui rentre, l'algorithme créé 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.

Décryptage à l'aide de Viterbi.

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. Les bits produits par le code sont issus de deux xor. regles_transition =

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

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

]