Algorithme forward-backward

L'algorithme se déroule en trois étapes :

1. Calcul progressif des probabilités ;
2. Calcul rétrogressif des probabilités ;
3. Calcul des « probabilités lissées ».

Les étapes progressives et rétrogressives sont souvent appelées « passage de message en avant » et « passage de message en arrière ». Cela vient de la façon dont l'algorithme traite les séquences observées. D'abord, l'algorithme avance en commençant à la première observation de la séquence pour aller jusqu'à la dernière, et ensuite repart en arrière jusqu'à la première. À chaque observation, une probabilité est calculée, et sera utilisée pour le prochain calcul de probabilité de l'observation suivante. Pendant le passage de retour, l'algorithme effectue également l'étape de « lissage ». Cette étape permet à l'algorithme de tenir compte de toutes les observations effectuées au préalable afin d'obtenir des résultats plus précis.

La description suivante utilise comme matrices de base des matrices de probabilités plutôt que des matrices de distribution de probabilité. On transforme la distribution de probabilité d'un modèle de Markov caché en une notation matricielle comme suit : Les probabilités de transition ${\displaystyle \mathbf {P} (X_{t}\mid X_{t-1})}$ d'une variable aléatoire donnée ${\displaystyle X_{t}}$ qui représente tous les états possibles d'un modèle de Markov caché seront représentés par la matrice ${\displaystyle \mathbf {T} }$, où l'indice de lignes, i, représentera l'état de départ; et où l'indice de colonne, j, représente l'état d'arrivée. Ainsi, ${\displaystyle \mathbf {T} _{i,j}=\mathbf {P} (X_{t}=j\mid X_{t-1}=i)}$ L'exemple ci-dessous représente un système ou la probabilité de rester dans l'état 1 si on y est déjà est de 70 % et la probabilité de transition de l'état 1 vers l'état 2 est de 30 %. La probabilité de passer de l'état 2 à l'état 1 est de 60 %, et celle de rester dans l'état 2 est de 40 %. La matrice de transition s'écrit donc :

${\displaystyle \mathbf {T} ={\begin{pmatrix}0.7&0.3\\0.6&0.4\end{pmatrix}}}$

Dans un modèle de Markov typique, on multiplierait un vecteur d'état ${\displaystyle \pi _{t}}$ par cette matrice pour obtenir les probabilités ${\displaystyle \pi _{t+1}}$ pour l'état suivant.

${\displaystyle \pi _{t+1}=\pi _{t}\mathbf {T} }$ .

Dans les modèles de Markov cachés, l'état est inconnu et l'on observe uniquement les événements associés avec les états possibles. Une matrice d'événements est de la forme :

${\displaystyle \mathbf {B} ={\begin{pmatrix}0.9&0.1\\0.2&0.8\end{pmatrix}}}$

et décrit les probabilités d'observer des événements étant donné un état particulier. Chaque élément ${\displaystyle b_{i,j}}$ représente la probabilité d’observer l’événement j dans l’état i. Dans l'exemple ci-dessus, l'événement 1 sera observé 90 % du temps pendant lequel on se situe dans l'état 1, alors que l'événement 2 a une probabilité de 10 % de se produire dans cet état. Par contre, l'événement 1 sera observé seulement 20 % du temps si l'on est dans l'état 2 et l'événement 2 a 80 % de chances de se produire. Étant donné un vecteur d'état (${\displaystyle \mathbf {\pi } }$), la probabilité d'observer un événement j est donnée par :

${\displaystyle \mathbf {P} (O=j)=\sum _{i}\pi _{i}b_{i,j}}$

Cela peut être représenté sous forme matricielle en multipliant le vecteur d'état (${\displaystyle \mathbf {\pi } }$) par une matrice d'observation (${\displaystyle \mathbf {O_{1}} }$) qui contient seulement des éléments sur sa diagonale. Chaque entrée représente la probabilité de l'événement observé étant donné chaque état. Si l'on continue l'exemple précédent, une observation de l'événement 1 serait donné par:

${\displaystyle \mathbf {O_{1}} ={\begin{pmatrix}0.9&0.0\\0.0&0.2\end{pmatrix}}}$

Cela nous permet de calculer les probabilités associées à la transition vers un nouvel état et en observant un nouvel événement donné. On définit la suite ${\displaystyle (\mathbf {f_{0:t}} )_{t\in \{0\dots \mathbf {T} \}}}$ en fonction du vecteur initial d’état ${\displaystyle \pi _{0}}$:

${\displaystyle \mathbf {f_{0:0}} =\mathbf {\pi _{0}} ,}$

${\displaystyle \mathbf {f_{0:1}} =\mathbf {\pi _{0}} \mathbf {T} \mathbf {O_{1}} ,}$

${\displaystyle \dots }$

${\displaystyle \mathbf {f_{0:t}} =\mathbf {f_{0:t-1}} \mathbf {T} \mathbf {O_{t}} }$

Pour chaque valeur de ${\displaystyle t}$, le vecteur ${\displaystyle \mathbf {f_{0:t}} }$ représente en fonction de ${\displaystyle \pi _{0}}$ la probabilité de transition à chaque état et en observant l'événement donné. C'est-à-dire :

${\displaystyle \mathbf {f_{0:t}} (i)=\mathbf {P} (O_{1},O_{2},\dots ,O_{t},X_{t}=i)\qquad (1)}$

On appelle probabilités vers l’avant la suite ${\displaystyle (\mathbf {f_{0:t}} )_{t\in \{0\dots \mathbf {T} \}}}$ .

Notons ${\displaystyle a_{t}}$ la somme des éléments de ce vecteur-ligne :

${\displaystyle a_{t}=\sum _{i=1}^{n}f_{0:t}(i)}$.

${\displaystyle a_{t}}$ représente l’intégrale de ${\displaystyle {f_{0:t}}}$ sur toutes les valeurs possibles de l’état ${\displaystyle X_{t}}$, c’est-à-dire la probabilité totale pour l'observation des événements donnés indépendamment de l'état final. (la vraisemblance de l'observation) :

${\displaystyle a_{t}=\mathbf {P} (O_{1},O_{2},\dots ,O_{t}).\qquad (2)}$

Le coefficient ${\displaystyle a_{t}}$ nous permet de normaliser le vecteur de probabilité de telle sorte que la somme de ses entrées soit égale à 1. On pose :

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =a_{t}^{-1}\mathbf {f_{0:t}} }$

On peut interpréter le vecteur ${\displaystyle \mathbf {{\hat {f}}_{0:t}} }$ comme suit :

${\displaystyle \mathbf {{\hat {f}}_{0:t}} (i)={\frac {\mathbf {f_{0:t}} (i)}{a_{t}}}={\frac {\mathbf {P} (O_{1},O_{2},\dots ,O_{t},X_{t}=i)}{\mathbf {P} (O_{1},O_{2},\dots ,O_{t})}}=\mathbf {P} (X_{t}=i|O_{1},O_{2},\dots ,O_{t})}$

Nous constatons donc que le vecteur de probabilité normalisé par le facteur d'échelle ${\displaystyle a_{t}}$ nous donne la probabilité d'être dans chacun des états à l'instant t, sachant les observations précédentes.

En pratique, on calcule ${\displaystyle a_{t}}$ par récurrence en normalisant à chaque étape le vecteur de probabilité de telle sorte que sa somme des entrées soit à 1, en appliquant la formule de récurrence :

${\displaystyle \mathbf {{\hat {f}}_{0:t}} =c_{t}^{-1}\ \mathbf {{\hat {f}}_{0:t-1}} \mathbf {T} \mathbf {O_{t}} }$

où ${\displaystyle c_{t}}$ représente un facteur d'échelle. Il est clair que ${\displaystyle \prod _{s=1}^{t}c_{s}=a_{t}}$.

Le calcul progressif nous a permis de connaître la probabilité d’observer les t premières observations et du t-ième état en fonction de la distribution de probabilité de l’état initial. En prolongeant ce calcul jusqu’à la fin, on peut calculer la probabilité d’observer toutes les observations et de l’état final. On peut tenter un calcul similaire, en arrière : Cherchons à déterminer :

${\displaystyle \mathbf {b_{t:T}} (i)=\mathbf {P} (O_{t+1},O_{t+2},\dots ,O_{T}|X_{t}=i)}$

C'est-à-dire, qu’à partir d’un état ${\displaystyle X_{t}}$ donné, nous cherchons à calculer la probabilité de toutes les observations futures. Ce calcul peut s’effectuer de proche en proche, en commençant par t=T, puis en calculant t=T-1, etc. C’est pourquoi on donne à ce calcul le nom de calcul rétrogressif. Le dernier élément ${\displaystyle \mathbf {b_{T:T}} (i)}$ est un cas dégénéré. il correspond à la probabilité de ne pas effectuer d’observation après le dernier état T. On a donc :

${\displaystyle \mathbf {b_{T:T}} =[1\ 1\ 1\ \dots ]^{T}}$

Nous pouvons définir toute la suite par récurrence :

${\displaystyle \mathbf {b_{t-1:T}} =\mathbf {T} \mathbf {O_{t}} \mathbf {b_{t:T}} }$

Nous pourrions normaliser ce vecteur, mais ce n’est généralement pas ce que l’on fait. Comme chaque vecteur représente la probabilité de la séquence des événements à venir étant donné un état particulier initial, la normalisation de ce vecteur serait équivalente à l'application du théorème de Bayes pour trouver la vraisemblance de chaque état initial en fonction des événements futurs.

Intéressons-nous au produit ${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}$ :

${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)=\mathbf {P} (O_{1},O_{2},\dots ,O_{t},X_{t}=i)\cdot \mathbf {P} (O_{t+1},O_{t+2},\dots ,O_{T}|X_{t}=i)}$ ${\displaystyle =\mathbf {P} (O_{1},O_{2},\dots ,O_{t},X_{t}=i)\cdot \mathbf {P} (O_{t+1},O_{t+2},\dots ,O_{T}|X_{t}=i,O_{1},O_{2},\dots ,O_{t})}$

D'après l'indépendance conditionnelle de ${\displaystyle O_{1:t}}$ et ${\displaystyle O_{t+1:T}}$ sachant ${\displaystyle X_{t}}$.

Ainsi,

${\displaystyle \mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)=\mathbf {P} (O_{1},O_{2},\dots ,O_{T},X_{t}=i).\qquad (3)}$

Posons ${\displaystyle \mathbf {\gamma _{t}} (i)={\frac {\mathbf {f_{0:t}} (i)\cdot \mathbf {b_{t:T}} (i)}{a_{T}}}.}$

D’après (2) et (3), il vient que :

${\displaystyle \mathbf {\gamma _{t}} (i)=\mathbf {P} (X_{t}=i|O_{1},O_{2},\dots ,O_{T})}$.

Les valeurs ${\displaystyle \mathbf {\gamma _{t}} (i)}$ fournissent la probabilité d'être dans l’état ${\displaystyle i}$ à l’instant ${\displaystyle t}$ . En tant que telles, elles sont utiles pour déterminer l'état le plus probable à tout moment. Il convient de noter, cependant, que le terme « état le plus probable » est quelque peu ambigu. Alors que l'état le plus probable est le plus susceptible d'être correct à un moment donné, la séquence des états probables individuellement n'est pas susceptible d'être la séquence globalement la plus probable. Cela parce que les probabilités pour chaque point sont calculées indépendamment les unes des autres. Ces calculs ne prennent pas en compte les probabilités de transition entre les états, et il est donc possible d'obtenir deux états à deux moments (t et t +1) qui soient à la fois les plus probables à ces instants mais qui aient une probabilité très faible de se produire successivement, parce que ${\displaystyle \mathbf {P} (X_{t}=i,X_{t+1}=j)\neq \mathbf {P} (X_{t}=i)\mathbf {P} (X_{t+1}=j)}$. On peut déterminer la séquence la plus probable des états qui ont produit une séquence d'observations donnée en utilisant l'algorithme de Viterbi.

En pratique, on ne calcule pas directement les valeurs ${\displaystyle \mathbf {b_{t:T}} }$, mais des valeurs normalisées par les coefficients issus du calcul progressif.

On utilise la relation de récurrence :

${\displaystyle \mathbf {{\hat {b}}_{t-1:T}} =c_{t}^{-1}\mathbf {T} \mathbf {O_{t}} \mathbf {{\hat {b}}_{t:T}} .}$

Ce vecteur de probabilité normalisé est lié à la précédente valeur par :

${\displaystyle \mathbf {{\hat {b}}_{t:T}} (i)={\frac {\mathbf {b_{t:T}} (i)}{\prod _{s=t+1}^{T}c_{s}}}.}$

Avec ces valeurs modifiées, on a : ${\displaystyle \mathbf {\gamma _{t}} (i)=\mathbf {{\hat {f}}_{0:t}} (i)\cdot \mathbf {{\hat {b}}_{t:T}} (i).}$

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Forward-backward algorithm » (voir la liste des auteurs).

• Algorithme de Baum-Welch
• Algorithme de Viterbi

• Portail de l'informatique théorique
• Portail des probabilités et de la statistique