Sat 03 February 2018

Markov Chain Monte Carlo (MCMC)방법에서는 Sampling 하고자 하는 분포가 있을 때, 임의의 분포의 Sample들로 부터 출발해서 Markov Transition을 반복한다. 그리고 충분한 반복 후에 Sample들이 원하는 분포로 수렴하도록 Markov Chain을 디자인한다. 그런데 이러한 번거로운 방법이 분포를 직접 근사하는 Rejection Sampling에 비해서 과연 어떤 점이 좋은 것일까?

Monte Carlo Sampling에 있어서 "좋다"는 것은 결국 분포를 얼마나 빨리 근사하는가이다. Rejection Sampling의 경우 이는 Acceptance Rate이 얼마나 1에 가까운지에 따라 결정된다. Sampling이 되는 족족 Accept된다면 빠른 속도로 근사할 수 있는 것이다. Rejection Sampling에서 Accept Rate은 Proposal 분포를 얼마나 실제 분포와 가깝게 잡느냐에 달려있다. 그런데 알려진 몇몇 경우를 제외하고는 임의의 분포에 대해서 가까운 Proposal 분포를 찾는 것은 불가능에 가깝다.

MCMC에서도 Proposal 분포라고 부르는 것은 있지만 Rejection Sampling의 그것과는 달리 Markov Chain의 Transition에 사용되는 Conditional 분포다. 여기서 Proposal 분포는 원래 분포와 비슷할 필요가 없다. 아니, 원래 분포는 \(p(x)\)이고 Proposal은 Conditional 분포인 \(q(x'|x)\) 이니 차라리 둘은 성격이 다르다고 하는 것이 맞겠다. Proposal 분포가 원래 분포와 딱히 밀접한 연관이 없으니, 대충 적당히 잡아주어도 일반적으로 잘 동작한다.

아니 그런데 적당히 잡으면 된다니 MCMC는 만능인 것인가? MCMC는 어떤 Inductive Bias를 쓰고 있는 것인가? MCMC의 성능을 좌우하는 것은 무엇인가?

Under the Hood

MCMC의 하나인 Metropolis-Hastings (M-H) Algorithm을 보자. M-H는 현재의 \(x\) 값에서 다음 \(x'\)값으로 Transition할 확률을 우선 \(q(x'|x)\)로 Propose한다. 그 다음에 Acceptance Rate을 다음과 같이 계산하고,

\(a_{x'\leftarrow x}\)의 확률로 \(x'\)으로의 Transition을 Accept하거나 \(1-a_{x'\leftarrow x}\)의 확률로 Reject하여 \(x\)에 남아있음으로써 Detailed Balance Condition:

을 맞춰준다. 여기서 재미있는 점은 Rejection Sampling과 달리 Reject한다고 해서 Sample을 버리지는 않는 다는 것이다. Reject되더라도 Transition을 하지 않을 뿐 현재 State \(x\)가 Sampling된다. 하지만 그럼에도 Acceptance Rate이 낮아지면 MCMC의 성능은 저하된다. 왜일까?

사실 Detailed Balance Condition을 만족하려면 Acceptance Rate이

의 조건만 만족하면 되는데, 위의 Acceptance Rate 식을 보면 모든 가능한 경우 중 Acceptance Rate가 최대가 되도록 만들어진 것을 알 수 있다. 예를 들어 \(a_{x'\leftarrow x}/a_{x\leftarrow x'}=0.8\) 인 경우를 생각해보면, \(a_{x'\leftarrow x}=0.8\), \(a_{x\leftarrow x'}=1\)로 해도 되지만, \(a_{x'\leftarrow x}=0.4\), \(a_{x\leftarrow x'}=0.5\)로 해도 Detailed Balance Condition에는 문제가 없다. 달라지는 것은, \(x\)에서든 \(x'\)에서든 Rejection이 많이 되어서 다른 State로 잘 움직이지를 못한다는 것이다. 예를 들어 전체 State가 두 개 밖에 없어서 \(P(x)=0.4\), \(P(x')=0.6\) 이었다고 하자. M-H의 경우는 \(x_{1}\), \(x_{2}\)를 계속 번갈아 가면 돌아다니되 \(x'\)에 조금 더 자주 머물 것이다. 그런데 Acceptance Rate이 전반적으로 낮아서 잘 돌아다지 못한다면 \(x\)에서 20번 Sample을 뽑은 다음에야 \(x'\)에서 30번 Sample을 뽑을 수 있게 되는 것이다. 이렇게 되면 50번, 더 정확히는 그 몇 배수의 Sample을 뽑아야 제대로 동작하게 된다. 즉, 속도가 느려진다. 이는 Mixing Speed라고 부르며 MCMC 성능의 중요한 척도이다.

그런데 Proposal 분포 \(q(x|x')\)는 Acceptance Rate에 영향을 주지 않는 것일까? 일반적으로 Proposal 분포는 \(q(x|x')=q(x'|x)\)로 대칭에 되게 잡아주어 식을 간단하게 만든다.

식을 놓고 보면 Proposal 분포가 주는 영향이 없어 보이지만 생각해보면 Transition을 진행할 때 다음 State인 \(x'\)을 결정하는 것이 \(q(x'|x)\)이므로 꽤나 영향을 준다고 할 수 있다. 예를 들어 \(q(x'|x)=\text{Uniform}(x-d,x+d),\quad d\gg1\) 으로 잡으면 다음 State \(x'\)이 \(x\)로 부터 너무 멀리에서 뽑히게 되는데, 웬만한 분포는 보통 Probability Mass가 특정 지역에 몰려 있으므로 \(p(x')\ll p(x)\) 가 되어 Acceptance Rate이 작을 확률이 높다.

역으로 생각해보면 Proposal을 잡을 때는 \(p(x')\)가 현재 \(p(x)\)에 비해 크게 떨어지지 않는 곳으로 가도록 해야한다는 것을 알 수 있다. 그런데 Sampling하고자 하는 분포의 Probability Density Function (PDF)와 큰 상관 없이 이를 달성하고 싶으므로 유일한 방법은 PDF의 Smoothness를 이용하는 것이다. 즉 M-H는 이러한 Inductive Bias를 쓰고 있는 것이다.

확률 분포 함수는 일반적으로 Smooth하다.

따라서 \(x'\)이 \(x\)로 부터 너무 멀리 떨어지지 않으면 \(p(x')\)도 \(p(x)\)와 비슷할 것이고, Acceptance Rate도 1에 가깝다.

다만 무작정 너무 가까운 \(x'\)만 Propose하면 먼 곳을 Exploration하지 못하므로 Mixing Speed가 떨어진다. 결국 적절한 Width의 Proposal을 찾아 쓰기는 해야할 것이다. Rejection Sampling의 Proposal을 찾는 것만큼 어렵지는 않더라도 말이다. 다음에 기회가 되면 Hamiltonian Monte Carlo에 대해서도 써보겠다.

Category: Bayesian Machine Learning Tagged: MCMC Personal Thoughts

Comments