Algoritme de Metropolis-Hastings

En estadística i física estadística, el algoritme de Metropolis-Hastings és un método de Mont Carlo en cadena de Markov per a obtindre una seqüència de mostres aleatòries en una distribució de provabilitat a partir de la qual és difícil el mostreig directe. Esta seqüència es pot usar per a aproximar la distribució (per eixemple, per a generar un histograma) o per a calcular una integral (per eixemple, un valor esperat). Metropolis-Hastings i uns atres algoritmes Montecarlo en cadena de Markov s'usen generalment per al mostreig de distribucions multidimensionales, especialment quan el número de dimensions és alt. Per a les distribucions unidimensionals, generalment hi ha atres métodos (per eixemple, el mostreig de rebuig adaptatiu) que poden generar directament mostres independents de la distribució, i estos estan lliures del problema de les mostres autocorrelacionadas, inherent als métodos Montecarlo en cadena de Markov.

Història

l'algoritme du el nom de Nicholas Metropolis, autor de l'artícul 1953 Equation of State Calculations by Fast Computing Machines junt en Arianna W. Rosenbluth, Marshall Rosenbluth, Augusta H. Teller i Edward Teller. Este artícul va propondre l'algoritme per al cas de distribucions de propostes simètriques, i W. K. Hastings ho va estendre al cas més general en 1970.

Existix certa controvèrsia sobre el crèdit per al desenroll de l'algoritme. Metropolis havia falcat el terme "Montecarlo" en un artícul anterior en Stanislav Ulam, estava familiarizado en els aspectes computacionals del método i va dirigir el grup en la Divisió Teòrica que va dissenyar i va construir la computadora MANIAC I utilisada en els experiments en 1952. No obstant, abans de 2003, no hi havia un conte detallat del desenroll de l'algoritme. Després, poc abans de la seua mort, Marshall Rosenbluth va assistir a una conferència de 2003 en LANL per a commemorar el 50 aniversari de la publicació de 1953. En esta conferència, Rosenbluth va descriure l'algoritme i el seu desenroll en una presentació titulada "Génesis de l'algoritme de Mont Carlo per a la mecànica estadística". Gubernatis fa més aclariments històrics en un artícul de revista de 2005 que relata la conferència del 50 aniversari. Rosenbluth deixa en clar que ell i la seua esposa Arianna varen fer el treball, i que Metropolis no va eixercitar cap paper en el desenroll que no siga proporcionar temps de computadora.

Açò contradiu una versió d'Edward Teller, qui afirma en les seues memòries que els cinc autors de l'artícul de 1953 varen treballar junts durant "dies (i nits)". Pel contrari, el relat detallat de Rosenbluth acredita a Teller una sugerència crucial pero primerenca de "aprofitar la mecànica estadística i prendre promijos de conjunt en lloc de seguir una cinemàtica detallada". Açò, diu Rosenbluth, ho va fer pensar en l'enfocament generalisat de Mont Carlo, un tema que, segons ell, havia discutit a sovint en Von Neumann. Arianna va contar (a Gubernatis en 2003) que Augusta Teller va començar el treball de la computadora, pero que la pròpia Arianna es va fer càrrec i va escriure el còdic des de zero. En una història oral registrada poc abans de la seua mort, Rosenbluth novament acredita a Teller per plantejar el problema original, a ell mateixa per resoldre-ho, i a Arianna per programar la computadora. En térmens de reputació, hi ha poques raons per a qüestionar el relat de Rosenbluth. En una memòria biogràfica de Rosenbluth, Freeman Dyson escriu:

Moltes voltes vaig ser en Rosenbluth, li vaig fer una pregunta [...] i vaig rebre una resposta en dos minuts. Per lo general, em duria una semana d'ardu treball comprendre en detalle per qué la resposta de Rosenbluth era correcta. Tenia una capacitat sorprenent per a vore a través d'una situació física complicada i aplegar a la resposta correcta per mig d'arguments físics. Enrico Fermi va ser l'únic un atre físic que he conegut que era igual a Rosenbluth en la seua comprensió intuïtiva de la física.

Intuïció

L'algoritme de Metropolis-Hastings pot extraure mostres de qualsevol distribució de provabilitat $P(x)$, sempre que conegam una funció $f(x)$ proporcional a la densitat de $P$ i els valors de $f(x)$ poden ser calculats. L'únic requisit és que $f(x)$ deu ser proporcional a la densitat, en lloc de ser exactament igual a ell, fa que l'algoritme de Metropolis-Hastings siga particularment útil, perque calcular el factor de normalisació necessari a sovint és extremadament difícil en la pràctica.

L'algoritme Metropolis-Hastings funciona generant una seqüència de valors de mostra de tal manera que, a mida que es produïxen més i més valors de mostra, la distribució de valors s'aproxima més a la distribució desijada $P(x)$. Estos valors de mostra es produïxen de forma iterativa, i la distribució de la següent mostra depén solament del valor de mostra actual (convertint aixina la seqüència de mostres en una cadena de Markov). Específicament, en cada iteración, l'algoritme elegix un candidat per al següent valor de mostra basat en el valor de mostra actual. Després, en certa provabilitat, el candidat és acceptat (en el cas del qual el valor candidat s'usa en la pròxima iteración) o rebujat (en el cas de la qual el valor candidat es descarta i el valor actual es reutilisa en la pròxima iteración): la provabilitat d'acceptació es determina comparant els valors de la funció $f(x)$ dels valors de mostra actuals i candidats sobre la distribució desijada $P(x)$.

Per a fins d'ilustració, a continuació es descriu l'algoritme Metropolis, un cas especial de l'algoritme Metropolis-Hastings a on la funció de la proposta és simètrica.

Algoritme de Metropolis (distribució de proposta simètrica)

Deixa a $f(x)$ ser una funció que siga proporcional a la distribució de provabilitat desijada $P(x)$ (un objectiu de distribució).

1. Inicialización: elegixca un punt arbitrari $x_t$ ser la primera mostra i elegir una densitat de provabilitat arbitrària $g(x\mid y)$ (a voltes escrita $Q(x\mid y)$) que sugerix un candidat per al següent valor de mostra $x$, donat el valor de mostra anterior $y$. En esta secció, s'assumix que el valor de $g$ és simètric; en atres paraules, est deu satisfer $g(x\mid y)=g(y\mid x)$. Una opció habitual és deixar que $g(x\mid y)$ siga una distribució gaussiana centrada en $y$, aixina els punts propencs a $y$ són més propensos a ser visitats a continuació, convertint la seqüència de mostres en una caminada aleatòria. La funció $g$ es denomina densitat de proposta o distribució de bots.
2. Per a cada iteración t:
   • Genera un candidat $x^{\prime }$ per a la següent mostra seleccionandolo de la distribució $g(x^{\prime }\mid x_t)$.
   • Calcula el ràtio d'acceptació $\alpha =f(x^{\prime })/f(x_t)$, que s'utilisarà per a decidir si accepta o rebuja al candidat. Ya que f és proporcional a la densitat de P, podem deduir que $\alpha =f(x^{\prime })/f(x_t)=P(x^{\prime })/P(x_t)$.
   • Acceptar o rebujar:
     • Genera un número aleatori uniforme $u\in [0,1]$.
     • Si $u\le \alpha$, llavors accepta el candidat de manera que $x_{t+1}=x^{\prime }$,
     • Si $u>\alpha$, llavors rebuja el candidat i coloca $x_{t+1}=x_t$ en el seu lloc.

Este algoritme continua intentant moure's aleatoriamente pel espai mostral, a voltes acceptant els moviments i unes atres permaneixent en el seu lloc. Note's que la relació d'acceptació $\alpha$ indica quina tan provable és la nova mostra proposta sobre la mostra actual, d'acort en la distribució $P(x)$. Si intentem moure-nos a un punt que siga més provable que el punt existent (és dir, un punt en una regió de major densitat de $P(x)$), sempre acceptarem el moviment. No obstant, si intentem moure-nos a un punt menys provable, a voltes rebujarem el moviment, i quant major siga la caiguda relativa de la provabilitat, més provable és que rebugem el nou punt. Per lo tant, tindrem que permanéixer en (i tornar grans cantitats de mostres de) regions d'alta densitat de $P(x)$, mentres visita ocasionalment regions de baixa densitat. Intuitivamente, esta és la raó per la qual este algoritme funciona i torna mostres que seguixen la distribució desijada $P(x)$.

En comparació a un algoritme com el mostreig de rebuig adaptatiu que genera directament mostres independents d'una distribució, Metropolis-Hastings i atres algoritmes Montecarlo en cadena de Markov tenen una série de desventages:

• Les mostres estan correlacionadas. Encara que a llarc determini seguixen correctament $P(x)$, un conjunt de mostres propenques es correlacionaron entre sí i no reflectiran correctament la distribució. Açò significa que si volem un conjunt de mostres independents, tenim que tirar la majoria de les mostres i solament se seleccionen cada cert número de mostra, per a algun valor de n (típicament determinat en examinar l'autocorrelación entre mostres adjacents). La autocorrelación pot reduir-se aumentant l'ample del bot (el tamany promig d'un bot, que està relacionat en la variació de la distribució del bot), pero açò també aumentarà la provabilitat de rebuig del bot propost. Un tamany de bot massa gran o massa chicotet conduirà a una cadena de Markov de mescla llenta, és dir, un conjunt altament correlacionado de mostres, per lo que es necessitarà una cantitat molt gran de mostres per a obtindre una estimació raonable de qualsevol propietat desijada de la distribució.
• Encara que la cadena de Markov finalment convergix a la distribució desijada, les mostres inicials poden seguir una distribució molt diferent, especialment si el punt de partida està en una regió de baixa densitat. Com a resultat, generalment és necessari un periodo de cremat, en el que es rebuja un número inicial de mostres (per eixemple, els primers 1000).

Per un atre costat, els métodos de mostreig de rebuig més simples sofrixen la "maldicció de la dimensionalidad", a on la provabilitat de rebuig aumenta exponencialment en funció del número de dimensions. Metropolis-Hastings, junt en atres métodos de Montecarlo en cadena de Markov, no tenen este problema en tal grau i, per lo tant, a sovint són les úniques solucions disponibles quan el número de dimensions de la distribució a muestrear és alt. Com a resultat, els métodos d'este tipo són a sovint els métodos d'elecció per a produir mostres a partir de models bayesianos jeràrquics i uns atres models estadístics d'alta dimensió utilisats hui en dia en moltes disciplines.

En distribucions multivariadas, l'algoritme clàssic de Metropolis-Hastings com es va descriure anteriorment implica elegir un nou punt de mostra multidimensional. Quan el número de dimensions és alt, trobar la distribució de bot adequada per a usar pot ser difícil, ya que les diferents dimensions individuals es comporten de maneres molt diferents, i l'ample de bot (vore dalt) deu ser "just" per a totes les dimensions al mateix temps. evite mesclar excessivament llent. Un enfocament alternatiu que a sovint funciona millor en tals situacions, conegut com a mostreig de Gibbs, implica elegir una nova mostra per a cada dimensió per separat de les demés, en lloc d'elegir una mostra per a totes les dimensions al mateix temps. Açò és especialment aplicable quan la distribució multivariada es compon d'un conjunt de variables aleatòries individuals en les que cada variable està condicionada a un chicotet número d'atres variables, com és el cas en la majoria dels models jeràrquics típics. Les variables individuals es mostren d'una en una, en cada variable condicionada als valors més recents de totes les demés. Es poden usar varis algoritmes per a elegir estes mostres individuals, depenent de la forma exacta de la distribució multivariada: algunes possibilitats són els métodos de mostreig de rebuig adaptatiu, l'algoritme de mostreig Metròpolis de rebuig adaptatiu o les seues millores, Un simple pas unidimensional de Metròpolis-Hastings, o mostreig de cort.

Archiu:3dRosenbrock.png

El resultat de tres cadenes de Markov que s'eixecuten en la funció 3D Rosenbrock utilisant l'algoritme Metropolis-Hastings. L'algoritme pren mostres de regions a on la provabilitat posterior és alta, i les cadenes comencen a mesclar-se en estes regions. La posició aproximada del màxim ha segut allumenada. Tinga en conte que els punts rojos són els que queden despuix del procés de cremat. Els primers han segut descartats.

Vore també

• Balanç detallat
• Algoritme Genètic
• Mostreig de Gibbs
• Métodos de partícules de camp mig
• Algoritme Langevin ajustat per Metropolis
• Transport de la llum de Metropolis
• Metròpolis d'intents múltiples
• Temple en paralel
• Algoritme de Crank-Nicolson precondicionado
• Filtre de partícules
• Algoritme de recocido simulat