Algorithme de Baum-Welch

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
image illustrant les probabilités et la statistique
Cet article est une ébauche concernant les probabilités et la statistique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ne cite pas suffisamment ses sources (juillet 2013).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références » (modifier l'article, comment ajouter mes sources ?).

L'algorithme de Baum-Welch est un algorithme utilisé pour réestimer les paramètres d'un modèle de Markov caché. Il utilise l'algorithme forward-backward et porte les noms de Leonard E. Baum et Lloyd Welch (en).

Présentation[modifier | modifier le code]

L'algorithme de Baum-Welch est un cas particulier d'une généralisation de l'algorithme espérance-maximisation (GEM).

Un des problèmes liés aux modèles de Markov cachés (HMM) est de trouver un modèle qui maximise la probabilité d'une séquence d'observations , c'est-à-dire, de déterminer le modèle qui explique le mieux la séquence. Le problème est qu'il n'est pas possible de trouver un tel modèle de façon analytique. L'algorithme de Baum-Welch est un algorithme itératif, qui permet d'estimer les paramètres du modèle qui maximisent la probabilité d'une séquence d'observables.

L'algorithme de Baum-Welch converge vers un maximum local.

Description de l'algorithme[modifier | modifier le code]

Calcul préliminaires[modifier | modifier le code]

Avant de décrire le processus d'estimation, nous avons besoin de savoir:

  • le nombre prévu de transitions d'un état en et
  • le nombre prévu de transitions d'un état ​​i à l'état j dans

Définissons d'abord la probabilité d'être dans l'état à l'instant et dans l'état à l'instant , étant donné une observation et le modèle .

avec la probabilité de transition de l'état vers l'état , et la probabilité d'observer lorsque l'on est dans l'état , et où les valeurs et définies ci après peuvent se calculer simplement avec l'algorithme forward-backward.

La figure montre une vue schématique partielle des éléments nécessaires pour le calcul de .

Xi-i-j-for-baum-welch.png

Nous définissons aussi la probabilité d'être dans l'état à l'instant ,

En sommant sur le temps, on obtient:

  • le nombre prévu de transitions d'un état dans l'observation

Et en faisant la même chose avec , nous obtenons:

  • le nombre prévu de transitions d'un état ​​ à l'état dans l'observation

Réestimation[modifier | modifier le code]

Le fonctionnement de la procédure itérative est le suivant:

  1. Partir d'un modèle initial qui peut être choisi aléatoirement.
  2. Réaliser le calcul des transitions et symboles émis qui sont les plus probables selon le modèle initial.
  3. Construire un nouveau modèle dans lequel la probabilité des transitions et des observations déterminée à l'étape précédente augmente. Pour la séquence des observables en question, le modèle aura désormais une probabilité plus élevée que le modèle précédent.

Ce processus de formation est répétée plusieurs fois jusqu'à ce qu'il n'y ait plus d'amélioration entre le modèle recalculé et l'ancien.

Probabilité d'être dans l'état à l'instant :

Re-estimation des probabilités de transition. Le numérateur correspond au nombre attendu de transitions de à , et le dénominateur représente le nombre attendu de transitions de :

,

Re-estimation des probabilités d'émission. Le numérateur correspond au nombre de fois où l'on est passé dans l'état et que l'on a observé , et le dénominateur représente le nombre de fois où l'on est passé dans l'état :

,