Modèles de Markov

Les modèles de Markov sont des outils mathématiques essentiels pour modéliser des phénomènes où les données présentent des dépendances dans le temps ou dans l’espace. Ils sont particulièrement utiles pour les étudiants et chercheurs en statistiques, informatique, traitement du signal ou bioinformatique, qui souhaitent comprendre comment représenter et analyser des séquences d’événements dépendants.

La question

Le travail s’intéresse à la modélisation des données dépendantes, contrairement à l’hypothèse classique d’indépendance et d’identiquement distribution (iid) des observations. Il s’agit de comprendre comment représenter des processus où l’état à un instant donné dépend de l’état précédent, ce qui est fréquent dans des domaines comme la météo, les cours boursiers, les signaux acoustiques ou les séquences d’ADN. Le problème est de formaliser ces dépendances pour pouvoir prédire, analyser ou inférer des états cachés à partir d’observations partielles.

Concepts de base

Un processus stochastique est une suite de variables aléatoires (X1, X2, ..., XT) définies sur un même espace fondamental Ω. Chaque variable représente l’état du processus à un instant t, appelé aussi observation. Contrairement aux hypothèses iid, ces variables ne sont généralement pas indépendantes, et leur dépendance est la clé pour modéliser des phénomènes temporels ou spatiaux.

Pour caractériser complètement un processus stochastique, il suffit de connaître :

• La loi de probabilité de la première variable X1, qui donne la distribution initiale des états.
• Les probabilités conditionnelles P(Xt = xj | X1 = x_i1, ..., Xt-1 = x_it-1) pour t > 1, qui décrivent la dépendance temporelle.

Une chaîne de Markov est un processus stochastique particulier qui vérifie la propriété de Markov : l’état à l’instant t dépend uniquement de l’état à l’instant t-1, et pas des états antérieurs. De plus, les probabilités de transition entre états sont supposées constantes dans le temps (stationnarité).

Cette propriété se traduit par :

P(Xt = xj | X1 = x_i1, ..., Xt-1 = x_it-1) = P(Xt = xj | Xt-1 = x_it-1)

et la matrice de transition T, où chaque élément T(i, j) = P(Xt = j | Xt-1 = i) représente la probabilité de passer de l’état i à l’état j.

Le processus de Markov peut être vu comme un automate stochastique où chaque état correspond à un état du processus, et chaque transition est étiquetée par une probabilité.

Approche

Pour illustrer, on considère un exemple simple : la météo avec deux états possibles, pluie (état 1) ou pas pluie (état 2). On suppose que la probabilité qu’il pleuve demain dépend uniquement du fait qu’il pleuve aujourd’hui, avec des probabilités α et β respectivement. La matrice de transition est alors :

[ α   1 - α ]
[ β   1 - β ]

La distribution initiale des états à l’instant 1 est donnée par une probabilité γ d’être dans l’état pluie.

Dans un modèle de Markov observable, on connaît directement la séquence des états Xt. La probabilité d’observer une séquence d’états est calculable à partir des probabilités initiales et des probabilités de transition. Par exemple, pour une séquence donnée, on multiplie la probabilité initiale par les probabilités de transition successives.

Le modèle devient plus complexe avec les modèles de Markov cachés (MMC), où les états réels ne sont pas directement observables. On observe seulement une séquence d’émissions ou d’observations qui dépendent de ces états cachés via des probabilités d’émission. L’objectif est alors d’inférer la séquence d’états la plus probable à partir des observations, ou d’estimer les paramètres du modèle.

Un MMC est défini par :

• Un ensemble fini d’états cachés S = {S1, ..., SN}.
• Un ensemble d’observations possibles O = {o1, ..., oM}.
• Une matrice de transition A = [a_ij], où a_ij = P(S_t+1 = j | S_t = i).
• Une matrice d’émission B = [b_j(m)], où b_j(m) = P(observation = o_m | état = S_j).
• Une distribution initiale π sur les états.

Trois problèmes majeurs se posent avec les MMC :

1. Évaluation : calculer la probabilité qu’une séquence d’observations soit générée par un modèle donné.
2. Décodage : déterminer la séquence d’états la plus probable ayant généré une séquence d’observations.
3. Apprentissage : estimer les paramètres du modèle (matrices de transition et d’émission, distribution initiale) à partir d’un ensemble de séquences observées.

Le calcul direct de la probabilité d’une séquence d’observations est intractable car il nécessite de sommer sur toutes les séquences d’états possibles, ce qui est exponentiel en la longueur T de la séquence et en le nombre N d’états.

Pour résoudre ce problème, on utilise la procédure avant (forward algorithm) qui calcule récursivement des variables α_t(i) représentant la probabilité d’observer la séquence partielle jusqu’à l’instant t et d’être dans l’état i à ce moment. Cette procédure a une complexité en O(N²T), bien plus efficace que la méthode naïve.

Symétriquement, la procédure arrière (backward algorithm) calcule des variables β_t(i) représentant la probabilité d’observer la séquence à partir de l’instant t+1, conditionnellement à l’état i à l’instant t.

Pour le problème de décodage, l’algorithme de Viterbi permet de trouver la séquence d’états la plus probable en utilisant une approche dynamique similaire à la procédure avant, mais en maximisant les probabilités au lieu de les sommer.

Enfin, pour l’apprentissage des paramètres du modèle, l’algorithme de Baum-Welch est utilisé. Il s’agit d’une variante de l’algorithme EM (Expectation-Maximization) adaptée aux MMC. Il alterne :

• Une étape E où l’on estime les probabilités d’être dans un état donné et de faire une transition donnée, à partir des observations et du modèle actuel.
• Une étape M où l’on met à jour les paramètres du modèle pour maximiser la vraisemblance des observations.

Résultats

Le travail montre que les modèles de Markov, et en particulier les modèles de Markov cachés, permettent de modéliser efficacement des séquences dépendantes dans le temps. Les algorithmes forward-backward et Viterbi fournissent des méthodes calculatoires tractables pour évaluer des séquences et inférer des états cachés. L’algorithme de Baum-Welch permet d’apprendre les paramètres du modèle à partir de données d’observation, même lorsque les états réels sont inconnus.

Ces résultats sont fondamentaux pour de nombreuses applications pratiques, comme la reconnaissance de la parole, la bioinformatique, ou la modélisation de phénomènes naturels, où les données sont séquentielles et bruitées.

Limitations et questions ouvertes

Le travail souligne que le calcul exact de la probabilité d’une séquence d’observations est intractable sans recours aux algorithmes spécifiques. De plus, l’apprentissage des paramètres repose sur des méthodes itératives qui peuvent converger vers des optima locaux, et la qualité des résultats dépend de la qualité des données et du choix du nombre d’états.

Enfin, les modèles de Markov cachés supposent que les observations sont conditionnellement indépendantes données les états, ce qui peut être une simplification excessive dans certains contextes complexes.

Glossaire

• Processus stochastique : suite de variables aléatoires indexées dans le temps.
• Propriété de Markov : dépendance uniquement de l’état précédent dans une chaîne de Markov.
• Chaîne de Markov : processus stochastique vérifiant la propriété de Markov et stationnarité des transitions.
• Matrice de transition : matrice donnant les probabilités de passage d’un état à un autre.
• Modèle de Markov caché (MMC) : modèle où les états sont cachés et les observations sont des probabilités conditionnelles des états.
• Procédure avant (forward) : algorithme récursif pour calculer la probabilité d’une séquence d’observations.
• Procédure arrière (backward) : algorithme complémentaire à la procédure avant, calculant des probabilités conditionnelles inverses.
• Algorithme de Viterbi : méthode dynamique pour trouver la séquence d’états la plus probable.
• Algorithme de Baum-Welch : algorithme EM pour estimer les paramètres d’un MMC à partir de données observées.