Algoritmus Metropolis – Hastings - Metropolis–Hastings algorithm

Tento návrh rozdělení Q navrhuje další bod ke kterému náhodná procházka mohla pohybovat.

V statistik a statistické fyziky je metropole-Hastings algoritmus je Monte Carlo Markov řetězec metoda (MCMC) pro získání sekvence náhodných vzorků z rozdělení pravděpodobnosti , z níž přímý odběr vzorků je obtížné. Tuto sekvenci lze použít k aproximaci distribuce (např. Ke generování histogramu ) nebo k výpočtu integrálu (např. Očekávané hodnoty). Metropolis – Hastings a další algoritmy MCMC se obecně používají pro vzorkování z vícerozměrných distribucí, zvláště když je počet dimenzí vysoký. Pro jednorozměrné distribuce obvykle existují jiné metody (např. Vzorkování s adaptivním odmítnutím ), které mohou přímo vracet nezávislé vzorky z distribuce, a ty neobsahují problém autokorelovaných vzorků, který je vlastní metodám MCMC.

Dějiny

Algoritmus byl pojmenován po Nicholasovi Metropolisovi , který je autorem článku z roku 1953 Rovnice stavových výpočtů rychlými výpočetními stroji společně s Ariannou W. Rosenbluth , Marshall Rosenbluth , Augusta H. Teller a Edward Teller . Tento článek navrhl algoritmus pro případ symetrických distribucí návrhů a WK Hastings jej v roce 1970 rozšířil na obecnější případ.

Existuje určitá kontroverze, pokud jde o kredit za vývoj algoritmu. Metropolis, který byl obeznámen s výpočetními aspekty této metody, vytvořil termín „Monte Carlo“ v dřívějším článku se Stanisławem Ulamem a vedl skupinu v teoretické divizi, která navrhla a vyrobila počítač MANIAC I používaný při experimentech v 1952. Před rokem 2003 však neexistoval podrobný popis vývoje algoritmu. Poté, krátce před svou smrtí, se Marshall Rosenbluth zúčastnil konference v LANL v roce 2003 u příležitosti 50. výročí publikace z roku 1953. Na této konferenci Rosenbluth popsal algoritmus a jeho vývoj v prezentaci s názvem „Genesis algoritmu Monte Carlo pro statistickou mechaniku“. Další historické objasnění uvádí Gubernatis v článku z deníku z roku 2005, který popisuje konferenci k 50. výročí. Rosenbluth dává jasně najevo, že on a jeho manželka Arianna odvedli práci a že Metropolis nehrála ve vývoji jinou roli než poskytování počítačového času.

To je v rozporu s účtem Edwarda Tellera, který ve svých pamětech uvádí, že pět autorů článku z roku 1953 spolupracovalo „dny (a noci)“. Naproti tomu podrobný popis Rosenblutha připisuje Tellerovi zásadní, ale raný návrh „využít statistickou mechaniku a vzít v úvahu souborné průměry namísto sledování podrobné kinematiky“. To, říká Rosenbluth, ho přimělo přemýšlet o zobecněném přístupu Monte Carlo - o tématu, které, jak říká, často diskutoval s Johnem Von Neumannem . Arianna Rosenbluth vyprávěla (Gubernatis v roce 2003), že Augusta Teller zahájila práci s počítačem, ale že to převzala sama Arianna a napsala kód od nuly. V ústní historii zaznamenané krátce před jeho smrtí Rosenbluth opět připisuje Tellerovi, že položil původní problém, sám jeho vyřešení a Arianna programování počítače. Pokud jde o pověst, není důvod zpochybňovat Rosenbluthův účet. V biografické monografii Rosenbluth Freeman Dyson píše:

Mnohokrát jsem přišel do Rosenbluthu, položil jsem mu otázku [...] a odpověď jsem dostal do dvou minut. Pak by mi obvykle trvalo týden tvrdé práce, abych detailně pochopil, proč byla Rosenbluthova odpověď správná. Měl úžasnou schopnost prohlédnout si komplikovanou fyzickou situaci a dosáhnout správné odpovědi fyzickými argumenty. Enrico Fermi byl jediný další fyzik, kterého jsem znal a který se svým intuitivním uchopením fyziky vyrovnal Rosenbluthovi.

Intuice

Algoritmus Metropolis – Hastings může čerpat vzorky z jakéhokoli rozdělení pravděpodobnosti s hustotou pravděpodobnosti za předpokladu, že známe funkci úměrnou hustotě a hodnoty z ní lze vypočítat. Díky požadavku, který musí být spíše úměrný hustotě, než aby se jí přesně rovnal, je algoritmus Metropolis – Hastings obzvláště užitečný, protože výpočet nezbytného normalizačního faktoru je v praxi často extrémně obtížný. ${\ displaystyle P (x)}$${\ displaystyle f (x)}$ ${\ displaystyle P}$${\ displaystyle f (x)}$${\ displaystyle f (x)}$

Algoritmus Metropolis – Hastings funguje tak, že generuje posloupnost hodnot vzorků takovým způsobem, že jak se vytváří stále více hodnot vzorků, distribuce hodnot se blíže blíží požadovanému rozdělení. Tyto hodnoty vzorků jsou vytvářeny iterativně, přičemž distribuce dalšího vzorku je závislá pouze na aktuální hodnotě vzorku (čímž sekvence vzorků vytvoří řetězec Markov ). Konkrétně při každé iteraci algoritmus vybere kandidáta na další hodnotu vzorku na základě aktuální hodnoty vzorku. Potom je s určitou pravděpodobností kandidát buď přijat (v takovém případě je kandidátská hodnota použita v další iteraci), nebo odmítnut (v takovém případě je kandidátská hodnota zahozena a aktuální hodnota je znovu použita v další iteraci) - pravděpodobnost přijetí je určeno porovnáním hodnot funkcí aktuálních a kandidátních hodnot vzorku s ohledem na požadované rozdělení. ${\ displaystyle f (x)}$

Pro ilustraci je níže popsán algoritmus Metropolis, speciální případ algoritmu Metropolis – Hastings, kde je funkce návrhu symetrická.

Algoritmus metropole (symetrická distribuce návrhu)

Nechť je funkce, která je úměrná požadované funkci hustoty pravděpodobnosti (aka rozdělení cíle). ${\ displaystyle f (x)}$${\ displaystyle P (x)}$

1. Inicializace: Vyberte libovolný bod, který má být prvním pozorováním ve vzorku, a zvolte libovolnou hustotu pravděpodobnosti (někdy psanou ), která navrhne kandidáta na další hodnotu vzorku vzhledem k hodnotě předchozího vzorku . V této části se předpokládá, že je symetrický; jinými slovy, musí uspokojit . Obvyklý výběr je nechat být Gaussian distribuce centrovaný při , takže body blíže k větší pravděpodobností navštíví příští, takže posloupnost vzorků do náhodné procházky . Funkce je označována jako hustota návrhu nebo distribuce skoků .${\ displaystyle x_ {t}}$${\ Displaystyle g (x \ mid y)}$${\ displaystyle Q (x \ mid y)}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle g}$${\ Displaystyle g (x \ mid y) = g (y \ mid x)}$${\ Displaystyle g (x \ mid y)}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle g}$
2. Pro každou iteraci t :
   • Vygenerováním kandidáta pro další vzorek výběrem z distribuce .${\ displaystyle x '}$${\ displaystyle g (x '\ mid x_ {t})}$
   • Vypočítat na poměr přijetí , který bude použit pro rozhodnutí, zda přijmout nebo odmítnout kandidáta. Protože f je úměrné hustotě P , máme to .${\ Displaystyle \ alpha = f (x ')/f (x_ {t})}$${\ Displaystyle \ alpha = f (x ')/f (x_ {t}) = P (x')/P (x_ {t})}$
   • Přijmout nebo odmítnout :
     • Vygenerujte jednotné náhodné číslo .${\ Displaystyle u \ v [0,1]}$
     • Pokud pak přijměte kandidáta nastavením ,${\ Displaystyle u \ leq \ alpha}$${\ displaystyle x_ {t+1} = x '}$
     • Pokud , pak kandidáta odmítněte a místo toho nastavte .${\ Displaystyle u> \ alpha}$${\ displaystyle x_ {t+1} = x_ {t}}$

Tento algoritmus pokračuje náhodným pokusem pohybovat se po ukázkovém prostoru, někdy tahy přijímá a někdy zůstává na místě. Poměr přijatelnosti udává, jak pravděpodobný je nový navrhovaný vzorek vzhledem k aktuálnímu vzorku podle rozdělení, jehož hustota je . Pokud se pokusíme přesunout do bodu, který je pravděpodobnější než stávající bod (tj. Bod v oblasti s vyšší hustotou odpovídající an ), vždy tento pohyb přijmeme. Pokud se však pokusíme přejít na méně pravděpodobný bod, někdy tento krok odmítneme a čím větší je relativní pokles pravděpodobnosti, tím je pravděpodobnější, že nový bod odmítneme. Budeme tedy mít tendenci zůstat v oblastech s vysokou hustotou (a vracet z nich velké množství vzorků) , zatímco jen příležitostně navštívíme oblasti s nízkou hustotou. Intuitivně to je důvod, proč tento algoritmus funguje a vrací vzorky, které hustotou sledují požadované rozdělení . ${\ Displaystyle \ alpha}$${\ displaystyle P (x)}$${\ displaystyle P (x)}$${\ Displaystyle \ alpha> 1 \ geq u}$${\ displaystyle P (x)}$${\ displaystyle P (x)}$

Ve srovnání s algoritmem, jako je adaptivní odmítnutí vzorkování, který přímo generuje nezávislé vzorky z distribuce, mají Metropolis – Hastings a další algoritmy MCMC řadu nevýhod:

• Vzorky jsou ve vzájemném vztahu. Přestože dlouhodobě sledují správně , sada blízkých vzorků bude navzájem korelovat a nebude správně odrážet distribuci. To znamená, že pokud chceme sadu nezávislých vzorků, musíme většinu vzorků vyhodit a odebrat pouze každý n -tý vzorek, pro nějakou hodnotu n (typicky určeno zkoumáním autokorelace mezi sousedními vzorky). Autokorelaci lze snížit zvýšením šířky skoku (průměrná velikost skoku, která souvisí s rozptylem rozdělení skoku), ale také se tím zvýší pravděpodobnost odmítnutí navrhovaného skoku. Příliš velká nebo příliš malá skoková velikost povede k pomalému míchání Markovova řetězce, tj. Vysoce korelované sady vzorků, takže k získání rozumného odhadu jakékoli požadované vlastnosti distribuce bude zapotřebí velmi velkého počtu vzorků.${\ displaystyle P (x)}$
• Ačkoli Markovův řetězec nakonec konverguje k požadované distribuci, počáteční vzorky mohou sledovat velmi odlišné rozdělení, zvláště pokud je počáteční bod v oblasti s nízkou hustotou. Jako výsledek, burn-in je obvykle nutné období, ve kterém počáteční počet vzorků (např první 1000 nebo tak nějak) jsou vyhozeny.

Na druhou stranu většina jednoduchých metod odběru vzorků odmítnutí trpí „ kletbou dimenzionality “, kde se pravděpodobnost odmítnutí exponenciálně zvyšuje v závislosti na počtu dimenzí. Metropolis – Hastings, spolu s dalšími metodami MCMC, nemají tento problém do takové míry, a proto jsou často jediným dostupným řešením, když je počet rozměrů distribuce, která má být odebrána, vysoký. V důsledku toho jsou metody MCMC často metodami volby pro produkci vzorků z hierarchických bayesovských modelů a dalších vysoce dimenzionálních statistických modelů používaných v dnešní době v mnoha oborech.

U vícerozměrných distribucí zahrnuje klasický algoritmus Metropolis – Hastings, jak je popsán výše, výběr nového vícerozměrného vzorkovacího bodu. Když je počet dimenzí vysoký, nalezení vhodné distribuce skákání k použití může být obtížné, protože různé jednotlivé dimenze se chovají velmi odlišnými způsoby a šířka skoku (viz výše) musí být „správná“ pro všechny dimenze najednou, aby vyhněte se příliš pomalému míchání. Alternativní přístup, který v takových situacích často funguje lépe, známý jako Gibbsovo vzorkování , zahrnuje výběr nového vzorku pro každou dimenzi odděleně od ostatních, nikoli výběr vzorku pro všechny dimenze najednou. Tímto způsobem se problém vzorkování z potenciálně vysoce dimenzionálního prostoru zredukuje na soubor problémů ke vzorkování z malé dimenzionality. To je zvláště použitelné, když je vícerozměrná distribuce složena ze sady jednotlivých náhodných proměnných, ve kterých je každá proměnná podmíněna pouze malým počtem dalších proměnných, jak je tomu ve většině typických hierarchických modelů . Jednotlivé proměnné jsou poté vzorkovány po jedné, přičemž každá proměnná je podmíněna nejnovějšími hodnotami všech ostatních. K výběru těchto jednotlivých vzorků lze použít různé algoritmy v závislosti na přesné formě vícerozměrné distribuce: některými možnostmi jsou metody vzorkování s adaptivním odmítnutím, algoritmus vzorkování s adaptivním odmítnutím, jednoduchý jednorozměrný krok Metropolis – Hastings nebo vzorkování řezů .

Formální odvození

Účelem algoritmu Metropolis – Hastings je generovat kolekci stavů podle požadovaného rozdělení . K dosažení tohoto cíle, algoritmus používá Markov proces , který dosahuje asymptoticky jedinečná pevná distribuce taková, že . ${\ displaystyle P (x)}$ ${\ displaystyle \ pi (x)}$${\ Displaystyle \ pi (x) = P (x)}$

Markovův proces je jednoznačně definován jeho pravděpodobnostmi přechodu , pravděpodobností přechodu z jakéhokoli daného stavu do jakéhokoli jiného daného stavu . Má jedinečné stacionární rozdělení, pokud jsou splněny následující dvě podmínky: ${\ Displaystyle P (x '\ mid x)}$${\ displaystyle x}$${\ displaystyle x '}$${\ displaystyle \ pi (x)}$

1. Existence stacionární distribuce : musí existovat stacionární distribuce . Dostatečný ale není nutnou podmínkou je podrobně rovnováhy , což znamená, že každý přechod je reverzibilní: pro každou dvojici stavů , je pravděpodobnost, že ve stavu, a přechází do stavu se musí rovnat pravděpodobnosti, že ve stavu, a přechází do stavu , .${\ displaystyle \ pi (x)}$${\ displaystyle x \ to x '}$${\ displaystyle x, x '}$${\ displaystyle x}$${\ displaystyle x '}$${\ displaystyle x '}$${\ displaystyle x}$${\ Displaystyle \ pi (x) P (x '\ mid x) = \ pi (x') P (x \ mid x ')}$
2. Jedinečnost stacionární distribuce : Stacionární distribuce musí být jedinečná. To je zaručeno ergodicitou Markovova procesu, který vyžaduje, aby každý stav musel (1) být neperiodický - systém se nevrací do stejného stavu v pevných intervalech; a (2) být kladně se opakující - očekávaný počet kroků pro návrat do stejného stavu je konečný.${\ displaystyle \ pi (x)}$

Algoritmus Metropolis – Hastings zahrnuje navrhování Markovova procesu (konstruováním pravděpodobností přechodu), který splňuje dvě výše uvedené podmínky, takže je zvoleno jeho stacionární rozdělení . Odvození algoritmu začíná podmínkou podrobného zůstatku : ${\ displaystyle \ pi (x)}$${\ displaystyle P (x)}$

${\ Displaystyle P (x '\ mid x) P (x) = P (x \ mid x') P (x '),}$

který je přepsán jako

${\ displaystyle {\ frac {P (x '\ mid x)} {P (x \ mid x')}} = {\ frac {P (x ')} {P (x)}}.}$

Přístup je oddělit přechod ve dvou dílčích krocích; návrh a přijetí-zamítnutí. Distribuce návrhu je podmíněná pravděpodobnost navržení daného stavu a distribuce přijetí je pravděpodobnost přijetí navrhovaného stavu . Pravděpodobnost přechodu lze zapsat jako jejich součin: ${\ displaystyle g (x '\ mid x)}$${\ displaystyle x '}$${\ displaystyle x}$${\ displaystyle A (x ', x)}$${\ displaystyle x '}$

${\ Displaystyle P (x '\ mid x) = g (x' \ mid x) A (x ', x).}$

Vložením tohoto vztahu do předchozí rovnice máme

${\ displaystyle {\ frac {A (x ', x)} {A (x, x')}}} = {\ frac {P (x ')} {P (x)}} {\ frac {g (x \ mid x ')} {g (x' \ mid x)}}.}$

Dalším krokem při odvozování je zvolit poměr přijetí, který splňuje výše uvedenou podmínku. Jednou z běžných možností je volba Metropolis:

${\ Displaystyle A (x ', x) = \ min \ left (1, {\ frac {P (x')} {P (x)}} {\ frac {g (x \ mid x ')} {g (x '\ mid x)}} \ right).}$

U tohoto poměru přijatelnosti Metropolis je podmínka splněna buď, nebo, a tak. ${\ displaystyle A}$${\ Displaystyle A (x ', x) = 1}$${\ Displaystyle A (x, x ') = 1}$

Algoritmus Metropolis – Hastings tedy sestává z následujícího:

1. Inicializovat
   1. Vyberte počáteční stav .${\ displaystyle x_ {0}}$
   2. Nastavit .${\ displaystyle t = 0}$
2. Opakovat
   1. Generujte náhodný kandidátský stav podle .${\ displaystyle x '}$${\ displaystyle g (x '\ mid x_ {t})}$
   2. Vypočítejte pravděpodobnost přijetí .${\ Displaystyle A (x ', x_ {t}) = \ min \ left (1, {\ frac {P (x')} {P (x_ {t})}} {\ frac {g (x_ {t } \ mid x ')} {g (x' \ mid x_ {t})}} \ right)}$
   3. Přijmout nebo odmítnout :
      1. vygenerovat jednotné náhodné číslo ;${\ Displaystyle u \ v [0,1]}$
      2. pokud , pak přijměte nový stav a nastavte ;${\ Displaystyle u \ leq A (x ', x_ {t})}$${\ displaystyle x_ {t+1} = x '}$
      3. pokud , pak odmítněte nový stav a zkopírujte starý stav dopředu .${\ Displaystyle u> A (x ', x_ {t})}$${\ displaystyle x_ {t+1} = x_ {t}}$
   4. Přírůstek : set .${\ displaystyle t = t+1}$

Za předpokladu splnění stanovených podmínek se přiblíží empirická distribuce uložených stavů . Počet iterací ( ) potřebných k efektivnímu odhadu závisí na počtu faktorů, včetně vztahu mezi a distribucí návrhu a požadované přesnosti odhadu. Pro distribuci na diskrétních stavových prostorech musí být v řádu času autokorelace Markovova procesu. ${\ displaystyle x_ {0}, \ ldots, x_ {T}}$${\ displaystyle P (x)}$${\ displaystyle T}$${\ displaystyle P (x)}$${\ displaystyle P (x)}$

Je důležité si všimnout, že v obecném problému není jasné, jakou distribuci je třeba použít, ani počet iterací nezbytných pro správný odhad; oba jsou volnými parametry metody, které musí být přizpůsobeny konkrétnímu problému v ruce. ${\ displaystyle g (x '\ mid x)}$

Použití v numerické integraci

Běžným použitím algoritmu Metropolis – Hastings je výpočet integrálu. Konkrétně v úvahu prostor a rozdělení pravděpodobnosti nad , . Metropolis – Hastings dokáže odhadnout integrál formy ${\ displaystyle \ Omega \ subset \ mathbb {R}}$${\ displaystyle P (x)}$${\ displaystyle \ Omega}$${\ displaystyle x \ in \ Omega}$

${\ Displaystyle P (E) = \ int _ {\ Omega} A (x) P (x) \, dx,}$

kde je (měřitelná) funkce zájmu. ${\ displaystyle A (x)}$

Zvažte například statistiku a její rozdělení pravděpodobnosti , což je okrajové rozdělení . Předpokládejme, že cílem je odhadnout dobu na ocase . Formálně lze zapsat jako ${\ displaystyle E (x)}$${\ displaystyle P (E)}$${\ displaystyle P (E)}$${\ displaystyle E}$${\ displaystyle P (E)}$${\ displaystyle P (E)}$

${\ Displaystyle P (E) = \ int _ {\ Omega} P (E \ mid x) P (x) \, dx = \ int _ {\ Omega} \ delta {\ big (} EE (x) {\ velký)} P (x) \, dx = E {\ velký (} P (E \ střední X) {\ velký)}}$

a odhadování lze tedy provést odhadem očekávané hodnoty funkce indikátoru , která je 1 kdy a nula jinak. Protože je na chvostu , je pravděpodobnost vykreslení stavu pomocí na ocasu úměrná , což je podle definice malé. Zde lze použít algoritmus Metropolis – Hastings k vzorkování (vzácnějších) stavů s větší pravděpodobností a tím ke zvýšení počtu vzorků použitých k odhadu na ocasech. To lze provést např. Pomocí distribuce vzorkování, která zvýhodňuje tyto stavy (např. S ). ${\ displaystyle P (E)}$ ${\ Displaystyle A_ {E} (x) \ equiv \ mathbf {1} _ {E} (x)}$${\ Displaystyle E (x) \ in [E, E+\ Delta E]}$${\ displaystyle E}$${\ displaystyle P (E)}$${\ displaystyle x}$${\ displaystyle E (x)}$${\ displaystyle P (E)}$${\ displaystyle P (E)}$${\ displaystyle P (E)}$${\ displaystyle \ pi (x)}$${\ Displaystyle \ pi (x) \ propto e^{aE}}$${\ displaystyle a> 0}$

Pokyny krok za krokem

Předpokládejme, že nejnovější vzorkovaná hodnota je . Abychom se řídili algoritmem Metropolis – Hastings, nakreslíme nový stav návrhu s hustotou pravděpodobnosti a vypočítáme hodnotu ${\ displaystyle x_ {t}}$${\ displaystyle x '}$${\ displaystyle g (x '\ mid x_ {t})}$

${\ displaystyle a = a_ {1} a_ {2},}$

kde

${\ displaystyle a_ {1} = {\ frac {P (x ')} {P (x_ {t})}}}$

je poměr pravděpodobnosti (např. Bayesovský zadní) mezi navrhovaným vzorkem a předchozím vzorkem a ${\ displaystyle x '}$${\ displaystyle x_ {t}}$

${\ displaystyle a_ {2} = {\ frac {g (x_ {t} \ mid x ')} {g (x' \ mid x_ {t})}}}$

je poměr hustoty návrhu ve dvou směrech (od do a naopak). Pokud je hustota návrhu symetrická, rovná se 1. Poté se nový stav zvolí podle následujících pravidel. ${\ displaystyle x_ {t}}$${\ displaystyle x '}$${\ displaystyle x_ {t+1}}$

Li ${\ displaystyle a \ geq 1 {:}}$

${\ displaystyle x_ {t+1} = x ',}$

jiný:

${\ displaystyle x_ {t+1} = {\ begin {cases} x '& {\ text {with likely}} a, \\ x_ {t} & {\ text {with likely}} 1-a. \ end {případy}}}$

Markovův řetězec je spuštěn z libovolné počáteční hodnoty a algoritmus je spuštěn pro mnoho iterací, dokud není tento počáteční stav „zapomenut“. Tyto vzorky, které jsou vyřazeny, jsou známé jako vypálení . Zbývající sada přijatých hodnot představuje vzorek z distribuce . ${\ displaystyle x_ {0}}$${\ displaystyle x}$${\ displaystyle P (x)}$

Algoritmus funguje nejlépe, pokud se hustota návrhu shoduje s tvarem distribuce cíle , z níž je obtížné přímé vzorkování . Pokud je použita Gaussova hustota návrhu , musí být parametr rozptylu naladěn během doby zážehu. To se obvykle provádí výpočtem míry přijatelnosti , což je zlomek navržených vzorků, který je přijat v okně posledních vzorků. Požadovaná míra přijetí závisí na cílové distribuci, nicméně teoreticky bylo ukázáno, že ideální míra přijetí pro jednorozměrné Gaussovo rozdělení je přibližně 50%, přičemž klesá pro přibližně -23% pro rozměrovou Gaussovu cílovou distribuci. ${\ displaystyle P (x)}$${\ Displaystyle g (x '\ mid x_ {t}) \ zhruba P (x')}$${\ displaystyle g}$${\ displaystyle \ sigma ^{2}}$${\ displaystyle N}$${\ displaystyle N}$

Pokud je příliš malý, řetěz se bude pomalu míchat (tj. Míra přijetí bude vysoká, ale po sobě jdoucí vzorky se budou pomalu pohybovat po prostoru a řetěz bude konvergovat jen pomalu k ). Na druhou stranu, pokud je příliš velký, míra přijetí bude velmi nízká, protože návrhy pravděpodobně přistanou v oblastech s mnohem nižší hustotou pravděpodobnosti, takže budou velmi malé a řetězec se opět bude sbíhat velmi pomalu. Distribuci návrhu obvykle vyladíte tak, aby algoritmy přijímaly řádově 30% všech vzorků - v souladu s teoretickými odhady uvedenými v předchozím odstavci. ${\ displaystyle \ sigma ^{2}}$${\ displaystyle P (x)}$${\ displaystyle \ sigma ^{2}}$${\ displaystyle a_ {1}}$

Výsledek tří Markovových řetězců běžících na funkci 3D Rosenbrock pomocí algoritmu Metropolis – Hastings. Algoritmus vzorkuje z oblastí, kde je pozdější pravděpodobnost vysoká, a řetězce se v těchto oblastech začínají míchat. Byla osvětlena přibližná poloha maxima. Červené body zůstávají po procesu vypalování. Ty dřívější byly vyřazeny.

Viz také

• Podrobný zůstatek
• Genetické algoritmy
• Gibbsův odběr
• Metody částic ve středním poli
• Langevinův algoritmus upravený podle metropole
• Světelná doprava metropole
• Metropolis na více pokusů
• Paralelní temperování
• Předběžný algoritmus Crank -Nicolson
• Sekvenční Monte Carlo
• Simulované žíhání

Reference

Poznámky

Další čtení

• Bernd A. Berg . Simulace Markovova řetězce Monte Carlo a jejich statistická analýza . Singapur, World Scientific , 2004.
• Siddhartha Chib a Edward Greenberg: „Porozumění algoritmu Metropolis - Hastings“. Americký statistik , 49 (4), 327–335, 1995
• David DL Minh a Do Le Minh. „Pochopení Hastingsova algoritmu.“ Komunikace ve statistice - Simulace a výpočet, 44: 2 332-349, 2015
• Bolstad, William M. (2010) Understanding Computational Bayesian Statistics , John Wiley & Sons ISBN  0-470-04609-0