[Sampling] Markov Chain Monte Carlo (MCMC) (2) - Metropolis-Hastings Algorithm

 

Metropolis-Hastings

MCMC에서 가장 많이 사용되는 알고리즘 중 하나이다.

임의의 target distribution에 대하여 이 알고리즘을 적용할 수 있다는 것이 장점이다.

물론 proposal distribution $q(x'|x)$와 unnormalized distribution $\tilde{p}(x)$는 필요하다.

그러나 full target distribution $p(x)$는 필요하지 않다.

이 알고리즘의 퀄리티는 proposal distribution $q(x'|x)$에 달려있다.

 

Metropolis-Hastings Algorithm

$x^{(1)}$을 랜덤하기 초기화한다.
for $t=1, \dots$ do
    Propose $x' \sim q(x'|x^{(t)})$
    accept $x'$ with probability $A(x'|x^{(t)})$
\[ A(x'|x^{(t)}) = \min \bigg\{ 1, \ \cfrac{p(x')q(x^{(t)}|x')}{p(x^{(t)})q(x'|x^{(t)})} \bigg\} \]
    accept라면 $x^{(t)}=x'$이고, reject라면 $x^{(t+1)}=x^{(t)}$ 이다.
end for

이때 acceptance probability에 $p(x)$로 적혀있지만, $p(x)$의 비율만을 고려하고 있으므로 상관이 없다.

$p(x)=\frac{\tilde{p}(x)}{Z}$ 이므로 $p(x')/p(x^{(t)}) = \tilde{p}(x') \tilde{p}(x^{(t)})$ 이기 때문이다.

 

$A(x'|x)$는 (현재 샘플)과 (이전 샘플) 의 비율 (현재샘플/이전샘플)을 비교하는 것이다.

Example of Metropolis-Hasting Algorithm (Machine Learning: A Probabilistic Perspective)

위 그림에서 분산에 따른 MH 알고리즘이 어떻게 샘플링되는지 보여준다.

target distribution은 2개의 Gaussian mixture이다. $(\mu = (-20, 20),\ \pi=(0.3, 0.7),\ \sigma=(100, 100))$

(a) 분산이 $1^2$인 경우, 초기값 근처에서 수렴(혹은 trapped)하여 유의미한 샘플링에 실패한 모습이다.

(b) 분산이 $500^2$ 인 경우, chain이 너무 끈끈해서(sticky) reject이 자주 일어나는 모습이다. (xy 평면에 그려진 샘플 값이 꺾여있다.)

(c) 분산이 $8^2$인 경우, 적절히 잘 탐색하여 샘플링한 모습이다.

반응형

MH for Baysian Inference

다시 베이지안 추론으로 돌아와서, 우리는 posterior를 계산해야했다.

\[ p(\theta|X) = \cfrac{p(X|\theta)p(\theta)}{p(X)} \]

여기서 target distribution은 posterior인 $p(\theta | X)$인데, 이건 직접적으로 계산이 불가능한 경우가 많았다.

 

metropolis-hasting을 이용하여 unnormalized distribution도 샘플링할 수 있기에 $p(\theta | X) := p(X | \theta)p(\theta)$를 이용하면

\[ A(\theta' | \theta) = \min \bigg\{ 1,\ \cfrac{p(X|\theta')p(\theta')q(\theta|\theta')}{p(X|\theta)p(\theta)q(\theta' | \theta)} \bigg\} \]

 

일반적으로 proposal로 가우시안 분포를 사용한다. 즉

\[ q(\theta' | \theta) = \mathcal{N}(\theta' | \theta, \sigma^2 I) \]

즉 분산$\sigma^2$이 크면 explore하게 되고, 분산이 작으면 exploit하는 경향이 있다.

 

만약 $\theta$의 범위가 제한되어 있다면 적절히 변환하여 이용할 수 있다.

예를 들어 $\theta \in (0, \infty)$ (양수조건) 이라 하자. 그러면 MH에서는 $\log (\theta')$로 변환하여 샘플링한다. 즉

\begin{align} q(\theta' | \theta) &= \log \mathcal{N}(\theta' | \log (\theta), \sigma^2) \\ &= \cfrac{1}{\theta' \sqrt{2 \pi \sigma^2 } } \exp \bigg( -\cfrac{(\log \theta' - \log \theta)^2}{2\sigma^2} \bigg) \end{align}