Metropolis-justerad Langevin-algoritm

Inom beräkningsstatistik är den Metropolis-justerade Langevin-algoritmen (MALA) eller Langevin Monte Carlo (LMC) en Markov-kedja Monte Carlo (MCMC) metod för att erhålla slumpmässiga prov – sekvenser av slumpmässiga observationer – från en sannolikhetsfördelning för vilken direkt urval är svårt . Som namnet antyder använder MALA en kombination av två mekanismer för att generera tillstånden för en slumpmässig promenad som har målsannolikhetsfördelningen som ett invariant mått :

• nya tillstånd föreslås med användning av ( överdämpad ) Langevin - dynamik , som använder utvärderingar av gradienten för målsannolikhetstäthetsfunktionen ;
• dessa förslag accepteras eller avvisas med Metropolis–Hastings-algoritmen , som använder utvärderingar av målsannolikhetstätheten (men inte dess gradient).

Informellt driver Langevin-dynamiken den slumpmässiga vandringen mot regioner med hög sannolikhet på samma sätt som ett gradientflöde, medan Metropolis–Hastings accept/reject-mekanism förbättrar blandnings- och konvergensegenskaperna för denna slumpmässiga promenad. MALA föreslogs ursprungligen av Julian Besag 1994, (även om metoden Smart Monte Carlo introducerades redan 1978) och dess egenskaper undersöktes i detalj av Gareth Roberts tillsammans med Richard Tweedie och Jeff Rosenthal . Många variationer och finesser har introducerats sedan dess, t.ex. den mångfaldiga varianten av Girolami och Calderhead (2011). Metoden är likvärdig med att använda Hamiltonian Monte Carlo (hybrid Monte Carlo) algoritm med endast ett enda diskret tidssteg.

Ytterligare detaljer

Låt $\pi$ beteckna en sannolikhetstäthetsfunktion på ${\displaystyle \mathbb {R} ^{d}} ,$ en från vilken man önskar dra en ensemble av oberoende och identiskt fördelade sampel. Vi betraktar den överdämpade Langevin Itô-diffusionen

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

drivs av tidsderivatan av en standard Brownsk rörelse $W$ . (Observera att en annan vanlig normalisering för denna diffusion är

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

som genererar samma dynamik.) I gränsen som $t\to \infty$ , denna sannolikhetsfördelning $\rho (t)$ av $X( t)$ närmar sig en stationär fördelning, som också är invariant under diffusionen, vilket vi betecknar $\rho _{\infty }$ . Det visar sig att $\rho _{\infty }=\pi$ faktiskt .

Ungefärliga provvägar för Langevin-diffusionen kan genereras med många diskreta tidsmetoder. En av de enklaste är Euler–Maruyama-metoden med ett fast tidssteg $\tau >0$ . Vi sätter $X_{0}:=x_{0}$ och definierar sedan rekursivt en approximation $X_{k}$ till den sanna lösningen $X( k\tau )$ av

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

där varje $\xi _{k}$ är ett oberoende drag från en multivariat normalfördelning på $\mathbb {R} ^{d}$ med medelvärde 0 och kovariansmatris lika med $d\times d$ identitetsmatris . Observera att $X_{k+1}$ är normalfördelade med medelvärde $X_{k}+\tau \nabla \log \pi ( X_{k})$ och kovarians lika med $2\tau$ gånger $d\times d$ identitetsmatrisen.

I motsats till Euler–Maruyama-metoden för att simulera Langevin-diffusionen, som alltid uppdaterar $X_{k}$ enligt uppdateringsregeln

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

MALA innehåller ett extra steg. Vi anser att ovanstående uppdateringsregel definierar ett förslag ${\tilde {X}}_{k+1}$ för ett nytt tillstånd,

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

Detta förslag accepteras eller förkastas enligt Metropolis-Hastings-algoritmen: set

$\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\},$

var

$q(x'\mid x)\leftto \exp (-{\frac {1}{4\tau }}\|x'-x-\tau \nabla \log \pi (x)\|_{2}^{2}\right)$

är övergångssannolikhetstätheten från $x$ till $x'$ (observera att i allmänhet $q(x'\ mitten x)\neq q(x\mitten x')$ ). Låt $u$ dras från den kontinuerliga enhetliga fördelningen på intervallet $[0,1]$ . Om $u\leq \alpha$ så accepteras förslaget och vi sätter $X_{k+1}:={\tilde {X }}_{k+1}$ ; annars avvisas förslaget och vi sätter $X_{k+1}:=X_{k}$ .

Den kombinerade dynamiken hos Langevin-diffusionen och Metropolis–Hastings-algoritmen uppfyller de detaljerade balansvillkoren som är nödvändiga för existensen av en unik, invariant, stationär fördelning $\rho _{\infty }=\pi$ . Jämfört med naiva Metropolis–Hastings har MALA fördelen att den vanligtvis föreslår flytt till regioner med högre ${\displaystyle \pi },$ som då är mer benägna att accepteras. Å andra sidan, när $\pi$ är starkt anisotropisk (dvs. den varierar mycket snabbare i vissa riktningar än andra), är det nödvändigt att ta $0<\tau \ll 1$ för att korrekt fånga Langevin-dynamiken; användandet av en positiv-definitiv förkonditioneringsmatris $A\in \mathbb {R} ^{d\times d}$ kan bidra till att lindra detta problem, genom att generera förslag enl.

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

så att ${\tilde {X}}_{k+1}$ har medelvärdet $X_{k}+\tau A \nabla \log \pi (X_{k})$ och kovarians $2\tau A$ .

För begränsade klasser av målfördelningar kan den optimala acceptansgraden för denna algoritm visas vara $0,574$ ; om det upptäcks vara väsentligt annorlunda i praktiken, $\tau$ modifieras i enlighet med detta.