L'algorithme Backward

Le deuxième algorithme utilisé par l'algorithme Baum-Welch est l'agorithme Backward. Cet algorithme délivre une seule information : $\beta_t(i)$
$\beta_t(i)$ peut se voir comme la probabilité d'observer la suite partielle ( $o_{t+1}o_{t+2}\ldots o_T$ ), qui commence à l'instant t+1 et se termine (à l'instant t) à l'état $S_i$

$$\beta_t(i) = Pr(o_{t+1}o_{t+2}\ldots o_T,q_t = S_i \vert \lambda )$$ (2.6)

Cet algorithme permet aussi de calculer P(O/$\lambda$ ) puisque

$$P(O/\lambda) = \sum_{i=1}^N \beta_1(i)$$ (2.7)

L'algorithme Backward se détermine ainsi :

Pour i = 1 à N Faire
$\beta_T(i) = 1$
FinPour

Pour t = T-1 à 1 Faire
Pour i = 1 à N Faire
$\beta_{t}(i) = \sum_{j=1}^N a_{ij}\beta_{t+1}(j)b_j(o_{t+1})$
FinPour
FinPour

L'algorithme Backward est conçu de manière similaire à l'algorithme Forward. Une seule chose diffère : l'ordre des lignes. En effet, contrairement au Forward, la dernière ligne de la matrice $\beta$ , correspond à l'observation du premier symbole $o_1$ , la deuxième ligne pour l'observation des 2 premiers symboles $o_{1}o_2$ et ainsi de suite jusqu'à la première ligne où la séquence entière est considérée. L'algorithme fonctionne également de manière inductive et peut aussi fournir une estimation correcte de P(O/$\lambda$ ).
A partir des variables $\alpha_t(i)$ et $\beta_t(i)$ , nous somme en mesure de calculer la vraisemblance P(O/$\lambda$ ) de la séquence d'observation O, pour le modèle $\lambda$ , à chaque instant t :

$$P(O/\lambda) = \sum_{i=1}^N \alpha_t(i)\beta_t(i)$$ (2.8)

puisque,

$$\alpha_t(i) = P(o_1\ldots o_t,q_t=S_i \vert \lambda)$$ (2.9)

$$\beta_t(i) = P(o_{t+1}\ldots o_T,q_t=S_i \vert \lambda)$$ (2.10)

on en déduit

$$\alpha_t(i)\beta_t(i) = P(o_1\ldots o_T,q_t=S_i \vert \lambda)$$ (2.11)

on peut alors exprimer P(O/$\lambda$ ) en sommant ce produit sur l'ensemble des états cachés de la CMC.