L'algorithme de Baum-Welch

L'algorithme de Baum-Welch est un algorithme à apprentissage. Son but étant la maximisation de la vraisemblance d'un modèle $\lambda$ , celui-ci modifie substantiellement les paramètres du modèle étudié afin d'augmenter sa vraisemblance. L'algorithme réalise son optimisation en ré-estimant les différents paramètres (A, B et $\Pi$ ), suivant la (ou les) séquence(s) observée(s).

Les estimations peuvent donc logiquement se concevoir ainsi :

$$\bar{\pi}_i = \textrm{probabilité d' être dans l' état S à l' instant t = 1}$$ (2.12)

$$\bar{a}_{ij}=\frac{\textrm{nombre de transitions de l'état }S_{i}\textrm{ vers }S_{j}}{\textrm{nombre de fois où l'on quitte }S_{i}}$$ (2.13)

$$\bar{b}_j(k)=\frac{\textrm{nombre de fois où l'on est dans l'état... ...rvant le symbole }v_{k}}{\textrm{nombre de fois où l'on est dans l'état }S_{j}}$$ (2.14)

Il est à noter que lorsque les dénominateurs de $\bar{a}_{ij}$ et $\bar{b}_j(k)$ sont nuls, les probabilités $\bar{a}_{ij}$ et $\bar{b}_j(k)$ ne peuvent pas être calculée. Or, puisque nous réalisons des estimations sur ces coefficients, nous pouvons mettres ces probabilités à 0.

Pour calculer (estimer) ces nouvelles probabilités, l'algorithme de Baum-Welch utilise deux nouvelles matrices : $\Xi$ et $\Gamma$ . Les coefficients de $\Xi$ , $\xi_t(i,j)$ , représentent la probabilité d'être dans l'état $S_i$ à l'instant t et de passer dans l'état $S_j$ à l'instant t+1, d'après le modèle $\lambda$ et la séquence d'observation O. Les coefficients de $\Gamma$ , $\gamma_t(i)$ , représentent la probabilité d'être dans l'état $S_i$ à l'instant t, sachant l'observation O et le modèle $\lambda$ .

Le calcul de ces coefficients est rapidement réalisé grâce aux deux matrices de paramètres $\alpha$ et $\beta$ , délivrées par les algorithmes Forward et Backward.

Calcul des coeffcients $\xi$ de la matrice $\Xi$ :

$$\xi_t(i,j) = \frac{\alpha_t(i)a_{ij}b_j(o_{t+1})\beta_{t+1}(j)}{ P(O/\lambda)}$$ (2.15)

Calcul des coeffcients $\gamma$ de la matrice $\Gamma$ :

$$\gamma_t(i) = \sum_{j=1}^N \xi_t(i,j) = \frac{\alpha_t(i)\beta_{t}(i)}{ P(O/\lambda)}$$ (2.16)

Ainsi, la ré-estimation des paramètres (A, B et $\Pi$ ) du modèle Markovien $\lambda$ est telle que :

$$\pi_i = \gamma_1(i) \ \ \ \ \ 1\leq i \leq N$$ (2.17)

$$\bar{a}_{ij} = \frac{\sum_{t=1}^{T-1} \xi_t(i,j)}{\sum_{t=1}^{T-1} \gamma_t(i)} \ \ \ \ \ 1\leq i\ et\ j \leq N$$ (2.18)

$$\bar{b}_i(k) = \frac{\sum_{t=1\cap o_t = v_k}^{T} \gamma_t(i)}{\sum_{t=1}^{T} \gamma_t(i)} \ \ \ \ \ 1\leq i \leq N$$ (2.19)

Après avoir ré-estimer les différents paramètres du modèle d'origine, l'algorithme recalcule la vraisemblance du nouveau modèle. Il va ensuite ré-itéré les différentes opérations de ré-estimation avec ce nouveau modèle, tant que la vraissemblance courante n'est pas maximale ( P(O/$\lambda$ )=1).

L'algorithme de Baum-Welch se construit ainsi :

Faire
Appliquer les algorithmes Forward et Backward

Pour t = 1 à T Faire
Pour i = 1 à N Faire
Pour j = 1 à N Faire
Calculer $\xi_t(i,j)$
FinPour
Calculer $\gamma_t(i)$
FinPour
FinPour
Ré-estimer $\lambda = ( A, B, \Pi )$
TantQue (il y a augmentation de P(0/$\lambda$ )) ou ( Il y a encore des itérations à Faire)