Est-ce facile? J'ai essayé
Alexey Kuzmin, directeur du développement des données et du travail chez DomKlik, professeur en science des données à Netology, a traduit un article de Rahul Agarwal sur la façon dont les méthodes de Monte Carlo fonctionnent avec les chaînes de Markov pour résoudre les problèmes avec un grand espace d'état.Tout le monde associé à la science des données a déjà entendu parler des méthodes de Monte Carlo avec les chaînes de Markov (MCMC). Parfois, le sujet est abordé lors de l'étude des statistiques bayésiennes, parfois lors de l'utilisation d'outils comme Prophète.
Mais MCMC est difficile à comprendre. Chaque fois que je lis sur ces méthodes, j'ai remarqué que l'essence de MCMC est cachée dans les couches profondes de bruit mathématique, et il est difficile de distinguer ce bruit. J'ai dû passer plusieurs heures à comprendre ce concept.
Dans cet article, une tentative d'expliquer les méthodes de Monte Carlo avec des chaînes de Markov est disponible, de sorte qu'il devienne clair à quoi elles servent. Je vais me concentrer sur quelques autres façons d'utiliser ces méthodes dans mon prochain post.
Commençons donc. MCMC se compose de deux termes: chaînes de Monte Carlo et de Markov. Parlons de chacun d'eux.
Monte Carlo
En termes simples
, les méthodes de Monte Carlo peuvent être définies comme de simples simulations.
Monte Carlo Methods tire son nom du Monte Carlo Casino de Monaco. Dans de nombreux jeux de cartes, vous devez connaître la probabilité de gagner le croupier. Parfois, le calcul de cette probabilité peut être mathématiquement compliqué ou insoluble. Mais nous pouvons toujours exécuter une simulation informatique pour jouer plusieurs fois à l'ensemble du jeu et considérer la probabilité comme le nombre de victoires divisé par le nombre de parties jouées.
C'est tout ce que vous devez savoir sur les méthodes de Monte Carlo. Oui, c'est juste une technique de modélisation simple avec un nom de fantaisie.
Chaînes de Markov
Étant donné que le terme MCMC se compose de deux parties, vous devez toujours comprendre ce que sont
les chaînes de Markov . Mais avant de passer aux chaînes de Markov, parlons un peu des propriétés de Markov.
Supposons qu'il existe un système d'états possibles M et que vous passez d'un état à un autre. Que rien ne vous dérange encore. Un exemple spécifique d'un tel système est la météo, qui passe de chaud à froid à modéré. Un autre exemple est le marché boursier, qui passe d'un état baissier à un état haussier et stagnant.
La propriété de Markov suggère que pour un processus donné qui se trouve dans l'état X
n à un instant particulier, la probabilité X
n + 1 = k (où k est l'un des M-états vers lesquels le processus peut aller) ne dépend que de quelle est cette condition en ce moment. Et pas sur la façon dont il a atteint son état actuel.
En termes mathématiques, nous pouvons écrire ceci sous la forme de la formule suivante:
Pour plus de clarté, vous ne vous souciez pas de la séquence de conditions que le marché a prises pour devenir haussier. La probabilité que le prochain État soit «baissier» n'est déterminée que par le fait que le marché est actuellement dans un état «haussier». Cela a également du sens dans la pratique.
Un processus avec une propriété Markov est appelé processus Markov. Pourquoi la chaîne Markov est-elle importante? En raison de sa distribution stationnaire.
Qu'est-ce que la distribution stationnaire?
Je vais essayer d'expliquer la distribution stationnaire en la calculant pour l'exemple ci-dessous. Supposons que vous ayez un processus Markov pour le marché boursier, comme indiqué ci-dessous.
Vous disposez d'une matrice de probabilité de transition qui détermine la probabilité d'une transition de l'état X
i à X
j .
Matrice de probabilité de transition, Q
Dans la matrice de probabilité transitoire Q, la probabilité que le prochain état soit «bull», étant donné l'état actuel de «bull» = 0,9; la probabilité que l'état suivant soit «baissier» si l'état actuel est «taureau» = 0,075. Et ainsi de suite.
Eh bien, commençons par un état particulier. Notre état sera déterminé par le vecteur [taureau, ours, stagnation]. Si nous commençons par un état «baissier», le vecteur sera comme ceci: [0,1,0]. Nous pouvons calculer la distribution de probabilité pour l'état suivant en multipliant le vecteur d'état actuel par la matrice de probabilité de transition.
Notez que les probabilités totalisent 1.La distribution des états suivante peut être trouvée par la formule:
Et ainsi de suite. À la fin, vous atteindrez un état stationnaire dans lequel l'état se stabilise:
Pour la matrice de probabilité de transition Q décrite ci-dessus, la distribution stationnaire s est
Vous pouvez obtenir une distribution stationnaire avec le code suivant:
Q = np.matrix([[0.9,0.075,0.025],[0.15,0.8,0.05],[0.25,0.25,0.5]]) init_s = np.matrix([[0, 1 , 0]]) epsilon =1 while epsilon>10e-9: next_s = np.dot(init_s,Q) epsilon = np.sqrt(np.sum(np.square(next_s - init_s))) init_s = next_s print(init_s) ------------------------------------------------------------------ matrix([[0.62499998, 0.31250002, 0.0625 ]])
Vous pouvez également partir de n'importe quel autre état - obtenir la même distribution stationnaire. Modifiez l'état initial dans le code si vous voulez vous en assurer.
Nous pouvons maintenant répondre à la question de savoir pourquoi la distribution stationnaire est si importante.
La distribution stationnaire est importante car elle peut être utilisée pour déterminer la probabilité qu'un système se trouve dans un certain état au hasard.
Pour notre exemple, on peut dire que dans 62,5% des cas le marché sera dans un état «haussier», 31,25% dans un état «baissier» et 6,25% en stagnation.
Intuitivement, vous pouvez voir cela comme une errance aléatoire autour de la chaîne.
Marche aléatoire
Vous êtes à un certain point et choisissez l'état suivant, en observant la distribution de probabilité de l'état suivant, en tenant compte de l'état actuel. Nous pouvons visiter certains nœuds plus souvent que d'autres, en fonction des probabilités de ces nœuds.
C'est ainsi que Google a résolu le problème de la recherche à l'aube d'Internet. Le problème était de trier les pages, selon leur importance. Google a résolu le problème en utilisant l'algorithme Pagerank. L'algorithme de Google Pagerank devrait considérer l'état comme une page et la probabilité d'une page dans une distribution stationnaire comme son importance relative.
Nous passons maintenant directement à l'examen des méthodes MCMC.
Quelles sont les méthodes de Monte Carlo avec les chaînes de Markov (MCMC)
Avant de répondre à ce qu'est MCMC, permettez-moi de poser une question. Nous connaissons la distribution bêta. Nous connaissons sa fonction de densité de probabilité. Mais peut-on prélever un échantillon de cette distribution? Pouvez-vous trouver un moyen de le faire?
Pensez ...
MCMC vous permet de choisir parmi n'importe quelle distribution de probabilité. Ceci est particulièrement important lorsque vous devez effectuer une sélection à partir de la distribution postérieure.
La figure montre le théorème de Bayes.
Par exemple, vous devez faire un échantillon à partir d'une distribution postérieure. Mais est-il facile de calculer la composante postérieure avec la constante de normalisation (évidence)? Dans la plupart des cas, vous pouvez les trouver sous la forme d'un produit de vraisemblance et de probabilité a priori. Mais calculer la constante de normalisation (p (D)) ne fonctionne pas. Pourquoi? Examinons de plus près.
Supposons que H ne prenne que 3 valeurs:
p (D) = p (H = H1) .p (D | H = H1) + p (H = H2) .p (D | H = H2) + p (H = H3) .p (D | H = H3)
Dans ce cas, p (D) est facile à calculer. Mais que faire si la valeur de H est continue? Serait-il possible de calculer cela aussi facilement, surtout si H prenait des valeurs infinies? Pour ce faire, une intégrale complexe devrait être résolue.
Nous voulons faire une sélection aléatoire à partir de la distribution postérieure, mais nous voulons également considérer p (D) comme une constante.
Wikipédia
écrit :
Les méthodes de Monte Carlo avec des chaînes de Markov sont une classe d'algorithmes d'échantillonnage à partir d'une distribution de probabilité, basée sur la construction d'une chaîne de Markov, qui en tant que distribution stationnaire a la forme souhaitée. L'état de la chaîne après une série d'étapes est ensuite utilisé comme sélection dans la distribution souhaitée. La qualité de l'échantillonnage s'améliore avec l'augmentation du nombre d'étapes.
Regardons un exemple. Disons que vous avez besoin d'un échantillon de la
distribution bêta . Sa densité:
où C est la constante de normalisation. En fait, c'est une fonction de α et β, mais je veux montrer qu'elle n'est pas nécessaire pour un échantillon de la distribution bêta, nous allons donc la prendre comme constante.
Le problème de distribution bêta est vraiment difficile, sinon pratiquement insoluble. En réalité, vous devrez peut-être travailler avec des fonctions de distribution plus complexes, et parfois vous ne connaîtrez pas les constantes de normalisation.
Les méthodes MCMC facilitent la vie en fournissant des algorithmes qui pourraient créer une chaîne de Markov ayant une distribution bêta comme distribution stationnaire, étant donné que nous pouvons choisir parmi une distribution uniforme (ce qui est relativement simple).
Si nous commençons par un état aléatoire et passons à l'état suivant sur la base d'un algorithme plusieurs fois, nous créerons finalement une chaîne de Markov avec une distribution bêta en tant que distribution stationnaire. Et les états que nous nous trouvons depuis longtemps peuvent être utilisés comme échantillon de la distribution bêta.
L'un de ces algorithmes MCMC est l'algorithme
Metropolis-Hastings.Algorithme de Metropolis-Hastings
Intuition:
Quel est donc le but?
Intuitivement, nous voulons parcourir une partie de la surface (notre chaîne de Markov) de manière à ce que le temps que nous passons à chaque emplacement soit proportionnel à la hauteur de la surface à cet emplacement (la densité de probabilité souhaitée à partir de laquelle nous voulons effectuer une sélection).
Ainsi, par exemple, nous aimerions passer deux fois plus de temps sur une colline de 100 mètres de haut que sur une colline voisine de 50 mètres. C'est bien que nous puissions faire cela même si nous ne connaissons pas les hauteurs absolues des points sur la surface: tout ce que vous devez savoir, ce sont les hauteurs relatives. Par exemple, si le sommet de la colline A est deux fois plus élevé que le sommet de la colline B, alors nous aimerions passer deux fois plus de temps en A qu'en B.
Il existe des schémas plus complexes pour proposer de nouveaux lieux et de nouvelles règles pour leur adoption, mais l'idée principale est la suivante:
- Choisissez un nouvel emplacement "suggéré".
- Découvrez à quel point cet emplacement est supérieur ou inférieur à celui actuel.
- Rester sur place ou déménager dans un nouvel endroit avec une probabilité proportionnelle à la hauteur des lieux.
Le but du MCMC est de choisir parmi une certaine distribution de probabilité sans avoir à connaître sa hauteur exacte à aucun moment (pas besoin de connaître C).
Si le processus «errance» est correctement configuré, vous pouvez vous assurer que cette proportionnalité (entre le temps passé et la hauteur de distribution) est atteinte .
Algorithme:
Définissons et décrivons maintenant la tâche en termes plus formels. Soit s = (s1, s2, ..., sM) la distribution stationnaire souhaitée. Nous voulons créer une chaîne de Markov avec une telle distribution stationnaire. Nous commençons par une chaîne de Markov arbitraire avec des états M avec la matrice de transition P, de sorte que pij représente la probabilité de transition de l'état i à j.
Intuitivement, nous savons parcourir la chaîne de Markov, mais la chaîne de Markov n'a pas la distribution stationnaire requise. Cette chaîne a une distribution stationnaire (dont nous n'avons pas besoin). Notre objectif est de changer la façon dont nous nous promenons dans la chaîne de Markov afin que la chaîne ait la distribution stationnaire souhaitée.
Pour ce faire:
- Commencez avec un état initial aléatoire i.
- Sélectionnez aléatoirement un nouvel état supposé en examinant les probabilités de transition dans la ième ligne de la matrice de transition P.
- Calculez une mesure appelée probabilité de décision, définie comme suit: aij = min (sj.pji / si.pij, 1).
- Lancez maintenant une pièce qui atterrit à la surface de l'aigle avec une probabilité aij. Si un aigle tombe, acceptez l'offre, c'est-à-dire passez à l'état suivant, sinon, rejetez l'offre, c'est-à-dire restez dans l'état actuel.
- Répétez plusieurs fois.
Après un grand nombre de tests, cette chaîne convergera et aura une distribution stationnaire s. Ensuite, nous pouvons utiliser des états de chaîne comme échantillon de n'importe quelle distribution.
En procédant ainsi pour échantillonner la distribution bêta, la seule fois où vous avez à utiliser la densité de probabilité est de rechercher la probabilité de prendre une décision. Pour ce faire, divisez sj par si (c'est-à-dire que la constante de normalisation C est annulée).
Sélection bêta
Passons maintenant au problème de l'échantillonnage à partir de la distribution bêta.
Une distribution bêta est une distribution continue sur [0,1] et peut avoir des valeurs infinies sur [0,1]. Supposons qu'une chaîne de Markov arbitraire P avec des états infinis sur [0,1] a une matrice de transition P telle que pij = pji = tous les éléments de la matrice.
Nous n'avons pas besoin de Matrix P, comme nous le verrons plus loin, mais je veux que la description du problème soit aussi proche que possible de l'algorithme que nous avons proposé.
- Commençons par un état initial aléatoire i obtenu à partir d'une distribution uniforme sur (0,1).
- Sélectionnez aléatoirement un nouvel état supposé en regardant les probabilités de transition dans la ième ligne de la matrice de transition P. Supposons que nous choisissions un autre état Unif (0,1) comme état supposé j.
- Calculez la mesure, qui est appelée la probabilité de prendre une décision:
Ce qui simplifie:
Puisque pji = pij, et où
- Lancez maintenant une pièce. Il est probable qu'un aigle tombera. Si un aigle tombe, vous devez accepter l'offre, c'est-à-dire passer à l'état suivant. Sinon, il vaut la peine de rejeter l'offre, c'est-à-dire de rester dans le même état.
- Répétez le test plusieurs fois.
Code:
Il est temps de passer de la théorie à la pratique. Nous allons écrire notre échantillon bêta en Python.
impo rt rand om
Comparez les résultats avec la distribution bêta réelle.
impo rt num py as np import pylab as pl import scipy.special as ss %matplotlib inline pl.rcParams['figure.figsize'] = (17.0, 4.0)
Comme vous pouvez le voir, les valeurs sont très similaires à la distribution bêta. Ainsi, le réseau MCMC a atteint un état stationnaire
Dans le code ci-dessus, nous avons créé un échantillonneur bêta, mais le même concept s'applique à toute autre distribution à partir de laquelle nous voulons effectuer une sélection.
Conclusions
C'était un super article. Félicitations si vous l'avez lu jusqu'à la fin.
En substance, les méthodes MCMC peuvent être complexes, mais elles nous offrent une grande flexibilité. Vous pouvez sélectionner n'importe quelle fonction de distribution en utilisant la sélection via le MCMC. En règle générale, ces méthodes sont utilisées pour échantillonner à partir de distributions postérieures.
Vous pouvez également utiliser MCMC pour résoudre des problèmes avec un grand espace d'état. Par exemple, dans un problème de sac à dos ou pour le déchiffrement. Je vais essayer de vous fournir des exemples plus intéressants dans le
prochain post. Restez à l'écoute.
Des éditeurs