5-3. MCMC(Estimation of Posterior - Markov Chain Monte Carlo) - 메트로폴리스-헤스팅스 알고리즘(Metropolis-Hastings Algorithm)

이번 글에서는 사후 분포를 계산할 수 없는 경우 이를 계산할 수 있는 방법인 MCMC(Markov Chain Monte Carlo) 방법 중 깁스 샘플러보다 더 일반적인 경우 사용되는 메트로폴리스-헤스팅스 알고리즘(Metropolis-Hastings Algorithm)에 대해 알아보겠습니다.

[관련 글] [Stochastic Process] 1. 확률 과정(Stochastic Process),[Stochastic Process] 2. 마르코프 체인(Markov Chain)

---

메트로폴리스-헤스팅스 알고리즘(Matropolis-Hastings Algorithm)

난수를 발생하고자 하는 목표 확률분포가 $f(y) \propto \pi(y)$ 혹은 $f(y) = c\pi(y)$와 같이 주어지고, 이때 정규화 상수 $c(=\frac {1}{\int {\pi(y)}dy})$를 모르는(계산할 수 없는) 경우, $f(y)$로부터 난수를 발생시키는 방법을 메트로폴리스-헤스팅스 알고리즘이라고 합니다. 메트로폴리스-헤스팅스 알고리즘을 구현하기 위해선 샘플링의 후보를 생성하는 확률 밀도 함수 (candidate-generating density function)  $q(y|x)$를 가정해야 합니다. 알고리즘은 다음과 같습니다.

 

1. 관심 있는 확률분포($Y$)의 초깃값 $Y_0$을 정합니다.

2. 앞서 가정한 후보 생성 확률 밀도 함수를 이용하여 후보$Y_{0}^{*}=q(y|Y_{0})$를 생성합니다.

3. 이동 확률 $\alpha$를 다음 식에 의해 계산합니다.

$\alpha=min \left [\frac {\pi(Y_0^*)/q(Y_0^*|Y_{0})}{\pi(Y_{0})/q(Y_{0}|Y_0^*)},~1 \right]$

4. $\textrm {uniform}(0,~1)$로부터 난수 $u$를 생성합니다.

5. 만약 $u \leq \alpha$이면 $Y_1=Y^*$과 같이 정하고, $u \geq \alpha$이면 $Y_1=Y_0$과 같이 정합니다.

6. 2.로 돌아가 과정을 반복합니다.

---

위의 과정을 반복하여 생성된 표본들은 그 전 샘플에서만 영향을 받기 때문에, $Y_0, Y_1,\cdots$는 $f(y)$를 극한 분포로 가지는 마르코프 연쇄가 됩니다.

또한 메트로폴리스-헤스팅스 알고리즘은 관심 있는 확률 밀도 함수 $f(y)$의 정규화 상수 $c$를 반드시 알아야 할 필요가 없기 때문에 아무리 $f(y)$가 복잡할지라도 적당한 후보 생성 확률 밀도 함수를 선택하면 $f(y)$를 따르는 난수를 샘플링할 수 있습니다.

---

메트로폴리스-헤스팅스 알고리즘에서 중요한 점은 후보 생성 확률 밀도 함수 $q(y|x)$ 를 가정하는 일입니다.

$q(y|x)$에 대한 가장 일반적인 선택은 $q(y|x)=q_1(|y-x|)$로 주어지는 확률 보행(random walk)입니다. 이때 후보 난수 $y$는 $y=x+z$의 형태(후보=현재 상태+잡음)로 생성됩니다.

예를 들어서 $z \sim \epsilon * N(0,~1)$인 경우, 후보 생성 함수는 현재 상태의 값 $x$를 중심으로 분산 $\epsilon^2$을 가지는 정규분포에서 후보 난수를 발생시키게 됩니다.