Algorithme forward-backward

En informatique, l'algorithme forward-backward, ou algorithme avant-arrière, 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 calculer l'ensemble des probabilités "en avant", qui donnent la probabilité d'obtenir k premières observations dans une séquence donnée, en terminant dans chaque état possible du modèle de Markov.

Il calcule également ensuite l'ensemble de probabilités "en arrière", qui représente la probabilité d'obtenir les autres observations étant donné un état initial. Ces deux ensembles de probabilités peuvent être combinées pour obtenir la probabilité d'être dans chaque état à un temps donné pendant l'observation de la séquence. 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 des probabilités "en avant"
2. Calcul des probabilités "en arrière"
3. Calcul des "probabilités lissées"

Les étapes "en avant" et "en arrière" 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. A 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.

Probabilités "en avant"

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 $\mathbf{P}(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 $\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. L'exemple ci-dessous représente un système ou la probabilité de rester dans le même état après chaque pas est de 70% et la probabilité de transition vers l'autre stade est de 30%. La matrice de transition s'écrit donc :

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

Dans un modèle de Markov typique, on multiplierait un vecteur d'état par cette matrice pour obtenir les probabilités pour l'état suivant. 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 :

$\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. 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 ($\mathbf{\pi}$), la probabilité d'observer un événement j est donnée par :

$\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 ($\mathbf{\pi}$) par une matrice d'observation ($\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:

$\mathbf{O_1} = \begin{pmatrix} 0.9 & 0.0 \\ 0.0 & 0.2 \end{pmatrix}$

Références

• (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)

Articles connexes

• Algorithme de Baum-Welch
• Algorithme de Viterbi