Raisonner sur un monde qui change

Un réseau bayésien décrit un monde qui reste immobile. La plupart des mondes ne le font pas. Vous observez un patient, un marché ou une route à travers des capteurs bruités et intermittents, et ce qui vous importe ne cesse de bouger pendant que vous le regardez. Cet article porte sur l’appareillage nécessaire, et sur un endroit où l’approche évidente donne discrètement la mauvaise réponse.

A. Deux hypothèses

Séparez les variables en un état $\mathbf{X}_t$, qui est vrai mais caché, et une évidence $\mathbf{E}_t$, que vous observez. La difficulté est que $P(\mathbf{X}_t \mid \mathbf{X}_{0:t-1})$ a un ensemble de parents qui croît sans fin. Deux hypothèses le bornent.

L’hypothèse de Markov dit que l’état courant ne dépend de l’historique qu’à travers l’état précédent, $\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 dit que la mesure courante ne dépend que de l’état courant. Toutes deux portent sur la question de savoir si la variable d’état est bien choisie, non sur le matériel : si la mesure d’hier renseigne encore sur celle d’aujourd’hui une fois l’état d’aujourd’hui connu, c’est qu’il manque quelque chose à l’état, et le remède est de l’enrichir.

L’exemple de Russell et Norvig est un gardien de sécurité en sous-sol qui veut savoir s’il pleut, et dont le seul indice est de voir si le directeur arrive avec un parapluie :

$$\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}$$

La pluie persiste, et le parapluie est un indicateur correct mais imparfait. Une fois les deux hypothèses en place, la loi jointe sur un historique entier se factorise en un a priori, un modèle de transition et un modèle de capteur :

$$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 petits facteurs décrivent désormais un historique de longueur quelconque. Toute question a une réponse - sommez les historiques qui s’accordent avec elle - et cette réponse coûte $2^t$, ce qui justifie l’existence du reste de cet article.

B. Filtrage, prédiction, lissage

Le filtrage entretient une croyance sur le présent. C’est une seule récursion, exécutée comme une prédiction puis une mise à jour : pousser la croyance à travers le modèle de transition, puis multiplier par la vraisemblance de la nouvelle observation et normaliser. La croyance est un vecteur de taille fixe : un agent peut donc l’exécuter indéfiniment.

Au jour 1 le parapluie apparaît. Le modèle de transition symétrique laisse l’a priori uniforme à $\langle 0.5, 0.5 \rangle$, et la mise à jour donne

$$\mathbf{P}(R_1 \mid u_1) = \alpha \langle 0.9, 0.2 \rangle \langle 0.5, 0.5 \rangle = \alpha \langle 0.45, 0.10 \rangle = \langle 0.818,\ 0.182 \rangle .$$

Au jour 2 la prédiction retombe à $\langle 0.627, 0.373 \rangle$ - un pas vers le futur coûte de la certitude sur cette chaîne - et un second parapluie la relève à $\langle 0.883, 0.117 \rangle$.

La prédiction est la même récursion sans la mise à jour. Poursuivez sans nouveau parapluie et la croyance décroît $0.818 \to 0.627 \to 0.551 \to 0.520 \to \cdots \to 0.5$, en se relâchant vers la distribution stationnaire de la chaîne. Ce n’est pas une dégradation numérique ; c’est le modèle qui est honnête. L’évidence est la seule chose qui maintienne une croyance à l’écart de ce point fixe, et tout prédicteur a donc un horizon au-delà duquel il ne dit plus rien.

Le lissage améliore une estimation antérieure à l’aide d’une évidence plus tardive, en séparant l’évidence à l’instant qui nous intéresse et en exécutant une seconde récursion à rebours. Pour le jour 1, le message rétrograde est

$$\mathbf{P}(u_2 \mid R_1) = (0.9 \times \langle 0.7, 0.3 \rangle) + (0.2 \times \langle 0.3, 0.7 \rangle) = \langle 0.69,\ 0.41 \rangle,$$

et le combiner avec le message progressif fait passer le jour 1 de $0.818$ à $\langle 0.883, 0.117 \rangle$. Le recul aide réellement : le parapluie du jour 2 rend la pluie plus probable au jour 2, et comme la pluie persiste cela se répercute en arrière. Notez que $\langle 0.69, 0.41 \rangle$ ne somme pas à un, et ne le doit pas - c’est une vraisemblance, non une distribution. Mettre en cache la passe progressive puis balayer en arrière lisse une séquence entière en $O(t)$ : c’est l’algorithme progressif-rétrograde.

Ci-dessous, chaque jour compte deux barres plutôt qu'une : la croyance après l'étape de prédiction, puis après la correction. L'affirmation selon laquelle, dans ce modèle, une moitié coûte de la certitude et l'autre la rachète devient une forme dans l'image, et non une phrase à croire. Poussez le curseur d'horizon pour voir une semaine sans observation se relâcher vers la distribution stationnaire, et lancez la passe arrière pour voir le jour 1 monter de 0,818 à 0,883 grâce à un parapluie qu'il n'avait pas encore vu.

C. La séquence la plus probable est une autre question

Le lissage répond à « pleuvait-il au jour 2 ? ». Demander « que s’est-il passé ? » n’est pas la même question posée plus finement, et le raccourci naturel - lisser chaque pas, prendre le gagnant à chacun - est faux.

Prenez la séquence d’observations sur trois jours pas de parapluie, parapluie, pas de parapluie. Il n’existe que huit historiques : listons-les.

$$\begin{array}{lll} \text{dry, dry, dry} & 0.0314 & 40.2\% \\ \text{dry, rain, dry} & 0.0259 & 33.2\% \\ \text{rain, rain, dry} & 0.0076 & 9.7\% \\ \text{dry, rain, rain} & 0.0076 & 9.7\% \\ \text{rain, rain, rain} & 0.0022 & 2.8\% \\ \text{others} & & 4.4\% \end{array}$$

Lisser le jour 2 somme tous les historiques dans lesquels il a plu : $0.332 + 0.097 + 0.097 + 0.028 = 0.554$, si bien que le jour 2 pris isolément est plus probablement humide que sec. Mais la séquence la plus probable est sec, sec, sec. Les deux sont correctes. La pluie au jour 2 rassemble son $0.554$ sur quatre historiques distincts, dont aucun n’est individuellement fort, tandis que l’explication entièrement sèche concentre $40.2\%$ dans un seul. Les marginales somment sur les chemins ; le meilleur chemin, non.

Le remède est la récursion de Viterbi, qui est le filtrage avec un seul changement - la somme sur l’état précédent devient un maximum :

$$\mathbf{m}_{1:t+1} = \mathbf{P}(\mathbf{e}_{t+1} \mid \mathbf{X}_{t+1}) \max_{x_t} \Big( \mathbf{P}(\mathbf{X}_{t+1} \mid x_t)\, m_{1:t}(x_t) \Big),$$

plus un pointeur arrière à chaque pas enregistrant quel prédécesseur l’a emporté, puisque le message donne la probabilité du meilleur chemin et non le chemin lui-même. Sur la séquence de cinq jours parapluie, parapluie, pas de parapluie, parapluie, parapluie, il renvoie pluie, pluie, sec, pluie, pluie : un parapluie manquant brise une série de pluie, mais pas plus d’un jour, parce que le modèle de transition rend un jour sec isolé moins coûteux qu’un changement de régime durable.

D. Quand l’état est un nombre réel

Suivez une position plutôt qu’un pile ou face et la croyance devient une densité, la prédiction devient une intégrale sans forme close, et la forme de la croyance peut changer à chaque pas. Une famille y échappe : supposez des modèles linéaires avec un bruit gaussien et les deux étapes restent gaussiennes, parce que pousser une gaussienne à travers une application linéaire et ajouter du bruit donne une gaussienne, et qu’un produit de gaussiennes est gaussien. La croyance est alors toujours décrite par une moyenne et une variance, quelle que soit la durée d’exécution du filtre.

Pour une marche aléatoire, la mise à jour est

$$\mu_{t+1} = \frac{(\sigma_t^2 + \sigma_x^2) z_{t+1} + \sigma_z^2 \mu_t}{\sigma_t^2 + \sigma_x^2 + \sigma_z^2}, \qquad \sigma_{t+1}^2 = \frac{(\sigma_t^2 + \sigma_x^2)\sigma_z^2}{\sigma_t^2 + \sigma_x^2 + \sigma_z^2},$$

une moyenne pondérée dans laquelle celle des deux - prédiction ou observation - qui est la moins incertaine a le plus voix au chapitre. Avec $\mu_0 = 0$, $\sigma_0 = 1$, $\sigma_x = 2$, $\sigma_z = 1$ et $z_1 = 2.5$, la loi a posteriori est $\mu_1 = 2.083$ avec $\sigma_1^2 = 0.833$. La moyenne reste en deçà de l’observation parce que la prédiction détient encore du poids, et la variance finit au-dessous des deux entrées, ce qui est tout l’intérêt de filtrer.

La mise à jour de la variance ne mentionne jamais l’observation. Toute la suite des variances, et avec elle le gain de Kalman, peut donc être calculée avant l’arrivée de la moindre donnée ; ici elle converge vers $\sigma^2 \approx 0.828$ et un gain constant d’environ $0.828$. Une variance stabilisée signifie que le filtre a appris ce que le bruit permet, non qu’il s’est arrêté : la moyenne continue de bouger.

Où cela vous laisse

Deux hypothèses transforment un historique non borné en deux petites tables. Une récursion progressive répond à ce qui est vrai maintenant, la même récursion sans évidence prédit jusqu’à se dissoudre dans la distribution stationnaire, et une passe rétrograde achète le recul. L’histoire la plus probable exige son propre algorithme, et la raison mérite d’être retenue chaque fois que vous êtes tenté d’assembler une réponse à partir de gagnants pris un à un. Le parcours de formation Raisonnement probabiliste dans le temps travaille chacun de ces points à la main et en code.