Stokastisk gradient Langevin-dynamik

SGLD kan tillämpas på optimering av icke-konvexa objektivfunktioner, som här visas som summan av Gausser.

Stokastisk gradient Langevin-dynamik ( SGLD ) är en optimerings- och samplingsteknik som består av egenskaper från Stokastisk gradientnedstigning , en Robbins-Monro- optimeringsalgoritm och Langevin-dynamik , en matematisk förlängning av molekylära dynamikmodeller . Liksom stokastisk gradientnedstigning är SGLD en iterativ optimeringsalgoritm som använder minibatching för att skapa en stokastisk gradientestimator, som används i SGD för att optimera en differentierbar objektivfunktion . Till skillnad från traditionell SGD kan SGLD användas för Bayesian inlärning som en provtagningsmetod. SGLD kan ses som Langevin-dynamik som tillämpas på posteriora distributioner, men den viktigaste skillnaden är att sannolikhetsgradienttermerna är minibatchade, som i SGD. SGLD, liksom Langevin-dynamik, producerar prover från en posterior fördelning av parametrar baserat på tillgängliga data. Metoden beskrevs först av Welling och Teh 2011, och den har tillämpningar i många sammanhang som kräver optimering, och den tillämpas framför allt i problem med maskininlärning.

Formell definition

Givet någon parametervektor $\theta$ , dess tidigare fördelning $p(\theta )$ , och en uppsättning datapunkter $X= \{x_{i}\}_{i=1}^{N}$ , Langevin dynamikprov från den bakre fördelningen ${\displaystyle p(\theta \mid X)\propto p(\theta )\prod _{i=1}^{N}p(x_{i}\mid \theta )} genom att uppdatera kedjan$ :

$\Delta \theta _{t}= {\frac {\varepsilon _{t}}{2}}\left(\nabla \log p(\theta _{t})+\summa _{i=1}^{N}\nabla \log p( x_{t_{i}}\mid \theta _{t})\right)+\eta _{t}$

Stokastisk gradient Langevin dynamics använder en modifierad uppdateringsprocedur med minibatchade sannolikhetstermer:

$\Delta \theta _{ }={\frac {\varepsilon _{t}}{2}}\left(\nabla \log p(\theta _{t})+{\frac {N}{n}}\summa _{i= 1}^{n}\nabla \log p(x_{t_{i}}\mid \theta _{t})\right)+\eta _{t}$

där $n<N$ är ett positivt heltal, $\eta _{t}\sim {\mathcal {N}}(0,\varepsilon _{ t})$ är Gaussiskt brus, $p(x\mid \theta )$ är sannolikheten för data givet parametervektorn $\theta$ , och våra stegstorlekar $\varepsilon _{t}$ uppfyller följande villkor:

$\sum _{t=1}^{\infty }\varepsilon _{t}=\infty \quad \sum _{ t=1}^{\infty }\varepsilon _{t}^{2}<\infty$

För tidiga iterationer av algoritmen härmar varje parameteruppdatering Stokastisk Gradient Descent; men när algoritmen närmar sig ett lokalt minimum eller maximum, krymper gradienten till noll och kedjan producerar sampel som omger det maximala a posteriori-modet som tillåter bakre slutledning. Denna process genererar ungefärliga prover från baksidan som genom att balansera variansen från det injicerade Gaussiska bruset och stokastisk gradientberäkning.

Ansökan

SGLD är tillämpbart i alla optimeringssammanhang för vilka det är önskvärt att snabbt erhålla posteriora prover istället för ett maximalt a posteriori-läge. Genom att göra så upprätthåller metoden beräkningseffektiviteten för stokastisk gradientnedstigning jämfört med traditionell gradientnedstigning samtidigt som den tillhandahåller ytterligare information om landskapet runt den kritiska punkten för målfunktionen. I praktiken kan SGLD appliceras på träning av Bayesian Neural Networks in Deep Learning , en uppgift där metoden ger en fördelning över modellparametrar. Genom att introducera information om variansen av dessa parametrar, karakteriserar SGLD dessa modellers generaliserbarhet vid vissa punkter under träningen. Dessutom tillåter erhållande av prover från en bakre fördelning osäkerhetskvantifiering med hjälp av konfidensintervall, en egenskap som inte är möjlig med traditionell stokastisk gradientnedstigning.

Varianter och tillhörande algoritmer

Om gradientberäkningar är exakta, reducerar SGLD ner till Langevin Monte Carlo- algoritmen, som först myntades i litteraturen om gitterfältteori . Denna algoritm är också en minskning av Hamiltonian Monte Carlo , som består av ett enstaka stegförslag snarare än en serie steg. Eftersom SGLD kan formuleras som en modifiering av både stokastisk gradientnedstigning och MCMC-metoder, ligger metoden i skärningspunkten mellan optimerings- och samplingsalgoritmer; Metoden upprätthåller SGD:s förmåga att snabbt konvergera till regioner med låg kostnad samtidigt som prover tillhandahålls för att underlätta bakre slutledning.

Med tanke på avslappnade begränsningar för stegstorlekarna $\varepsilon _{t}$ så att de inte närmar sig noll asymptotiskt, misslyckas SGLD med att producera prover för vilka Metropolis Hastings avvisningsfrekvens är noll, och därför blir ett MH-avvisningssteg nödvändig. Den resulterande algoritmen, kallad Metropolis Adjusted Langevin-algoritmen, kräver steget:

${\frac {p(\mathbf {\theta } ^{t}\mid \mathbf {\theta} ^{t+1})p^{*}\left(\mathbf {\theta} ^{t}\right)} {p\left(\mathbf {\theta} ^{t+1}\mid \mathbf {\theta} ^{t}\right)p^{*}(\mathbf {\theta} ^{t+1} )}}<u,\ u\sim {\mathcal {U}}[0,1]$

där $p(\theta ^{t}\mid \theta ^{t+1})$ är en normalfördelning centrerad ett gradientnedstigningssteg från $\ theta ^{t}$ och $p(\theta )$ är vår målfördelning.

Blandningshastigheter och algoritmisk konvergens

Nya bidrag har bevisat övre gränser för blandningstider för både den traditionella Langevin-algoritmen och den Metropolis-justerade Langevin-algoritmen. Utgivna i Ma et al., 2018, definierar dessa gränser den hastighet med vilken algoritmerna konvergerar till den sanna bakre fördelningen, formellt definierad som:

$\tau (\varepsilon ;p^{0})=\min \left\{k\mid \left\ |p^{k}-p^{*}\right\|_{\mathrm {V} }\leq \varepsilon \right\}$

där $\varepsilon \in (0,1)$ är en godtycklig feltolerans, $p^{0}$ är en initial fördelning, $p^{* }$ är den bakre fördelningen, och $||*||_{TV}$ är den totala variationsnormen . Under vissa regularitetsförhållanden för en L-Lipschitz slät objektiv funktion $U(x)$ som är m-starkt konvex utanför ett område med radie $R$ med villkorsnummer ${ \displaystyle \kappa ={\frac {L}{m}}}$ , vi har blandningshastighetsgränser:

$\tau _{ULA}(\varepsilon ,p^{0})\ leq {\mathcal {O}}\left(e^{32LR^{2}}\kappa ^{2}{\frac {d}{\varepsilon ^{2}}}\ln \left({\frac { d}{\varepsilon ^{2}}}\right)\right)$

$\tau _{MALA}(\varepsilon ,p^{0})\leq {\mathcal {O}}\left(e^{16LR^{2} }\kappa ^{3/2}d^{1/2}\left(d\ln \kappa +\ln \left({\frac {1}{\varepsilon }}\right)\right)^{3 /2}\right)$

där $\tau _{ULA}$ och $\tau _{MALA}$ hänvisar till blandningshastigheterna för den ojusterade Langevin-algoritmen respektive den Metropolis-justerade Langevin-algoritmen. Dessa gränser är viktiga eftersom de visar att beräkningskomplexiteten är polynom i dimensionen $d$ villkorad av att $LR^{2}$ är ${\mathcal {O}} (\log d)$ .