Revue de Metropolis Hastings - Vers la science des données - Support IVY : Encyclopédie #1 et site d'informations, Conseils, Tutorials, Guides et plus

Table des matières

ArticlesA lire

Normalisation – Vitrine – Programmation

Effet du traitement dans l’étude observationnelle

Quelles sont les techniques pour détecter les anomalies

Réseaux adverses génératifs – Vers la science des données

Revue de Metropolis Hastings – Vers la science des données

Quand Randomness est devenu le leader

Introduction très courte

Metropolis Hastings est une classe d’algorithmes d’échantillonnage MCMC (Markov Chain Monte Carlo). Son utilisation la plus courante consiste à optimiser l’échantillonnage à partir d’une distribution postérieure lorsque la forme analytique est intraitable ou peu plausible à échantillonner. Ce post suit les statistiques et les étapes historiques qui ont conduit à l’apparition de cet algorithme.

Inférence statistique

La statistique est une discipline inspirante. L’idée selon laquelle chaque source de données: la taille du condo à New York, le revenu annuel en Afrique ou la distribution de noms sûrs au Japon peut être gérée en utilisant le même ensemble d’outils mathématiques et fournir un corollaire cohérent ne doit pas être considérée comme acquise. Comme la physique utilise ses équations rigoureuses pour décrire l’ensemble des phénomènes du monde réel, les statistiques utilisent une assez petite quantité d’outils analytiques pour clarifier le comportement de toutes les données du monde réel.

L’un des principaux problèmes d’inférence en statistique est l’estimation des paramètres de distribution tels que l’identification des paramètres de la gaussienne (moyenne et stdev) est l’une des principales attributions des statisticiens. Pour utiliser des distributions, il faut définir un cadre de probabilité. Il existe deux approches principales pour de tels cadres:

· Le fréquentiste

· Le bayésien

La fréquentatrice n’a aucune connaissance préalable des données, elle voit la probabilité comme une fréquence à long terme. Chaque essai est une expérience unique dans une séquence infinie. Elle n’attribue jamais de probabilité aux paramètres, c’est-à-dire qu’une moyenne d’échantillon est une valeur mesurable fixe. Néanmoins, comme il est fixe, nous ne pouvons pas lui attribuer de probabilité. Selon les termes d’un statisticien: «il n’y a aucune probabilité d’avoir de la soupe aujourd’hui», car aujourd’hui n’est pas une séquence infinie d’événements.

Bayesian d’autre part a une croyance. Le bayésien a une croyance préalable sur la distribution du paramètre. Les données sont agrégées afin de mettre à jour cette croyance. La croyance en la distribution des paramètres se manifeste dans la distribution précédente et la probabilité est la probabilité d’obtenir les données sur cette croyance. Le produit de ces deux fonctions est proportionnel à la fonction postérieure. Dans le monde des Bayes, non seulement les données mais aussi les paramètres sont des variables aléatoires. Contrairement au fréquentiste, une fois les données obtenues, il ne s’agit plus d’une variable aléatoire.

De manière plus rigoureuse, nous pouvons écrire des modèles bayésiens en utilisant la formule de Bayes:

Où H est notre hypothèse sur les paramètres et D les données.

P (H) est la distribution a priori sur les paramètres qui est notre hypothèse sur la distribution des paramètres
P (D | H) est la vraisemblance: la probabilité que, étant donné un ensemble de paramètres H, nous obtiendrons l’échantillon D.
P (H | D) est la distribution postérieure

P (D) est la distribution des données

L’objectif est d’estimer le postérieur sur l’a priori, la vraisemblance et la distribution des données

L’exemple binomial-bêta

Quelle est la probabilité qu’un joueur de basket-ball fasse le prochain coup franc compte tenu de ses statistiques?

Prenons l’exemple d’un joueur qui a fait 80 tentatives sur 100. La distribution naturelle de ce problème est la distribution binomiale avec paramètre q. On sait que la probabilité de y lancer qu’il a fait de n devient:

Nous devons encore intégrer notre croyance antérieure. Nous supposons que 0 < q <1 et qu’il a une distribution bêta avec les paramètres positifs α , β

On a :

Notez que

Nous pouvons écrire cela explicitement

Quelle est la distribution bêta avec les paramètres α + y ,β + n-y

Il nous suffit de définir les valeurs de α et β (notre «croyance probabiliste»).

Nous devons noter les points suivants:

1. Le postérieur a une distance bêta comme la précédente. On peut considérer que les paramètres ont été mis à jour.

2. Lorsque le postérieur a la même distribution que l’a priori, nous disons que l’a priori est le conjugué de la vraisemblance, son «Conjugué antérieur»

Cet exemple illustre une méthode pratique pour utiliser l’inférence bayésienne. Cependant, comme nous le savons dans d’autres domaines, la vie est parfois fastidieuse. Souvent, lorsque nous étudions les problèmes bayésiens du «monde réel», nous pouvons rencontrer deux obstacles:

Le terme de normalisation (le dénominateur) est insoluble.

Nous n’avons pas une belle fonction antérieure pour la probabilité

Dans cet article, nous discuterons des méthodes pour résoudre ces obstacles.

Monte Carlo (ou simulation Monte Carlo) est une classe d’algorithmes qui utilise l’aléatoire et l’échantillonnage pour résoudre des problèmes mathématiques. En particulier, il est utilisé lorsque la fonction est difficile à écrire analytiquement (il n’y a pas de forme fermée). Nous utilisons ces méthodes pour résoudre des problèmes tels que l’intégration ou l’optimisation. Depuis qu’elles ont été développées, les méthodes de Monte Carlo ont changé l’approche de l’utilisation des simulations. Ils offrent des solutions aux problèmes déterministes en utilisant la probabilité.

Histoire

Au cours des années 1930, Fermi a étudié le problème de diffusion des neutrons en utilisant des méthodes aléatoires. Cependant, il n’a jamais publié. En 1946, le monde travaillait sur une nouvelle invention: un ordinateur rapide. À cette époque, Stanislaw Ulam, l’un des vétérans du projet de Manhattan, était curieux de savoir comment estimer les chances de gagner le Solitaire. Il s’est rendu compte que la «pensée abstraite» est moins bénéfique que de simplement laisser la nouvelle machine simuler ce problème et simplement compter les résultats. Cette pensée l’a amené à réfléchir à des problèmes de physique tels que la diffusion des neutrons. Avec Von Neumann, ils sont devenus les pionniers de ces méthodes. Mathématiquement, les premières mesures qu’ils ont prises ont été de convertir des équations différentielles en une forme conviviale MC (comme dit plus loin, ils utilisent des méthodes stochastiques pour résoudre des problèmes déterministes). Comme ce projet était secret, Metropolis (un co-chercheur qui dirigeait le projet MANIAC deux ans plus tard) a donné le nom de code Monte Carlo (là, l’oncle d’Ulam avait l’habitude de jouer). L’apparition de MC a créé un besoin de meilleurs générateurs aléatoires, donc Von Neumann a développé la machine à pseudo-générateur (connue sous le nom de méthode du carré moyen). Ces méthodes ont été utilisées à Los Alamos un peu plus tard dans l’invention de la bombe à hydrogène.

Monte Carlo – Exemple classique: estimation de PI

Intégration Monte Carlo

L’apparition de Monte Carlo a offert une grande quantité d’outils numériques pour résoudre des problèmes mathématiques. Un éminent était le intégrales définies

L’objectif était d’estimer l’intégrale d’une fonction h sur un domaine X. Ce problème peut être défini comme le calcul de la moyenne suivante:

où X est une variable aléatoire et F une fonction de densité

Nous pouvons utiliser l’estimation MC

Simplement en randomisant la séquence de x de F indépendamment

le loi forte des grands nombres implique que cet estimateur converge vers la moyenne analytique de h en dessous de f presque sûrement

Exemple – Intégrale définie

Considérez l’intégrale suivante

Il peut être écrit comme suit:

Ainsi en utilisant l’estimateur suivant:

Un nouvel obstacle

Nous avons un outil stochastique qui rend les problèmes numériques traitables. Cependant, un nouveau mec est arrivé à la fête: pour les distributions telles que gaussiennes ou uniformes, nous pouvons toujours trouver un échantillonneur. Mais parfois, nous sommes intéressés par l’échantillonnage à partir de distributions que notre s / w n’a pas d’échantillonneur pertinent. Pour souligner, connaître f n’implique pas d’avoir son sampler. De toute évidence, nous devons rechercher des solutions de contournement pour de tels cas.

Méthode CDF inverse

Rappeler que fonction de distribution cumulative (CDF) d’une variable aléatoire X est définie par

Le CDF inverse (algorithme de transformation inverse) vise à échantillonner à partir d’une distribution lorsque l’on a son cumulatif inverse.

Depuis le CDF F est une fonction non décroissante sur la droite, on peut définir un fonction inverse généralisée g

Exemple de distribution exponentielle dans le monde réel

Considérons la distribution exponentielle, nous pouvons définir

Considérez un r.v X, avec une distribution F que nous ne pouvons pas échantillonner, où g est donné. Nous pouvons échantillonner comme suit:

U ~ Unif (0,1) et X = G (U), nous pouvons simuler à partir de F

Exemple

Considérons l’intervalle (a, b). Nous souhaitons échantillonner

X ~ N (μ, σ) I (a

Accepter – Méthode de rejet

Une méthode supplémentaire pour échantillonner à partir de fonctions difficiles à échantillonner est la méthode d’acceptation-rejet. Ici, nous souhaitons échantillonner à partir d’un pdf cible F où F est connu jusqu’à une constante. Supposons que nous avons un moyen simple d’échantillonner la fonction g (par exemple uniforme ou gaussien) que nous appelons fonction de proposition. De plus, nous supposons qu’il existe:

Idéalement, nous avons

Nous pouvons utiliser l’algorithme suivant pour simuler à partir de F

Le taux d’acceptation est alors de 1 / m. La constante inconnue n’influence pas le taux d’acceptation. Pour voir cela, nous la désignons cette constante par t

Ce qui implique

Motivation de l’algorithme

L’idée principale derrière cet algorithme est la capacité d’envelopper F en utilisant le produit de g et la constante inconnue.

Où l’axe X représente les échantillons et l’axe Y représente la quantité u * M * g (x). La sortie d’un tel algorithme suit le graphique suivant:

Chaîne de Markov

La propriété Markov déclare que dans une séquence d’expériences, connaître le présent rend le passé et l’avenir indépendants. Les expériences sont sans mémoire. De manière plus rigoureuse:

Si P ne dépend pas de t, on dit que c’est homogène.

Exemples

Homme ivre

Un exemple classique pour les chaînes de Markov est le problème de «l’homme ivre». Nous souhaitons estimer la place d’un homme ivre à la fois t. Il est clair que nous pouvons mesurer l’ensemble de son mouvement et construire une distribution «conditionnée sur toute la trajectoire». Cependant, si nous connaissons sa place au moment t-1 nous avons la distribution complète au cours de l’étape suivante. On peut imaginer que si au moment t-1 nous observons en arrière, l’emplacement de l’ivrogne au moment t-x, pour X entier, n’a pas de sens pour prédire le temps t. Les probabilités pour l’étape suivante sont entièrement déterminées par le lieu actuel.

Jour de pluie

Traditionnellement, nous supposons que la question de savoir s’il pleuvra demain ou non est markovienne. Nous nous attendons à ce que la connaissance de la météo d’aujourd’hui fournisse une distribution sur la météo de demain. Il peut être représenté à l’aide de cette matrice:

La ligne supérieure et la colonne de gauche font référence à la pluie (c’est-à-dire que nous avons une probabilité de 0,9 que si aujourd’hui il pleut, alors demain ce sera aussi, et 0,2 que si aujourd’hui il fait beau alors demain il pleuvra)

Donc, nous connaissons maintenant un MC (Monte Carlo) et un autre MC (Chaîne de Markov). C’est le bon moment pour essayer de les combiner ensemble.

Les méthodes MCMC visent à échantillonner à partir d’une distribution que nous connaissons jusqu’à une constante mais ne pouvons pas échantillonner directement. Afin d’expliquer Metropolis Hastings, nous présenterons sa terminologie de base.

Notations et terminologie (trucs rigoureux et amusants pour les nerds)

Accessible signifie en fait que si nous sommes actuellement sur l’état u il y a une probabilité positive que nous arrivions à déclarer v en un nombre fini d’étapes

Communiquer– Deux états u et v sont communiquer si u-> v et v-> u

À savoir, deux États sont communiquer si ils sont accessibles dans les deux sens.

Irréductible – Si tous les états d’une chaîne sont communiquer, la chaîne est irréductible .

Récurrent Un état v est récurrent si la probabilité qu’il revienne par étapes finies est 1.

Récurrence – Une chaîne de Markov est appelée Récurrence si pour tous ses états v sont récurrent. Si ce n’est pas la récidive c’est Transitoire . Une chaîne récurrente qui, pour chaque état, le temps de retour attendu est fini, est appelée positif récurrent sinon c’est null récurrent.

À savoir, si vous partez de l’état j , vous reviendrez à j uniquement par pas de temps qui sont des multiplications de d. Si d = 1 on dit que j est a-périodique

De toute évidence, si les États u, v sont communiquer leurs périodes sont similaires.

Ergodicité -Un état est ergodique si elle est récurrente a-périodique et positive. Si tous les états d’une chaîne sont ergodiques, alors la chaîne est ergodique

Introduction et définition du problème

Metropolis Hastings est considéré comme le tout premier algorithme MCMC. Comme vous l’avez déjà déduit des sections précédentes, il vise à échantillonner à partir d’une distribution arbitraire qui n’est pas «échantillonnable» et utilise les propriétés MCMC.

Le début

En 1953, Metrpolis, Rosenbluth, Rosenbluth, Teller et Teller (en effet, trop de Juifs, de conjoints et une corrélation sémantique étendue), ont étudié les phénomènes de transition de phase. Ils ont publié un article « Calculs d’équations d’état par des machines à calcul rapide« . Le but de cet article était de traiter le «Disque dur dans une boîte« Problème:

Supposons que nous ayons une boîte contenant des molécules de substance qui ne peuvent pas se chevaucher (« disque dur”). Ils ont étudié l’équation du gaz idéal.

Méthodologie de recherche

Le groupe de recherche a utilisé la méthodologie suivante:

Température (T ) c’est réglé

Quantité de particules (n) c’est réglé

Volume de gaz (V) c’est réglé

Ils ont étudié la pression (P) as

En suivant ces hypothèses, ils ont entouré chaque particule d’un cube fixe et ont défini une discrétisation au sein de ce cube. L’idée était de randomiser une nouvelle paire de coordonnées avec dans le cube tant qu’elles sont valides (pas de chevauchement). Ils ont appelé cette étape symétrique Fonction de proposition (voir la section d’acceptation-rejet)

Le processus était donc:

Metropolis était le chercheur le plus expérimenté. Comme je l’ai mentionné ci-dessus, il avait une expérience de travail avec Ulam et Von Neumann à Monte-Carlo. Cependant, il y a des affirmations qui sont venues (principalement de Rosenbluth mais aussi de Teller) qu’ils méritent tous un crédit (Teller, comme vous le savez tous, est devenu célèbre pour une autre invention non négligée).

En 1970, Hastings a publié un article «Méthodes d’échantillonnage Monte Carlo utilisant les chaînes de Markov et leurs applications», Il a étendu la solution à la proposition non symétrique. Pour proposition q l’algorithme final est le suivant:

Une remarque évidente: dans MCMC, les échantillons ne sont pas indépendants. Ainsi, ayant plutôt un M fixe comme en accept-rejet, nous dupliquons l’échantillon précédent.

Il existe plusieurs exemples classiques pour M.H. algorithme:

Une description plus organisée de l’échantillonneur bayésien est présentée ici

Modèle de covariance

Les intrigues au-delà montrent:

1. L’échantillon de données

2. L’ensemble de Rho démontré

3. La fonction postérieure

Désavantages

M.H a des avantages mais aussi quelques inconvénients:

1 Bien qu’il fonctionne nettement mieux en haute dimension que les autres algorithmes d’acceptation-rejet (il gère assez bien la malédiction de la conditionnalité), il a un taux de «brûlure», c’est-à-dire qu’il converge lentement et que l’objectif n’est pas atteint immédiatement.

2 Les événements rares sont à peine pris.

3 échantillons sont corrélés

Quelle est la prochaine?

Metropolis Hastings a déjà des améliorations:

1. Le plus célèbre est l’algorithme de Gibbs qui est couramment utilisé dans des applications telles que R.B.M et L.D.A.

2. En physique et chimie physique, le stochastique Recuit algorithme est massivement utilisé.

3 Une amélioration intéressante de M.H. est la chaîne hamiltonienne de Markov (H.M.C)

Sur ces sujets, nous parlerons dans un autre article.

Remerciements

Ce poste a demandé à quelqu’un de me mettre au défi de m’asseoir et de l’écrire et à quelqu’un de vérifier que je ne suis pas trop incohérent. Le premier a été fait par Shlomo Kashani qui a fait sa corvée en tant qu’évangéliste ML, et le second par Savvy Ilana Volfin. Ils ont tous deux fait une relecture massive, donc tous les échecs sont de leur faute.

Bibliographie

https://towardsdatascience.com/a-zero-math-introduction-to-markov-chain-monte-carlo-methods-dcba889e0c50

https://bookdown.org/rdpeng/advstatcomp/markov-chain-monte-carlo.html

Markov Chain Monte Carlo en pratique Gilks, Richardson

http://www.columbia.edu/~mh2078/MachineLearningORFE/MCMC_Bayes.pdf

https://towardsdatascience.com/from-scratch-bayesian-inference-markov-chain-monte-carlo-and-metropolis-hastings-in-python-ef21a29e25a

https://www.probabilisticworld.com/frequentist-bayesian-approaches-inferential-statistics/

https://ocw.mit.edu/courses/mathematics/18-05-introduction-to-probability-and-statistics-spring-2014/readings/MIT18_05S14_Reading20.pdf

https://365datascience.com/bayesian-vs-frequentist-approach/

https://www.geeksforgeeks.org/estimating-value-pi-using-monte-carlo/

https://la-science.lanl.gov/cgi-bin/getfile?00326866.pdf

http://www.mit.edu/~ilkery/papers/MetropolisHastingsSampling.pdf