Introduction aux chaînes de Markov

Les chaînes de Markov sont une manière assez commune, et relativement simple, de modéliser statistiquement des processus aléatoires. Elles ont été utilisées dans de nombreux domaines différents, allant de la génération de textes à la modélisation financière. Un exemple populaire est r/SubredditSimulator, qui utilise les chaînes de Markov pour automatiser la création de contenu pour un subreddit entier. Dans l’ensemble, les chaînes de Markov sont conceptuellement assez intuitives et très accessibles, car elles peuvent être mises en œuvre sans l’utilisation de concepts statistiques ou mathématiques avancés. Elles sont un excellent moyen de commencer à apprendre la modélisation probabiliste et les techniques de science des données.

Scénario

Pour commencer, je vais les décrire avec un exemple très commun :

Imagine that there were two possible states for weather: sunny or cloudy. You can always directly observe the current weather state, and it is guaranteed to always be one of the two aforementioned states.Now, you decide you want to be able to predict what the weather will be like tomorrow. Intuitively, you assume that there is an inherent transition in this process, in that the current weather has some bearing on what the next day's weather will be. So, being the dedicated person that you are, you collect weather data over several years, and calculate that the chance of a sunny day occurring after a cloudy day is 0.25. You also note that, by extension, the chance of a cloudy day occurring after a cloudy day must be 0.75, since there are only two possible states.You can now use this distribution to predict weather for days to come, based on what the current weather state is at the time.

Cet exemple illustre plusieurs des concepts clés d’une chaîne de Markov. Une chaîne de Markov consiste essentiellement en un ensemble de transitions, qui sont déterminées par une certaine distribution de probabilité, qui satisfont la propriété de Markov.

Observez comment dans l’exemple, la distribution de probabilité est obtenue uniquement en observant les transitions du jour actuel au jour suivant. Cela illustre la propriété de Markov, la caractéristique unique des processus de Markov qui les rend sans mémoire. Cela les rend généralement incapables de produire avec succès des séquences dans lesquelles une certaine tendance sous-jacente devrait se produire. Par exemple, bien qu’une chaîne de Markov puisse imiter le style d’écriture d’un auteur sur la base de la fréquence des mots, elle serait incapable de produire un texte contenant un sens profond ou une signification thématique, car ceux-ci sont développés sur des séquences de texte beaucoup plus longues. Ils n’ont donc pas la capacité de produire un contenu dépendant du contexte puisqu’ils ne peuvent pas prendre en compte la chaîne complète des états antérieurs.

Le modèle

Formellement, une chaîne de Markov est un automate probabiliste. La distribution de probabilité des transitions d’état est typiquement représentée comme la matrice de transition de la chaîne de Markov. Si la chaîne de Markov a N états possibles, la matrice sera une matrice N x N, telle que l’entrée (I, J) est la probabilité de transition de l’état I à l’état J. De plus, la matrice de transition doit être une matrice stochastique, une matrice dont les entrées de chaque ligne doivent s’additionner à exactement 1. Ceci est tout à fait logique, puisque chaque ligne représente sa propre distribution de probabilité.

En outre, une chaîne de Markov possède également un vecteur d’état initial, représenté par une matrice N x 1 (un vecteur), qui décrit la distribution de probabilité de commencer à chacun des N états possibles. L’entrée I du vecteur décrit la probabilité que la chaîne commence à l’état I.

Ces deux entités sont typiquement tout ce qui est nécessaire pour représenter une chaîne de Markov.

Nous savons maintenant comment obtenir la chance de transition d’un état à un autre, mais comment trouver la chance que cette transition se produise sur plusieurs étapes ? Pour formaliser cela, nous voulons maintenant déterminer la probabilité de passer de l’état I à l’état J sur M étapes. Il s’avère que ce résultat est en fait très simple à obtenir. Étant donné une matrice de transition P, on peut la déterminer en calculant la valeur de l’entrée (I, J) de la matrice obtenue en élevant P à la puissance de M. Pour les petites valeurs de M, on peut facilement le faire à la main avec des multiplications répétées. Cependant, pour les grandes valeurs de M, si vous êtes familier avec l’algèbre linéaire simple, une façon plus efficace d’élever une matrice à une puissance est d’abord de diagonaliser la matrice.

Conclusion

Maintenant que vous connaissez les bases des chaînes de Markov, vous devriez maintenant être en mesure de les implémenter facilement dans un langage de votre choix. Si le codage n’est pas votre fort, il existe également de nombreuses propriétés plus avancées des chaînes de Markov et des processus de Markov dans lesquelles vous pouvez vous plonger. À mon avis, la progression naturelle le long du parcours théorique serait vers les processus de Markov cachés ou MCMC. Les chaînes de Markov simples sont les blocs de construction d’autres techniques de modélisation plus sophistiquées, donc avec cette connaissance, vous pouvez maintenant passer à diverses techniques dans des sujets tels que la modélisation de croyance et l’échantillonnage.