Processus de Markov et modèles de capteur

Tous les modèles vus jusqu’ici décrivaient un monde qui reste immobile pendant que vous raisonnez sur lui. Voici que le monde change, et que vous l’observez à travers un capteur qui ment parfois. L’appareillage nécessaire se révèle être le réseau bayésien du parcours précédent, déroulé dans le temps et rendu répétitif à dessein.

État et évidence

Séparez les variables en deux.

• $\mathbf{X}_t$ est l’état à l’instant $t$ : ce qui est effectivement vrai, et que vous ne pouvez pas observer.
• $\mathbf{E}_t$ est l’évidence à l’instant $t$ : ce que rapportent vos capteurs. L’observation est $\mathbf{E}_t = \mathbf{e}_t$.

Le temps est découpé en pas de taille fixe, si bien que $t$ compte des tranches plutôt que des secondes. L’intervalle est un choix de modélisation ; les algorithmes s’en moquent.

Le monde du parapluie

L’exemple de Russell et Norvig est délibérément minuscule. Vous êtes gardien de sécurité dans une installation souterraine. Vous voulez savoir s’il pleut aujourd’hui, et votre seul contact avec le monde extérieur est de voir le directeur arriver chaque matin avec ou sans parapluie. Ainsi $R_t$ (pluie aujourd’hui) est l’état, $U_t$ (parapluie aujourd’hui) est l’évidence, et tout le problème consiste à inférer une variable cachée à partir d’un indicateur indirect.

$$\begin{array}{ll} P(R_0) = \langle 0.5,\ 0.5 \rangle & \\[4pt] P(r_t \mid r_{t-1}) = 0.7 & P(r_t \mid \lnot r_{t-1}) = 0.3 \\[4pt] P(u_t \mid r_t) = 0.9 & P(u_t \mid \lnot r_t) = 0.2 \end{array}$$

Lisez ces trois blocs comme un a priori, un modèle de transition et un modèle de capteur. La pluie persiste : un jour pluvieux est suivi d’un autre avec probabilité $0.7$. Le directeur est un indicateur correct mais imparfait : il porte un parapluie $90\%$ des jours de pluie, et $20\%$ des jours secs tout de même.

Deux hypothèses

Un historique n’a pas de longueur bornée, si bien que $P(\mathbf{X}_t \mid \mathbf{X}_{0:t-1})$ fait intervenir une loi conditionnelle dont l’ensemble des parents croît sans limite. Deux hypothèses le rabotent.

L’hypothèse de Markov. L’état courant ne dépend de l’historique qu’à travers un nombre borné d’états précédents. En n’en prenant qu’un, on obtient un processus de Markov d’ordre un :

$$\mathbf{P}(\mathbf{X}_t \mid \mathbf{X}_{0:t-1}) = \mathbf{P}(\mathbf{X}_t \mid \mathbf{X}_{t-1}).$$

L’hypothèse de Markov sur les capteurs. La mesure courante ne dépend que de l’état courant :

$$\mathbf{P}(\mathbf{E}_t \mid \mathbf{X}_{0:t}, \mathbf{E}_{0:t-1}) = \mathbf{P}(\mathbf{E}_t \mid \mathbf{X}_t).$$

Toutes deux sont des affirmations sur l’état, non sur la physique ou le matériel. Si la mesure d’hier vous apprend encore quelque chose sur celle d’aujourd’hui une fois l’état d’aujourd’hui connu, c’est qu’il manque quelque chose à votre variable d’état.

Quand l’hypothèse est fausse, élargissez l’état. Si la pluie d’aujourd’hui dépend réellement des deux jours précédents, vous avez deux remèdes. Augmenter l’ordre du modèle, en laissant $R_t$ dépendre de $R_{t-1}$ et de $R_{t-2}$ ; ou le garder d’ordre un et enrichir l’état, en ajoutant $\mathit{Season}_t$ ou $\mathit{Pressure}_t$ de sorte que la dépendance supplémentaire passe par une variable plutôt que par le temps. Le second est en général meilleur, parce qu’il énonce quelque chose sur le monde plutôt qu’il ne rapièce.

Nous supposons aussi que le processus est stationnaire : les modèles de transition et de capteur sont les mêmes à chaque pas. C’est ce qui permet à deux petites tables de décrire un historique de longueur quelconque. Stationnaire ne veut pas dire statique - le monde change, ce sont les lois qui ne changent pas.

La loi jointe

Avec ces hypothèses, le modèle est un réseau bayésien ordinaire dans lequel le seul parent de chaque état est l’état précédent et le seul parent de chaque observation est son propre état. La sémantique est celle du parcours précédent :

$$P(\mathbf{X}_{0:t}, \mathbf{E}_{1:t}) \;=\; P(\mathbf{X}_0) \prod_{i=1}^{t} P(\mathbf{X}_i \mid \mathbf{X}_{i-1})\, P(\mathbf{E}_i \mid \mathbf{X}_i).$$

Trois facteurs décrivent un historique de longueur quelconque, et c’est là tout le bénéfice.

Exemple travaillé : la probabilité d’un historique

Supposons qu’il pleuve les deux jours et que le parapluie apparaisse les deux fois. En lisant une entrée par facteur :

$$\begin{aligned} P(r_1, r_2, u_1, u_2) &= \underbrace{\textstyle\sum_{r_0} P(r_1 \mid r_0) P(r_0)}_{0.7 \times 0.5 + 0.3 \times 0.5 \,=\, 0.5} \times P(u_1 \mid r_1) \times P(r_2 \mid r_1) \times P(u_2 \mid r_2) \\ &= 0.5 \times 0.9 \times 0.7 \times 0.9 \\ &= 0.2835 . \end{aligned}$$

Parce que tout historique a une probabilité, toute question sur le monde a une réponse : sommez les historiques qui s’accordent avec elle. C’est correct et sans espoir - il y en a $2^t$. La leçon suivante explique comment ne pas les énumérer.

Voici cette chaîne avec ses entrées. Chaque flèche porte l’unique entrée de table qu’elle apporte, et le produit en dessous est l’historique que vous avez choisi : changez un jour, et exactement deux entrées bougent. Le compte à côté est le prix de la réponse honnête, et il double à chaque jour ajouté. Le panneau du bas énonce l’hypothèse de Markov sur le capteur en quatre nombres, car c’est celle que l’on sur-interprète : le parapluie d’hier dit bel et bien quelque chose sur celui d’aujourd’hui, et cesse de rien dire dès que la pluie d’aujourd’hui est connue.

Les quatre questions

Tout ce que fait le reste de ce parcours se range dans quatre tâches.

• Filtrage : $\mathbf{P}(\mathbf{X}_t \mid \mathbf{e}_{1:t})$, la croyance sur le présent étant donné tout ce qui précède. C’est ce qu’entretient un agent en fonctionnement.
• Prédiction : $\mathbf{P}(\mathbf{X}_{t+k} \mid \mathbf{e}_{1:t})$ pour $k > 0$, la croyance sur un état futur.
• Lissage : $\mathbf{P}(\mathbf{X}_k \mid \mathbf{e}_{1:t})$ pour $k < t$, une meilleure estimation d’un état antérieur, obtenue avec le recul.
• Explication la plus probable : $\operatorname*{argmax}_{\mathbf{x}_{1:t}} P(\mathbf{x}_{1:t} \mid \mathbf{e}_{1:t})$, l’unique historique qui explique le mieux les observations.

Les trois premières partagent une même récursion. La quatrième, de façon trompeuse, non.

Avant le quiz

Sachez séparer l’état de l’évidence, énoncer les deux hypothèses de Markov et dire quel objet chacune contraint, écrire la loi jointe comme un produit de facteurs a priori, de transition et de capteur, et nommer les deux remèdes quand l’hypothèse s’ajuste mal.