L'algorithme de Baum-Welch

De part le caractère caché des états d'un modèle Markovien, il n'est pas rare que les différents paramètres du modèle (la matrice de transition des états cachés, la matrice de génération des symboles suivant les états, ainsi que la matrice de probabilité de départ) soient eux aussi à déterminer, à estimer. Un algorithme particulièrement efficace dans l'estimation des paramètres d'une chaîne de Markov cachée est l'algorithme de Baum-Welch.
L'algorithme de Baum-Welch est dérivé de l'algorithme EM (Expectation Maximization). Dans ce dernier, l'objectif est de maximiser (ou minimiser) une probabilité du type P(X/M), d'un modèle probabiliste (Markovien dans notre cas).
Une maximisation en mathématiques est généralement la solution de l'équation :

$$\frac{\partial P(X/M)}{\partial \lambda} = 0$$ (2.1)

où $\lambda$ est le vecteur de variables paramètres du modèle M.
La résolution de ce type d'équation est dans la pratique difficile, voire impossible à obtenir.

L'utilisation d'algorithmes itératifs, comme l'algorithme EM par exemple, permet néanmoins d'estimer de manière assez précise et rapide la solution optimale de l'équation.
L'algorithme de Baum-Welch est un algorithme à apprentissage. Etant donné un ensemble de séquences d'observations O et un modèle initial $\lambda$ , l'algorithme de Baum-Welch entreprend une ré-estimation des paramètres du modèle de manière à augmenter la vraisemblance de génération des séquences d'observations. La maximisation de la vraisemblance P(O/$\lambda$ ) peut donc se voir comme l'optimisation du modèle $\lambda$ sachant que l'on a observé la ou les séquences O.

Afin de maximiser rapidement la vraisemblance $P(O/\lambda)$ du modèle, il est nécessaire d'utiliser un algorithme de calcul (de $P(O/\lambda)$ ) de complexité faible. Or, la manière la plus évidente pour déternimer $P(O/\lambda)$ est la suivante :

$$P(O/\lambda) = Pr(S_1S_2S_3\ldots S_T/\lambda\wedge O)+ Pr(S_2S_2... ...{T+1}/\lambda\wedge O) + Pr(S_iS_jS_k\ldots S_z/\lambda\wedge O)\ +\ etc \ldots$$ (2.2)

avec i,j...z $\in 1 \ldots N$ .

Il nous faut donc additionner tous les arrangements avec répétition (de T termes) possibles des $S_i$ , avec $i\in 0\ldots N$ . Le nombre de séquences différentes (arrangements avec répétition) étant alors de $N^T$ . Ce qui revient à écrire :

$$P(O/\lambda) = \sum_{Arrangements\ des\ q_i} \pi_{q_1}b_{q_1}(o_1... ..._2)\ldots a_{q_{T-1}q_T}b_{q_T}(o_T)\ avec\ q_i \in S = \left\{S_1..S_N\right\}$$ (2.3)

Cependant, cette formule possède une complexité en $2TN^T$ , bien trop importante. Aussi, l'algorithme "`Forward-Backward"' a été conçu pour diminuer la complexité de calcul.