[Sampling] Markov Chain Monte Carlo (MCMC) (3) - Gibbs sampling

Gibbs Sampling

Gibbs sampling은 MCMC 기법 중에서 Metropolis-Hastings 알고리즘의 특수한 형태이다.

확률변수가 다음과 같을 때 사용할 수 있다.

$x = [x_1, x_2, \dots, x_d]^\top$이고 target distribution이 $p(x)$일 때 다음을 만족하면 Gibbs sampling을 적용할 수 있다.

\[ x_i \sim p(x_i | x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_d) \]

$x_i$가 $x \setminus x_i$ condition에서 샘플링되는 조건이다.

Gibbs sampling in Gaussian. 두 변수 $z_1$, $z_2$가 번갈아 가며 샘플링된다.

Gibbs sampling algorithm

랜덤하게 $x^{(1)}$를 초기화한다.
for $t=1, \dots$ do
    $x^{(t+1)} = x^{(t)}$
    for $j=1, \dots$ do
        sample $x_j^{(t+1)} \sim p(x_j | \{ x_k^{(t+1)} \}_{k \neq j})$ 
    end for
end for

 

Correctness

Metropolis-Hastings 알고리즘에서 proposal distribution이 다음과 같은 경우와 동일하다.

\[ q(x'|x)=p(x'_j | \{ x_k \}_{k \neq j}) \delta_{ \{ x_k \}_{k \neq j} } (\{ x'_k \}_{k \neq j}) \]

 

acceptance probability $A(x'|x)$는 다음과 같다.

\begin{align} A(x'|x) &= \min \bigg\{ 1, \cfrac{p(x')q(x|x')}{p(x)q(x'|x)} \bigg\} \\ &= \min \bigg\{ 1, \cfrac{p(x')p(x_j | \{ x'_k \}_{k \neq j})}{p(x)p(x'_j| \{ x_k \}_{k \neq j})} \bigg\} \\ &= 1 \end{align}

반응형