마르코프 체인 몬테 카를로(Markov Chain Monte Carlo), 흔히 MCMC 방법이라 알려진 이 기법은 다양한 형태의 분포로부터 parameter의 sampling을 수행할 수 있는 방법이다.

우리는 베이지안 방법론을 사용하는 과정에서 사전 분포(prior distribution)와 데이터를 바탕으로 하는 likelihood 를 곱해 사후 분포(Posterior distribution)를 결정짓는다.

\[p(\theta\mid\mathbf{X}) \propto p(\theta)p(\mathbf{X}\mid\theta)\]

사전 분포를 선택할 때, conjugate prior를 설정하지 않는다면, 우리가 목표로하는 사후 분포는 익숙한 형태의 분포가 아닐 가능성이 아주 높다. 그래서 사후 분포에서 parameter \(\theta\)에 대한 sampling을 진행하는 것은 어려운 일이다. MCMC 방법론은 이처럼 closed form이 아닌 사후 분포에서 parameter \(\theta\)를 sampling 할 때, 유용하게 사용된다.

특히 MCMC 방법은 parameter의 차원이 높은 경우에도 수행할 수 있다는 장점을 갖고 있다. 메트로폴리스-헤스팅스(Metropolis-Hastings) 알고리즘, 깁스 샘플러(Gibbs Sampler)가 MCMC 방법론 중 하나이며 이번 포스팅에서는 MCMC 기법에 대해서 논의를 진행해보고자 한다.

마르코프 체인(Markov Chain)

MCMC 기법을 이해하기 위해서는 먼저 마르코프 체인(Markov Chain)의 성질을 이해해야 한다. Markov Chain의 특징들 중에서 어떤 조건에서 Markov Chain이 특정 분포로 수렴하게 되는지를 중점적으로 살펴볼 필요가 있다.

우선 우리는 다음과 같은 확률변수의 조건부 독립성 성질을 만족함을 가정하는 것에서 Markov Chain에 대한 논의를 시작한다.

\[p(\theta^{(t+1)}\mid\theta^{1},...,\theta^{(t)}) = p(\theta^{(t+1)}\mid\theta^{(t)})\]

\(p(\theta^{(t+1)}\mid\theta^{(t)})\) 란 parameter \(\theta\)가 \(\theta^{(t)}\) 상태에서 \(\theta^{(t+1)}\) 로 변하는 전이 확률(transition probability) \(T(\theta^{(t)},\theta^{(t+1)})\) 이라 부르기도 한다. 흥미로운 것은 몇가지 조건이 추가되는 순간, \(t \to \infty\)이면 \(\theta\) 의 분포 \(\pi(\theta)\)는 특정한 분포로 수렴하게 된다. 이제부터는 추가되는 몇가지 조건들에 대해 살펴보자.

우선, 모든 \(t\) 값에 대해 transition probability가 동일한 Markov Chain을 동질적(homogeneous)인 Markov Chain이라고 말한다.

parameter \(\theta\)의 \(t+1\) 시점의 marginalized probability \(p(\theta^{(t+1)})\) 은 Chain 상에서 이전 \(t\) 시점의 \(\theta\) 의 marginalized probability에 영향을 받는다.

\[p(\theta^{(t+1)}) = \sum_{\theta^{(t)}} p(\theta^{(t+1)}\mid\theta^{(t)})p(\theta^{(t)})\]

만약 Chain의 각 단계가 parameter \(\theta\)의 분포를 변치않고 유지한다면, 이 \(\theta\)의 분포는 Markov Chain에 대해 stationary 하다고 표현한다.

\(\theta\)의 분포 \(p(\theta)\) 가 stationary 하기위한 충분 조건(필요 조건은 아님)은 다음과 같은 수식이 성립되는 transition probability를 활용하는 것이다. 이 수식을 detailed balanced condition 이라 부른다. 그리고 이 detailed balanced condition을 만족하는 경우 time-reversible 하다고 말한다.

\[p(\theta^{(t+1)})p(\theta^{(t)}\mid\theta^{(t+1)}) = p(\theta^{(t)})p(\theta^{(t+1)}\mid\theta^{(t)})\]

여기에 추가적으로 \(t \to \infty\)인 경우, 초기 \(p(\theta^{0})\) 을 어떻게 설정하더라도 \(p(\theta^{(t)})\) 이 stationary distribution \(\pi(\theta)\)로 수렴하게 만드는 조건(ergodic)을 만족시키면, 유일한 stationary distribution을 갖게 된다.

즉, detailed balanced condition을 만족한다면 우리는 parameter \(\theta\)에 대한 stationary distribution, \(\pi(\theta)\)가 존재함을 알 수 있고 ergodic까지 만족한다면, 우리는 유일한 stationary distribution이 존재한다고 말할 수 있다.

Markov Chain vs MCMC

앞서 살펴보았듯이, Markov Chain 이론은 transition probability \(T(\theta^{(t)},\theta^{(t+1)})\) 가 주어진 상황에서 \(t \to \infty\)일 때, parameter \(\theta\)에 대한 stationary distribution \(\pi(\theta)\) 를 발견하는 것에 초점을 둔다.

반면, MCMC 방법은 Markov Chain의 이론을 가져오지만 사용 목적에 있어서 차이를 보인다.

MCMC 방법은 포스팅의 초입에서 말했듯이 분포로부터 parameter에 대한 sampling을 수행하기 위해 사용되는 방법이라는 점을 다시 떠올려 보자. 즉, MCMC 방법에서는 stationary distribution \(\pi(\theta)\)는 이미 주어진 상태이다. 따라서 MCMC 방법에서 관심있는 것은 효율적으로(빠른 속도로) parameter의 stationary distribution으로 수렴할 수 있도록 하는 transition probability \(T(\theta^{(t)},\theta^{(t+1)})\) 을 발견해내는 것이다.

어떻게 최적의 Markov-Chain을 만들 것인가에 대한 문제를 다루는 셈인데 대표적인 방법으로는 Metropolis-Hastings Algorithm 또는 Gibbs Sampler 방법론이 알려져있다. 2가지 방식에 대해서는 별도의 포스팅을 통해 알아보도록 하자. 2가지 알고리즘 모두, 현재 \(t\)시점의 parameter를 기반으로 하여 \(t+1\)시점의 parameter를 얻어내는 방식을 취한다.

MCMC 방법론에서의 이슈

MCMC기법은 먼저 최적의 transition probability \(T(\theta^{(t)},\theta^{(t+1)})\) 를 생성한 후, 이 transition probability를 활용한 Markov-Chain을 시행함으로써 parameter에 대한 sampling을 수행한다.

이 때 중요하게 체크해야할 2가지 사항이 있다. 첫째, Chain의 수렴(convergence) 여부를 확인해야하는 것이며 둘째, 각 단계는 이전 단계의 상태에 영향을 받기 때문에 sampling을 하는 과정에서 주의해야한다는 것이다.

먼저 Chain의 수렴을 확인하는 이슈를 살펴보자. Chain의 수렴을 확인하기 위해서 기본적으로 우리는 각 시행마다 시작점(Starting Point)를 다양하게 주어야 한다. 그림과 같이 4개 Chain의 시작점이 달라도 \(t \to \infty\)에 따른 stationary distribution은 4가지 모두 유사해야 한다.

CF

그리고 그림을 통해서도 확인할 수 있듯이, 우리는 Chain을 통해서 Sampling을 진행하기 이전에 각 Chain이 stationary distribution으로 수렴하기 위한 충분한 시간을 주어야 한다. 즉, Chain이 아래와 같이 진행된다고 할 때,

\[\theta^{(1)} \to \theta^{(2)} \to \cdot\cdot\cdot \to \theta^{(m)} \to \theta^{(m+1)} \to \cdot\cdot\cdot \to \theta^{(m+n)}\]

Sampling의 대상이 되는 것은 \(m+1\) 번째 이후의 값들로 해야한다는 것이다. 이 상황에서 \(m\)번째까지의 시행은 Burn-in Period라고 부르며, Chain을 통해 stationary distribution으로 향할 수 있는 시간을 벌어주는 단계라고 볼 수 있다. 적절한 \(m\)값을 찾는 것은 Chain의 Trace Plot을 그려본 후, 적절한 시점을 \(m\)값으로 설정해주면 된다.

그러나 또 다른 문제가 있다. 기본적으로 Markov Chain은 \(t+1\)시점의 parameter가 \(\theta%{(t)}\)의 영향을 받으므로 자기상관(Autocorrelation)의 문제를 내포하고 있다. 이러한 문제를 해결하기 위해서는 \(m+1\)번째 시행 이후로 각 \(k\)번째 parameter를 Sampling함으로써 해결할 수 있다.

마찬가지로 \(k\)값을 설정하는 것은 \(\theta^{(t)}\)와 \(\theta^{(t+k)}\)의 자기상관성이 유효하지 않게 되는지를 Autocorrelation Plot 통해 확인하여 직접 설정해주면 된다. 이러한 조치를 통해 우리는 Sampling된 결과가 서로 독립적이라고 간주할 수 있게 된다.

참조 문헌

  1. PRML

  2. BDA