Bayesian과 MCMC 알고리즘 (Gibbs and Metropolis-Hastings Algorithm)

Motivation

 깁스 샘플링이 무엇인가를 정의하기 전에 이것이 왜 필요한지에 대해서 먼저 생각해보자. '우리'는 베이지안이라고 가정을 하겠다. 베이지안은 '일반적'으로 우리의 현상을 표현하는 latent variable을 가정한다. 우리의 현상, 혹은 관측을 Y라 하고, 이 현상의 원인을 X라 했을 때, 다음 세 가지를 정의한다. 

 - 편의상 X를 내면의 감정이라하고, Y를 외면의 표현이라고 하자. 

 - X는 기쁨, 슬픔, 등등이 있고, Y에는 웃음, 울기, 짜증 등등이 있을 것이다. 

1. Likelihood (개인적으로 우도란 단어를 별로 좋아하지 않는다.)

 $$\mathbb{P}(Y|X)$$

이것이 의미하는 것은 어떤 의도가 주어졌을 때 현상이 일어날 확률이다. 예를 들면 슬플 경우 꽤나 높은 확률로 울 것이다. 

2. Posterior 

 $$ \mathbb{P}(X|Y) $$

베이지안의 주된 목적은 바로 이것을 구하는 것이다. 다시 말해서 우리에게 현상이 주어졌을 때 원인을 찾는 것이다. 예를 들면 누가 웃고 있을 때 과연 이 사람이 슬픈지, 기쁜지를 알아내는 것이다. 이는 단순히 Likelihood와는 다르다. 현상에서 원인을 '역으로' 맞추는 것이기 때문에 추가 정보가 필요하고, 이것이 Prior이다. 이는 해당 사람이 평소에 슬픈지, 기쁜지에 대한 사전 정보이다. 

3. Prior

 $$ \mathbb{P}(X) $$

이것은 앞서 말한 사전 정보이다. 사람이 평소에 기쁜지, 슬픈지, 짜증내는지에 대한 정보이다. 이 정보의 유무에 따라 베이지안과 프리퀀티스트를 나눈다고 볼 수 있다. 

그리고, 위의 식들을 하나로 묶는 것이 바로 베이즈 법칙이다. 

 $$ \mathbb{P}(X|Y) \propto \mathbb{P}(Y|X) \mathbb{P}(X) $$

말로 풀어서 설명을 해보면 어떤 사람이 울고 있을 때 이 사람이 기쁠 확률은 

1. 해당 사람이 기쁠 때 울 확률과

2. 해당 사람이 평소에 기쁠 확률을 

곱해서 구해진다는 것이다. 나름 일리가 있다. 

여기서 한 가지 주의할 점은 비례한다는 것이다. 정확한 확률 분포를 구하기 위해서는 normalize를 해줘야하고, 이는.. 어렵다! 특정 Likelihood와 Prior가 곱해졌을 경우 Posterior를 쉽게 구할 수 있는 경우가 있는데 이런 Prior를 Conjugate Prior라고 한다. 대표적인 예로는 가우시안-가우시안+인버스 감마, 디리클레-멀티노미알 등이 있다. 자세한건 위키를 참고하면 된다.  

위에서 설명한 Likelihood, Prior, Posterior에 대한(?) 그림

 우리가 어떤 '값'을 원한다고 하자. 예를 들면 울고 있는 저 사람이 기쁠 '확률'을 구하시오! 혹은 이 사람이 기쁜지 슬픈지를 '구분'하시오! 란 명령이 내려졌다고 하자. 이런 경우에 베이지언은 다음과 같은 해답을 내놓는다. 

 $$ \mathbb{E}[X] = \int_{\mathcal{X}} X \mathbb{P}(X|Y) dX $$

즉 Posterior mean을 구한다는 의미이다. 그리고 이 적분은 가능한 모든 X의 공간인 '$\mathcal{X}$'에서 수행되어야한다. 하지만 우리가 모두 알듯이 적분은 어렵다. 그래서 이를 근사하고자 할 때 사용되는 것이 바로 Monte Carlo Markov Chain (MCMC) 알고리즘이다. 위의 적분은  큰 수의 법칙에 따라 다음과 같이 표현될 수 있다. 

$$ \int_{\mathcal{X}} X \mathbb{P}(X|Y) dX \sim \frac{1}{N} \sum_{i=1}^N X_i $$

그리고 여기서 필요한 가정이

$$ X_i \stackrel{iid}{\sim} \mathcal{P}(X|Y) $$

이다. 즉 우리가 모은 N개의 데이터가 Posterior에서 '추출된' 데이터야 한다는 것이다. 

하지만 이는 생각보다 쉽지가 않다. 여기에는 두 가지 이슈가 있다. 

1. 우리가 추출할 수 있는 확률은 Uniform 혹은 Gaussian 정도이다. 

2. 데이터의 차원이 커질 수록 exponential하게 어려워진다.. 

첫 번째 문제를 다루고 있는 것이 Metropolis-Hastings (MH) 알고리즘이고, 두 번째 문제를 다루고 있는 것이 Gibbs 샘플링이다. 

Metropolis-Hastings (MH) Algorithm

 알고리즘 자체는 매우 간단하고, 증명은 매우 복잡하니 알고리즘 설명만 하겠다. 여기서 증명이라는 것은 이런 식으로 뽑아도 괜찮다는 것을 의미한다. 

1. 목적

'$\pi(X) = \mathbb{P}(X|Y)$'가 주어졌을 때, '$\pi(X)$'에서 N개의 샘플인 '$X_1, X_2, ..., X_N$'을 구하는 것이다. 

2. 알고리즘

초기화

 : 임의의 '$q(y|x)$'를 설정한다. 그리고 이는 우리가 sample할 수 있어야한다. 일반적으로 다음과 같이 설정한다. 

$$q(y|x) \sim \mathcal{N}(x, \sigma^2)$$

의미를 생각해보면 현재 샘플된 값 주변에서 다음 샘플을 뽑고자 하는 것이다. 

 : 초기값 '$X_1$' 을 구한다. 

'$n$'-th 샘플링

 1. '$Y \sim q(y|X_{n-1})$'에서 '$Y$'를 뽑는다. 

 2. 다음과 같이 '$r$'을 구한다. 

$$ r(x, y) = \min(\frac{f(Y)q(X_{n-1}|Y)}{f(X_{n-1})q(Y|X_{n-1})}, 1) $$

이 때 '$f$'는 '$\pi$'에 비례하는 함수이다. 

 3. '$r$'의 확룰로 '$X_n = Y$'로 하고, '$1-r$'의 확률로 '$X_n = X_{n-1}$'로 한다. 

사족1: '$r$'의 의미를 살펴보면, 이 값은 '$Y$'가 우리의 분포인 '$\pi(Y)$'에 대해서 얼마나 적합한지를 나타낸다. 분모에 '$f(Y)$'가 있으므로, 확률이 더 높은 걸 뽑으려고 하는 경향성을 볼 수 있다. 사실 우리는 '$X_i$'들을 다 모아서 empirical distribution을 그렸을 때 '$\pi(\cdot)$'이 되도록 하길 원하므로 일맥상통한다고 볼 수 있다. 

사족2: 여기서 '$f$'는 우리가 관심있는 '$\pi$'에 비례함에 주목하자. 바꿔말하면 정확한 확률 분포가 아니라 비례하는 pseudo-distribution이여도 이 알고리즘은 돌아갈 수 있다. 

위의 알고리즘에서 알 수 있듯이 우리는 우리의 목적인 '$\pi(X)$'에서 X를 직접 뽑을 필요가 없다. 하지만 이 알고리즘은 데이터의 차원이 커질 수록 매우 오랜 시간이 걸려서 알고리즘이 돌아간다. 자세한 것은 위키(http://en.wikipedia.org/wiki/Metropolis–Hastings_algorithm)를 참고하도록 하자. 

Gibbs Sampling

1. 목적

깁스 샘플링에 대한 포스팅은 예전에 한 적이 있다. (http://enginius.tistory.com/296) 벌써 2년 전이다.. 시간 참 빠르다. 여튼 깁스 샘플링의 의의(?)는 고차원 공간에서 샘플링을 효과적으로 할 수 있다는데 있다. 사실 개념은 굉장히 straight-forward하다. '$d$' 차원의 랜덤 변수를 '$d$' 개의 '$1$'차원 변수로 나눠서 보겠다는 것이다. 

2. 알고리즘

우리가 관심있는 것이 '$X = {x_1, x_2, ..., x_d}$'의 '$d$'차원 변수라고 할 때, 이들을 나눠서 샘플링 하면 된다. 즉, 

$$ \pi(x_i | X_{\sim i})$$ 

를 잘 정의하고, '$i = 1, 2, ..., d$'로 반복하면서 '$X$'를 뽑는다. 간단하다. 

물론 여기서 위의 확률 분포에서 뽑기가 힘들 땐, 앞서 설명한 Metropolis-Hastings 알고리즘을 이용하면된다. 

정리하자면 임의의 다차원 확률 분포가 주어졌을 때, 이들을 conditional distribution으로 변경할 수 있다면, Metropolis-Hastings 알고리즘과 Gibbs sampling을 이용해서 이들 분포를 따르는 확률분포의 seqeunce를 뽑아낼 수 있고, Posterior mean을 구할 수 있다.