February 11, 2019 10:00

저번 포스트에서 Markov Chain Monte Carlo(MCMC)에 대해서 간략히 알아보고 MCMC를 구현하는 대표적 알고리즘인 Metropolis-Hastings 알고리즘을 이해해보았습니다. 이번에는 이어서 MCMC의 수렴속도에 대해 논의해봅시다.

MCMC가 만드는 샘플들은 target distribution에 점점 수렴하는 특징이 있습니다. 다르게 말하면 MCMC가 만들어내는 샘플을 사용하기 위해서는 샘플들이 target distribution에 수렴할 때 까지 기다려야 합니다. 적절히 수렴한 상태를 mix 되었다고 하고 이때까지 걸리는 시간을 mixing time이라고 합니다.

저번에 MCMC가 다른 샘플링 기법들에 비해 빠른 수렴속도를 가진다고 했는데, 사실 절대적인 수렴속도는 일반적으로 빠르지 못합니다. 때문에 MCMC는 수렴을 보장하는 강력한 성질에도 불구하고 응용분야에서 실제로는 효과적으로 사용되지못하고 있습니다. 다만, 빠르게 수렴하는 MCMC, 즉 fast mixing MCMC 알고리즘을 만들지 못한 것일 뿐 아직 개선될 여지는 있습니다. 특정 상황에서 빠르게 수렴하는 방법이 개발되어오고 있고, 일반적으로 빠르게 수렴하는 MCMC 알고리즘을 만드려는 연구도 현재 활발히 진행중입니다.

따라서 이번 글에서는 현재까지 MCMC의 수렴속도를 올리기 위한 대표적 연구를 간단히 정리하는 것을 목표로 합니다. 디테일은 배제하고 연구의 아이디어를 소개하는 방향으로 작성 해보겠습니다. 글의 마지막에는 최근 딥러닝을 이용해 효율적인 MCMC를 만드는데 성공한 논문들에 대해서도 간략히 소개하겠습니다.

상태개수가 유한할 때

상태개수가 유한할 때는 기본적으로 대부분의 문제에서 상태들간의 이동을 나타내는 그래프가 주어지게 됩니다. 즉, transition probability 없이 markov chain이 주어졌을 때, target distribution으로 가장 빨리 수렴하는 (수렴이 보장된) transition probability를 찾는 문제가 됩니다. 더 나아가 이 문제는 주로 reversible markov chain(저번 포스트에서 설명했던 detailed balance를 만족시키는 markov chain, 수렴이 보장됨)에 대해서만 다루는데, 그 이유는 target distribution으로 수렴하는 것이 우선 보장되어야 수렴속도를 논의하는 것이 의미있기 때문입니다.

이 문제는 2004년 S. Boyd의 논문에서 Semidefinite Programming(SDP) 문제임이 증명되면서 그 실마리가 풀리게 됩니다. SDP는 convex 최적화 문제의 한 종류로 최적해가 유일하게 보장되며 다항시간내에 해결되는 좋은 형태입니다. 저자는 이 문제를 fastest mixing markov chain(FMMC) 문제로 규정하고 수학적으로 완전하게 SDP로 변환해 냅니다. 즉, 상태개수가 유한할 때는 가장 빨리 수렴하는 최적의 transition probability를 수학적으로 완전히 찾아낼 수 있습니다.

다만, 실제로 MCMC가 도전할만한 복잡한 분포의 경우에는 상태개수가 굉장히 많아서 FMMC를 적용하기에는 부적합한 경우가 많습니다. 상태개수가 작거나 적당히 큰 경우에는 SDP 혹은 SDP를 근사해서 푸는 방법으로 해결할 수 있지만, 상태개수가 굉장히 큰 경우에는 모든 transition probability를 찾아내기에는 시간이 너무 오래걸립니다. 이 경우에는 FMMC로 풀기보다는 Metropolis-Hastings(MH)와 같은 일반적인 알고리즘에 의존하는 것이 좋습니다.

일반적인 경우

일반적인 경우는 대부분 MH류의 알고리즘에 의존합니다. MH류의 알고리즘이란 sampling이 쉬운 proposal distribution을 통해 샘플을 생성해내고, 특수한 markov chain을 구성하여 샘플들이 점점 target distribution에 수렴하도록 하는 것입니다. 하지만 저번 포스트에서도 언급했듯이 이 알고리즘들은 어떤 proposal을 선택하냐에 따라서 수렴속도가 크게 달라지게 되며, 좋은 proposal을 찾는 것 또한 굉장히 어려운 문제입니다. 특히 MH류는 여러 개의 mode 중 (distribution을 그렸을 때 봉우리 부분, 확률 밀도가 높은 부분들) 한가지 mode에 주로 집중한다는 취약점이 있습니다. Target distribution을 정확히 표현하려면 적절한 시간내에 상태공간을 균형있게 탐색해야하는데 확률밀도가 높은 지점을 찾는 순간 그 주변을 굉장히 오랜시간 동안 맴돌기 때문입니다. 이 문제점을 mode collapse라 부릅니다. MH알고리즘과 그 변형들이 개발되고 나서 오랜시간 동안 이 문제점이 지적되어 왔고, 이 것을 해결하기 위해 Hamiltonian Monte Carlo(HMC) 또는 Hybrid Monte Carlo 라는 새로운 샘플링 기법이 개발됩니다.

Hamiltonian Monte Carlo

HMC를 설명하기에 앞서 Hamiltonian dynamics(해밀턴 역학)에 대해서 알아봅시다. 해밀턴 역학은 쉽게 말해 전체 에너지가 보존되는 고전역학 계에서 물체의 움직임을 위치벡터 $x$와 운동량벡터 $p$를 이용해 해석하는 것을 말합니다. 이때 물체의 에너지는 운동에너지 $K(p)$와 위치에너지 $U(x)$로 표현되고 전체 에너지 $H(x, p)=K(p) + U(x)$를 해밀턴이라 부릅니다. 이 계의 움직임은 다음의 해밀턴 방정식으로 표현됩니다.

$\frac{\partial x}{\partial t} = \frac{\partial H}{\partial p} = \frac{\partial K}{\partial p},\frac{\partial p}{\partial t} = -\frac{\partial H}{\partial x} = -\frac{\partial U}{\partial x}$

따라서 $\frac{\partial K}{\partial p}$ 와 $\frac{\partial U}{\partial x}$을 알 수 있다면 시간 $t$에 따라 $(x, p)$의 변화를 계산 할 수 있습니다.

HMC는 이 Hamilton dynamics를 이용해 MH알고리즘의 좋은 proposal을 만들어냅니다. 샘플 $x=X_{t-1}$에서 $X_t$를 뽑을 때 임의의 운동량 $p$를 설정하여 $(x,p)$로 부터 새로운 샘플 $(x’, p’)$를 얻은 후 $x’$만을 취하게 됩니다. 이 과정에서 markov chain의 수렴성을 유지하고 운동량의 효과를 무시할 수 있어야 하기에, 다소 복잡한 수학적 논의가 진행되므로 이글에서는 다루지 않겠습니다. 그렇다면 이 방법이 mode collapse 어떻게 해소시켜줄 수 있을까요?

그 비밀은 바로 운동량 $p$에 있습니다. 예를 한번 들어보겠습니다. 기존의 MH알고리즘은 지구 주위를 돌지 못하고 추락해버린 인공위성과 유사합니다. 지구주위를 돌려는 목적으로 만들어졌지만 중력을 이기지 못하고 쏘아올려진 후 바로 추락하게 됩니다. 이 인공위성은 지구의 모든 면을 보지 못합니다. 반면 HMC는 지구로 추락하지 않고 스스로 운동량을 가지고 있어 지구 주위를 돌 수 있는 인공위성입니다. 적절한 운동량을 가진다면 추락하지도, 탈출하지도 않고 지구주위를 안정적으로 돌 수 있습니다. 결국 운동량 덕분에 지구의 모든 면을 균형있게 관찰할 수 있습니다. 즉, HMC는 운동량이라는 새로운 변수로 인해 하나의 mode에 집중하지 않고 전체 상태공간을 효율적으로 탐색하여 수렴속도를 줄이게 됩니다.

HMC가 성능면으로 볼때 일반적으로 현재까지 가장 우수한 알고리즘으로 평가받고 있습니다. 다만 HMC는 target distribution이 continuous하지 않으면 적용할 수 없다는 단점이 있습니다.

최근연구동향: 딥러닝 MCMC 알고리즘

HMC의 등장에도 여전히 더 빠르고 좋은 샘플링 기법이 필요합니다. 최근에는 딥러닝을 이용해서 효율적인 MCMC 알고리즘을 개발하려는 시도가 수차례 보고 되고 있습니다. 그 첫번째는 2017년 NIPS에 투고된 논문 A-NICE-MC: Adversarial Training for MCMC입니다. 이 논문은 GAN을 이용해 MCMC의 proposal을 만드는데 성공했습니다.

GAN은 아시다시피 Generated Adversarial Network의 줄임말입니다. Generator network(G), discriminator network(D)가 따로 존재하여 서로의 성능을 같이 개선시켜나갑니다. 그런데 만약 G를 HMC의 proposal로 학습시키면 어떨까요? 위 논문에서는 같은 아이디어를 사용하여 proposal을 neural network로 구성한 MCMC 알고리즘을 만드는데 성공했습니다. GAN에서 G의 역할은 랜덤 노이즈 벡터 $v$를 받아서 target distribution의 진짜 샘플을 모방하는 가짜 샘플을 계속 만들어내는 것입니다. HMC의 랜덤 운동량 벡터 $p$를 받아서 새로운 샘플을 만들어내는 것을 neural network로 해결하기 위함입니다.

다양한 영역에서 성공적인 성능을 보인 GAN을 MCMC에 처음으로 적용했다는 의미를 가지는 논문이지만 아직까지도 단점이 너무 많습니다. 우선 GAN은 target distribution의 실제 샘플을 필요로 하므로 NICE-MC도 target distribution의 실제 샘플이 어느정도 있어야 합니다. 따라서 샘플이 없는 경우에는 적용하기가 어렵습니다. 또한 NICE-MC는 학습과정에서 불안정한 요소가 많아서 여전히 mode collapse 문제에 취약합니다.

이 논문이 투고된지 1년 만에 딥러닝을 이용해 효율적인 MCMC를 만든 논문이 많이 등장했습니다. 거의 모든 연구의 핵심은, 지금까지 proposal을 손으로 튜닝했던 과거와는 달리 proposal을 neural network로 구성하는데에 있습니다. 저도 이 분야에 흥미를 갖고 공부하는 입장으로서 머지않아 딥러닝이 샘플링 분야를 크게 발전시킬 것으로 기대하고 있습니다.

이번 포스트에서는 간략하게 MCMC분야의 흐름을 살펴보았지만, 다음 포스트에서는 실제 응용사례와 직접 구현한 결과로 MCMC에 대해 디테일하게 이해해보겠습니다.

참고문헌

1. Markov Chain Mixing Time-Wikipedia
2. Fastest Mixing Markov Chain on a Graph, S. Boyd et. al, 2004
3. A Conceptual Introduction to Hamiltonian Monte Carlo, M. Betancourt, 2017
4. A-NICE-MC: Adversarial Training for MCMC, J. Song et. al, NIPS, 2017