Commune · Savoirs
Algorithme forward-backward
Calculer la probabilité d'une séquence observée dans le contexte des modèles de Markov cachés
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.
Lire la suite
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. L'algorithme se déroule en trois étapes : 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 ».
Texte : Wikipédia, CC BY-SA 4.0. · Image : Enrique Benimeli (CC BY-SA 3.0) ·