8.62 메트로폴리스-헤이스팅스 알고리즘

8.62 메트로폴리스-헤이스팅스 알고리즘

1. 메트로폴리스-헤이스팅스의 개요

메트로폴리스-헤이스팅스(Metropolis-Hastings, M-H) 알고리즘은 임의의 목표 분포 p(\mathbf{x})로부터 샘플을 생성하는 가장 일반적인 MCMC 방법이다. 메트로폴리스(1953)의 대칭 버전이 헤이스팅스(1970)에 의해 일반 제안 분포로 확장되었다. 수락-거부 메커니즘에 의해 목표 분포를 정상 분포로 갖는 마르코프 체인을 구성한다.

2. 알고리즘의 세부 절차

입력: 목표 분포 p(\mathbf{x}) (정규화 상수까지 알면 됨), 제안 분포 q(\mathbf{x}' \vert \mathbf{x}), 초기 상태 \mathbf{x}_0, 반복 횟수 T

절차:

  1. t = 0, 1, \ldots, T-1에 대해:
  2. \quad 제안 분포로부터 후보 샘플 \mathbf{x}' \sim q(\cdot \vert \mathbf{x}_t) 생성
  3. \quad 수락 확률 계산:

\alpha(\mathbf{x}_t, \mathbf{x}') = \min\left(1, \frac{p(\mathbf{x}')q(\mathbf{x}_t \vert \mathbf{x}')}{p(\mathbf{x}_t)q(\mathbf{x}' \vert \mathbf{x}_t)}\right)

  1. \quad u \sim U(0, 1) 생성
  2. \quad if u < \alpha: \mathbf{x}_{t+1} = \mathbf{x}' (수락)
  3. \quad else: \mathbf{x}_{t+1} = \mathbf{x}_t (거부, 현재 상태 유지)

3. 정상 분포의 증명

M-H가 생성하는 마르코프 체인의 전이 커널이 세부 균형 조건을 만족함을 보임으로써 p가 정상 분포임을 증명할 수 있다.

전이 커널은:

T(\mathbf{x}' \vert \mathbf{x}) = q(\mathbf{x}' \vert \mathbf{x})\alpha(\mathbf{x}, \mathbf{x}') \quad (\mathbf{x}' \neq \mathbf{x})

세부 균형 조건:

p(\mathbf{x})T(\mathbf{x}' \vert \mathbf{x}) = p(\mathbf{x}')T(\mathbf{x} \vert \mathbf{x}')

는 수락 확률의 정의에 의해 자동으로 만족된다.

4. 수락 확률의 해석

\frac{p(\mathbf{x}')q(\mathbf{x}_t \vert \mathbf{x}')}{p(\mathbf{x}_t)q(\mathbf{x}' \vert \mathbf{x}_t)}

이 비율은 두 가지 요소의 곱이다.

  • 확률비 p(\mathbf{x}')/p(\mathbf{x}_t): 새 상태가 현재 상태보다 목표 분포에서 확률이 높으면 > 1
  • 제안비 q(\mathbf{x}_t \vert \mathbf{x}')/q(\mathbf{x}' \vert \mathbf{x}_t): 제안 분포의 비대칭성을 보정

후자를 헤이스팅스 보정(Hastings correction)이라 하며, 대칭 제안에서는 1이 된다.

5. 대칭 제안(메트로폴리스)

제안 분포가 대칭 q(\mathbf{x}' \vert \mathbf{x}) = q(\mathbf{x} \vert \mathbf{x}')이면 수락 확률이 단순화된다.

\alpha(\mathbf{x}, \mathbf{x}') = \min\left(1, \frac{p(\mathbf{x}')}{p(\mathbf{x})}\right)

대표적인 대칭 제안은 랜덤 워크(random walk)이다.

\mathbf{x}' = \mathbf{x} + \boldsymbol{\epsilon}, \quad \boldsymbol{\epsilon} \sim \mathcal{N}(\mathbf{0}, \boldsymbol{\Sigma})

6. 제안 분포의 선택

6.1 스텝 크기의 조정

제안 분포의 스케일이 알고리즘의 효율성을 결정한다.

  • 스케일이 너무 작으면: 대부분 수락되지만 이동이 작아 탐색이 느림
  • 스케일이 너무 크면: 대부분 거부되어 체인이 멈춤

최적 수락률은 일반적으로 23% (고차원) 또는 44% (1차원) 근방으로 알려져 있다.

6.2 적응적 MCMC

실행 중에 제안 분포의 매개변수(평균, 공분산)를 적응적으로 조정하는 방법이다. 적응이 빈도를 감소시키는 조건에서 유효한 MCMC를 유지할 수 있다.

7. 독립 제안(Independence Sampler)

제안 분포가 현재 상태에 무관한 경우 q(\mathbf{x}' \vert \mathbf{x}) = q(\mathbf{x}'):

\alpha = \min\left(1, \frac{p(\mathbf{x}')q(\mathbf{x})}{p(\mathbf{x})q(\mathbf{x}')}\right)

중요도 샘플링과 유사하지만, 수락-거부 메커니즘에 의해 마르코프 체인을 형성한다. q가 p에 가까울 때 효율적이다.

8. 실용적 고려

8.1 언더플로 방지

수락 확률을 로그 도메인에서 계산하여 수치적 언더플로를 방지한다.

\ln\alpha = \min(0, \ln p(\mathbf{x}') - \ln p(\mathbf{x}) + \ln q(\mathbf{x} \vert \mathbf{x}') - \ln q(\mathbf{x}' \vert \mathbf{x}))

8.2 번인과 샘플 수집

초기 샘플들은 정상 분포에 도달하기 전이므로 버리고(번인), 그 이후의 샘플을 사용한다. 번인 기간은 수렴 진단으로 결정한다.

9. 로봇 공학에서의 응용

베이지안 캘리브레이션: 로봇 캘리브레이션 파라미터의 사후 분포를 M-H로 탐색한다.

글로벌 위치 추정: 다봉 사후 분포를 가진 위치 추정 문제에서 M-H 기반 MCMC가 활용된다.

모델 선택: 가역 점프 MCMC(Reversible Jump MCMC) 등 M-H의 확장이 모델 차원이 가변인 문제에 적용된다.

10. 참고 문헌

  • Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). “Equation of State Calculations by Fast Computing Machines.” Journal of Chemical Physics, 21(6), 1087–1092.
  • Hastings, W. K. (1970). “Monte Carlo Sampling Methods Using Markov Chains and Their Applications.” Biometrika, 57(1), 97–109.
  • Robert, C. P., & Casella, G. (2004). Monte Carlo Statistical Methods (2nd ed.). Springer.
  • Brooks, S., et al. (Eds.). (2011). Handbook of Markov Chain Monte Carlo. CRC Press.

version: 1.0