Hamiltonské Monte Carlo - Hamiltonian Monte Carlo - Wikipedia

v výpočetní fyzika a statistika, Hamiltonské Monte Carlo algoritmus (také známý jako hybridní Monte Carlo), je Markovský řetězec Monte Carlo metoda pro získání posloupnosti náhodné vzorky který konvergovat být distribuováno podle cílového rozdělení pravděpodobnosti, pro které je obtížné přímé vzorkování. Tuto posloupnost lze použít k odhadu integrály s ohledem na cílovou distribuci (očekávané hodnoty ).

Hamiltonovské Monte Carlo odpovídá instanci Algoritmus Metropolis – Hastings, s Hamiltonova dynamika evoluce simulovaná pomocí a časově reverzibilní a numerický integrátor šetřící objem (obvykle integrátor leapfrog ) navrhnout přesun do nového bodu ve stavovém prostoru. Ve srovnání s použitím a Gaussova náhodná procházka distribuce návrhů v Algoritmus Metropolis – Hastings „Hamiltonovské Monte Carlo snižuje korelaci mezi po sobě následujícími vzorkovanými státy tím, že navrhuje pohyby do vzdálených států, které udržují vysokou pravděpodobnost přijetí kvůli přibližné úspora energie vlastnosti simulované hamiltonovské dynamiky při použití a symplektický integrátor. Snížená korelace znamená méně Markovův řetězec vzorky jsou potřebné k aproximaci integrálů s ohledem na cílové rozdělení pravděpodobnosti pro daný Monte Carlo chyba. Algoritmus původně navrhli Simon Duane, Anthony Kennedy, Brian Pendleton a Duncan Roweth v roce 1987^[1] pro výpočty v mřížková kvantová chromodynamika.

Algoritmus

Předpokládejme, že cílová distribuce do vzorku je ${ displaystyle f ( mathbf {x})}$ a řetězec vzorků ${ displaystyle mathbf {X} _ {0}, mathbf {X} _ {1}, mathbf {X} _ {2}, ldots}$ je požadováno. The Hamiltonovy rovnice jsou

${ displaystyle { frac {{ text {d}} x_ {i}} {{ text {d}} t}} = { frac { částečné H} { částečné p_ {i}}}}$

a

${ displaystyle { dfrac {{ text {d}} p_ {i}} {{ text {d}} t}} = - { dfrac { částečné H} { částečné x_ {i}}}}$

kde ${ displaystyle x_ {i}}$ a ${ displaystyle p_ {i}}$ jsou ${ displaystyle i}$tá složka pozice a hybnost vektor, resp ${ displaystyle H}$ je Hamiltonian. Nechat ${ displaystyle M}$ být hmotnostní matice který je symetrický a kladně určitý, pak je hamiltonián

${ displaystyle H ( mathbf {x}, mathbf {p}) = U ( mathbf {x}) + { dfrac {1} {2}} mathbf {p} ^ { text {T}} M ^ {- 1} mathbf {p}}$

kde ${ displaystyle U ( mathbf {x})}$ je potenciální energie. Potenciální energie pro cíl je uvedena jako

${ displaystyle U ( mathbf {x}) = - ln f ( mathbf {x})}$

který pochází z Boltzmannův faktor.

Algoritmus vyžaduje kladné celé číslo pro počet skokových kroků žáby ${ displaystyle L}$ a kladné číslo pro velikost kroku ${ displaystyle Delta t}$. Předpokládejme, že řetěz je na ${ displaystyle mathbf {X} _ {n} = mathbf {x} _ {n}}$. Nechat ${ displaystyle mathbf {x} _ {n} (0) = mathbf {x} _ {n}}$. Nejprve, a náhodný Gaussian hybnost ${ displaystyle mathbf {p} _ {n} (0)}$ je čerpáno z ${ displaystyle { text {N}} vlevo ( mathbf {0}, M vpravo)}$. Dále bude částice po určitou dobu běžet pod hamiltonovskou dynamikou ${ displaystyle L Delta t}$, to se děje numerickým řešením Hamiltonových rovnic pomocí algoritmus skokové žáby. Vektory polohy a hybnosti po čase ${ displaystyle Delta t}$ pomocí algoritmu skokové žáby jsou

${ displaystyle mathbf {p} _ {n} left (t + { dfrac { Delta t} {2}} right) = mathbf {p} _ {n} (t) - { dfrac { Delta t} {2}} nabla left.U ( mathbf {x}) right | _ { mathbf {x} = mathbf {x} _ {n} (t)}}$

${ displaystyle mathbf {x} _ {n} (t + Delta t) = mathbf {x} _ {n} (t) + Delta tM ^ {- 1} mathbf {p} _ {n} vlevo (t + { dfrac { Delta t} {2}} vpravo)}$

${ displaystyle mathbf {p} _ {n} (t + Delta t) = mathbf {p} _ {n} vlevo (t + { dfrac { Delta t} {2}} vpravo) - { dfrac { Delta t} {2}} nabla left.U ( mathbf {x}) right | _ { mathbf {x} = mathbf {x} _ {n} (t + Delta t)} }$

Na tyto rovnice se má vztahovat ${ displaystyle mathbf {x} _ {n} (0)}$ a ${ displaystyle mathbf {p} _ {n} (0)}$ ${ displaystyle L}$ krát získat ${ displaystyle mathbf {x} _ {n} (L Delta t)}$ a ${ displaystyle mathbf {p} _ {n} (L Delta t)}$.

Protože algoritmus skokové žáby je numerická metoda a neřeší přesně Hamiltonovy rovnice, a Metropolis – Hastings krok je použit. Přechod od ${ displaystyle mathbf {X} _ {n} = mathbf {x} _ {n}}$ na ${ displaystyle mathbf {X} _ {n + 1}}$ je

${ displaystyle mathbf {X} _ {n + 1} | mathbf {X} _ {n} = mathbf {x} _ {n} = { begin {cases} mathbf {x} _ {n} (L Delta t) & { text {s pravděpodobností}} alpha left ( mathbf {x} _ {n} (0), mathbf {x} _ {n} (L Delta t) vpravo ) mathbf {x} _ {n} (0) & { text {jinak}} end {případů}}}$

kde

${ displaystyle alpha left ( mathbf {x} _ {n} (0) _ {n}, mathbf {x} _ {n} (L Delta t) right) = { text {min} } left (1, { dfrac { exp left [-H ( mathbf {x} _ {n} (L Delta t), mathbf {p} _ {n} (L Delta t)) right]} { exp left [-H ( mathbf {x} _ {n} (0), mathbf {p} _ {n} (0)) right)}} right)}$

Pro získání se to opakuje ${ displaystyle mathbf {X} _ {n + 1}, mathbf {X} _ {n + 2}, mathbf {X} _ {n + 3}, ldots}$.

Žádný vzorkovač otáček

Vzorkovač bez otáčení (NUTS)^[2] je rozšíření ovládáním ${ displaystyle L}$ automaticky. Ladění ${ displaystyle L}$ je kritická. Například v jednorozměrném ${ displaystyle { text {N}} (0,1 / { sqrt {k}})}$ v takovém případě je potenciál ${ displaystyle U (x) = kx ^ {2} / 2}$ což odpovídá potenciálu a jednoduchý harmonický oscilátor. Pro ${ displaystyle L}$ příliš velká, částice bude oscilovat a tato ztráta výpočetního času. Pro ${ displaystyle L}$ příliš malá, částice se bude chovat jako náhodná chůze.

Volně NUTS náhodně spouští hamiltoniánskou dynamiku dopředu i dozadu v čase, dokud není splněna podmínka obratu. Když k tomu dojde, je pro vzorek MCMC vybrán náhodný bod z cesty a proces se opakuje od tohoto nového bodu.

Podrobně, a binární strom je konstruován tak, aby sledoval cestu kroků skokové žáby. K vytvoření vzorku MCMC se provede iterační postup. Proměnná řezu ${ displaystyle U_ {n} sim { text {Uniform}} (0, exp (-H [ mathbf {x} _ {n} (0), mathbf {p} _ {n} (0) ]))}$ je vzorkováno. Nechat ${ displaystyle mathbf {x} _ {n} ^ {+}}$ a ${ displaystyle mathbf {p} _ {n} ^ {+}}$ být poloha a hybnost přední částice. Podobně, ${ displaystyle mathbf {x} _ {n} ^ {-}}$ a ${ displaystyle mathbf {p} _ {n} ^ {-}}$ pro zpětnou částici. V každé iteraci binární strom náhodně vybere rovnoměrně pro posun vpřed částice dopředu v čase nebo zpětné částice zpět v čase. Také pro každou iteraci se počet kroků skokové žáby zvýší o faktor 2. Například v první iteraci se přední částice pohybuje v čase vpřed pomocí 1 kroku skokové žáby. V další iteraci se zpětná částice pohybuje zpět v čase pomocí 2 skokových žabích kroků.

Iterativní postup pokračuje, dokud není splněna podmínka U-Turn

${ displaystyle ( mathbf {x} _ {n} ^ {+} - mathbf {x} _ {n} ^ {-}) cdot mathbf {p} _ {n} ^ {-} <0 quad { text {or}} quad ( mathbf {x} _ {n} ^ {+} - mathbf {x} _ {n} ^ {-}) cdot mathbf {p} _ {n} ^ {+} <0}$

nebo když se Hamiltonian stane nepřesným

${ displaystyle exp left [-H ( mathbf {x} _ {n} ^ {+}, mathbf {p} _ {n} ^ {+}) + delta right]$

nebo

${ displaystyle exp left [-H ( mathbf {x} _ {n} ^ {-}, mathbf {p} _ {n} ^ {-}) + delta right]$

kde například ${ displaystyle delta = 1000}$.

Jakmile je splněna podmínka obratu, další vzorek MCMC, ${ displaystyle mathbf {x} _ {n + 1}}$, je získáno rovnoměrným vzorkováním cesty skokové žáby sledované binárním stromem ${ displaystyle { mathbf {x} _ {n} ^ {-}, ldots, mathbf {x} _ {n} (- Delta t), mathbf {x} _ {n} (0) , mathbf {x} _ {n} ( Delta t), ldots, mathbf {x} _ {n} ^ {+} }}$ který uspokojuje

${ displaystyle U_ {n} < exp left [-H ( mathbf {x_ {n + 1}}, mathbf {p_ {n + 1})} right]}$

To je obvykle uspokojeno, pokud jsou zbývající parametry HMC rozumné.

Viz také

• Dynamická metoda Monte Carlo
• Software pro molekulární modelování v Monte Carlu
• Stan

Reference

Další čtení

• Neal, Radford M (2011). „MCMC s využitím Hamiltonian Dynamics“ (PDF). V Steve Brooks; Andrew Gelman; Galin L. Jones; Xiao-Li Meng (eds.). Příručka Markovského řetězce Monte Carlo. Chapman and Hall / CRC. ISBN  9781420079418.
• Betancourt, Michael (2018). „Koncepční úvod do Hamiltonovského Monte Carla“. arXiv:1701.02434. Bibcode:2017arXiv170102434B. Citovat deník vyžaduje | deník = (Pomoc)
• Liu, Jun S. (2004). Strategie Monte Carlo ve vědecké práci na počítači. Springerova řada ve statistice, Springer. 189-203. ISBN  978-0-387-76369-9.

externí odkazy

• Betancourt, Michaele. „Efektivní Bayesiánský závěr s Hamiltonian Monte Carlo“. MLSS Island 2014 - přes Youtube.
• Hamiltonian Monte Carlo od nuly
• Optimalizace a metody Monte Carlo