Hamiltonian Monte Carlo for sampling from high-dimensional Gaussian distributions

Abstract

초고차원의 정규 분포를 따르는 샘플을 생성하는 것은 다양한 분야의 모델링 및 시뮬레이션에서 중요한 역할을 수행하고 있다. 따라서 다양한 분야의 연구자들이 지금까지 다양한 샘플링 방법론들을 제안해왔으며, 현재에도 지속적으로 효율적인 샘플링을 위한 방법론들이 연구되고 있다. 이러한 샘플링 방법론들은 크게 두 분류 로 나뉘게 되는데, 첫 번째는 반복 수치 선형대수 (iterative numerical linear algebra) 를 활용한 방법론들이고 그리고 두 번째는 마코프 체인 몬테 카를로 (Markov Chain Monte Carlo)를 기반으로 한 방법론들이다. 두 방법론 모두 각자 가진 장점들로 인해 현재까지도 다양한 변형 알고리즘들이 연구되고 있다. 하지만 두 부류의 방법론들 모두 단점을 가지고 있다. 우선 반복 수치 선형대수를 활용한 방법론들은 특정한 공분산 행렬의 고유치들의 분포를 대상으로 한 경우에 는 굉장히 효율적인 계산과 성능을 보이는 반면, 공분산 행렬의 값이 큰 고유치들이 밀집되어 있는 경우 굉장히 비효율적인 알고리즘이 되는 단점이 존재한다. 최악의 경우, 샘플링에 실패하는 경우 또한 발생하는 것을 본 논문의 실험을 통해 확인하였 다. 전통적인 MCMC 방법론들의 경우도 마찬가지로, 초고차원 정규 분포의 경우 계산비용이 크고 수렴 속도가 느리다는 단점이 존재한다. 따라서 이를 해결하고자 저렴한 계산비용을 목표로 한 대안 알고리즘들이 최근 많이 연구가 되었고, 계산 효율이 크게 증진된 결과를 보였다. 하지만, 해당 대안 알고리즘들은 기본적으로 편 향된 분포를 점근 분포로 가지고 있으며 또한 특정 상황에서만 수렴성이 보장되는 단점을 가진다. 실제 샘플링 수행 시, 수렴성을 나타내는 값을 사전에 항상 계산 하기는 것은 어렵기 때문에, 이는 모델링을 수행하는 입장에서 큰 장애물이 될 수 있다. 본 학위논문은 고차원 샘플링에 적합하다고 알려진 해밀토니안 몬테 카를로 (Hamiltonian Monte Carlo)를 초고차원 정규 분포 샘플링에 활용하였다. 정규 분포를 HMC 를 통해 샘플링하는 것은 잘 알려진 적용 분야이나, 초고차원에서의 샘플링 가능성 과 그 계산 효율성에 대해서는 아직 연구가 충분히 진행되지 않았다. 본 학위논문 에서는 어떤 시뮬레이션 상황에서 HMC가 강력한 성능을 발휘하고, 반대로 낮은 성능을 보이는 환경을 기존에 연구되고 있던 이론을 바탕으로 분석하였다. 본 논문 에서는 HMC가 다른 방법론들이 다른 방법론들이 샘플링에 실패 혹은 낮은 성능을 보이는 시뮬레이션 환경 상에서 HMC가 강력한 성능을 보일 수 있음을 이론 및 실험 적으로 보였다. 또한 HMC가 취약한 시뮬레이션 환경 상황에서도 다른 방법론들에 비해 강건한 성능을 보이는 것을 실험적으로 확인하였다. 따라서 HMC가 초고차원 정규분포 샘플링 상황에서 안정적인 선택지가 될 수 있음을 보였다. 주어진 시뮬레이션 환경 상에서, 샘플링 난이도는 일반적으로 사전에 알기 어렵 다는 것을 감안하면 HMC는 훌륭한 초기 선택지가 될 수 있다. 또한 다른 방법론들 은 복잡한 사전처리 (preconditioning)을 사용할지라도 공분산 행렬의 구조에 따라 여전히 수렴 속도를 향상시키기 어려울 수 있는 반면에, HMC는 이러한 추가적인 계산 비용 없이 샘플링을 안전하게 수행할 수 있다. 따라서 이러한 장점들을 바 탕으로 HMC가 다양한 초고차원 정규분포 샘플링 응용에 적용될 수 있을 것으로 기대된다.

Sampling from a high-dimensional Gaussian distribution is an important task in many applications. Common approaches rely on the approximation to the square root of the covariance matrix of the target distribution, for which various numerical methods are available. In this thesis, we utilize the Hamiltonian Monte Carlo (HMC) for sampling from a high-dimensional Gaussian distribution. Under various illconditioned situations, HMC-based methods with carefully chosen hyperparameters are competitive to existing methods such as Krylov subspace and MCMC methods. Moreover, with the extensive numerical experiments, HMC can be a robust choice without strong dependency on specific simulation settings. To avoid additional computational costs in the implementation, we provide a general guideline for selecting hyperparameters of HMC for Gaussian target distribution.