Metropolis-Hastingsov algoritem je v statistiki in statistični fiziki metoda MCMC za pridobivanje sekvence naključnih vzorcev z verjetnostne porazdelitve, iz katere je neposredno vzorčenje težavno. To sekvenco lahko uporabljamo za aproksimiranje porazdelitve (npr. za generiranje histograma) ali izračunanje integrala (npr. pričakovana vrednost). Metropolis-Hastings in drugi MCMC algoritmi se na splošno uporabljajo za vzorčenje z večdimenzionalne porazdelitve, zlasti, ko je število dimenzij visoko. Za enodimenzionalne porazdelitve so običajno druge metode (npr. adaptivno vzorčenje zavračanja), ki neposredno dajo neodvisne vzorce s porazdelitve in ti nimajo težav s avtokoreliranimi vzorci, ki so inherentni pri MCMC metodah.
Zgodovina
Algoritem se imenuje po grško-ameriškem matematiku, fiziku in računalnikarju Nicholasu Metropolisu in kanadskem statistiku Wilfredu Keithu Hastingsu. Dolgo časa je bil znan samo kot Metropolisov algoritem, po Metropolisu, soavtorju članka Equation of State Calculations by Fast Computing Machines iz leta 1953 skupaj z Arianno W. Rosenbluth, Marshallom Rosenbluthom, Augusto H. Teller in Edwardom Tellerjem. Članek je predlagal algoritem za primer simetrične predlagane razporeditve, leta 1970 pa ga je Hastings razširil na splošnejši primer. Posplošena metoda je dobila ime po obeh avtorjih, čeprav prvotna raba imena »Metropolis-Hastings« ni jasna.
Glede zaslug za razvoj Metropolisovega algoritma obstaja nekaj kontroverznosti. Metropolis, ki je poznal računski vidik metode, je oblikoval izraz »Monte Carlo« v predhodnem članku s Stanisławom Marcinom Ulmom in je vodil skupino v teoretičnem oddelku, ki je oblikoval in zgradil računalnik MANIAC I, ki je bil uporabljen v poskusih leta 1952. Do leta 2003 niso bile znane nobene podrobnosti o razvoju algoritma. Malo pred svojo smrtjo leta 2003 se je Marshal Rosenbluth udeležil konference v LANL za obeležitev 50-letnice objave leta 1953. Na tej konferenci je Rosenbluth opisal algoritem in njegov razvoj v predstavitvi za naslovom »Stvaritev algoritma Monte Carlo za statistično mehaniko«. Nadaljnje zgodovinsko pojasnilo je ponudil Gubernatis v svojem članku iz leta 2005, s katerim je ponovno obeležil 50-letnico konference. Rosenbluth je sporočil, da sta delo opravila on in njegova žena Arianna, medtem ko Metropolis ni igral nobene vloge v razvoju, razen zagotavljanja računalniškega časa.
To nasprotuje Tellerjevim trditvam, ki v svojih spominih trdi, da so avtorji članka iz leta 1953 delali skupaj »noč in dan«.Teller, Edward. Memoirs: A Twentieth-Century Journey in Science and Politics. Perseus Publishing, 2001, p. 328 Po drugi strani, podrobni zapisi Rosenblutha vse zasluge pripisujejo Tellerju z bistvenim in zgodnjim predlogom »poslužiti se statistične mehanike in izračunati skupna povprečja namesto podrobne kinematike«. Rosenbluth trdi, da je zaradi tega začel razmišljati o posplošenem pristopu Monte Carlo tema, o kateri je pogosto govoril z Johnom Von Neumannom. Arianna Rosenbluth se spominja (Gubernatisa leta 2003) da je Augusta Teller začela z računalniškim delom, vendar je Arianna sama začela z začetka in napisala vso kodo sama. V ustni pripovedi, posneti malo pred njegovo smrtjo,Rosenbluth, Marshall. "Oral History Transcript". American Institute of Physics Rosenbluth ponovno pripisuje vse zasluge Tellerju, za postavitev prvotne težave, on sam jo je rešil in Arianna je programirala računalnik.
Sklici
Nadaljnje branje
Bernd A. Berg. Markov Chain Monte Carlo Simulations and Their Statistical Analysis. Singapore, World Scientific, 2004. Siddhartha Chib and Edward Greenberg: "Understanding the Metropolis–Hastings Algorithm". American Statistician, 49(4), 327–335, 1995 David D. L. Minh and Do Le Minh. "Understanding the Hastings Algorithm." Communications in Statistics - Simulation and Computation, 44:2 332-349, 2015 Bolstad, William M. (2010) Understanding Computational Bayesian Statistics, John Wiley & Sons
Kategorija:Ekonometrija Kategorija:Statistika Kategorija:Algoritmi Kategorija:Strojno učenje