Přeskočit na obsah

Markov chain Monte Carlo: Porovnání verzí

Z Wikipedie, otevřené encyklopedie
Interaktivně procházet historii
← Přejít na předchozí porovnáníPřejít na další porovnání →
Smazaný obsah Přidaný obsah
VizuálníWikitext
+pracuje se
-- nepracuje se, už
Řádek 1: Řádek 1:
'''Markov chain Monte Carlo''' ('''MCMC''', česky asi ''Monte Carlo pomocí Markovova řetězce'') je ve [[statistika|statistice]] třída [[algoritmus|algoritmů]] pro vzorkování z [[Rozdělení pravděpodobnosti|pravděpodobnostního rozdělení]] založená na konstrukci [[Markovův řetězec|Markovova řetězce]], který má požadované rozdělení jako svou [[rovnovážná distribuce|rovnovážnou distribuci]]. Stav řetězce po několika krocích se pak použije jako vzorek z požadované distribuce. Kvalita vzorku se zvyšuje se zvýšením počtu kroků.
{{pracuje se}}
[[soubor:Metropolis algorithm convergence example.png|thumbnail|Konvergence algoritmu [[Metropolisův-Hastingsův algoritmus|Metropolis-Hastings]]. MCMC se pokusí přiblížit k modré distribuci prostřednictvím oranžové distribuce]]
'''Markov chain Monte Carlo''' ('''MCMC''', česky asi ''Monte Carlo pomocí Markovova řetězce'') je ve [[statistice|statistika]] třída [[algoritmů|algoritmus]] pro vzorkování z [[pravděpodobnostního rozdělení|Rozdělení pravděpodobnosti]] založená na konstrukci [[Markovova řetězce|Markovův řetězec]], který má požadované rozdělení jako svou [[rovnovážnou distribuci|rovnovážná distribuce]]. Stav řetězce po několika krocích se pak použije jako vzorek z požadované distribuce. Kvalita vzorku se zvyšuje se zvýšením počtu kroků.


Metody '''Monte Carlo pomocí náhodné procházky''' tvoří velkou podtřídu MCMC metod.


== Aplikační domény ==
Konvergence algoritmu Metropolis-Hastings. MCMC se pokusí přiblížit k modré distribuci prostřednictvím oranžové distribuce
Metody Monte Carlo pomocí náhodné procházky tvoří velkou podtřídu MCMC metod.


* MCMC metody jsou primárně využívány pro výpočet [[numerická matematika|numerických aproximací]] [[vícerozměrný integrál|vícerozměrných integrálů]], například v [[Bayesovská statistika|Bayesovské statistice]], [[výpočetní fyzika|výpočetní fyzice]], [[počítačová biologie|počítačové biologii]] a [[matematická lingvistika|počítačové lingvistice]].<ref>See Gill 2008.</ref><ref>See Robert & Casella 2004.</ref>
* V Bayesovské statistice byl nedávný vývoj MCMC metod klíčovým krokem pro možnost počítat velké [[hierarchický model|hierarchické modely]], které vyžadují integrace přes více než stovky nebo dokonce tisíce neznámých parametrů.<ref>{{cite book|last1=Banerjee|first1=Sudipto|last2=Carlin|first2=Bradley P.|last3=Gelfand|first3=Alan P.|title=Hierarchical Modeling and Analysis for Spatial Data|publisher=CRC Press|isbn=978-1-4398-1917-3|page=xix|edition=Second Edition}}</ref>
* Také se používají pro generování vzorků, které postupně zabydlují/pokrývají řídké oblasti selhání ve [[vzorkování řídkých událostí]].


== Klasifikace ==
Aplikační domény


=== Metoda Monte Carlo s náhodnou procházkou ===
MCMC metody jsou primárně využívány pro výpočet numerických aproximací [[vícerozměrných integrálů]], například v [[Bayesovské statistice]], [[výpočetní fyzice]], [[počítačové biologii]] a počítačové linguistice.[1][2]
{{Podrobně| náhodná procházka}}
V [[Bayesovské statistice]] byl nedávný vývoj MCMC metod klíčovým krokem pro možnost počítat velké [[hierarchické modely]], které vyžadují integrace přes více než stovky nebo dokonce tisíce neznámých parametrů.[3]
Také se používají pro gene+rování vzorků, které postupně zabydlují/pokrývají řídké oblasti selhání ve [[vzorkování řídkých událostí]].
Klasifikace


==== Vícerozměrné integrály ====
Metoda Monte Carlo s náhodnou procházkou {{Viz také: náhodná procházka}}
Pokud se použije metoda MCMC pro aproximaci [[vícerozměrný integrál|vícerozměrného integrálu]], soubor "chodců" se pohybuje náhodně. Pro každý bod, kde chodec zastaví, se hodnota integrandu v tomto bodě započítává do integrálu. Chodec pak může provést řadu průběžných kroků po okolí, hledajíc místo s přiměřeně velkým přínosem pro integrál, do kterého se přesune v dalším kroku.
Vícerozměrné integrály
Pokud se použije metoda MCMC pro aproximaci [[vícerozměrného integrálu]], soubor "chodců" se pohybuje náhodně. Pro každý bod, kde chodec zastaví, se hodnota integrandu v tomto bodě započítává do integrálu. Chodec pak může provést řadu průběžných kroků po okolí, hledajíc místo s přiměřeně velkým přínosem pro integrál, do kterého se přesune v dalším kroku.


Metody Monte Carlo s náhodnou procházkou patří mezi náhodné simulace nebo-li Monte Carlo methody. Nicméně, náhodné vzorky integrandu používané při běžné Monte Carlo integration jsou jsou statisticky nezávislé, kdežto ty používané v metodách MCMC jsou korelovány. Markovův řetěyec je konstruován takovým způsobem, aby mělo daný integrand jako svou [[rovnovážnou distribuci]].
Metody Monte Carlo s náhodnou procházkou patří mezi náhodné [[počítačová simulace|simulace]] nebo-li [[Metoda Monte Carlo|Monte Carlo metody]]. Nicméně, náhodné vzorky integrandu používané při běžné [[Monte Carlo integrování|Monte Carlo integraci]] jsou jsou [[statisticky nezávislé]], kdežto ty používané v metodách MCMC jsou [[korelace|korelovány]]. [[Markovův řetězec]] je konstruován takovým způsobem, aby měl daný integrand jako svou [[Markovův řetězec#Steady-state analysis and limiting distributions-rovnovážná distribuce|rovnovážnou distribuci]].


==== Příklady ====

Příklady
Příklady metod Monte Carlo s náhodnou procházkou zahrnují následující:
Příklady metod Monte Carlo s náhodnou procházkou zahrnují následující:


Metropolisův–Hastingsův algoritmus: Tato metoda generuje náhodnou procházku s využitím navrhované hustoty rozdělení a používá metodu pro odmítnutí některých z navrhovaných vzorků.
* [[Metropolisův-Hastingsův algoritmus]]: Tato metoda generuje [[ náhodná procházka| náhodnou procházku]] s využitím navrhované hustoty rozdělení a používá metodu pro odmítnutí některých z navrhovaných vzorků.
[[Gibbsovo vzorkování]]: Tato metoda vyžaduje, aby všechny [[podmíněné distribuce]] cílové distribuce byly vzorkovány přesně. Je populární, částečně proto, že nevyžaduje žádné "ladění".
* [[Gibbsovo vzorkování]]: Tato metoda vyžaduje, aby všechny [[podmíněná distribuce|podmíněné distribuce]] cílové distribuce byly vzorkovány přesně. Je populární, částečně proto, že nevyžaduje žádné "ladění".
[[Slice vzorkování]]: Tato metoda závisí na principu, že lze vzorkovat z distribuce pomocí vzorkování rovnoměrně z oblasti pod grafem dané funkce hustoty. Metoda střídá rovnoměrném vzorkování ve svislém směru s rovnoměrným vzorkováním z vodorovného "plátku" definovaném aktuální vertikální polohou.
* [[Slice vzorkování]]: Tato metoda spočívá na principu, že lze vzorkovat z distribuce pomocí vzorkování rovnoměrně z oblasti pod grafem dané funkce hustoty. Metoda střídá rovnoměrné vzorkování ve svislém směru s rovnoměrným vzorkováním z vodorovného "plátku" (angl. slice) definovaném aktuální vertikální polohou.
[[Multiple-try Metropolis]]: Tato metoda je variantou Metropolisova-Hastingsova algoritmu, která umožňuje opakované pokusy v každém bodě. Tím, že je možné vykonat větší kroky při každé iteraci, pomáhá řešit [[prokletí dimenzionality]].
* [[Multiple-try Metropolis]]: Tato metoda je variantou Metropolisova-Hastingsova algoritmu, která umožňuje opakované pokusy v každém bodě. Tím, že je možné vykonat větší kroky při každé iteraci, pomáhá řešit [[prokletí dimenzionality]].
[[Reversibilní skok]]: Tato metoda je variantou Metropolisova-Hastingsova algoritmu, která umožňuje návrhy, které mění dimenzionalitu prostoru.[4] MCMC metody, které mění dimenzionalitu, se již dlouho používají v aplikacích statistické fyziky, kde se pro některé problémy používá distribuce, která je [[velký kanonický soubor]]] (například, když počet molekul v krabici je proměnný). Ale varianta reverzibilního skoku je užitečné, když se dělá MCMC nebo Gibbs vzorkování nad [[neparametrický]]m bayesovským modelem, napříkklad těch, které zahrnují [[proces Dirichletův]] nebo [[ proces čínské restaurace ]] , kde počet směsných komponenty / clusterů / atd. je automaticky odvodit z dat.
* [[Reversibilní skok]]: Tato metoda je variantou Metropolisova-Hastingsova algoritmu, která umožňuje návrhy, které mění dimenzionalitu prostoru.<ref>See Green 1995.</ref> MCMC metody, které mění dimenzionalitu, se již dlouho používají v aplikacích [[statistická fyzika|statistické fyziky]], kde se pro některé problémy používá distribuce, která je [[velký kanonický soubor]] (například, když počet molekul v krabici je proměnný). Ale varianta reverzibilního skoku je užitečná, když se dělá MCMC nebo Gibbs vzorkování nad [[neparametrický]]m bayesovským modelem, například takovým, který zahrnuje [[Dirichletův proces ]] nebo [[ proces čínské restaurace]], kde počet směsných komponent/klasterů/atd. je automaticky odvozen z dat.
Jiné metody MCMC
Markov Chain quasi-Monte Carlo (MCQMC)[5][6]
+ Přidat překlad
+ Přidat překlad
+ Přidat překlad
+ Přidat překlad
+ Přidat překlad
Konvergence


=== Jiné metody MCMC ===
[[Markov Chain quasi-Monte Carlo]] (MCQMC)<ref>Chen, S., Josef Dick, and Art B. Owen. "Consistency of Markov chain quasi-Monte Carlo on continuous state spaces." The Annals of Statistics 39.2 (2011): 673-701.</ref><ref>Tribble, Seth D. Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences. Diss. Stanford University, 2007.</ref>
<!-- + Přidat překlad 5x -->

== Konvergence ==
Obvykle to není těžké sestavit Markovův řetěz s požadovanými vlastnostmi. Obtížnější problém je určit, kolik kroků je zapotřebí ke konvergenci k stacionárnímu rozdělení s přijatelnou chybou. Dobrý řetěz bude mít [[rychlé mísení]]: stacionární distribuce je dosaženo rychle z libovolné počáteční pozice.
Obvykle to není těžké sestavit Markovův řetěz s požadovanými vlastnostmi. Obtížnější problém je určit, kolik kroků je zapotřebí ke konvergenci k stacionárnímu rozdělení s přijatelnou chybou. Dobrý řetěz bude mít [[rychlé mísení]]: stacionární distribuce je dosaženo rychle z libovolné počáteční pozice.


Typicky, MCMC vzorkování pouze aproximuje cílovou distribuci, protože je tam vždy nějaký zbytkový efekt počáteční pozice. Sofistikovanější algoritmy založené na MCMC, jako napříkald [[ coupling from the past ]] můžou produkovat přesné vzorky, za cenu dodatečného výpočtu a neomezeného (i když konečného v očekávání) času běhu.

Mnoho maetod Monte Carlo s náhodnou procházkou se pohybuje po rovnovážné distribuci v relativně malých krocích, bez tendence, aby kroky pokračovaly ve stejném směru. Tyto metody jdou snadno implementovat a analyzovat, ale bohužel může trvat dlouhou dobu, než procházka prozkoumá celý prostor. Chodec se často vrací zpět a pokrývá již prozkoumaný prostor.

== Viz také ==
* [[Bayesovská statistika]]
* [[Bayesovská síť]]
* [[Coupling from the past]]
* [[Gibbsovo vzorkování]]
* [[Quasi-Monte Carlo method]]
* [[Hybrid Monte Carlo]]
* [[Metropolisův-Hastingsův algoritmus]]
* [[Multiple-try Metropolis]]
* [[Částicový filtr]]
* [[Reversible-jump]]
* [[Slice sampling]]


== Poznámky ==
Typicky, MCMC vzorkování pouze aproximuje cílovou distribuci, protože je tam vždy nějaký zbytkový efekt počáteční pozice. Sofistikovanější algoritmy založené na MCMC, jako napříkald [[ coupling from the past ]] můžou produkovat přesné vzorky, za cenu dodatečného výpočtu a neomezeného (i když konečného v očekávání) casu běhu.
{{reflist}}


Mnoho maetod Monte Carlo s náhodnou procházkou se pohybuje po rovnovážné distribuci v relativně malých krocích, bez tendence, aby kroky pokračovaly ve stejném směru. Tyto metody jdou snadno implementovat a analyzovat, ale bohužel může trvat dlouhou dobu, než procházka prozkoumá celý prostor. Chodec se často vrací zpět a pokrývá prostor již prozkoumán.


== Reference ==
Viz také
* Christophe Andrieu, Nando De Freitas and Arnaud Doucet, [http://www.cs.princeton.edu/courses/archive/spr06/cos598C/papers/AndrieuFreitasDoucetJordan2003.pdf ''An Introduction to MCMC for Machine Learning''], 2003
*{{cite book
| last1 = Asmussen
| first1 = Søren
| last2 = Glynn
| first2 = Peter W.
| title = Stochastic Simulation: Algorithms and Analysis
| publisher = Springer
| series = Stochastic Modelling and Applied Probability
| volume = 57
| year = 2007
}}
*{{cite web
| first = P.
| last = Atzberger
| url = http://www.math.ucsb.edu/~atzberg/spring2006/monteCarloMethod.pdf
| title = An Introduction to Monte-Carlo Methods
}}
*{{cite book
| first = Bernd A.
| last = Berg
| author1link = Bernd A. Berg
| title = Markov Chain Monte Carlo Simulations and Their Statistical Analysis
| publisher = [[World Scientific]]
| year = 2004
}}
*{{cite book
| last = Bolstad
| first = William M.
| year = 2010
| title = Understanding Computational Bayesian Statistics
| publisher = Wiley
| isbn = 0-470-04609-0
}}
*{{cite journal
| first1 = George
| last1 = Casella
| first2 = Edward I.
| last2 = George
| title = Explaining the Gibbs sampler
| journal = ''[[The American Statistician]]''
| volume = 46
| pages = 167–174
| year = 1992
| doi=10.2307/2685208
}} ''(Basic summary and many references.)''
*{{cite journal
| first1 = A.E.
| last1 = Gelfand
| first2 = A.F.M.
| last2 = Smith
| title = Sampling-Based Approaches to Calculating Marginal Densities
| journal = [[Journal of the American Statistical Association]]
| volume = 85
| pages = 398–409
| year = 1990
| doi=10.1080/01621459.1990.10476213
}}
*{{cite book
| first1 = Andrew
| last1 = Gelman
| author1link = Andrew Gelman
| first2 = John B.
| last2 = Carlin
| first3 = Hal S.
| last3 = Stern
| first4 = Donald B.
| last4 = Rubin
| author4link = Donald B. Rubin
| title = Bayesian Data Analysis
| publisher = [[Chapman and Hall]]
| edition = 1st
| year = 1995
}} ''(See Chapter 11.)''
*{{cite journal
| first1 = S.
| last1 = Geman
| first2 = D.
| last2 = Geman
| author2link = Donald Geman
| title = Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images
| journal = [[IEEE Transactions on Pattern Analysis and Machine Intelligence]]
| volume = 6
| pages = 721–741
| year = 1984
}}
*{{cite book
| last1 = Gilks
| first1 = W.R.
| last2 = Richardson
| first2 = S.
| first3 = D.J.
| last3 = Spiegelhalter
| author3link = David Spiegelhalter
| title = Markov Chain Monte Carlo in Practice
| publisher = [[Chapman and Hall]]/CRC
| year = 1996
}}
*{{cite book
| first = Jeff
| last = Gill
| title = Bayesian methods: a social and behavioral sciences approach
| edition = 2nd
| year = 2008
| publisher = [[Chapman and Hall]]/CRC
| isbn = 1-58488-562-9
}}
*{{cite journal
| first = P.J.
| last = Green
| title = Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination
| journal = [[Biometrika]]
| volume=82
| issue = 4
| pages = 711–732
| year = 1995
| doi = 10.1093/biomet/82.4.711
}}
*{{cite journal
| first = Radford M.
| last = Neal
| title = Slice Sampling
| journal = [[Annals of Statistics]]
| volume = 31
| issue = 3
| pages = 705–767
| year = 2003
| jstor = 3448413
| doi=10.1214/aos/1056562461
}}
*{{cite web
| last = Neal
| first = Radford M.
| url = http://www.cs.utoronto.ca/~radford/review.abstract.html
| title = ''Probabilistic Inference Using Markov Chain Monte Carlo Methods''
| year = 1993
}}
*{{cite book
|first = Christian P.
|last = Robert
|last2 = Casella
|first2 = G.
|title = Monte Carlo Statistical Methods
|edition = 2nd
|year = 2004
|publisher = Springer
|isbn = 0-387-21239-6
}}
*{{cite book
| first1 = R.Y.
| last1 = Rubinstein
| first2 = D.P.
| last2 = Kroese
| title = Simulation and the Monte Carlo Method
| edition = 2nd
| publisher = [[John Wiley & Sons|Wiley]]
| year = 2007
| isbn = 978-0-470-17794-5
}}
*{{cite journal
| first = R.L.
| last = Smith
| title = Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions
| journal = [[Operations Research: A Journal of the Institute for Operations Research and the Management Sciences|Operations Research]]
| volume = 32
| pages = 1296–1308
| year = 1984
| doi=10.1287/opre.32.6.1296
}}
*{{cite journal
| first = J.C.
| last = Spall
| title = Estimation via Markov Chain Monte Carlo
| journal = [[IEEE Control Systems Magazine]]
| volume = 23
| issue = 2
| pages = 34–45
|date=April 2003
| doi=10.1109/mcs.2003.1188770
}}
*{{cite journal
| last1 = Stramer
| first1 = O.
| last2 = Tweedie
| first2 = R.
| year = 1999
| title = Langevin-Type Models II: Self-Targeting Candidates for MCMC Algorithms
| journal = Methodology and Computing in Applied Probability
| volume = 1
| issue = 3
| pages = 307–328
| doi=10.1023/A:1010090512027
}}


Bayesovská statistika
Bayesovská siť
[[Coupling from the past]]
[[Gibbsovo vzorkování]]
[[Quasi-Monte Carlo method]]
[[Hybrid Monte Carlo]]
Metropolisův–Hastingsův algoritmus
[[Multiple-try Metropolis]]
[[Částicový filtr]]
[[Reversible-jump]]
[[Slice sampling]]
Notes


== Externí odkazy ==
↑ See Gill 2008.
↑ See Robert & Casella 2004.
↑ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. Hierarchical Modeling and Analysis for Spatial Data (Second Edition ed.). CRC Press. p. xix. ISBN 978-1-4398-1917-3.
↑ See Green 1995.
↑ Chen, S., Josef Dick, and Art B. Owen. "Consistency of Markov chain quasi-Monte Carlo on continuous state spaces." The Annals of Statistics 39.2 (2011): 673-701.
↑ Tribble, Seth D. Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences. Diss. Stanford University, 2007.
↑ Papageorgiou, Anargyros, and J. F. Traub. "Beating Monte Carlo." Risk 9.6 (1996): 63-65.
↑ Sobol, Ilya M. "On quasi-monte carlo integrations." Mathematics and Computers in Simulation 47.2 (1998): 103-112.
↑ See Neal 2003.
↑ See Stramer 1999.
Reference


* [http://web.archive.org/web/20110531150413/http://www.bioss.ac.uk/students/alexm/MCMCintroPresentation.pdf MCMC sampling and other methods in a basic overview], by Alexander Mantzaris (original link - now broken), ''Vzorkování MCMC a jiné metody v základním přehledu''
Externí odkazy
* [http://www.lbreyer.com/classic.html Visual demonstration of MCMC sampling methods (Java applet)], by Laird Breyer, ''Vizuální znázornění metod MCMC odběru vzorků''
* [http://www.ece.sunysb.edu/~zyweng/MCMCexample.html A Toy Example of MCMC sampling], by Zhiyuan Weng, ''Jednoduchý příklad MCMC vzorkování''
* [http://micans.org/mcl/ MCL - a cluster algorithm for graphs], by Stijn van Dongen, ''MCL - klastrovací algoritmus pro grafy''
* [http://pymc-devs.github.io/pymc/ PyMC] - Pythonovský modul implementující Bayesovské statistické modely a fitovací algoritmů, včetně Markov chain Monte Carlo.


{{překlad|en|Markov chain Monte Carlo|664160555}}
MCMC sampling and other methods in a basic overview, by Alexander Mantzaris (original link - now broken), Vzorkování MCMC a jiné metody v základním přehledu
[[Kategorie:Bayesovská statistika]]
Visual demonstration of MCMC sampling methods (Java applet), by Laird Breyer, Vizuální znázornění metod MCMC odběru vzorků
A Toy Example of MCMC sampling, by Zhiyuan Weng, Jednoduchý příklad MCMC vzorkování
MCL - a cluster algorithm for graphs, by Stijn van Dongen, MCL - klastrovací algoritmus pro grafy
PyMC - Pythonovský modul implementující Bayesovské statistické modely a fitovací algoritmů, včetně Markov chain Monte Carlo.
Bayesovská statistika

Verze z 31. 5. 2015, 18:07

Markov chain Monte Carlo (MCMC, česky asi Monte Carlo pomocí Markovova řetězce) je ve statistice třída algoritmů pro vzorkování z pravděpodobnostního rozdělení založená na konstrukci Markovova řetězce, který má požadované rozdělení jako svou rovnovážnou distribuci. Stav řetězce po několika krocích se pak použije jako vzorek z požadované distribuce. Kvalita vzorku se zvyšuje se zvýšením počtu kroků.

Konvergence algoritmu Metropolis-Hastings. MCMC se pokusí přiblížit k modré distribuci prostřednictvím oranžové distribuce

Metody Monte Carlo pomocí náhodné procházky tvoří velkou podtřídu MCMC metod.

Aplikační domény

Klasifikace

Metoda Monte Carlo s náhodnou procházkou

Podrobnější informace naleznete v článku náhodná procházka.

Vícerozměrné integrály

Pokud se použije metoda MCMC pro aproximaci vícerozměrného integrálu, soubor "chodců" se pohybuje náhodně. Pro každý bod, kde chodec zastaví, se hodnota integrandu v tomto bodě započítává do integrálu. Chodec pak může provést řadu průběžných kroků po okolí, hledajíc místo s přiměřeně velkým přínosem pro integrál, do kterého se přesune v dalším kroku.

Metody Monte Carlo s náhodnou procházkou patří mezi náhodné simulace nebo-li Monte Carlo metody. Nicméně, náhodné vzorky integrandu používané při běžné Monte Carlo integraci jsou jsou statisticky nezávislé, kdežto ty používané v metodách MCMC jsou korelovány. Markovův řetězec je konstruován takovým způsobem, aby měl daný integrand jako svou rovnovážnou distribuci.

Příklady

Příklady metod Monte Carlo s náhodnou procházkou zahrnují následující:

  • Metropolisův-Hastingsův algoritmus: Tato metoda generuje náhodnou procházku s využitím navrhované hustoty rozdělení a používá metodu pro odmítnutí některých z navrhovaných vzorků.
  • Gibbsovo vzorkování: Tato metoda vyžaduje, aby všechny podmíněné distribuce cílové distribuce byly vzorkovány přesně. Je populární, částečně proto, že nevyžaduje žádné "ladění".
  • Slice vzorkování: Tato metoda spočívá na principu, že lze vzorkovat z distribuce pomocí vzorkování rovnoměrně z oblasti pod grafem dané funkce hustoty. Metoda střídá rovnoměrné vzorkování ve svislém směru s rovnoměrným vzorkováním z vodorovného "plátku" (angl. slice) definovaném aktuální vertikální polohou.
  • Multiple-try Metropolis: Tato metoda je variantou Metropolisova-Hastingsova algoritmu, která umožňuje opakované pokusy v každém bodě. Tím, že je možné vykonat větší kroky při každé iteraci, pomáhá řešit prokletí dimenzionality.
  • Reversibilní skok: Tato metoda je variantou Metropolisova-Hastingsova algoritmu, která umožňuje návrhy, které mění dimenzionalitu prostoru.[4] MCMC metody, které mění dimenzionalitu, se již dlouho používají v aplikacích statistické fyziky, kde se pro některé problémy používá distribuce, která je velký kanonický soubor (například, když počet molekul v krabici je proměnný). Ale varianta reverzibilního skoku je užitečná, když se dělá MCMC nebo Gibbs vzorkování nad neparametrickým bayesovským modelem, například takovým, který zahrnuje Dirichletův proces nebo proces čínské restaurace, kde počet směsných komponent/klasterů/atd. je automaticky odvozen z dat.

Jiné metody MCMC

Markov Chain quasi-Monte Carlo (MCQMC)[5][6]

Konvergence

Obvykle to není těžké sestavit Markovův řetěz s požadovanými vlastnostmi. Obtížnější problém je určit, kolik kroků je zapotřebí ke konvergenci k stacionárnímu rozdělení s přijatelnou chybou. Dobrý řetěz bude mít rychlé mísení: stacionární distribuce je dosaženo rychle z libovolné počáteční pozice.

Typicky, MCMC vzorkování pouze aproximuje cílovou distribuci, protože je tam vždy nějaký zbytkový efekt počáteční pozice. Sofistikovanější algoritmy založené na MCMC, jako napříkald coupling from the past můžou produkovat přesné vzorky, za cenu dodatečného výpočtu a neomezeného (i když konečného v očekávání) času běhu.

Mnoho maetod Monte Carlo s náhodnou procházkou se pohybuje po rovnovážné distribuci v relativně malých krocích, bez tendence, aby kroky pokračovaly ve stejném směru. Tyto metody jdou snadno implementovat a analyzovat, ale bohužel může trvat dlouhou dobu, než procházka prozkoumá celý prostor. Chodec se často vrací zpět a pokrývá již prozkoumaný prostor.

Viz také

Poznámky

  1. ↑ See Gill 2008.
  2. ↑ See Robert & Casella 2004.
  3. ↑ BANERJEE, Sudipto; CARLIN, Bradley P.; GELFAND, Alan P. Hierarchical Modeling and Analysis for Spatial Data. Second Edition. vyd. [s.l.]: CRC Press ISBN 978-1-4398-1917-3. S. xix. 
  4. ↑ See Green 1995.
  5. ↑ Chen, S., Josef Dick, and Art B. Owen. "Consistency of Markov chain quasi-Monte Carlo on continuous state spaces." The Annals of Statistics 39.2 (2011): 673-701.
  6. ↑ Tribble, Seth D. Markov chain Monte Carlo algorithms using completely uniformly distributed driving sequences. Diss. Stanford University, 2007.


Reference

  • Christophe Andrieu, Nando De Freitas and Arnaud Doucet, An Introduction to MCMC for Machine Learning, 2003
  • ASMUSSEN, Søren; GLYNN, Peter W. Stochastic Simulation: Algorithms and Analysis. [s.l.]: Springer, 2007. (Stochastic Modelling and Applied Probability; sv. 57). 
  • ATZBERGER, P. An Introduction to Monte-Carlo Methods [online]. Dostupné online. 
  • BERG, Bernd A. Markov Chain Monte Carlo Simulations and Their Statistical Analysis. [s.l.]: World Scientific, 2004. 
  • BOLSTAD, William M. Understanding Computational Bayesian Statistics. [s.l.]: Wiley, 2010. ISBN 0-470-04609-0. 
  • CASELLA, George; GEORGE, Edward I. Explaining the Gibbs sampler. The American Statistician. 1992, s. 167–174. DOI 10.2307/2685208.  (Basic summary and many references.)
  • GELFAND, A.E.; SMITH, A.F.M. Sampling-Based Approaches to Calculating Marginal Densities. Journal of the American Statistical Association. 1990, s. 398–409. DOI 10.1080/01621459.1990.10476213. 
  • GELMAN, Andrew; CARLIN, John B.; STERN, Hal S.; RUBIN, Donald B. Bayesian Data Analysis. 1st. vyd. [s.l.]: Chapman and Hall, 1995.  (See Chapter 11.)
  • GEMAN, S.; GEMAN, D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence. 1984, s. 721–741. 
  • GILKS, W.R.; RICHARDSON, S.; SPIEGELHALTER, D.J. Markov Chain Monte Carlo in Practice. [s.l.]: Chapman and Hall/CRC, 1996. 
  • GILL, Jeff. Bayesian methods: a social and behavioral sciences approach. 2nd. vyd. [s.l.]: Chapman and Hall/CRC, 2008. ISBN 1-58488-562-9. 
  • GREEN, P.J. Reversible-jump Markov chain Monte Carlo computation and Bayesian model determination. Biometrika. 1995, s. 711–732. DOI 10.1093/biomet/82.4.711. 
  • NEAL, Radford M. Slice Sampling. Annals of Statistics. 2003, s. 705–767. DOI 10.1214/aos/1056562461. JSTOR 3448413. 
  • NEAL, Radford M. Probabilistic Inference Using Markov Chain Monte Carlo Methods [online]. 1993. Dostupné online. 
  • ROBERT, Christian P.; CASELLA, G. Monte Carlo Statistical Methods. 2nd. vyd. [s.l.]: Springer, 2004. ISBN 0-387-21239-6. 
  • RUBINSTEIN, R.Y.; KROESE, D.P. Simulation and the Monte Carlo Method. 2nd. vyd. [s.l.]: Wiley, 2007. ISBN 978-0-470-17794-5. 
  • SMITH, R.L. Efficient Monte Carlo Procedures for Generating Points Uniformly Distributed Over Bounded Regions. Operations Research. 1984, s. 1296–1308. DOI 10.1287/opre.32.6.1296. 
  • SPALL, J.C. Estimation via Markov Chain Monte Carlo. IEEE Control Systems Magazine. April 2003, s. 34–45. DOI 10.1109/mcs.2003.1188770. 
  • STRAMER, O.; TWEEDIE, R. Langevin-Type Models II: Self-Targeting Candidates for MCMC Algorithms. Methodology and Computing in Applied Probability. 1999, s. 307–328. DOI 10.1023/A:1010090512027. 


Externí odkazy

V tomto článku byl použit překlad textu z článku Markov chain Monte Carlo na anglické Wikipedii.

Citováno z „https://cs.wikipedia.org/w/index.php?title=Markov_chain_Monte_Carlo&oldid=12630471“