Comment expliqueriez-vous Markov Chain Monte Carlo (MCMC) à un profane?

Peut-être que le concept, pourquoi il est utilisé et un exemple.

Premièrement, nous devons comprendre ce qu'est une chaîne de Markov. Prenons l' exemple météorologique suivant de Wikipedia. Supposons que les conditions météorologiques d'un jour donné ne puissent être classées que dans deux états: ensoleillé et pluvieux. Basé sur l'expérience passée, nous savons ce qui suit:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Rainy)}=0.50$

Depuis, le temps est soit ensoleillé, soit pluvieux le lendemain:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Rainy)}=0.50$

De même, laissez:

$P(\text{Next day is Rainy}\,\vert \,\text{Given today is Sunny)}=0.10$

Par conséquent, il s'ensuit que:

$P(\text{Next day is Sunny}\,\vert \,\text{Given today is Sunny)}=0.90$

Les quatre nombres ci-dessus peuvent être représentés de manière compacte sous la forme d'une matrice de transition représentant les probabilités que le temps passe d'un état à un autre, comme suit:

$P = \begin{bmatrix} & S & R \\ S& 0.9 & 0.1 \\ R& 0.5 & 0.5 \end{bmatrix}$

Nous pourrions poser plusieurs questions dont les réponses suivent:

Q1: Si le temps est ensoleillé aujourd'hui, quel temps fera-t-il demain?

A1: Depuis, nous ne savons pas ce qui va se passer, le mieux que nous puissions dire est qu’il ya chances qu’il soit ensoleillé et pluie.10 $90\%$$10\%$

Q2: Qu'en est-il deux jours à compter d'aujourd'hui?

A2: Prévision d'un jour: ensoleillé, pluvieux. Par conséquent, dans deux jours:10 $90\%$$10\%$

Le premier jour il peut y avoir du soleil et le lendemain il peut aussi être ensoleillé. Les chances que cela se produise sont: .$0.9 \times 0.9$

Ou

Le premier jour il peut pleuvoir et le deuxième jour il peut faire soleil. Les chances que cela se produise sont les suivantes: .$0.1 \times 0.5$

Par conséquent, la probabilité que le temps soit ensoleillé dans deux jours est de:

$P(\text{Sunny 2 days from now} = 0.9 \times 0.9 + 0.1 \times 0.5 = 0.81 + 0.05 = 0.86$

De même, la probabilité qu'il pleuve est de:

$P(\text{Rainy 2 days from now} = 0.1 \times 0.5 + 0.9 \times 0.1 = 0.05 + 0.09 = 0.14$

En algèbre linéaire (matrices de transition), ces calculs correspondent à toutes les permutations d'une transition à l'autre (ensoleillé à ensoleillé ( ), ensoleillé à pluvieux ( ), pluvieux à ensoleillé ( ) ou pluie à pluie ( )) avec leurs probabilités calculées:S 2 R R 2 S R 2$S_2S$$S_2R$$R_2S$$R_2R$

Dans la partie inférieure de l'image, nous voyons comment calculer la probabilité d'un état futur ( ou ) à partir des probabilités (fonction de masse de probabilité, ) pour chaque état (ensoleillé ou pluvieux) au temps zéro (maintenant). ou ) comme une simple multiplication matricielle.t + 2 P M F t $t+1$$t+2$$PMF$$t_0$

Si vous continuez à la prévision du temps comme cela , vous remarquerez que finalement le Prévisions jour -ème, où est très grand ( par exemple ), les probabilités se dépose « d'équilibre » suivants:n $n$$n$$30$

$P(\text{Sunny}) = 0.833$

et

$P(\text{Rainy}) = 0.167$

En d’autres termes, vos prévisions pour le ième jour et le ème jour restent les mêmes. En outre, vous pouvez également vérifier que les probabilités «d'équilibre» ne dépendent pas du temps qu'il fait aujourd'hui. Vous obtiendrez les mêmes prévisions météorologiques si vous commencez par supposer que le temps est aujourd’hui ensoleillé ou pluvieux.n + $n$$n+1$

L'exemple ci-dessus ne fonctionnera que si les probabilités de transition d'état satisfont à plusieurs conditions que je ne traiterai pas ici. Mais notez les caractéristiques suivantes de cette "belle" chaîne de Markov (belle = les probabilités de transition satisfont aux conditions):

Indépendamment de l'état de départ initial, nous atteindrons éventuellement une distribution de probabilité d'équilibre des états.

Markov Chain Monte Carlo exploite la fonctionnalité ci-dessus comme suit:

Nous voulons générer des tirages au sort à partir d'une distribution cible. Nous identifions ensuite un moyen de construire une chaîne de Markov «sympa» telle que sa distribution de probabilité d'équilibre soit notre distribution cible.

Si nous pouvons construire une telle chaîne, nous commençons arbitrairement à partir d'un point donné et nous répétons la chaîne de Markov plusieurs fois (comme nous prévoyons la météo fois). Finalement, les tirages que nous générons apparaissent comme s’ils venaient de notre distribution cible.$n$

Nous estimons ensuite les quantités d'intérêt (par exemple, la moyenne) en prenant la moyenne d'échantillon des tirages après avoir écarté quelques tirages initiaux, qui constituent la composante de Monte Carlo.

Il existe plusieurs manières de construire de «belles» chaînes de Markov (par exemple, échantillonneur de Gibbs, algorithme Metropolis-Hastings).

Je pense que l'algorithme Metropolis-Hastings (à chaîne d'indépendance) procure une intuition simple et agréable.

Tout d'abord, quel est l'objectif? MCMC a pour objectif de tirer des échantillons d'une distribution de probabilité sans avoir à connaître sa hauteur exacte en aucun point. MCMC parvient à cela "à errer" dans cette distribution de telle sorte que le temps passé dans chaque emplacement soit proportionnel à la hauteur de la distribution. Si le processus "errant" est configuré correctement, vous pouvez vous assurer que cette proportionnalité (entre le temps passé et la hauteur de la distribution) est atteinte.

Intuitivement, nous voulons marcher sur une surface (grumeleuse) de telle sorte que le temps que nous passons (ou # échantillons) à chaque emplacement soit proportionnel à la hauteur de la surface à cet endroit. Ainsi, par exemple, nous aimerions passer deux fois plus de temps sur une colline située à 100 m d'altitude que sur une colline proche située à 50 m d'altitude. La bonne chose est que nous pouvons le faire même si nous ne connaissons pas les hauteurs absolues des points de la surface: tout ce que nous devons savoir, ce sont les hauteurs relatives . Par exemple, si une colline A est deux fois plus haute que la colline B, nous aimerions passer deux fois plus de temps en A que nous en passons en B.

La variante la plus simple de l'algorithme Metropolis-Hastings (échantillonnage de chaîne d'indépendance) réalise ceci comme suit: supposons que dans chaque pas de temps (discret), nous choisissions un nouvel emplacement "proposé" aléatoire (sélectionné uniformément sur toute la surface). Si l'emplacement proposé est plus élevé que notre position actuelle, déplacez-vous. Si l'emplacement proposé est inférieur, déplacez-vous vers le nouvel emplacement avec une probabilité p, où p est le rapport entre la hauteur de ce point et la hauteur de l'emplacement actuel. (c.-à-d., lancez une pièce avec une probabilité p de faire des têtes; si elle monte des têtes, déplacez-vous vers le nouvel emplacement; si cela arrive, restez où vous êtes) Conservez une liste des emplacements où vous vous êtes rendu à chaque pas de temps et cette liste aura (de manière asyptotique) la bonne proportion de temps passé dans chaque partie de la surface.

Il existe des schémas plus complexes pour proposer de nouveaux emplacements et les règles pour les accepter, mais l’idée de base reste: 1) choisir un nouvel emplacement "proposé"; (2) calculez combien cet emplacement est supérieur ou inférieur à votre emplacement actuel; (3) probablement rester ou se déplacer à cet endroit d'une manière qui respecte l'objectif général de passer du temps proportionnellement à la hauteur de l'emplacement.

A quoi sert-il? Supposons que nous ayons un modèle probabiliste du temps qui nous permet d'évaluer A * P (météo), où A est une constante inconnue. (Cela arrive souvent - de nombreux modèles sont faciles à formuler de telle sorte que vous ne pouvez pas déterminer ce qu'est A). Nous ne pouvons donc pas évaluer exactement P ("pluie demain"). Cependant, nous pouvons faire fonctionner l'échantillonneur MCMC pendant un moment, puis demander: quelle fraction d'échantillons (ou "emplacements") s'est retrouvée dans l'état "pluie demain". Cette fraction sera la prévision météorologique probabiliste (basée sur un modèle).

Je dirais probablement quelque chose comme ça:

"Chaque fois que nous voulons parler de probabilités, nous intégrons vraiment une densité. Dans l'analyse bayésienne, beaucoup de densités que nous trouvons ne sont pas analytiquement traitables: vous ne pouvez les intégrer que si vous pouvez les intégrer du tout Alors, au lieu de cela, simulons beaucoup la variable aléatoire, puis calculons les probabilités à partir de nos nombres aléatoires simulés. Si nous voulons connaître la probabilité que X soit inférieur à 10, nous comptons les Proportion de résultats variables aléatoires simulés inférieurs à 10 et que nous utilisons comme estimation. C’est la partie "Monte Carlo", c’est une estimation de probabilité basée sur des nombres aléatoires. Avec suffisamment de nombres aléatoires simulés, l’estimation est très bonne, mais elle reste intrinsèquement aléatoire.

"Alors pourquoi" Chaîne de Markov "? Parce que dans certaines conditions techniques, vous pouvez générer un processus sans mémoire (ou processus markovien) qui a la même distribution limite que la variable aléatoire que vous essayez de simuler. Nombre de types de processus de simulation différents qui génèrent des nombres aléatoires corrélés (basés uniquement sur la valeur actuelle de ces nombres), et vous avez la garantie qu'une fois que vous aurez rassemblé suffisamment de résultats, vous obtiendrez une pile de chiffres qui ressemble " comme si "vous aviez réussi à prélever des échantillons indépendants de la distribution compliquée que vous vouliez connaître.

"Ainsi, par exemple, si je veux estimer la probabilité qu'une variable aléatoire normale standard soit inférieure à 0,5, je pourrais générer dix mille réalisations indépendantes à partir d'une distribution normale standard et compter le nombre inférieur à 0,5; supposons que j'en ai 6905 qui étaient moins de 0,5 sur 10 000 échantillons au total; mon estimation pour P (Z <0,5) serait de 0,6905, ce qui n’est pas si éloigné de la valeur réelle, c’est une estimation de Monte Carlo.

la liste des nombres que je tire de la procédure sera distribuée comme un grand nombre de tirages à partir de quelque chose qui génère des variables aléatoires normales. Cela me donnerait une simulation de Monte Carlo par chaîne de Markov pour une variable aléatoire normale normale. Si je l’utilisais pour estimer les probabilités, ce serait une estimation MCMC. "

Imaginez que vous souhaitiez trouver une meilleure stratégie pour battre vos amis au jeu de société Monopoly. Simplifiez ce qui compte dans le jeu et posez-vous la question suivante: quelles sont les propriétés les plus fréquentées? La réponse dépend de la structure du plateau, des règles du jeu et des lancers de deux dés.

Voici un moyen de répondre à la question. Il suffit de suivre un seul morceau du tableau pour lancer les dés et suivre les règles. Comptez combien de fois vous avez atterri sur chaque propriété (ou programmez un ordinateur pour faire le travail à votre place). Éventuellement, si vous avez suffisamment de patience ou si vous avez assez bien programmé les règles dans votre ordinateur, vous obtiendrez une bonne image des propriétés qui suscitent le plus d’affaires. Cela devrait vous aider à gagner plus souvent.

Ce que vous avez fait est une analyse de Markov Chain Monte Carlo (MCMC). Le conseil définit les règles. La prochaine étape dans laquelle vous atterrissez dépend de votre situation actuelle et non de celle où vous étiez auparavant. Les probabilités spécifiques sont déterminées par la distribution des lancers de deux dés. MCMC est l'application de cette idée à des systèmes mathématiques ou physiques, comme ce que sera la météo de demain ou l'endroit où finira un grain de pollen tamponné au hasard par des molécules de gaz.

OK, voici ma meilleure tentative d'explication informelle et grossière.

Une chaîne de Markov est un processus aléatoire qui a pour propriété que l'avenir ne dépend que de l'état actuel du processus et non du passé, c'est-à-dire qu'il est sans mémoire. Un exemple de processus aléatoire pourrait être la bourse. Un exemple de chaîne de Markov serait un jeu de plateau comme Monopoly ou Snakes and Ladders, dans lequel votre position future (après avoir jeté le dé) ne dépendrait que de votre position d'origine avant le rôle, et non de vos positions précédentes. Un exemple classique de chaîne de Markov est la "promenade de l'ivrogne". Imaginez quelqu'un qui est ivre et qui ne peut se déplacer que d'un seul pas à gauche ou à droite. L'ivrogne bouge à gauche ou à droite avec une probabilité égale. Il s'agit d'une chaîne de Markov où la position future / suivante de l'ivresse dépend uniquement de l'endroit où il se trouve actuellement.

Les méthodes de Monte Carlo sont des algorithmes de calcul (de simples ensembles d'instructions) qui échantillonnent de manière aléatoire un processus à l'étude. C’est un moyen d’estimer quelque chose qui est trop difficile ou trop long à trouver de manière déterministe. Il s’agit essentiellement d’une forme de simulation informatique d’un processus mathématique ou physique. Le surnom de Monte Carlo vient de l'analogie entre la génération d'un nombre aléatoire et de casinos. Revenons à notre exemple de jeu de société plus tôt, peut-être voudrions-nous savoir si certaines propriétés du Monopoly Board sont visitées plus souvent que d’autres. Une expérience de Monte Carlo impliquerait de lancer les dés de manière répétée et de compter le nombre de fois où vous atterririez sur chaque propriété. Il peut également être utilisé pour calculer des intégrales numériques. (De manière très informelle, nous pouvons considérer une intégrale comme la zone située sous le graphique d’une fonction. ) L’intégration de Monte Carlo fonctionne très bien sur des fonctions de grande dimension en prenant un échantillon aléatoire de points de la fonction et en calculant un type de moyenne à ces différents points. En augmentant la taille de l'échantillon, la loi des grands nombres nous indique que nous pouvons augmenter la précision de notre approximation en couvrant de plus en plus la fonction.

Ces deux concepts peuvent être combinés pour résoudre des problèmes difficiles dans des domaines tels que l'inférence bayésienne, la biologie computationnelle, etc. où des intégrales multidimensionnelles doivent être calculées pour résoudre des problèmes communs. L'idée est de construire une chaîne de Markov qui converge vers la distribution de probabilité souhaitée après plusieurs étapes. L'état de la chaîne après un grand nombre d'étapes est ensuite utilisé comme échantillon de la distribution souhaitée et le processus est répété. Il existe de nombreux algorithmes MCMC différents qui utilisent différentes techniques pour générer la chaîne de Markov. Les plus courantes incluent les échantillons Metropolis-Hastings et Gibbs.

Extrait des méthodes bayésiennes pour les hackers

Le paysage bayésien

$N$$N$$p_1$$p_2$

$\text{Exp}(3)$$\text{Exp}(10)$

La visualisation ci-dessous le montre. Plus la couleur est rouge foncé, plus la probabilité que les inconnues se trouvent à cet endroit est élevée. Inversement, les zones en bleu plus foncé indiquent que nos prédécesseurs attribuent une très faible probabilité aux inconnus qui s'y trouvent.

Ce sont des exemples simples dans un espace 2D, où notre cerveau peut bien comprendre les surfaces. En pratique, les espaces et les surfaces générés par nos a priori peuvent être de dimensions beaucoup plus élevées.

$X$$X$fait remonter la surface d'origine pour créer de hautes montagnes . La quantité de poussant vers le haut est combattue par la probabilité a priori, de sorte que moins de probabilité a priori des moyens plus de résistance. Ainsi, dans le cas de double exponentiel précédent, une montagne (ou plusieurs montagnes) qui pourrait éclater près du coin (0,0) serait beaucoup plus haute que les montagnes qui se rapprochent de (5,5), car il y a plus de résistance près de (5,5). La montagne, ou peut-être plus généralement les chaînes de montagnes, reflètent la probabilité a posteriori de trouver les vrais paramètres.

$\lambda$

$\text{Uniform}(0,5)$

Le point noir représente les vrais paramètres. Même avec 1 point d’échantillon, comme ce qui a été simulé ci-dessus, la montagne tente de contenir le vrai paramètre. Bien entendu, l'inférence avec une taille d'échantillon de 1 est incroyablement naïve, et le choix d'une taille d'échantillon aussi réduite n'était qu'illustratif.

Explorer le paysage à l'aide de la MCMC

$N$$N$$N$de la distribution postérieure, pas la distribution elle-même. Allongeant à l'extrême notre analogie montagneuse, MCMC exécute une tâche similaire à celle de demander à plusieurs reprises: "Quelle est la probabilité que ce caillou que je trouve provient de la montagne que je cherche?", Et termine son travail en renvoyant des milliers de cailloux acceptés dans l'espoir de les reconstruire la montagne d'origine. Dans MCMC et PyMC Lingo, la séquence retournée de "galets" correspond aux échantillons, appelés le plus souvent des traces .

Lorsque je dis que MCMC effectue une recherche intelligente, je veux dire que MCMC convergera, espérons-le, vers les zones de probabilité postérieure élevée. Pour ce faire, MCMC explore les positions proches et se déplace dans des zones à probabilité plus élevée. Encore une fois, peut-être que "converger" n'est pas un terme précis pour décrire la progression de MCMC. Converger implique généralement de se déplacer vers un point de l’espace, mais MCMC se déplace vers une zone plus vaste dans l’espace et se déplace au hasard dans cette zone, en prélevant des échantillons de cette zone.

Au début, renvoyer des milliers d'échantillons à l'utilisateur peut sembler être un moyen inefficace de décrire les distributions postérieures. Je dirais que c'est extrêmement efficace. Considérez les possibilités alternatives:

1. Renvoyer une formule mathématique pour les "chaînes de montagnes" impliquerait de décrire une surface à N dimensions avec des pics et des vallées arbitraires.
2. Rendre le "sommet" du paysage, tout en étant mathématiquement possible et raisonnable, car le point le plus élevé correspond à l'estimation la plus probable des inconnues, ignore la forme du paysage, ce qui, selon nous, est très important pour déterminer la confiance postérieure. dans les inconnus.

Outre les raisons de calcul, la raison la plus forte pour retourner des échantillons est probablement le fait que nous pouvons facilement utiliser la loi des grands nombres pour résoudre des problèmes difficiles à résoudre. Je reporte cette discussion pour le prochain chapitre.

Algorithmes pour exécuter MCMC

Il existe une grande famille d'algorithmes effectuant MCMC. Simplement, la plupart des algorithmes peuvent être exprimés à un niveau élevé comme suit:

1. Start at current position.
2. Propose moving to a new position (investigate a pebble near you ).
3. Accept the position based on the position's adherence to the data 
and prior distributions (ask if the pebble likely came from the mountain).
4. If you accept: Move to the new position. Return to Step 1.
5. After a large number of iterations, return the positions.

De cette façon, nous allons dans la direction générale vers les régions où les distributions postérieures existent et collectons des échantillons avec parcimonie au cours du voyage. Une fois que nous avons atteint la distribution postérieure, nous pouvons facilement collecter des échantillons car ils appartiennent probablement tous à la distribution postérieure.

Si la position actuelle de l'algorithme MCMC est dans une zone de probabilité extrêmement faible, ce qui est souvent le cas lorsque l'algorithme commence (généralement à un emplacement aléatoire dans l'espace), l'algorithme se déplacera dans des positions qui ne sont probablement pas postérieures. mais mieux que tout le reste à proximité. Ainsi, les premiers mouvements de l'algorithme ne reflètent pas le postérieur.

Il y a donc beaucoup de réponses ici, résumées dans les manuels de statistiques / probabilités, Wikipedia, etc. Je pense que nous avons des "laïcs" où je travaille; Je pense qu'ils sont dans le département marketing. Si je dois leur expliquer quelque chose de technique, j'applique la règle "montrer ne dit rien". Avec cette règle en tête, je leur montrerais probablement quelque chose comme ça.

L'idée ici est d'essayer de coder un algorithme que je peux apprendre à épeler - non pas en apprenant les centaines (milliers?) De règles du type Ajouter un fin à un mot qui se termine par un e silencieux. si la fin commence par une voyelle . Une des raisons qui ne fonctionnera pas est que je ne connais pas ces règles (je ne suis même pas sûr que celui que je viens de réciter soit correct). Au lieu de cela, je vais lui apprendre à épeler en lui montrant un groupe de mots correctement orthographiés et en lui permettant d'extraire les règles de ces mots, ce qui est plus ou moins l'essence de Machine Learning, quel que soit l'algorithme - extraction de modèle et reconnaissance de modèle .

Le critère de succès est l’épellation correcte d’un mot que l’algorithme n’a jamais vu auparavant (je me rends compte que cela peut arriver par hasard, mais cela ne se produira pas pour les spécialistes du marketing, j’ignorerai donc, et en plus, je vais avoir l’algorithme essayez d’épeler non pas un mot, mais beaucoup, il est donc peu probable que nous soyons trompés par quelques suppositions chanceuses).

Il y a une heure environ, j'ai téléchargé (sous forme de fichier texte) de l'excellent site du projet Gutenberg, le roman de Herman Hesse, Siddhartha . J'utiliserai les mots de ce roman pour apprendre à l'algorithme comment épeler.

J'ai donc codé l'algorithme ci-dessous qui a balayé ce roman, trois lettres à la fois (chaque mot a un caractère supplémentaire à la fin, qui est un "espace" ou la fin du mot). Les séquences de trois lettres peuvent en dire long. Par exemple, la lettre «q» est presque toujours suivie de «u»; la séquence 'ty' se produit généralement à la fin d'un mot; z le fait rarement, et ainsi de suite. (Remarque: j'aurais tout aussi bien pu lui donner des mots entiers pour l'entraîner à parler en phrases complètes - exactement la même idée, juste quelques ajustements au code.)

Cependant, rien de tout cela ne concerne MCMC, cela se produit après l’entraînement, lorsque nous donnons à l’algorithme quelques lettres aléatoires (sous forme de graine) et qu’il commence à former des «mots». Comment l'algorithme construit-il des mots? Imaginez qu'il ait le bloc 'en tant que'; quelle lettre ajoute-t-il ensuite? Au cours de la formation, l’algorithme a construit une matrice de fréquence massive * séquence-séquence * parmi tous les milliers de mots du roman. Quelque part dans cette matrice se trouve le bloc de trois lettres "qua" et les fréquences des caractères pouvant suivre la séquence. L'algorithme sélectionne une lettre en fonction des fréquences qui pourraient éventuellement la suivre. Donc, la lettre que l'algorithme sélectionne ensuite dépend - et uniquement - des trois derniers de sa file d'attente pour la construction de mots.

Donc, c'est un algorithme de Markov Chain Monte Carlo.

Je pense que la meilleure façon d’illustrer son fonctionnement est de montrer les résultats en fonction des différents niveaux de formation. Le niveau d’entraînement varie en fonction du nombre de passages de l’algorithme, mais plus le nombre de passages est élevé, plus la fidélité des matrices de fréquence de séquence de lettres est élevée. Voici les résultats - sous la forme de chaînes de 100 caractères générées par l'algorithme - après une formation sur le roman 'Siddharta'.

Un seul passage dans le roman, Siddhartha :

alors whoicks ger wiff tous les mothany debout ar vous livide theartim boueux sullintionexpreach son sible son

(Tout de suite, il a appris à parler presque parfaitement le gallois; je ne m'y attendais pas.)

Après deux passages dans le roman:

le spectacle ack wor prenskinith wass un twor a vu que pas encore de théatre terre chahatingle était l'ov là

Après 10 passes:

malgré, mais le devrait prier avec ack maintenant avoir de l'eau son chien levier douleur pieds chacun pas la mémoire faible

Et voici le code (en Python, je suis presque sûr que cela pourrait être fait en R en utilisant un paquet MCMC, parmi lequel il y en a plusieurs, en seulement 3-4 lignes)

def create_words_string(raw_string) :
  """ in case I wanted to use training data in sentence/paragraph form; 
      this function will parse a raw text string into a nice list of words;
      filtering: keep only words having  more than 3 letters and remove 
      punctuation, etc.
  """
  pattern = r'\b[A-Za-z]{3,}\b'
  pat_obj = re.compile(pattern)
  words = [ word.lower() for word in pat_obj.findall(raw_string) ]
  pattern = r'\b[vixlm]+\b'
  pat_obj = re.compile(pattern)
  return " ".join([ word for word in words if not pat_obj.search(word) ])

def create_markov_dict(words_string):
  # initialize variables
  wb1, wb2, wb3 = " ", " ", " "
  l1, l2, l3 = wb1, wb2, wb3
  dx = {}
  for ch in words_string :
    dx.setdefault( (l1, l2, l3), [] ).append(ch)
    l1, l2, l3 = l2, l3, ch
  return dx

def generate_newtext(markov_dict) :
  simulated_text = ""
  l1, l2, l3 = " ", " ", " "
  for c in range(100) :
    next_letter = sample( markov_dict[(l1, l2, l3)], 1)[0]
    simulated_text += next_letter
    l1, l2, l3 = l2, l3, next_letter
  return simulated_text

if __name__=="__main__" :
  # n = number of passes through the training text
  n = 1
  q1 = create_words_string(n * raw_str)
  q2 = create_markov_dict(q1)
  q3 = generate_newtext(q2)
  print(q3)

MCMC est généralement utilisé comme alternative aux techniques de simulation brutes de Monte Carlo. MCMC et d’autres techniques de Monte Carlo sont utilisées pour évaluer des intégrales difficiles, mais MCMC peut être utilisé plus généralement.

Par exemple, un problème courant en statistique consiste à calculer le résultat moyen associé à un modèle probabiliste / stochastique. Les techniques MCMC et Monte Carlo résoudraient ce problème en générant une séquence de résultats simulés que nous pourrions utiliser pour estimer la moyenne vraie.

Les techniques MCMC et les méthodes brutes de Monte Carlo fonctionnent car la proportion à long terme de simulations égale à un résultat donné sera égale * à la probabilité modélisée de ce résultat. Par conséquent, en générant suffisamment de simulations, les résultats produits par les deux méthodes seront précis.

* Je dis égal, bien qu'en général je devrais parler d'ensembles mesurables. Un profane, cependant, ne serait probablement pas intéressé par ceci *

Cependant, bien que le Monte Carlo brut implique la production de nombreuses simulations indépendantes, chacune étant distribuée selon la distribution modélisée, MCMC implique la création d’une marche aléatoire qui "visite" à long terme chaque résultat avec la fréquence souhaitée.

Pour MCMC, le truc consiste donc à choisir une marche aléatoire qui "visitera" chaque résultat avec les fréquences souhaitées à long terme.

Un exemple simple pourrait être de simuler à partir d'un modèle indiquant que la probabilité du résultat "A" est de 0,5 et celle du résultat "B" de 0,5. Dans ce cas, si je commençais la marche aléatoire à la position "A" et que je prescrivais qu'à chaque étape il basculait vers l'autre position avec une probabilité de 0,2 (ou toute autre probabilité supérieure à 0), je pouvais être sûr qu'après un grand nombre de pas de la marche aléatoire aurait visité chacun des points "A" et "B" dans environ 50% des pas - conformément aux probabilités prescrites par notre modèle

Ceci est évidemment un exemple très ennuyeux. Cependant, il s'avère que MCMC est souvent applicable dans des situations dans lesquelles il est difficile d'appliquer des techniques standard de Monte Carlo ou autres.

Vous pouvez trouver un article qui couvre les bases de ce que c'est et pourquoi cela fonctionne ici:

http://wellredd.uk/basics-markov-chain-monte-carlo/

Je suis un analyste de l’ADN qui utilise un logiciel de génotypage probabiliste totalement continu pour interpréter les preuves ADN et je dois expliquer comment cela fonctionne devant un jury. Certes, nous simplifions excessivement et je me rends compte qu'une partie de cette simplification sacrifie la précision de certains détails au nom de l'amélioration de la compréhension globale. Mais, dans le contexte d'un jury comprenant comment ce processus est utilisé dans l'interprétation de l'ADN sans diplômes universitaires ni années d'expérience professionnelle, ils comprennent l'essentiel :)

Contexte: Le logiciel utilise la métropole Hastings MCMC et un modèle biologique imitant le comportement connu des profils ADN (le modèle est construit sur la base de données de validation générées par l’analyse en laboratoire de nombreux profils ADN de conditions connues représentant la plage rencontrée dans le cas inconnu). Il y a 8 chaînes indépendantes et nous évaluons la convergence pour déterminer s'il convient de réexécuter en augmentant le taux de gravure et les acceptations consécutives (acceptation par défaut de gravure 100k et acceptations après 400k)

À la demande de l’accusation / de la défense à propos de MCMC: nous expliquons qu’il s’agit de markov chain Monte Carlo et représente une classe / un type spécial d’algorithme utilisé pour la résolution de problèmes complexes et qu’un algorithme est un simple mot faisant référence à une série de procédures ou de routines effectuées par un ordinateur ... Les algorithmes mcmc fonctionnent en proposant une solution, en simulant cette solution, puis en évaluant dans quelle mesure cette simulation reflète les données de preuves réellement observées ... une simulation qui convient bien à l'observation de preuves a une probabilité plus élevée une simulation qui ne correspond pas bien à l'observation ... au cours de nombreux échantillonnages / suppositions répétés des solutions proposées, les chaînes de Markov s'éloignent des solutions à faible probabilité pour adopter les solutions à forte probabilité qui correspondent / expliquent mieux le profil des preuves observées jusqu'à l'équilibre final atteint,ce qui signifie que l'algorithme a une capacité limitée à échantillonner de nouvelles propositions générant des probabilités considérablement accrues

Interrogé sur la métropole Hastings: nous expliquons qu'il s'agit d'un raffinement de l'algorithme MCMC décrivant son processus de prise de décision acceptant ou rejetant une proposition ... généralement expliqué par une analogie du jeu pour enfants "chaud / froid", mais j'ai peut-être envisagé d'utiliser " balayez à droite ou à gauche "quand le jury est particulièrement jeune !! : p Mais, en utilisant notre analogie chaud / froid, nous acceptons toujours une hypothèse à chaud et acceptons parfois une hypothèse à froid une fraction du temps. Nous expliquons toutefois que le but de l'acceptation de l'hypothèse à froid est de garantir aux chaînes un large éventail de possibilités, opposé à rester coincé autour d'une proposition particulière avant l'équilibre réel

Édité pour ajouter / clarifier: avec l'analogie chaud / froid, nous expliquons que dans le jeu pour enfants, le leader choisit un objet / une zone cible dans la pièce et les joueurs supposent à tour de rôle dans quelle direction se déplacer par rapport à leur position / position actuelle. Le chef leur dit de changer de position / de changer de position s'il le faut et qu'ils perdent leur tour ou de rester en place s'il le faut. De même, dans notre logiciel, la décision de déplacer / accepter ne dépend que de la probabilité de la proposition comparée à la probabilité de la position actuellement occupée ... CEPENDANT, la cible est prédéfinie / connue du leader du jeu pour enfants alors que le la cible dans notre logiciel n'est pas prédéfinie - elle est complètement inconnue (et pourquoi

Comme je le disais, super super basique et absolument dépourvu de détails techniques pour améliorer la compréhension - nous nous efforçons d'expliquer à peu près au niveau d'éducation moyen. N'hésitez pas à faire des suggestions. Je vais les incorporer.

Cette question est large mais les réponses sont souvent assez informelles. Vous pouvez également consulter cet article qui donne une description mathématique concise d’une vaste classe d’algorithmes MCMC, notamment les algorithmes de Metropolis-Hastings, l’échantillonnage de Gibbs, les méthodes à variables auxiliaires de Metropolis et de Gibbs, l’échantillonnage par tranches, les propositions récursives, l’échantillonnage directionnel, les Hamiltonien Monte Carlo, échantillonnage NUTS, algorithmes pseudo-marginaux de Metropolis-Hastings et hamiltonien pseudo-marginal de Monte Carlo, comme indiqué par les auteurs.

Une critique crédible est donnée ici

Je trouverai plus de temps pour élaborer son contenu au format stackexchange.

$f(x,y)=z=x^2+2*x*y$$(x,y)$$f(x,y)$$f(x,y)$

$f(x,y,z,t,s,...,zzz)$

Cette vidéo (qui commence à 17h50) contient une très bonne déclaration d'intuition.

Imaginez que vous souhaitiez échantillonner des points situés sur les branches vertes (multidimensionnelles) de cette image. Si vous jetez des points sur tout le super-espace noir et vérifiez leur valeur, vous gaspillez beaucoup d’énergie d’échantillonnage (recherche). Il serait donc plus judicieux de contrôler votre stratégie d’échantillonnage (qui peut être automatisée) pour choisir des points plus proches des branches vertes (là où cela compte). Les branches vertes peuvent être trouvées en étant frappées une fois accidentellement (ou contrôlées), et le reste de l'effort d'échantillonnage (points rouges) sera généré par la suite. Le rouge est attiré par la ligne verte en raison de la matrice de transition de Markov qui fait office de moteur d’échantillonnage.

Ainsi, en termes simples, MCMC est une méthode d'échantillonnage permettant d'économiser de l'énergie (à faible coût), en particulier lorsque vous travaillez dans un espace gigantesque et «sombre» (multidimensionnel).