Algorithme forward-backward

Image d'un réseau de neurones de type perceptron multi-couches, mettant en avant le calcul de la valeur du neurone $(i_3,o_4)$

En informatique, l'algorithme forward-backward, ou algorithme progressif-rétrogressif, est un algorithme pour calculer la probabilité d'une séquence observée dans le contexte des modèles de Markov cachés.

L'algorithme commence par effectuer un calcul progressif des probabilités, un calcul « en avant », qui donne la probabilité d'obtenir les k premières observations dans une séquence donnée, en terminant dans chaque état possible du modèle de Markov.

Il effectue également ensuite un calcul rétrogressif des probabilités, qui représente la probabilité d'obtenir les autres observations ultérieures à un état initial. Ces deux ensembles de probabilités peuvent être combinés pour obtenir à tout instant la probabilité de l’état caché, sachant la séquence totale des événements observés. L'algorithme forward-backward peut donc être utilisé afin de trouver les états les plus probables pour un modèle de Markov à n'importe quel instant.

Présentation

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.

Calcul progressif des probabilités

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 $𝐏(X_t\mid X_{t-1})$ d'une variable aléatoire donnée $X_t$ qui représente tous les états possibles d'un modèle de Markov caché seront représentés par la matrice $𝐓$, 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, ${𝐓}_{i,j}=𝐏(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 :

$𝐓=\left(\begin{array}{cc}0.7& 0.3\\ 0.6& 0.4\end{array}\right)$

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

${\pi }_{t+1}={\pi }_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 :

$𝐁=\left(\begin{array}{cc}0.9& 0.1\\ 0.2& 0.8\end{array}\right)$

et décrit les probabilités d'observer des événements étant donné un état particulier. Chaque élément $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 ($\mathit{\pi }$), la probabilité d'observer un événement j est donnée par :

$𝐏(O=j)=\sum _i{\pi }_i{b}_{i,j}$

Cela peut être représenté sous forme matricielle en multipliant le vecteur d'état ($\mathit{\pi }$) par une matrice d'observation (${𝐎}_{\mathrm{𝟏}}$) 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:

${𝐎}_{\mathrm{𝟏}}=\left(\begin{array}{cc}0.9& 0.0\\ 0.0& 0.2\end{array}\right)$

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 $({𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}{)}_{t\in \{0\dots 𝐓\}}$ en fonction du vecteur initial d’état ${\pi }_0$:

${𝐟}_{\mathrm{𝟎}\mathbf{:}\mathrm{𝟎}}={\mathit{\pi }}_{\mathrm{𝟎}},$

${𝐟}_{\mathrm{𝟎}\mathbf{:}\mathrm{𝟏}}={\mathit{\pi }}_{\mathrm{𝟎}}𝐓{𝐎}_{\mathrm{𝟏}},$

$\dots$

${𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}={𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭\mathbf{-}\mathrm{𝟏}}𝐓{𝐎}_{𝐭}$

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

${𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}(i)=𝐏(O_1,O_2,\dots ,O_t,X_t=i)(1)$

On appelle probabilités vers l’avant la suite $({𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}{)}_{t\in \{0\dots 𝐓\}}$ .

Notons $a_t$ la somme des éléments de ce vecteur-ligne :

$a_t=\sum _{i=1}^n{f}_{0:t}(i)$.

$a_t$ représente l’intégrale de $f_{0:t}$ sur toutes les valeurs possibles de l’état $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) :

$a_t=𝐏(O_1,O_2,\dots ,O_t).(2)$

Le coefficient $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 :

${\widehat{𝐟}}_{\mathrm{𝟎}\mathbf{:}𝐭}=a_t^{-1}{𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}$

On peut interpréter le vecteur ${\widehat{𝐟}}_{\mathrm{𝟎}\mathbf{:}𝐭}$ comme suit :

${\widehat{𝐟}}_{\mathrm{𝟎}\mathbf{:}𝐭}(i)=\frac{{𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}(i)}{a_t}=\frac{𝐏(O_1,O_2,\dots ,O_t,X_t=i)}{𝐏(O_1,O_2,\dots ,O_t)}=𝐏(X_t=i|O_1,O_2,\dots ,O_t)$

Nous constatons donc que le vecteur de probabilité normalisé par le facteur d'échelle $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 $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 :

${\widehat{𝐟}}_{\mathrm{𝟎}\mathbf{:}𝐭}=c_t^{-1}{\widehat{𝐟}}_{\mathrm{𝟎}\mathbf{:}𝐭\mathbf{-}\mathrm{𝟏}}𝐓{𝐎}_{𝐭}$

où $c_t$ représente un facteur d'échelle. Il est clair que $\prod _{s=1}^t{c}_s=a_t$.

Calcul rétrogressif des probabilités

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 :

${𝐛}_{𝐭\mathbf{:}𝐓}(i)=𝐏(O_{t+1},O_{t+2},\dots ,O_T|X_t=i)$

C'est-à-dire, qu’à partir d’un état $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 ${𝐛}_{𝐓\mathbf{:}𝐓}(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 :

${𝐛}_{𝐓\mathbf{:}𝐓}=[111\dots {]}^T$

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

${𝐛}_{𝐭\mathbf{-}\mathrm{𝟏}\mathbf{:}𝐓}=𝐓{𝐎}_{𝐭}{𝐛}_{𝐭\mathbf{:}𝐓}$

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.

Calcul des «probabilités lissées»

Intéressons-nous au produit ${𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}(i)\cdot {𝐛}_{𝐭\mathbf{:}𝐓}(i)$ :

${𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}(i)\cdot {𝐛}_{𝐭\mathbf{:}𝐓}(i)=𝐏(O_1,O_2,\dots ,O_t,X_t=i)\cdot 𝐏(O_{t+1},O_{t+2},\dots ,O_T|X_t=i)$ $=𝐏(O_1,O_2,\dots ,O_t,X_t=i)\cdot 𝐏(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 $O_{1:t}$ et $O_{t+1:T}$ sachant $X_t$.

Ainsi,

${𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}(i)\cdot {𝐛}_{𝐭\mathbf{:}𝐓}(i)=𝐏(O_1,O_2,\dots ,O_T,X_t=i).(3)$

Posons ${\mathit{\gamma }}_{𝐭}(i)=\frac{{𝐟}_{\mathrm{𝟎}\mathbf{:}𝐭}(i)\cdot {𝐛}_{𝐭\mathbf{:}𝐓}(i)}{a_T}.$

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

${\mathit{\gamma }}_{𝐭}(i)=𝐏(X_t=i|O_1,O_2,\dots ,O_T)$.

Les valeurs ${\mathit{\gamma }}_{𝐭}(i)$ fournissent la probabilité d'être dans l’état $i$ à l’instant $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 $𝐏(X_t=i,X_{t+1}=j)\ne 𝐏(X_t=i)𝐏(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 ${𝐛}_{𝐭\mathbf{:}𝐓}$, mais des valeurs normalisées par les coefficients issus du calcul progressif.

On utilise la relation de récurrence :

${\widehat{𝐛}}_{𝐭\mathbf{-}\mathrm{𝟏}\mathbf{:}𝐓}=c_t^{-1}𝐓{𝐎}_{𝐭}{\widehat{𝐛}}_{𝐭\mathbf{:}𝐓}.$

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

${\widehat{𝐛}}_{𝐭\mathbf{:}𝐓}(i)=\frac{{𝐛}_{𝐭\mathbf{:}𝐓}(i)}{\prod _{s=t+1}^T{c}_s}.$

Avec ces valeurs modifiées, on a : ${\mathit{\gamma }}_{𝐭}(i)={\widehat{𝐟}}_{\mathrm{𝟎}\mathbf{:}𝐭}(i)\cdot {\widehat{𝐛}}_{𝐭\mathbf{:}𝐓}(i).$

Articles connexes

• Algorithme de Baum-Welch
• Algorithme de Viterbi