L'algorithme forward

Quelle est la probabilité de ce que nous avons vu ?

Supposons que nous ayons vu les mouvements Petit, Grand, Grand. Quelle est la probabilité de cette suite sous notre modèle ? On pourrait lister tous les chemins cachés (Calme-Calme-Calme, Calme-Calme-Orageux, etc.), calculer la probabilité de chacun et les additionner. Avec $K$ états et $T$ jours, cela fait $K^{T}$ chemins, beaucoup trop. L'algorithme forward fait la même somme en $T\cdot K^{2}$ étapes en réutilisant le travail. Il garde un nombre $\alpha_t(j)$ : la probabilité des $t$ premières observations et d'être dans l'état $j$ le jour $t$ .

\alpha_1(j)=\pi_jB_j(o_1),\qquad \alpha_t(j)=\Big[\sum_i\alpha_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad P(o_1,\dots,o_T)=\sum_j\alpha_T(j)

(1)

Lisez la récurrence avec des mots : pour être dans l'état $j$ aujourd'hui, on venait d'un état $i$ hier (somme sur $i$ avec la probabilité de transition), puis l'état d'aujourd'hui a produit l'observation d'aujourd'hui. Diviser $\alpha_t$ par son total donne les probabilités filtrées, votre croyance sur l'état d'aujourd'hui sachant les données jusqu'à aujourd'hui. Un problème pratique : multiplier beaucoup de petits nombres donne des nombres qui tendent vers zéro. On divise donc à chaque pas par le total $c_t$ et on le garde. Le log de la probabilité des données est alors simplement la somme des $\ln c_t$ .

Petit, Grand, GrandJour 1 :

\alpha_1=(0{,}6\cdot0{,}9,\ 0{,}4\cdot0{,}3)=(0{,}54,\ 0{,}12)

, total

c_1=0{,}66

. Jour 2 (un grand mouvement) : Calme reçoit

(0{,}54\cdot0{,}9+0{,}12\cdot0{,}2)\cdot0{,}1=0{,}051

et Orageux

(0{,}54\cdot0{,}1+0{,}12\cdot0{,}8)\cdot0{,}7=0{,}105

, total

0{,}156

, donc la probabilité filtrée d'Orageux est

0{,}105/0{,}156=0{,}673

. Le jour 3 donne

\alpha_3=(0{,}00669,\ 0{,}06237)

. La probabilité de toute la suite est

0{,}00669+0{,}06237=0{,}0691

et son log vaut

-2{,}673

Algorithme forward : somme sur tous les chemins cachés en $T\cdot K^{2}$ étapes au lieu de $K^{T}$ .
Probabilités filtrées : normalisez $\alpha_t$ pour obtenir votre croyance sur l'état du jour à partir des données jusqu'à aujourd'hui.
Mise à l'échelle : divisez par $c_t$ à chaque pas et additionnez les $\ln c_t$ pour éviter le soupassement.

Lab : ce qui est noté

La première valeur forward15 pts
Le total du premier jour10 pts
Filtré après deux jours15 pts
La probabilité de la suite15 pts
La log-vraisemblance10 pts
Ce que l'algorithme forward économise10 pts
Associer le vocabulaire10 pts
Pourquoi les valeurs sont remises à l'échelle15 pts

Quelle est la probabilité de ce que nous avons vu ?

\alpha_1(j)=\pi_jB_j(o_1),\qquad \alpha_t(j)=\Big[\sum_i\alpha_{t-1}(i)A_{ij}\Big]B_j(o_t),\qquad P(o_1,\dots,o_T)=\sum_j\alpha_T(j)

(1)

Petit, Grand, GrandJour 1 :

\alpha_1=(0{,}6\cdot0{,}9,\ 0{,}4\cdot0{,}3)=(0{,}54,\ 0{,}12)

, total

c_1=0{,}66

. Jour 2 (un grand mouvement) : Calme reçoit

(0{,}54\cdot0{,}9+0{,}12\cdot0{,}2)\cdot0{,}1=0{,}051

et Orageux

(0{,}54\cdot0{,}1+0{,}12\cdot0{,}8)\cdot0{,}7=0{,}105

, total

0{,}156

, donc la probabilité filtrée d'Orageux est

0{,}105/0{,}156=0{,}673

. Le jour 3 donne

\alpha_3=(0{,}00669,\ 0{,}06237)

. La probabilité de toute la suite est

0{,}00669+0{,}06237=0{,}0691

et son log vaut

-2{,}673

Algorithme forward : somme sur tous les chemins cachés en $T\cdot K^{2}$ étapes au lieu de $K^{T}$ .
Probabilités filtrées : normalisez $\alpha_t$ pour obtenir votre croyance sur l'état du jour à partir des données jusqu'à aujourd'hui.
Mise à l'échelle : divisez par $c_t$ à chaque pas et additionnez les $\ln c_t$ pour éviter le soupassement.

Lab : ce qui est noté

La première valeur forward15 pts
Le total du premier jour10 pts
Filtré après deux jours15 pts
La probabilité de la suite15 pts
La log-vraisemblance10 pts
Ce que l'algorithme forward économise10 pts
Associer le vocabulaire10 pts
Pourquoi les valeurs sont remises à l'échelle15 pts

Quelle est la probabilité de ce que nous avons vu ?

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.

L'algorithme forward

Quelle est la probabilité de ce que nous avons vu ?

Lab : ce qui est noté

Connectez-vous pour exécuter votre code.