Próbkowanie Monte Carlo łańcuchami Markowa: Różnice pomiędzy wersjami

Z Wikipedii, wolnej encyklopedii
Przeglądaj historię interaktywnie
[wersja nieprzejrzana][wersja nieprzejrzana]
← poprzednia edycjanastępna edycja →
Usunięta treść Dodana treść
WizualnieWikikod
m polonizacja
RadostW (dyskusja | edycje)
213 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
{{Przetłumaczony|en|Markov chain Monte Carlo}}

'''Próbkowanie Monte Carlo łańcuchami Markowa''' (ang. Markov Chain Monte Carlo, MCMC) – w [[Statystyka|statystyce]] klasa [[Algorytm|algorytmów]] próbkowania z [[Rozkład prawdopodobieństwa|rozkładu prawdopodobieństwa]]. Poprzez budowę [[Łańcuch Markowa|Łańcucha Markowa]], który ma [[Łańcuch Markowa|rozkład równowagowy]] taki jak szukana dystrybucja, można wydajnie próbkować złożone rozkłady prawdopodobieństwa. Im większa liczba kroków w takim algorytmie, tym dokładniej rozkład próbki odpowiada pożądanemu rozkładowi.
'''Próbkowanie Monte Carlo łańcuchami Markowa''' (ang. Markov Chain Monte Carlo, MCMC) – w [[Statystyka|statystyce]] klasa [[Algorytm|algorytmów]] próbkowania z [[Rozkład prawdopodobieństwa|rozkładu prawdopodobieństwa]]. Poprzez budowę [[Łańcuch Markowa|Łańcucha Markowa]], który ma [[Łańcuch Markowa|rozkład równowagowy]] taki jak szukana dystrybucja, można wydajnie próbkować złożone rozkłady prawdopodobieństwa. Im większa liczba kroków w takim algorytmie, tym dokładniej rozkład próbki odpowiada pożądanemu rozkładowi.
[[Plik:Metropolis_algorithm_convergence_example.png|mały|Zbieżność algorytmu<font color="#000000"> </font>[[Algorytm Metropolisa-Hastingsa|Metropolisa-Hastingsa]]. MCMC przybliża niebieski rozkład pomarańczowym rozkładem coraz dokładniej, gdy rośnie liczba kroków.]]
[[Plik:Metropolis_algorithm_convergence_example.png|mały|Zbieżność algorytmu<font color="#000000"> </font>[[Algorytm Metropolisa-Hastingsa|Metropolisa-Hastingsa]]. MCMC przybliża niebieski rozkład pomarańczowym rozkładem coraz dokładniej, gdy rośnie liczba kroków.]]
Linia 30: Linia 32:
== Przypisy ==
== Przypisy ==
{{Przypisy}}
{{Przypisy}}


== Biliografia ==
{{refbegin|30em}}
* Christophe Andrieu, Nando De Freitas, Arnaud Doucet and Michael I. Jordan [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
| name1 = George 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
}}
*{{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
}}
{{refend}}

Wersja z 16:37, 7 lis 2018

Próbkowanie Monte Carlo łańcuchami Markowa (ang. Markov Chain Monte Carlo, MCMC) – w statystyce klasa algorytmów próbkowania z rozkładu prawdopodobieństwa. Poprzez budowę Łańcucha Markowa, który ma rozkład równowagowy taki jak szukana dystrybucja, można wydajnie próbkować złożone rozkłady prawdopodobieństwa. Im większa liczba kroków w takim algorytmie, tym dokładniej rozkład próbki odpowiada pożądanemu rozkładowi.

Zbieżność algorytmu Metropolisa-Hastingsa. MCMC przybliża niebieski rozkład pomarańczowym rozkładem coraz dokładniej, gdy rośnie liczba kroków.

Błądzenie losowe Monte-Carlo jest istotną dużą podklasą takich procesów próbkowania.

Dziedziny stosowania

Algorytmy MCMC są używane głównie do obliczania przybliżeń numerycznych dla całek wielowymiarowych, na przykład w statystyce Bayesowskiej, fizyce komputerowej, biologii obliczeniowej[1] i lingwistyce komputerowej[2][3].

W statystyce Bayesowskiej nowe badania algorytmów MCMC były kluczowym krokiem potrzebnym do wyliczania dużych modeli hierarchicznych, które wymagają całkowania w dziedzinach setek parametrów swobodnych[4].

W próbkowaniu rzadkich zdarzeń są one również wykorzystywane do tworzenia próbek, które stopniowo odzwierciedlają rzadko odwiedzane obszary (co jest szczególnie istotne dla obszarów ryzyka).

Przykłady

Przykłady błądzenia losowego Monte Carlo obejmuje następujące algorytmy:

  • Algorytm Metropolis–Hastings: ta metoda generuje błądzenie losowe w oparciu o gęstość przyjmowania i odrzucania propozycji kolejnych kroków.
  • Próbkowanie Gibbsa: ta metoda dodatkowo wymaga, aby wszystkie warunkowe rozkłady prawdopodobieństwa docelowego rozkładu były znane (z dokładnością do stałej). Gdy próbkowanie warunkowych rozkładów nie jest łatwe, inne sub-metody próbkowanie mogą być użyte (patrz na przykład[5][6][7]). Próbkowanie Gibbsa zawdzięcza swoją popularność głównie brakowi parametrów swobodnych.
  • Próbkowanie przekrojów: Ta metoda opiera się na obserwacji, że dystrybucje można wiernie próbkować poprzez jednorodne próbkowanie odpowiednich podzbiorów dziedziny. Metoda wykonuje dwa rodzaje kroków naprzemiennie: próbkę 'w pionie' z rozkładu jednorodnego i próbkę 'w poziomie' z podzbioru dziedziny dla której gęstość prawdopodobieństwa jest mniejsza od próbki 'pionowej'.
  • Wielokrotne Metropolis: ta metoda jest odmianą algorytmu Metropolis–Hastings, która pozwala na wiele prób w każdym punkcie. Poprzez umożliwienie dłuższych kroków w każdej iteracji, częściowo rozwiązuje "przekleństwa wymiaru"[8][9].
  • Odwracalny-skok: ta metoda jest odmiana algorytmu Metropolis–Hastings, która pozwala na dynamiczną zmianę wymiaru przestrzeni próbkowania[10]. Algorytmy MCMC, które zmieniają wymiar są stosowane w mechanice statystycznej, gdzie dla pewnych przypadków próbkowany rozkład układu wielkiego kanonicznego (na przykład gdy liczba cząsteczek w dziedzinie jest zmienna) zmienia wymiar dziedziny.

Redukowanie korelacji

Bardziej złożone metody wykorzystują różne sposoby, aby zmniejszyć korelację pomiędzy kolejnymi próbkami. Algorytmy te mogą być trudniejsze w implementacji, ale często wykazują szybszą zbieżność (tj. mniejszą ilość kroków w celu uzyskania tej samej dokładności próbkowania).

Przykłady

Przykłady MCMC, nie należących do metod błądzenia losowego obejmują następujące algorytmy:

  • Hybrydowa metoda Monte-Carlo (HMC): unika błądzenia losowego poprzez wprowadzenie pędu i równań Hamiltonowskich, takich że energia potencjalna jest proporcjonalna do docelowego rozkładu prawdopodobieństwa. Takie podejście skutkuje szybszym poruszaniem się po dziedzinie próbkowania i daje lepszą zbieżność do docelowego rozkładu.
  • Istnieją też warianty próbkowania przekrojów, które nie korzystają z błądzenia losowego[11].
  • MCMC Langevina i inne metody oparte na gradiencie (czasem także na drugiej pochodnej) logarytmu rozkładu warunkowego pozwalają na tworzenie propozycji, które mają większą szansę na poruszanie się w kierunku dużej gęstości prawdopodobieństwa[12].

Przypisy

  1. ↑ Ankur Gupta, James B. Rawlings. Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology. „AIChE pismo”. 60 (4), s. 1253–1268, April 2014. DOI: 10.1002/aic.14409. PMID: 27429455. PMCID: PMC4946376. 
  2. ↑ Zobacz: Gill 2008.
  3. ↑ Zobacz: Robert & Casella 2004.
  4. ↑ Sudipto Banerjee, Bradley P. Carlin, Alan P. Gelfand: Hierarchical Modeling and Analysis for Spatial Data. Wyd. Wyd.2. CRC Press, s. xix. ISBN 978-1-4398-1917-3.
  5. ↑ W. R. Gilks, P. Wild. Adaptive Rejection Sampling for Gibbs Sampling. „Journal of the Royal Statistical Society. Series C (Applied Statistics)”. 41 (2), s. 337–348, 1992-01-01. DOI: 10.2307/2347565. JSTOR: 2347565. 
  6. ↑ W.R. Gilks, N.G. Best, K.K.C. Tan. Adaptive Rejection Metropolis Sampling within Gibbs Sampling. „Journal of the Royal Statistical Society. Series C (Applied Statistics)”. 44 (4), s. 455–472, 1995-01-01. DOI: 10.2307/2986138. JSTOR: 2986138. 
  7. ↑ L. Martino, J. Read, D. Luengo. Independent Doubly Adaptive Rejection Metropolis Sampling Within Gibbs Sampling. „IEEE Transactions on Signal Processing”. 63 (12), s. 3123–3138, 2015-06-01. DOI: 10.1109/TSP.2015.2420537. arXiv:1205.5494. ISSN 1053-587X. Bibcode: 2015ITSP...63.3123M. 
  8. ↑ Jun S. Liu, Faming Liang, Wing Hung Wong. The Multiple-Try Method and Local Optimization in Metropolis Sampling. „Journal of the American Statistical Association”. 95 (449), s. 121–134, 2000-03-01. DOI: 10.1080/01621459.2000.10473908. ISSN 0162-1459. 
  9. ↑ Luca Martino, Jesse Read. On the flexibility of the design of multiple try Metropolis schemes. „Computational Statistics”. 28 (6), s. 2797–2823, 2013-07-11. DOI: 10.1007/s00180-013-0429-2. arXiv:1201.0646. ISSN 0943-4062. 
  10. ↑ Zobacz: Green 1995.
  11. ↑ Zobacz: Neal 2003.
  12. ↑ Zobacz: Stramer 1999.


Biliografia

Szablon:Refbegin

Szablon:Refend

Źródło: „https://pl.wikipedia.org/w/index.php?title=Próbkowanie_Monte_Carlo_łańcuchami_Markowa&oldid=54971391”