해밀턴 몬테카를로(Hamiltonian Monte Carlo, HMC)는 직접 샘플링이 어려운 목표 확률 분포에 수렴하는 무작위 샘플 시퀀스를 얻기 위한 마르코프 체인 몬테카를로(Markov chain Monte Carlo, MCMC) 방법의 일종이다. 원래 명칭은 하이브리드 몬테카를로(hybrid Monte Carlo)였으며, 얻어진 샘플 시퀀스는 목표 분포에 대한 적분, 예컨대 기댓값이나 적률(moment)을 추정하는 데 사용된다.
개요
해밀턴 몬테카를로는 메트로폴리스-헤이스팅스 알고리즘(Metropolis–Hastings algorithm)의 한 사례로 볼 수 있다. 상태 공간에서 새로운 지점으로의 이동을 제안하기 위해 시간 가역적(time-reversible)이고 부피 보존적(volume-preserving)인 수치 적분기, 일반적으로는 도약 적분기(leapfrog integrator)를 사용하여 해밀턴 동역학(Hamiltonian dynamics)의 시간 전개를 시뮬레이션한다.
메트로폴리스-헤이스팅스 알고리즘에서 가우스 무작위 행보(Gaussian random walk) 제안 분포를 사용하는 방식과 비교할 때, 해밀턴 몬테카를로는 심플렉틱 적분기(symplectic integrator)를 사용할 때 시뮬레이션된 해밀턴의 근사적인 에너지 보존 특성 덕분에 높은 수용 확률을 유지하면서도 먼 곳으로의 이동을 제안한다. 이는 연속적으로 샘플링된 상태 간의 상관관계를 줄이며, 결과적으로 주어진 몬테카를로 오차 수준에서 목표 확률 분포에 대한 적분을 근사하는 데 필요한 마르코프 체인 샘플 수가 적어진다는 의미를 가진다.
알고리즘의 원리
해밀턴 몬테카를로에서는 목표 분포를 위치 변수에 대한 잠재 에너지(potential energy)로 변환한다. 목표 확률 밀도 함수를 f(x)라고 할 때, 잠재 에너지는 U(x) = −ln f(x)로 주어진다. 체계 전체를 기술하는 해밀토니안 H(x, p)는 위치 에너지 U(x)와 운동 에너지 항으로 구성되며, 운동량 p에 대해 가우스 분포 N(0, M)으로부터 무작위 추출된다. 여기서 M은 대칭 양정부호(positive definite) 질량 행렬이다.
알고리즘은 다음의 단계로 진행된다.
- 현재 상태에서 무작위 가우스 운동량을 추출한다.
- 해밀턴의 운동 방정식을 도약 적분기로 수치 적분하여 LΔt 시간 동안 상태를 전개한다. 여기서 L은 도약 스텝 수, Δt는 스텝 크기이다.
- 메트로폴리스-헤이스팅스 수용/기각 단계를 적용하여 새로운 상태를 얻는다. 수용 확률은 시뮬레이션 전후의 해밀토니안 값 차이에 기반한다.
해밀턴 동역학이 에너지를 정확히 보존한다면 수용 확률은 1이 되지만, 수치 적분의 이산화 오차로 인해 근사적인 보존만 이루어져 수용/기각 과정이 필요한 구조이다.
역사
이 알고리즘은 원래 1987년에 사이먼 듀에인(Simon Duane), 앤소니 케네디(Anthony D. Kennedy), 브라이언 펜들턴(Brian J. Pendleton), 던컨 로웨스(Duncan Roweth)에 의해 격자 양자 색역학(lattice quantum chromodynamics) 계산을 위해 제안되었다. 이후 1996년에 래드포드 M. 닐(Radford M. Neal)이 이 방법이 더 광범위한 종류의 통계적 문제, 특히 인공신경망 분야에 적용될 수 있음을 보여주었다.
그러나 알고리즘을 사용하기 위해 모델 그래프의 기울기(gradient)를 제공해야 한다는 부담 때문에 통계학과 기타 정량적 분야에서의 광범위한 채택은 지연되었다. 2010년대 중반, 확률적 프로그래밍 언어인 스탠(Stan)의 개발자들이 자동 미분(automatic differentiation)과 결합하여 해밀턴 몬테카를로를 구현하면서 널리 보급되었다.
파생 기법 및 확장
해밀턴 몬테카를로의 주요 확장으로는 No-U-Turn 샘플러(NUTS)가 있다. NUTS는 도약 스텝 수 L을 자동으로 조절하는 방식으로, L이 너무 크면 입자가 진동하여 계산 시간이 낭비되고 L이 너무 작으면 무작위 행보처럼 행동하는 문제를 해결한다. NUTS는 해밀턴 동역학을 시간상 앞뒤로 무작위로 전개하면서 U-turn 조건이 만족될 때까지 이진 트리를 구성하고, 그 경로에서 샘플을 추출하는 방식으로 동작한다.
또한 메트로폴리스-조정 랑주뱅 알고리즘(Metropolis-adjusted Langevin algorithm)과 같은 관련 기법도 존재하며, 스탠(Stan), 파이엠씨(PyMC), 튜링.jl(Turing.jl) 등의 확률적 프로그래밍 언어 및 라이브러리에서 해밀턴 몬테카를로를 구현하고 있다.
활용 분야
해밀턴 몬테카를로는 베이즈 추론(Bayesian inference)에서 사후 분포의 샘플링을 위해 널리 사용되며, 통계 물리학, 계산 화학, 기계 학습 등 다양한 분야에서 고차원 확률 분포의 샘플링 문제에 응용된다. 특히 고차원 문제에서 전통적인 무작위 행보 기반 MCMC 방법보다 효율적인 것으로 알려져 있다.
참고 문헌
- Duane, S.; Kennedy, A. D.; Pendleton, B. J.; Roweth, D. (1987). "Hybrid Monte Carlo". Physics Letters B 195(2): 216–222.
- Neal, R. M. (1996). "Monte Carlo Implementation". Bayesian Learning for Neural Networks. Springer.
- Hoffman, M. D.; Gelman, A. (2014). "The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo". Journal of Machine Learning Research 15(1): 1593–1623.
- Betancourt, M. (2018). "A Conceptual Introduction to Hamiltonian Monte Carlo". arXiv:1701.02434.
- Gelman, A.; Lee, D.; Guo, J. (2015). "Stan: A Probabilistic Programming Language for Bayesian Inference and Optimization". Journal of Educational and Behavioral Statistics 40(5): 530–543.
