Langevinův algoritmus upravený podle metropole - Metropolis-adjusted Langevin algorithm

v výpočetní statistika, Langevinův algoritmus upravený metropolí (MALA) nebo Langevin Monte Carlo (LMC) je Markovský řetězec Monte Carlo (MCMC) metoda získávání náhodné vzorky - sekvence náhodných pozorování - z a rozdělení pravděpodobnosti pro které je přímý odběr vzorků obtížný. Jak název napovídá, MALA používá kombinaci dvou mechanismů ke generování stavů a náhodná procházka který má cílové rozdělení pravděpodobnosti jako invariantní míra:

• nové státy se navrhují pomocí (přehnané ) Langevinova dynamika, které využívají hodnocení spád cíle funkce hustoty pravděpodobnosti;
• tyto návrhy jsou přijímány nebo odmítány pomocí Algoritmus Metropolis – Hastings, která využívá vyhodnocení cílové hustoty pravděpodobnosti (nikoli však její gradient).

Langevinova dynamika neformálně řídí náhodné procházky směrem k regionům s vysokou pravděpodobností ve způsobu gradientního toku, zatímco mechanismus přijetí / odmítnutí Metropolis – Hastings zlepšuje vlastnosti míchání a konvergence této náhodné procházky. MALA byla původně navržena Julian Besag v roce 1994,^[1] a jeho vlastnosti byly podrobně prozkoumány Gareth Roberts dohromady s Richard Tweedie^[2] a Jeff Rosenthal.^[3] Od té doby bylo zavedeno mnoho variací a vylepšení, např. the potrubí varianta Girolami a Calderhead (2011).^[4] Metoda je ekvivalentní použití Hamiltonské Monte Carlo algoritmus pouze s jediným diskrétním časovým krokem.^[4]

Více podrobností

Nechat ${ displaystyle pi}$ označit funkci hustoty pravděpodobnosti na ${ displaystyle mathbb {R} ^ {d}}$, z nichž je žádoucí čerpat soubor nezávislé a identicky distribuované Vzorky. Uvažujeme o přehnaném Langevinovi Je to difúze

${ displaystyle { dot {X}} = nabla log pi (X) + { sqrt {2}} { dot {W}}}$

poháněn časovou derivací standardu Brownův pohyb ${ displaystyle W}$. (Všimněte si, že další běžně používaná normalizace pro tuto difúzi je

${ displaystyle { dot {X}} = { frac {1} {2}} nabla log pi (X) + { dot {W}},}$

který generuje stejnou dynamiku.) V limitu jako ${ displaystyle t to infty}$, toto rozdělení pravděpodobnosti ${ displaystyle rho (t)}$ z ${ displaystyle X (t)}$ se blíží stacionární distribuci, která je také neměnná pod difúzí, kterou označujeme ${ displaystyle rho _ { infty}}$. Ukazuje se, že ve skutečnosti ${ displaystyle rho _ { infty} = pi}$.

Přibližné cesty vzorku Langevinovy ​​difúze lze generovat mnoha metodami diskrétního času. Jedním z nejjednodušších je Metoda Euler – Maruyama s pevným časovým krokem ${ displaystyle tau> 0}$. Jsme si stanovili ${ displaystyle X_ {0}: = x_ {0}}$ a poté rekurzivně definovat aproximaci ${ displaystyle X_ {k}}$ ke skutečnému řešení ${ displaystyle X (k tau)}$ podle

${ displaystyle X_ {k + 1}: = X_ {k} + tau nabla log pi (X_ {k}) + { sqrt {2 tau}} xi _ {k},}$

kde každý ${ displaystyle xi _ {k}}$ je nezávislé losování z a vícerozměrné normální rozdělení na ${ displaystyle mathbb {R} ^ {d}}$ s znamenat 0 a kovarianční matice rovná se ${ displaystyle d krát d}$ matice identity. Všimněte si, že ${ displaystyle X_ {k + 1}}$ je normálně distribuován se střední hodnotou ${ displaystyle X_ {k} + tau nabla log pi (X_ {k})}$ a kovariance rovna ${ displaystyle 2 tau}$ krát ${ displaystyle d krát d}$ matice identity.

Na rozdíl od metody Euler – Maruyama pro simulaci Langevinovy ​​difuze, která se vždy aktualizuje ${ displaystyle X_ {k}}$ podle pravidla aktualizace

${ displaystyle X_ {k + 1}: = X_ {k} + tau nabla log pi (X_ {k}) + { sqrt {2 tau}} xi _ {k},}$

MALA zahrnuje další krok. Výše uvedené pravidlo aktualizace považujeme za definování a návrh ${ displaystyle { tilde {X}} _ {k + 1}}$ pro nový stát,

${ displaystyle { tilde {X}} _ {k + 1}: = X_ {k} + tau nabla log pi (X_ {k}) + { sqrt {2 tau}} xi _ {k}.}$

Tento návrh je přijat nebo odmítnut podle sady algoritmů Metropolis-Hastings: set

${ displaystyle alpha: = min left {1, { frac { pi ({ tilde {X}} _ {k + 1}) q (X_ {k} mid { tilde {X} } _ {k + 1})} { pi ({X} _ {k}) q ({ tilde {X}} _ {k + 1} mid X_ {k})}} right }, }$

kde

${ Displaystyle q (x ' mid x) propto exp left (- { frac {1} {4 tau}} | x'-x- tau nabla log pi (x) | _ {2} ^ {2} vpravo)}$

je hustota pravděpodobnosti přechodu z ${ displaystyle x}$ na ${ displaystyle x '}$ (Všimněte si, že obecně ${ Displaystyle q (X ' mid x) neq q (x mid x')}$). Nechat ${ displaystyle u}$ být čerpány z kontinuální rovnoměrné rozdělení na intervalu ${ displaystyle [0,1]}$. Li ${ displaystyle u leq alpha}$, pak je návrh přijat a my jsme stanovili ${ displaystyle X_ {k + 1}: = { tilda {X}} _ {k + 1}}$; jinak je návrh zamítnut a my jsme nastavili ${ displaystyle X_ {k + 1}: = X_ {k}}$.

Kombinovaná dynamika Langevinovy ​​difúze a algoritmu Metropolis – Hastings uspokojuje podrobný zůstatek podmínky nezbytné pro existenci jedinečného, ​​neměnného, ​​stacionárního rozdělení ${ displaystyle rho _ { infty} = pi}$. Ve srovnání s naivní Metropolis – Hastings má MALA tu výhodu, že obvykle navrhuje přesun do vyšších oblastí ${ displaystyle pi}$ pravděpodobnost, které pak budou s větší pravděpodobností přijaty. Na druhou stranu, když ${ displaystyle pi}$ je silně anizotropní (tj. v některých směrech se mění mnohem rychleji než v jiných), je třeba se řídit ${ displaystyle 0 < tau ll 1}$ za účelem správného zachycení Langevinovy ​​dynamiky; použití pozitivního-definitivního předběžná úprava matice ${ displaystyle A in mathbb {R} ^ {d krát d}}$ může pomoci zmírnit tento problém generováním návrhů podle

${ displaystyle { tilde {X}} _ {k + 1}: = X_ {k} + tau A nabla log pi (X_ {k}) + { sqrt {2 tau A}} xi _ {k},}$

aby ${ displaystyle { tilde {X}} _ {k + 1}}$ má průměr ${ displaystyle X_ {k} + tau A nabla log pi (X_ {k})}$ a kovariance ${ displaystyle 2 tau A}$.

V praktických aplikacích je optimální míra přijetí pro tento algoritmus ${ displaystyle 0,574}$; pokud se zjistí, že je podstatně odlišný, ${ displaystyle tau}$ by měl být odpovídajícím způsobem upraven.^[3]

Reference