Search
Duplicate

AI/ Langevin Dynamics, Langevin Monte Carlo(LMC)

Langevin Dynamics

Langevin Dynamics는 물리학의 브라운 운동(Brownian motion) 모델에 기초하며, 입장의 운동이 결정론적인 힘과 무작위적인 힘의 합으로 기술된다. 이것은 다음과 같은 연속 시간 확률 미분 방정식으로 표현된다.
dx=f(x)dt+g(x)dWdx = f(x)dt + g(x)dW
여기서 dxdx는 위치의 변화, f(x)f(x)는 입자에 작용하는 결정론적 힘(예: 기울기), g(x)g(x)는 무작위성의 강도, dWdW는 와이너 과정(표준 브라운 운동)을 나타낸다.
머신러닝 분야에서 Langevin Dynamics는 에너지 함수 E(x)\mathcal{E}(x)를 최소화하는 상태를 찾기 위해 사용된다. 여기서 Langevin Dynamics를 사용하여 샘플들이 낮은 에너지 상태로 수렴하도록 유도할 수 있다. 이것은 다음과 같은 Langevin Dynamics 방정식으로 모델링할 수 있다. 아래 식에서 ϵ\epsilon은 학습률 또는 시간 간격의 크기를 나타낸다.
θt+1=θt−ϵ∇θE(θt)+2ϵN(0,I)\boldsymbol{\theta}_{t+1} = \boldsymbol{\theta}_t - \epsilon \nabla_{\boldsymbol{\theta}} \mathcal{E}(\boldsymbol{\theta}_t) + \sqrt{2\epsilon} \mathcal{N}(\bold{0}, \bold{I})
참고로 연속 시간인 경우에는 기존 값을 업데이트하는 방식이 아니라 다음과 같이 직접 계산할 수 있다. 그러나 컴퓨터에서는 각 시간 단계별로 계산해야 하기 때문에 일반적으로 이산 방법을 이용하여 근사 모델을 사용한다.
dθt=−∇E(θt)dt+2dWtd\boldsymbol{\theta}_{t} = -\nabla\mathcal{E}(\boldsymbol{\theta}_t)dt + \sqrt{2}d\bold{W}_t

Langevin Monte Carlo(LMC)

Hamiltonian Monte Carlo(HMC)에 대해 L=1L=1 leapfrog step을 취하는 경우를 Langevin Monte Carlo 또는 Metropolis Adjusted Langevin Algorithm(MALA)라 부른다. 아래 pseudo code 참조
Algorithm: Langevin Monte Carlo
1.
for t=1:Tt=1:T do
a.
랜덤 모멘텀 생성 vt−1∼N(0,Σ)\bold{v}_{t-1} \sim \mathcal{N}(\bold{0},\boldsymbol{\Sigma})
b.
θ∗=θt−1−η22Σ−1∇E(θt−1)+ηΣ−1vt−1\boldsymbol{\theta}^* = \boldsymbol{\theta}_{t-1}-{\eta^2 \over 2} \boldsymbol{\Sigma}^{-1}\nabla \mathcal{E}(\boldsymbol{\theta}_{t-1})+\eta\boldsymbol{\Sigma}^{-1}\bold{v}_{t-1}
c.
v∗=vt−1−η2∇E(θt−1)−η2∇E(θ∗)\bold{v}^* = \bold{v}_{t-1} - {\eta\over 2} \nabla\mathcal{E}(\boldsymbol{\theta}_{t-1})-{\eta \over 2} \nabla \mathcal{E}(\boldsymbol{\theta}^*)
d.
α=min⁡(1,exp⁡[−H(θ∗,v∗)]/exp⁡[−H(θt−1,vt−1)])\alpha = \min(1,\exp[-\mathcal{H}(\boldsymbol{\theta}^*,\bold{v}^*)]/\exp[-\mathcal{H}(\boldsymbol{\theta}_{t-1},\bold{v}_{t-1})]) 계산
e.
확률 α\alpha로 θt=θ∗\boldsymbol{\theta}_t = \boldsymbol{\theta}^*을 설정 그렇지 않으면 θt=θt−1\boldsymbol{\theta}_t = \boldsymbol{\theta}_{t-1}
MH의 수락 단계를 제거하면 더 단순화 할 수 있다. 이 경우 업데이트는 다음이 된다. 여기서 vt−1∼N(0,Σ)\bold{v}_{t-1} \sim \mathcal{N}(\bold{0},\boldsymbol{\Sigma})이고 ϵt−1∼N(0,I)\boldsymbol{\epsilon}_{t-1} \sim \mathcal{N}(\bold{0},\bold{I})
θt=θt−1−η22Σ−1∇E(θt−1)+ηΣ−1vt−1=θt−1−η22Σ−1∇E(θt−1)+ηΣ−1ϵt−1\begin{aligned} \boldsymbol{\theta}_t &= \boldsymbol{\theta}_{t-1}-{\eta^2\over2}\boldsymbol{\Sigma}^{-1}\nabla\mathcal{E}(\boldsymbol{\theta}_{t-1})+\eta \boldsymbol{\Sigma}^{-1}\bold{v}_{t-1} \\ &= \boldsymbol{\theta}_{t-1}-{\eta^2\over2}\boldsymbol{\Sigma}^{-1}\nabla\mathcal{E}(\boldsymbol{\theta}_{t-1})+\eta\sqrt{\boldsymbol{\Sigma}^{-1}}\boldsymbol{\epsilon}_{t-1} \end{aligned}
이 업데이트에 대해 stochastic gradient를 사용하면 Stochastic Gradient Langevin Descent(SGLD)라는 방법이 된다.

참고

Made with