L'algorithme de Baum-Welch est un cas particulier de l'algorithme d'espérance-maximisation (EM) utilisé pour trouver les paramètres inconnus d'un modèle de Markov caché (HMM). C'est la méthode principale pour l'inférence dans les HMM, utilisant l'algorithme forward-backward pour calculer les statistiques de l'étape d'espérance. L'algorithme est nommé d'après Leonard E. Baum et Lloyd R. Welch, qui l'ont développé avec des collègues au IDA Center for Communications Research à Princeton à la fin des années 1960 et au début des années 1970.
Un modèle de Markov caché décrit la probabilité conjointe d'une collection de variables aléatoires discrètes cachées et observées. Il repose sur l'hypothèse que la i-ème variable cachée, étant donné la (i-1)-ème variable cachée, est indépendante des variables cachées précédentes, et que les variables d'observation actuelles dépendent uniquement de l'état caché courant. L'algorithme de Baum-Welch utilise l'algorithme EM pour trouver l'estimation du maximum de vraisemblance des paramètres d'un HMM étant donné un ensemble de vecteurs de caractéristiques observés.
Description Formelle
Soit \(X_t\) une variable aléatoire cachée discrète avec \(N\) valeurs possibles, représentant \(N\) états au total. Les probabilités de transition sont supposées indépendantes du temps, ce qui conduit à la définition de la matrice de transition stochastique \(A = \{a_{ij}\} = P(X_t = j \mid X_{t-1} = i)\). La distribution initiale des états est donnée par \(\pi_i = P(X_1 = i)\).
Les variables d'observation \(Y_t\) peuvent prendre l'une des \(K\) valeurs possibles. La probabilité d'une certaine observation \(y_i\) au temps \(t\) pour l'état \(X_t = j\) est donnée par \(b_j(y_i) = P(Y_t = y_i \mid X_t = j)\). Cela donne la matrice \(N \times K\) \(B = \{b_j(y_i)\}\). Une séquence d'observations est donnée par \(Y = (Y_1 = y_1, Y_2 = y_2, \ldots, Y_T = y_T)\). Ainsi, une chaîne de Markov cachée peut être décrite par \(\theta = (A, B, \pi)\). L'algorithme de Baum-Welch trouve un maximum local pour \(\theta^* = \arg\max_\theta P(Y \mid \theta)\).
Étapes de l'Algorithme
L'algorithme affine itérativement les estimations des paramètres. Dans l'étape d'espérance, il calcule les probabilités forward \(\alpha_t(i) = P(Y_1, \ldots, Y_t, X_t = i \mid \theta)\) et les probabilités backward \(\beta_t(i) = P(Y_{t+1}, \ldots, Y_T \mid X_t = i, \theta)\) en utilisant l'algorithme forward-backward. Ces probabilités sont utilisées pour calculer les statistiques suffisantes attendues, telles que la probabilité d'être dans l'état \(i\) au temps \(t\) et la probabilité de transition de l'état \(i\) à l'état \(j\) entre les temps \(t\) et \(t+1\).
Dans l'étape de maximisation, l'algorithme met à jour les paramètres \(A\), \(B\), et \(\pi\) pour maximiser la log-vraisemblance attendue. Les probabilités de transition mises à jour sont calculées comme le rapport des comptes attendus de transitions de l'état \(i\) à l'état \(j\) sur les comptes attendus d'être dans l'état \(i\). De même, les probabilités d'émission sont mises à jour en fonction des comptes attendus d'observations dans chaque état. La distribution initiale des états est mise à jour en fonction de la probabilité attendue d'être dans chaque état au temps 1.
L'algorithme continue d'itérer jusqu'à convergence, généralement lorsque le changement de log-vraisemblance tombe en dessous d'un seuil. Il est garanti de converger vers un maximum local de la fonction de vraisemblance, mais pas nécessairement le maximum global.
Stabilité Numérique
L'algorithme de Baum-Welch est numériquement instable en raison de son calcul récursif des probabilités conjointes. À mesure que le nombre de variables augmente, ces probabilités conjointes deviennent de plus en plus petites, ce qui fait que les récursions forward approchent rapidement des valeurs inférieures à la précision machine. Cela peut provoquer un sous-dépassement (underflow) dans les implémentations pratiques, en particulier pour les longues séquences d'observations. Pour atténuer cela, les implémentations utilisent souvent des techniques de mise à l'échelle, telles que la normalisation des variables forward et backward à chaque pas de temps, ou le travail dans le domaine logarithmique.
Applications
L'une des premières applications majeures des HMM était dans le domaine du traitement de la parole. Dans les années 1980, les HMM sont apparus comme un outil utile dans l'analyse des systèmes biologiques et de l'information, en particulier l'information génétique. Ils sont depuis devenus un outil important dans la modélisation probabiliste des séquences génomiques. L'algorithme de Baum-Welch est également utilisé dans le traitement du langage naturel, comme l'étiquetage morpho-syntaxique et la reconnaissance d'entités nommées, ainsi qu'en biologie computationnelle pour la prédiction de gènes et la prédiction de structure des protéines.
Concepts Connexes
L'algorithme de Baum-Welch est étroitement lié à d'autres techniques d'estimation de paramètres en apprentissage automatique. C'est une instance spécifique de l'algorithme d'espérance-maximisation, largement utilisé pour les modèles à variables latentes. L'algorithme forward-backward, qui est un composant clé, est également utilisé dans d'autres tâches d'inférence HMM telles que l'algorithme de Viterbi pour le décodage. Dans l'apprentissage profond moderne, des principes similaires apparaissent dans l'entraînement de modèles avec variables latentes, bien que les réseaux de neurones utilisent souvent des méthodes basées sur le gradient comme optimiseur Adam et variantes de SGD au lieu de l'EM. La connexion de l'algorithme avec apprentissage automatique et intelligence artificielle est fondamentale, car il a fourni un cadre précoce pour l'apprentissage à partir de données séquentielles.