Gibbs Sampling
7 minute read

Sampling Based Inference

Metropolis Hastings Algorithm

MCMC 방법 중 하나.

GOAL

  1. Generate a transition matrix from the stationary distribution
  2. Stationary distribution $\pi(\theta)$ of our MCMC sampling to be $p(x)$

즉, 타겟 분포정상분포(stationary distribution)로 가지는 마코프 체인을 발생시키기 위한 것.

General Algorithm of MCMC

  1. Current value $\theta^t$
  2. Propose a candidate $\theta^* \sim q(\theta^* \mid \theta^t)$ where $q_t$ is a Proposal distribution.
    (우리가 잘 알고 있으며, 표본을 쉽게 추출할 수 있는 분포를 하나 가정한다.)
  3. With an acceptance probability $\alpha$

여기서 만약 proposal distrubution $q$가 symmetric하면,

Acceptance probability r은 다음과 같이 주어진다.

$r>1$이면, $\theta^*$가 $\theta^t$보다 probable하다는 것이고 당연히 $\theta^t$를 $\theta^*$로 옮겨야할것.

Metropolis Hastings Algorithm

cf) Reversible Markov Chain

This is the detailed balance, or balance equation.
$i$ 상태에서 $j$ 상태로 가는 확률과 $j$ 상태에서 $i$ 상태로 가는 확률이 동일해야한다는 가정인데, 이 조건을 만족하면 $\pi$는 반드시 stationary distribution이 된다. (그 역은 성립하지 않으므로, Reversible Markov Chain이 더 강한 조건이라고 볼 수 있다.)

즉, $q$를 reversible markov chain으로 만들어주기 위해 $r$을 조절하는 것.


Random Walk MH Algorithm

Example 분산의 변화에 따른 샘플링 변화

Gibbs Sampling

MCMC algorithm의 한 예, MH Algorithm의 special case!

깁스 샘플링은 다음번 생성될 표본은 현재 샘플에 영향을 받는다는 점에서는 MCMC와 같지만, 나머지 변수는 그대로 두고 한 변수에만 변화를 준다는 점이 다르다.

The Gibbs Sampler is an itertive algorithm that constructs a dependent sequence of parameter values whose distribution converges to the target joint posterior distribution.

Example

3개의 확률변수의 결합확률분포 $p(x, y, z)$로부터 깁스 샘플링을 진행하려고 한다.

절차

(1) 임의의 표본 $X_0 = (x_0, y_0, z_0)$를 선택한다.

(2) 모든 변수에 대해 변수 하나만을 변경해 새로운 $X_i$을 뽑는데, 이 과정을 $i = 1, …, m$까지 반복한다.

(1) ($i=1$일때) 현재 주어진 표본 $X_0$의 두번째, 세번째 변수 $y_0, z_0$를 고정시킨다.
(2) 첫번째 변수 $x_0$를 대체할 새로운 값 $x_1$을 $P(x_1 \mid y_0, z_0)$로부터 뽑는다.
(3) 첫번째 변수 $x_1, z_0$을 고정시킨다.
(4) 두번째 변수 $y_0$를 대체할 새로운 값 $y_1$을 $P(y_1 \mid x_1, z_0)$로부터 뽑는다.
(5) 첫번째 변수 $x_1$, 두번째 변수 $y_1$을 고정시킨다.
(6) 세번째 변수 $z_0$를 대체할 새로운 값 $z_1$을 $P(z_1 \mid x_1, y_1)$로부터 뽑는다.
(7) 최종적으로 구한 $X_1 = (x_1, y_1, z_1)$

이때 새로운 값을 뽑는 데 쓰인 조건부 확률은 결합확률분포 $p(x,y,z)$에 비례한다. 그리고 결합확률분포를 계산하는 것은 어렵지만 full conditional pdf를 구하는 것은 다른 변수들이 다 상수 취급되어버리기 때문에 훨씬 간단하다.

이 성질을 이용해서 iterative하게 표본을 추출하다보면, 표본의 앞부분은 초기 상태 $X_0$에 크게 의존하지만 충분히 많이 뽑고 난 뒤에는 초기 상태에 관계 없이 타겟 확률분포 $p$에 기반한 표본을 수집할 수 있게 된다.


Assessing Convergence

The Burn-In Phase

Example

$\{0, 1, \dots, 20\}$의 값을 가지는 균등분포에서의 symmetric random walk를 가정해보자. 왼쪽의 예시에서는 chain이 10에서 출발하고, 오른쪽의 예시에서는 17에서 출발한다. 추이를 살펴보면 표본들이 균일하게 추출되기 시작하는 것은 약 100 step 이후이다. 즉 출발점이 거의 100 step 이후에 잊혀진다는 것이다.

그럼 일반적으로 chain은 언제 converge 하는걸까? 직접 수백번의 시행을 해보기 전에 언제쯤 수렴할지 알 방법이 없을까?

Mixing Rates of Markov Chains

이와 같은 식을 통해서 mixing time을 구할 수도 있지만, 일반적으로 mixing time을 구하는 과정은 transition matrix를 우선 알아야 하기 때문에 굉장히 계산하기가 어렵다.

이에 대한 대안으로 다음과 같은 몇가지 방법이 제시된다.

  1. Trace plot (가장 간단한 방법!)
  2. Estimated potential scale reduction (강의에서는 따로 다루지 않음)

cf) Strictly speaking, these methods do not diagnose convergence, but rather non-convergence. That is, the method may claim the chain has converged when in fact it has not. This is a flaw common to all convergence diagnostics, since diagnosing convergence is computationally intractable in general (Bhatnagar et al. 2010).

Trace Plot

Example #1

We show the traceplot for $x$ which was sampled from a mixture of two 1-Dimensional Gaussians using four different methods: MH with a symmetric Gaussian proposal of variance $\sigma^2 \in {1, 8, 500}$, and Gibbs sampling. We see that $\sigma^2 = 1$ has not mixed, which is also evident from Figure 24.7(a), which shows that a single chain never leaves the area where it started.

Example #2

“Isn’t the Gibbs sampler guaranteed to eventually provide a good approximation to $p(\theta)$?”

It is, but “eventually” can be a very long time in some situations.

10,000 step 정도 거치고 나니 $p(\theta)$를 잘 나타내고 있다.


Auto-correlation

Example

We see that the Autocorrelation Function of the Gibbs sampler (bottom right) dies off to 0 much more rapidly than the MH samplers, indicating that each Gibbs sample is “worth” more than each MH sample.

Autocorrelation을 줄이는 방법? Thinning

How many chains?

A natural question to ask is: how many chains should we run?

We could,

  1. run one long chain to ensure convergence, and then collect samples spaced far apart.
  2. run many short chains, but that wastes the burn-in time.

In practice it is common to run a medium number of chains (say 3) of medium length (say 100,000 steps), and to take samples from each after discarding the first half of the samples. If we initialize at a local mode, we may be able to use all the samples, and not wait for burn-in.


참고자료

Machine Learning: A Probabilistic Perspective, Kevin P. Murphy
A First Course in Bayesian Statistical Methods, Peter D. Hoff
https://ratsgo.github.io/statistics/2017/05/31/gibbs/

Recent Posts

Pretraining-Based Natural Language Generation for Text Summarization
Style Transfer from Non-Parallel Text by Cross-Alignment
End-To-End Memory Networks
A Structured Self-Attentive Sentence Embedding
Learning Loss for Active Learning