Metropolis-Hastingsov algoritem

Iz Wikipedije, proste enciklopedije
Predlagana porazdelitev Q predlaga naslednjo točko, v katero naj se slučajni sprehod premakne.

V statistiki in statistični fiziki je Metropolis-Hastingsov algoritem MCMC metoda 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[uredi | uredi kodo]

Algoritem je poimenovan po Nicholasu Metropolisu in Wilfredu Hastingsu. Dolgo časa je bil algoritem 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.[1][2] Članek je predlagal algoritem za primer simetrične predlagane razporeditve, leta 1970 pa ga je W. Hastings razširil na splošnejši primer.[3] Posplošena metoda je dobila ime po obeh avtorjih, čeprav prvotna raba imena »Metropolis-Hastings« ni jasna.

Glede zaslug za razvoj algoritma Metropolis obstaja nekaj kontroverznosti. Metropolis, ki je poznal računski vidik metode, je oblikoval iz raz »Monte Carlo« v predhodnem članku z Stanisławom 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 Monte Carlo algoritma za statistično mehaniko«.[4] Nadaljnje zgodovinsko pojasnilo je ponudil Gubernatis v svojem članku iz leta 2005,[5] 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 trditvam Edwarda Tellerja, ki v svojih spominih trdi, da so avtorji članka iz leta 1953 delali skupaj »noč in dan«.[6] 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 generaliziranem Monte Carlo pristopu – 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,[7] Rosenbluth ponovno pripisuje vse zasluge Tellerju, za postavitev prvotne težave, on sam jo je rešil in Arianna je programirala računalnik.

Sklici[uredi | uredi kodo]

  1. ↑ Kalos, Malvin H.; Whitlock, Paula A. (1986). Monte Carlo Methods Volume I: Basics. New York: Wiley. str. 78–88.
  2. ↑ Tierney, Luke (1994). »Markov chains for exploring posterior distributions«. The Annals of Statistics. 22 (4): 1701–1762.
  3. ↑ Hastings, W.K. (1970). »Monte Carlo Sampling Methods Using Markov Chains and Their Applications«. Biometrika. 57 (1): 97–109. Bibcode:1970Bimka..57...97H. doi:10.1093/biomet/57.1.97. JSTOR 2334940. Zbl 0219.65008.
  4. ↑ M.N. Rosenbluth (2003). »Genesis of the Monte Carlo Algorithm for Statistical Mechanics«. AIP Conference Proceedings. 690: 22–30. Bibcode:2003AIPC..690...22R. doi:10.1063/1.1632112.
  5. ↑ J.E. Gubernatis (2005). »Marshall Rosenbluth and the Metropolis Algorithm«. Physics of Plasmas. 12 (5): 057303. Bibcode:2005PhPl...12e7303G. doi:10.1063/1.1887186.
  6. ↑ Teller, Edward. Memoirs: A Twentieth-Century Journey in Science and Politics. Perseus Publishing, 2001, p. 328
  7. ↑ Rosenbluth, Marshall. "Oral History Transcript". American Institute of Physics

Nadaljnje branje[uredi | uredi kodo]

Pridobljeno iz »https://sl.wikipedia.org/w/index.php?title=Metropolis-Hastingsov_algoritem&oldid=6142197«