Algorithme de Baum-Welch

Un article de Wikipédia, l'encyclopédie libre.
Cet article est une ébauche concernant les probabilités et les statistiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).

L'algorithme de Baum-Welch, ou algorithme forward-backward, ou encore algorithme de propagation alpha-beta permet, dans le cadre d'un modèle de Markov caché, de calculer la probabilité d'une séquence d'observations étant donné le modèle.

Étant donné une séquence s de longueur n, et un HMM de matrice de transition T et de matrice d'émission E, si la séquence est d'alphabet Η, de taille \left | \Eta \right \vert, on a :

  • calcul des \alpha_i(k) = P(s_{1:i}, h_i = k) \,\, \; \forall i = 1, ..., n \,\, et \,\, \forall k \in \Eta
  • calcul de P(s) = \sum_{k \in \Eta} \alpha_n(k)
  • initialisation : α1(k) = P(s1:1,h1 = k) = T(0,k)E(k,s1) = π(k)E(k,s1) où π est la distribution de probabilité initiale et π(k) est le k-ième élément de celle-ci.
  • récursion : \alpha_i(k) = \sum_{j \in \Eta} \alpha_{i - 1}(j) T(j, k) E(k, s_i)

Cet algorithme a une compelxité de l'ordre de O(n{\left |\Eta \right \vert}^2)


[modifier] Références

  • Introduction to Computational Genomics, Cristianini and Hahn.