Metropolis-Hastings(MH) Algorithm

해당 문서는 Coursera 강의 Bayesian Statistics: Techniques and Models
를 보고 공부한 것을 정리한 노트입니다.

---

1. Marcov Chain

우리는 이전 포스팅에서 몬테 카를로 방법을 보았다. 몬테 카를로 방식은 주어진 확률에서 랜덤하게 표본추출을 함으로써 모든 표본이 서로 독립이라는 것이 보장된다.

하지만 우리가 곧 다뤄볼 표본추출방법인 MCMC는, 일반 몬테 카를로 방식과 달리 현재 샘플이 다음 샘플의 추출에 영향을 주면서 모든 표본이 서로 독립이 아니게 된다. MCMC는 Marcov Chain Monte Carlo의 준말이므로 먼저 우리는 Marcov Chain을 이해해야 한다.

여기서는 Marcov Chain의 정의만 가볍게 다루고 넘어가겠다.

기본적으로 chain rule of probability로 인해 다음이 성립한다.

마르코프 체인은, 위의 식을 마르코프 가정을 통해 간략화한다. 마르코프 가정이란 현재의 확률변수에 대한 확률분포는 바로 이전 step에만 기인한다는 가정이다.

수식으로 나타내 보자면

이렇게 볼 수 있겠다.
따라서 우리는 마르코프 가정 하에서 첫번째 expression을 이렇게 써볼 수 있다.

$p(X_1,X_2,...,X_n)=p(X_1)\cdot p(X_2|X_1)\cdot p(X_3|X_2)\cdot ...\cdot p(X_n|X_{n-1})$

이때 확률이 마르코프 가정에 의해 연쇄적으로 얽혀 있기 때문에 이를 Markov Chain이라고 부른다.

2. Metropolis-Hastings

MCMC에서 자주 사용되는 알고리즘 중 하나인 MH 알고리즘을 먼저 이해하고 넘어가자.

$p(\theta) \propto g(\theta)$ 일 때,

1. select initial value $\theta_0$

2. for $i=1,...,m$, repeat:

   a) Draw candidate $\theta^* \sim q(\theta^* |\theta_{i-1})$
   b) $\alpha = \frac{g(\theta^* )q(\theta_{i-1}|\theta^* )}{g(\theta_{i-1})q(\theta^* |\theta_{i-1})}$
   c) if $\alpha \geq1$, accept $\theta^*$ and set $\theta_i\leftarrow \theta^*$
   d) if $0<\alpha <1$, accept $\theta^*$ and set $\theta_i\leftarrow\theta^*$ with prob.$\alpha$
   reject $\theta^*$ and set $\theta_i\leftarrow \theta_{i-1}$ with prob $1-\alpha$

해당 과정에서 $\theta_i$를 결정할 때 현재의 상태 $\theta_{i-1}$에만 영향을 받기 때문에, 해당 알고리즘은 Markov Chain이다.

이때 특별히 candidate $\theta^*$의 proposal distribution 의 중심이 $\theta_{i-1}$이고 이렇게 이전 값에 depend할때 이것을 random walk metropolis-hastings라고 한다.

이때 분포 q는 보통 symmetric한 분포, 그 중에서도 정규분포로 가정된다. 만약 q가 조건값을 평균으로 가지고 분산이 일정한 정규분포라면 위의 $\frac{g(\theta^* )q(\theta_{i-1}|\theta^* )}{g(\theta_{i-1})q(\theta^* |\theta_{i-1})}$식에서 분자와 분모의 q 분포가 같은 분포가 되어 사라지게 된다. 결국 우리는 $\frac{g(\theta^* )}{g(\theta_{i-1})}$ 부분만 보면 되니까 계산이 훨씬 편해진다.

다음 포스팅에서는 MH 알고리즘의 특별한 예시인 gibbs samplig에 대해서 살펴보겠다.