L'algorithme Forward

Le premier algorithme utilisé par l'algorithme Baum-Welch est l'agorithme Forward. Cet algorithme délivre deux informations : P(O/$\lambda$ ) et $\alpha_t(i)$
où $\alpha_t(i)$ est la probabilité de la suite d'observations partielle ( $o_1o_2\ldots o_{t}$ ), se terminant (à l'instant t) à l'état $S_i$

$$\alpha_t(i) = Pr(o_1o_2\ldots o_{t},q_t = S_i \vert \lambda )$$ (2.4)

et P(O/$\lambda$ ), la probabilité d'apparition de la (ou des) séquence(s) observée(s) O, avec le modèle courant $\lambda$ , ( valeur à optimiser)
P(O/$\lambda$ ) est telle que :

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

L'algorithme Forward se détermine ainsi :

Pour i = 1 à N Faire
$\alpha_1(i) = \pi_ib_i(o_1)$
FinPour

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

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

La procédure Forward détermine P(O/$\lambda$ ) en utilisant exactement la même formule (2.3) développée précédemment, mais de manière inductive, ce qui diminue fortement le temps et le nombre de calculs. En effet, l'algorithme Forward place dans un premier temps, dans la première 'ligne' $\alpha_1$ , la probabilité d'obtenir l'état caché i sachant que l'on a observé le symbole $o_1$ (donc $\alpha_1(i) = \pi_ib_i(o_1)$ , avec $\pi_i$ la probabilité d'avoir l'état i en premier, et $b_i(o_1)$ la probabilité d'observer $o_1$ lorsque l'état i est 'apparu').
Par la suite, l'algorithme détermine la t ième ligne suivante, en s'appuyant sur la t-1 ième ligne de la matrice $\alpha$ . L'induction permet ainsi d'obtenir $\alpha_{t+1}(j)$ , tel que $\alpha_{t+1}(j)$ soit égale à la somme des probabilités d'avoir observer les t premiers symboles suivant tous les chemins des états cachés possibles, et de passer à l'état j, en observant le symbole $o_{t+1}$ à l'instant t+1. La matrice $\alpha$ ainsi obtenue condense les calculs importants et redondants, qui seront nécessaires par la suite, dans l'algorithme de Baum-Welch.
De plus, il est important de remarquer que la somme des termes de la dernière ligne de la matrice $\alpha$ représente la probabilité recherchée P(O/$\lambda$ ), puisque la dernière ligne représente la chaîne entièrement observée ( $o_1\ldots o_T$ ).