Modèle de Markov caché

Un modèle de Markov caché applique l’idée du réseau bayésien à un monde qui change. Les variables sont séparées en un état, qui est vrai mais inobservable, et une évidence, qui est observée et peu fiable. Le temps est découpé en tranches de taille fixe, et le processus est supposé stationnaire, c’est-à-dire que les deux mêmes lois conditionnelles s’appliquent à chaque pas. Russell et Norvig l’introduisent avec un gardien de sécurité qui ne peut pas voir le temps qu’il fait et doit inférer s’il pleut à partir du fait que son directeur arrive ou non avec un parapluie.

Ce sont les deux hypothèses qui rendent le modèle fini. L’hypothèse de Markov énonce que l’état courant ne dépend de tout l’historique qu’à travers l’état immédiatement précédent ; l’hypothèse de Markov sur les capteurs énonce que l’observation courante ne dépend que de l’état courant. Toutes deux portent sur la question de savoir si la variable d’état a été bien choisie, et non sur le capteur physique. Quand la première est en défaut, les remèdes habituels sont d’augmenter l’ordre du modèle ou, mieux, d’élargir l’état pour que la dépendance manquante passe par une variable plutôt que par le temps.

Sous ces hypothèses, la loi jointe sur un historique complet se factorise en un a priori, un facteur de transition par pas et un facteur d’observation par pas. Toute requête se ramène alors à l’une de quatre tâches. Le filtrage calcule la croyance sur l’état courant étant donné toute l’évidence accumulée, et c’est ce qu’entretient un agent en fonctionnement. La prédiction prolonge cette croyance dans le futur, où, faute d’évidence nouvelle, elle se relâche vers la distribution stationnaire de la chaîne et finit par ne plus porter aucune information. Le lissage estime un état antérieur à l’aide d’évidence arrivée par la suite, en multipliant le message progressif par un message rétrograde qui résume les observations plus tardives. Exécuter la passe progressive une fois puis balayer en sens inverse lisse une séquence entière en temps linéaire en sa longueur : c’est l’algorithme progressif-rétrograde.

La quatrième tâche est d’une autre nature. Demander l’unique séquence d’états la plus probable n’est pas demander l’état le plus probable à chaque pas, car une marginale somme sur tous les chemins passant par un état alors qu’une séquence est un seul chemin. Assembler les gagnants pas à pas peut donc produire une histoire moins probable qu’une autre, et l’algorithme de Viterbi existe pour optimiser sur des chemins entiers : c’est la récursion progressive dont la somme sur l’état précédent est remplacée par un maximum, plus un pointeur arrière à chaque pas pour pouvoir retrouver le chemin gagnant et non seulement sa probabilité. Quand l’état est continu plutôt que discret, le même cycle de prédiction et de mise à jour ne survit que pour des familles particulières ; le cas linéaire-gaussien donne le filtre de Kalman.

Dans le monde du parapluie, l’état est le fait qu’il pleuve, avec P(pluie aujourd’hui | pluie hier) = 0,7 et P(pluie aujourd’hui | sec hier) = 0,3, et le capteur est l’apparition d’un parapluie, avec P(parapluie | pluie) = 0,9 et P(parapluie | sec) = 0,2. En partant d’un a priori uniforme, un premier parapluie donne une croyance filtrée de ⟨0,818, 0,182⟩, et un second le lendemain donne ⟨0,883, 0,117⟩.

Lisser le jour 1 une fois le jour 2 observé le fait passer de 0,818 à 0,883, parce que le second parapluie rend la pluie plus probable au jour 2 et que la pluie persiste. Le message rétrograde qui porte cette information est ⟨0,69, 0,41⟩, dont la somme ne vaut pas un parce qu’il s’agit d’une vraisemblance et non d’une distribution.

Sur les observations pas de parapluie, parapluie, pas de parapluie, la probabilité lissée de pluie au jour 2 vaut 0,554, et pourtant la séquence la plus probable est « sec » les trois jours, à 0,402 contre 0,332 pour la suivante. La marginale rassemble sa masse à partir de quatre histoires distinctes ; la séquence gagnante concentre la sienne dans une seule.