Předem připravený algoritmus Crank – Nicolson - Preconditioned Crank–Nicolson algorithm

v výpočetní statistika, předem připravený Crank – Nicolsonův algoritmus (pCN) je Markovský řetězec Monte Carlo (MCMC) metoda získávání náhodné vzorky - sekvence náhodných pozorování - z cíle rozdělení pravděpodobnosti pro které je přímý odběr vzorků obtížný.

Nejvýznamnějším rysem algoritmu pCN je jeho rozměrová robustnost, díky čemuž je vhodný pro vysokodimenzionální problémy vzorkování. Algoritmus pCN je dobře definovaný, s nedegenerovanou pravděpodobností přijetí, dokonce i pro cílové distribuce na nekonečně rozměrných Hilbertovy prostory. V důsledku toho, když je pCN implementován na počítači v reálném světě ve velké, ale konečné dimenzi N, tj. na N-dimenzionální podprostor původního Hilbertova prostoru, vlastnosti konvergence (např ergodicita ) algoritmu jsou nezávislé na N. To je v silném kontrastu se schématy, jako je Gaussova náhodná procházka Metropolis – Hastings a Langevinův algoritmus upravený podle metropole, jehož pravděpodobnost přijetí degeneruje na nulu jako N inklinuje k nekonečnu.

Algoritmus zavedl v roce 2013 Cotter, Roberts, Stuart a bílá,^[1] a jeho vlastnosti ergodicity byly prokázány o rok později Kadeřnice, Stuart a Vollmer.^[2]

Popis algoritmu

Přehled

Algoritmus pCN generuje Markovův řetězec ${ displaystyle (X_ {n}) _ {n in mathbb {N}}}$ v Hilbertově prostoru ${ displaystyle { mathcal {H}}}$ jehož invariantní míra je míra pravděpodobnosti ${ displaystyle mu}$ formuláře

{ displaystyle mu (E) = { frac {1} {Z}} int _ {E} exp (- Phi (x)) , mu _ {0} ( mathrm {d} x )}

pro každého měřitelná množina ${ displaystyle E subseteq { mathcal {H}}}$ , s normalizační konstantou ${ displaystyle Z}$ dána

{ displaystyle Z = int _ { mathcal {H}} exp (- Phi (x)) , mu _ {0} ( mathrm {d} x),}

kde ${ displaystyle mu _ {0} = { mathcal {N}} (0, C_ {0})}$ je Gaussova míra na ${ displaystyle { mathcal {H}}}$ s operátor kovariance ${ displaystyle C_ {0}}$ a ${ displaystyle Phi colon { mathcal {H}} do mathbb {R}}$ je nějaká funkce. Metoda pCN se tedy použila na míra pravděpodobnosti cíle, která je změnou váhy referenční Gaussovy míry.

The Algoritmus Metropolis – Hastings je obecná třída metod, které se snaží vyrobit takové Markovovy řetězce ${ displaystyle (X_ {n}) _ {n in mathbb {N}}}$ , a to nejprve dvoustupňovým postupem navrhující nový stát ${ displaystyle X '_ {n + 1}}$ vzhledem k aktuálnímu stavu ${ displaystyle X_ {n}}$ a pak přijímání nebo odmítnutí tento návrh definuje další stav podle konkrétní pravděpodobnosti přijetí ${ displaystyle X_ {n + 1}}$ . Myšlenka algoritmu pCN spočívá v tom, že chytrý výběr (nesymetrického) návrhu nového stavu ${ displaystyle X '_ {n + 1}}$ daný ${ displaystyle X_ {n}}$ může mít přidruženou funkci pravděpodobnosti přijetí s velmi žádoucími vlastnostmi.

Návrh pCN

Zvláštní forma tohoto návrhu pCN má být

{ displaystyle X '_ {n + 1} = { sqrt {1- beta ^ {2}}} X_ {n} + beta Xi _ {n + 1},}

{ displaystyle Xi _ {n + 1} sim mu _ {0} { text {i.i.d.}}}

nebo ekvivalentně

{ displaystyle X '_ {n + 1} | X_ {n} sim { mathcal {N}} vlevo ({ sqrt {1- beta ^ {2}}} X_ {n}, beta C_ {0} vpravo).}

Parametr ${ displaystyle 0 < beta <1}$ je velikost kroku, kterou lze libovolně zvolit (a dokonce optimalizovat pro statistickou účinnost). Jeden pak generuje ${ displaystyle Z_ {n + 1} sim mathrm {Unif} ([0,1])}$ a sady

{ displaystyle X_ {n + 1} = X '_ {n + 1} { text {if}} Z_ {n + 1} leq alpha (X_ {n}, X' _ {n + 1}) ,}

{ displaystyle X_ {n + 1} = X_ {n} { text {if}} Z_ {n + 1}> alpha (X_ {n}, X '_ {n + 1}).}

Pravděpodobnost přijetí má jednoduchou formu

{ displaystyle alpha (x, x ') = min (1, exp ( phi (x) - phi (x')))}}

Může se to ukázat^[2] že tato metoda nejen definuje Markovův řetězec, který uspokojuje podrobný zůstatek s ohledem na cílovou distribuci ${ displaystyle mu}$ , a proto má ${ displaystyle mu}$ jako neměnná míra, ale také má spektrální mezeru, která je nezávislá na dimenzi ${ displaystyle { mathcal {H}}}$ , a tak zákon z ${ displaystyle X_ {n}}$ konverguje k ${ displaystyle mu}$ tak jako ${ displaystyle n to infty}$ . Tedy, i když je možné, že ještě bude nutné vyladit parametr velikosti kroku ${ displaystyle beta}$ pro dosažení požadované úrovně statistické účinnosti je výkon metody pCN robustní vzhledem k dimenzi uvažovaného problému vzorkování.

Kontrast se symetrickými návrhy

Toto chování pCN je v ostrém kontrastu s návrhem Gaussian random random walk

{ displaystyle X '_ {n + 1} mid X_ {n} sim { mathcal {N}} vlevo (X_ {n}, beta gama vpravo)}

s jakoukoli volbou kovariance nabídky ${ displaystyle Gamma}$ , nebo jakýkoli symetrický návrhový mechanismus. To lze zobrazit pomocí Cameron – Martinova věta že pro nekonečně-dimenzionální ${ displaystyle { mathcal {H}}}$ u tohoto návrhu je pravděpodobnost přijetí nulová ${ displaystyle mu}$ -téměř všechny ${ displaystyle X '_ {n + 1}}$ a ${ displaystyle X_ {n}}$ . V praxi, když člověk implementuje návrh Gaussova náhodného pochodu v dimenzi ${ displaystyle N}$ , tento jev lze vidět tak, že

pro pevné ${ displaystyle beta}$ , pravděpodobnost přijetí má tendenci k nule jako ${ displaystyle N až infty}$ , a
pro pevnou požadovanou pravděpodobnost kladného přijetí, ${ displaystyle beta až 0}$ tak jako ${ displaystyle N až infty}$ .

Reference

^ Cotter, S.L .; Roberts, G. O .; Stuart, A. M .; White, D. (2013). "Metody MCMC pro funkce: úprava starých algoritmů, aby byly rychlejší". Statist. Sci. 28 (3): 424–446. arXiv:1202.0709. doi:10.1214 / 13-STS421. ISSN 0883-4237.
^ ^A ^b Hairer, M .; Stuart, A. M .; Vollmer, S. J. (2014). „Spektrální mezery pro algoritmus Metropolis – Hastings v nekonečných rozměrech“. Ann. Appl. Probab. 24 (6): 2455–2490. arXiv:1112.1392. doi:10.1214 / 13-AAP982. ISSN 1050-5164.

[CRSW2013-1] Cotter, S.L .; Roberts, G. O .; Stuart, A. M .; White, D. (2013). "Metody MCMC pro funkce: úprava starých algoritmů, aby byly rychlejší". Statist. Sci. 28 (3): 424–446. arXiv:1202.0709. doi:10.1214 / 13-STS421. ISSN 0883-4237.

[HSV2014-2] A ^b Hairer, M .; Stuart, A. M .; Vollmer, S. J. (2014). „Spektrální mezery pro algoritmus Metropolis – Hastings v nekonečných rozměrech“. Ann. Appl. Probab. 24 (6): 2455–2490. arXiv:1112.1392. doi:10.1214 / 13-AAP982. ISSN 1050-5164.

[1]

[2]