Search
Duplicate

AI/ Metropolis-Hastings Algorithm

Metropolis-Hastings Algorithm

Metropolis-Hastings(MH) 알고리즘은 복잡한 확률 분포에서 샘플을 추출하는 가장 단순한 MCMC 알고리즘이다. 이것은 target 분포에서 직접 샘플링 하기가 어려울 때, 샘플링하고자 하는 분포를 근사하는 Markov Chain을 구성하고 이 체인을 통해 분포의 샘플을 생성한다.
MH는 각 단계에서 현재 상태 x\bold{x}에서 새로운 상태 x′\bold{x}'로 q(x′∣x)q(\bold{x}'|\bold{x})의 확률로 움직이는 것을 제안한다. 여기서 qq는 proposal 분포(또는 kernel이라고도 함)라 하고 일반적으로 가우시안 같은 간단한 분포를 사용한다.
x′\bold{x}'로 이동을 제안 받으면 각 상태에서 소모된 시간의 장기 비율이 목표 분포 p∗(x)p^*(\bold{x})에 비례 하도록 보장하는 어떤 공식에 따라 이 제안을 수락할지 거절할지 결정한다. 제안이 수락되면 새로운 상태는 x′\bold{x}'이고 그렇지 않으면 현재 상태 x\bold{x}에서 샘플링을 반복한다.
제안이 대칭 q(x′∣x)=q(x∣x′)q(\bold{x}'|\bold{x}) = q(\bold{x}|\bold{x}')인 경우, 수락 확률은 다음 공식에 의해 주어진다.
A=min⁡(1,p∗(x′)p∗(x))A = \min\left(1, {p^*(\bold{x}') \over p^*(\bold{x})} \right)
x′\bold{x}'이 x\bold{x}보다 더 가능성이 높으면 p∗(x′)p∗(x)>1{p^*(\bold{x}') \over p^*(\bold{x})} > 1이므로 분명히 거기로 이동한다. 그러나 x′\bold{x}'가 가능성이 낮더라도 상대적인 확률에 의존하여 어쨌든 그곳으로 이동할 수 있다. 따라서 가능성이 더 높은 상태로만 탐욕적으로 이동하는 대신 가끔 가능성이 낮은 상태로 ‘내리막(downhill)’ 이동을 허용한다.
제안이 비대칭 q(x′∣x)≠q(x∣x′)q(\bold{x}'|\bold{x}) \ne q(\bold{x}|\bold{x}')인 경우, 수락 확률은 다음과 같이 주어진다. 이것을 Hastings correction이라 한다.
A=min⁡(1,α)α=p∗(x′)q(x∣x′)p∗(x)q(x′∣x)=p∗(x′)/q(x′∣x)p∗(x)/q(x∣x′)\begin{aligned} A &= \min(1,\alpha) \\ \alpha &= {p^*(\bold{x}')q(\bold{x}|\bold{x}') \over p^*(\bold{x})q(\bold{x}'|\bold{x})}={p^*(\bold{x}')/q(\bold{x}'|\bold{x}) \over p^*(\bold{x}) / q(\bold{x}|\bold{x}')} \end{aligned}
MH가 유용한 이유는 타겟 분포의 정규화 상수를 모르더라도 샘플링이 가능하기 때문이다. 예컨대 타겟 분포를 unnormalized p~(x)\tilde{p}(\bold{x})와 정규화 상수 ZZ를 이용하여 p∗(x)=1Zp~(x)p^*(\bold{x}) = {1\over Z}\tilde{p}(\bold{x})라 하면 위의 식을 다음처럼 작성할 수 있다.
α=(p~(x′)/Z)q(x∣x′)(p~(x)/Z)q(x′∣x)\alpha = {(\tilde{p}(\bold{x}') /Z)q(\bold{x}|\bold{x}') \over (\tilde{p}(\bold{x})/Z) q(\bold{x}'|\bold{x})}
여기서 분모와 분자의 정규화 상수 ZZ는 상쇄되므로 ZZ를 모르더라도 p∗p^*에서 샘플링 할 수 있다.
제안 분포 qq가 타겟의 지지(support)를 커버하면 유효하거나 인정된다. 형식적으로 이것을 다음처럼 작성할 수 있다.
supp(p∗)⊆∪xsupp(q(⋅∣x))\text{supp}(p^*) \sube \cup_x \text{supp}(q(\cdot|x))

참고

Made with