Expliquer l'algorithme en arrière pour le modèle de Markov caché

8

J'ai implémenté l' algorithme Viterbi et Forward , hélas, je ne peux pas comprendre comment fonctionne l' algorithme Backward . Intuitivement, je sens que je dois faire la même chose que dans Forward uniquement vers l'arrière, en utilisant les valeurs calculées pendant la propagation vers l'avant .

Mon intuition est-elle correcte?

J'ai lu beaucoup de diapositives et j'en ai assez de la notation mathématique à ce stade. Ça n'aide pas. J'ai besoin de quelque chose qui, en anglais simple, explique la différence entre les algorithmes Backward et Forward .

Pouvez-vous fournir une brève explication sur la façon dont l' algorithme Backward est effectué?

Supposons le petit HMM suivant et les résultats de l' algorithme Forward pour la séquence "BB" ci-dessous:

START -> 1
H: 0.5 * 0.8 = 0.4
L: 0.5 * 0.6 = 0.3

1 -> 2
H: 0.4 * 0.2 * 0.8 + 0.3 * 0.6 * 0.8 = 0.208
L: 0.4 * 0.8 * 0.6 + 0.3 * 0.4 * 0.6 = 0.264

2 -> END
END: 0.208 * 0.3 + 0.264 * 0.7 = 0.2472

entrez la description de l'image ici

minéraux
la source

Réponses:

7

On dirait que votre séquence d'observation est B, B. Notons l'observation au tempst comme zt et l'état caché au moment t comme Xt. Si nous désignonsαt(je) comme les valeurs à terme et βt(je) comme valeurs en arrière (je est l'un des états cachés possibles)

αt(je)=P(Xt=je,z1:t)

Ça signifie αt(je) est la probabilité d'arriver à déclarer je au moment t émission des observations à temps t. Alors,

βt(je)=P(zt+1:TXt=je) qui est la probabilité d'émettre la séquence restante de t+1 jusqu'à la fin des temps après avoir été caché je au moment t.

Pour faire la récursivité sur βt(je) nous pouvons écrire,

P(zt+1:TXt=je)=jP(Xt+1=j,zt+1:TXt=je)

En utilisant la règle de chaîne, P(Xt+1=j,zt+1:TXt=je)=P(zt+2:T,zt+1,Xt+1=jXt=je)=P(zt+2:Tzt+1,Xt+1=j,Xt=je)P(zt+1Xt+1=j,Xt=je)P(Xt+1=jXt=je)

Des indépendances conditionnelles de HMM, les probabilités ci-dessus se simplifient pour P(zt+2:TXt+1=j)P(zt+1Xt+1=j)P(Xt+1=jXt=je)

Notez que P(zt+2:TXt+1=j)=βt+1(j) de notre définition.

Substitution à P(zt+1:TXt=je) on a,

βt(je)=P(zt+1:TXt=je)=jβt+1(j)P(zt+1Xt+1=j)P(Xt+1=jXt=je)

Vous avez maintenant une récursivité pour la bêta. Les deux derniers termes de la dernière équation que vous connaissez de votre modèle. Ici, à partir de la fin de la chaîne (T), nous allons en arrière en calculant toutβt, d'où l'algorithme rétrograde. En avant, vous devez commencer par le début et vous allez à la fin de la chaîne.

Dans votre modèle, vous devez initialiser βT(je)=P(XT=je)=1 pour tous je. Il s'agit de la probabilité de ne pas émettre d'observations aprèsT=2.

user2939212
la source