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

3. 알고리즘 설명

메트로폴리스-헤이스팅스 알고리즘은 확률 분포에서 난수열을 생성하는 방법이다. 이 알고리즘은 확률 밀도 함수(또는 확률 함수)에 비례하는 함수를 알고 있다면, 어떤 확률 분포에서도 난수열을 생성할 수 있게 해준다.^[9][10] 이 방법은 특히 실제로는 계산하기 어려운 경우가 많은 확률 밀도의 정규화 인자를 계산할 필요가 없다는 장점이 있다.

이 알고리즘은 다음 표본의 분포가 현재 표본 값에만 의존하는 마르코프 연쇄를 생성한다. 난수열의 길이가 길수록 목표 분포 P(x)를 더 잘 근사하게 된다. 반복 계산은 다음 상태 후보를 계산하고, 이를 채택하거나 기각하는 절차로 구성된다. 채택 확률은 P(x)에 관한 현재 상태와 다음 상태의 확률 밀도 함수를 비교하여 결정된다.

핵심 아이디어는 다음과 같다.

1. 무작위 이동: 표본 공간을 무작위로 이동하면서, 때로는 이동을 수락하고 때로는 제자리에 머무른다.

2. 채택률: 특정 점 x에서 P(x)는 알고리즘이 해당 점에 소요한 반복 횟수에 비례한다. 채택률은 새로운 제안된 표본이 현재 표본과 비교하여 얼마나 가능한지를 나타낸다.

3. 고밀도 영역 선호: 현재 점보다 더 가능성이 높은 점(즉, P(x)의 고밀도 영역)으로 이동하려고 하면 항상 이동을 수락한다. 덜 가능성이 높은 점으로 이동하려고 하면 때때로 이동을 거부하며, 확률의 상대적 감소가 클수록 새로운 점을 거부할 가능성이 더 커진다.

이러한 방식으로 알고리즘은 P(x)의 고밀도 영역에 머무르면서(많은 수의 표본을 반환) 가끔 저밀도 영역을 방문하는 경향을 보인다. 이것이 이 알고리즘이 작동하여 밀도 P(x)로 원하는 분포를 따르는 표본을 반환하는 이유이다.

하지만 다음과 같은 단점도 존재한다.

• 자기 상관: 표본은 자기상관되어, 인접한 표본 집합이 서로 상관될 수 있다. 이는 분포를 올바르게 반영하지 못하게 할 수 있다.
• 번인(burn-in): 마르코프 연쇄는 결국 원하는 분포로 수렴하지만, 초기 표본은 매우 다른 분포를 따를 수 있다. 따라서 초기 표본을 버리는 '번인' 기간이 필요하다.^[4]

3. 1. 메트로폴리스 알고리즘 (대칭 제안 분포)

• 제안 분포 $Q(x^*|x\_t)$에서 다음 상태가 될 후보 $x^*$를 생성한다.
• 채택률 $\backslash alpha\; =\; \backslash frac\{f(x^*)\}\{f(x\_t)\}$를 계산한다. 채택률은 후보의 채택 또는 기각을 결정하는 데 사용된다. $P$의 확률 밀도 함수는 $f$에 비례하므로, $\backslash alpha\; =\; \backslash frac\{f(x^*)\}\{f(x\_t)\}\; =\; \backslash frac\{P(x^*)\}\{P(x\_t)\}$이다.
• $\backslash alpha\; \backslash ge\; 1$이면 후보 $x^*$는 확실하게 채택되어 다음 상태는 $x\_\{t+1\}\; =\; x^*$가 된다. 그렇지 않으면 확률 $\backslash alpha$로 후보를 채택한다. 후보가 기각되면 다음 상태도 현재와 변함없이 $x\_\{t+1\}\; =\; x\_t$로 한다.

3. 2. 일반적인 메트로폴리스-헤이스팅스 알고리즘

• 표본은 자기상관된다. 인접한 표본 집합은 서로 상관되어 분포를 올바르게 반영하지 않을 수 있다.
• 마르코프 연쇄는 결국 원하는 분포로 수렴하지만, 초기 표본은 매우 다른 분포를 따를 수 있어 ''번인'' 기간이 필요하다.^[4]

• $g(x\text{'}\; \backslash mid\; x\_t)$에 따라 무작위 후보 상태 $x\text{'}$을 생성한다.
• 수락 확률 $A(x\text{'},\; x\_t)\; =\; \backslash min\backslash left(1,\; \backslash frac\{P(x\text{'})\}\{P(x\_t)\}\; \backslash frac\{g(x\_t\; \backslash mid\; x\text{'})\}\{g(x\text{'}\; \backslash mid\; x\_t)\}\backslash right)$를 계산한다.
• 균일 무작위 숫자 $u\; \backslash in\; [0,\; 1]$을 생성한다.
• $u\; \backslash le\; A(x\text{'}\; ,\; x\_t)$이면, $x\_\{t+1\}\; =\; x\text{'}$로 설정하여 수락한다.
• $u\; >\; A(x\text{'}\; ,\; x\_t)$이면, $x\_\{t+1\}\; =\; x\_\{t\}$로 설정하여 거부한다.
• $t\; =\; t\; +\; 1$로 설정한다.

4. 알고리즘의 장단점

메트로폴리스-헤이스팅스 알고리즘(M-H 알고리즘)은 확률 밀도 함수를 직접 계산하기 어려울 때, 그 함수에 비례하는 함수를 이용하여 원하는 확률 분포를 따르는 난수열을 생성하는 방법이다. 이는 통계학 및 통계물리학에서 상수배를 모르는 확률 밀도 함수로부터 난수를 생성해야 할 때 유용하게 사용된다.

M-H 알고리즘은 다음과 같은 장단점을 갖는다.
장점:

• 상수배를 모르는 확률 밀도 함수에서도 난수 생성이 가능하다. 이는 확률 밀도 함수의 정확한 형태를 알기 어려운 경우에 매우 유용하다.
• 알고리즘의 구조가 직관적이고, 구현이 비교적 간단하다.

• 생성된 난수열이 서로 상관관계를 가질 수 있다. 즉, 인접한 난수들이 독립적이지 않고 서로 영향을 줄 수 있다. 이 때문에 목표 확률 분포를 정확하게 근사하기 위해서는 많은 반복 계산이 필요할 수 있다. 상관관계를 줄이기 위해, 일정 간격으로 난수를 추출하거나, 다음 상태 후보를 현재 상태와 적절히 멀리 제안하는 방법 등이 사용될 수 있다.
• 반복 계산 초기에는 생성된 난수열이 목표 분포와 큰 차이를 보일 수 있다. 이를 '번인(burn-in)' 기간이라고 하며, 이 기간 동안 생성된 난수는 버리고, 일정 시간이 지난 후의 난수들만 사용하는 것이 일반적이다.
• 고차원 공간에서는 차원의 저주로 인해 효율성이 떨어질 수 있다. 이 경우, 깁스 샘플링 등 다른 방법을 고려해 볼 수 있다.
• 제안 분포의 선택이 알고리즘의 성능에 큰 영향을 미친다. 목표 분포와 유사한 형태의 제안 분포를 선택하는 것이 좋지만, 고차원 문제에서는 적절한 제안 분포를 찾기 어려울 수 있다.

5. 활용 분야

메트로폴리스-헤이스팅스 알고리즘(M-H 알고리즘)은 확률 분포에서 난수열을 생성하는 데 사용되며, 이는 통계학이나 통계물리학 등 다양한 분야에서 활용된다. 특히, 확률 밀도 함수의 상수배를 몰라도 난수 생성이 가능하다는 점이 큰 장점이다.

M-H 알고리즘으로 생성하는 난수열은 목표 분포를 근사하며, 이는 마르코프 연쇄의 원리를 이용한다. 즉, 다음 난수의 확률 분포는 현재 난수의 값에만 의존한다. 알고리즘의 핵심은 다음 상태 후보를 계산하고 채택 또는 기각하는 과정을 반복하는 것이다. 채택 확률은 현재 상태와 다음 상태 후보의 확률 밀도 함수를 비교하여 결정된다.

하지만 M-H 알고리즘에는 몇 가지 단점이 있다.

• 난수열이 상관관계를 가질 수 있다. 인접한 난수들은 서로 상관관계를 가지므로, 목표 분포를 정확하게 근사하려면 많은 반복 계산이 필요할 수 있다.
• 초기값이 목표 분포와 멀리 떨어져 있으면, 목표 분포에 수렴하는 데 시간이 오래 걸릴 수 있다.

6. 관련 알고리즘

다음은 메트로폴리스-헤이스팅스 알고리즘과 관련된 알고리즘들이다.

• 깁스 샘플링: 모든 차원에 대해 한 번에 샘플링하는 대신, 각 차원별로 새로운 샘플을 선택한다. 다변량 분포에서 각 변수가 소수의 다른 변수에만 조건부로 지정된 경우에 유용하다.
• 해밀토니안 몬테카를로법
• 슬라이스 샘플링
• 담금질 기법
• 메트로폴리스법
• MTM 알고리즘

• 역함수법: 구하려는 분포의 확률 밀도 함수의 역함수를 얻을 수 있는 경우에 사용한다.
• 기각 샘플링: 구하려는 분포에 비례하는 함수를 얻을 수 있는 경우에 사용한다.
• 적응적 기각 샘플링: 적응적으로 포락선을 정해 기각을 줄이는 방법이다.
• 중요도 샘플링: 중요도 가중치를 고려하여 기댓값을 얻는 방법이다.
• SIR sampling-importance-resampling

7. 추가 정보

마르코프 연쇄 몬테카를로(MCMC) 방법은 차원의 저주에 덜 민감하여 고차원 문제에 유용하다. 제안 분포의 선택은 알고리즘의 효율성에 큰 영향을 미치며, 알고리즘의 수렴 속도를 높이기 위한 다양한 개선 방법들이 연구되고 있다.

메트로폴리스-헤이스팅스 알고리즘은 다음과 같은 단점이 있다.

• 표본은 자기상관된다. 인접한 표본 집합은 서로 상관되어 분포를 올바르게 반영하지 않는다.
• 마르코프 연쇄는 결국 원하는 분포로 수렴하지만, 시작점이 저밀도 영역에 있는 경우 특히 초기 표본은 매우 다른 분포를 따를 수 있다. 결과적으로 초기 표본 수를 버리는 ''번인'' 기간이 일반적으로 필요하다.^[4]

참조

_[1] 서적 Monte Carlo Methods Volume I: Basics Wiley
_[2] 논문 Markov chains for exploring posterior distributions https://projecteucli[...] 1994
_[3] 논문 Adaptive Rejection Sampling for Gibbs Sampling 1992-01-01
_[4] 서적 Bayesian data analysis Chapman & Hall / CRC 2004
_[5] 논문 Gibbs sampler and coordinate ascent variational inference: A set-theoretical review
_[6] 논문 Adaptive Rejection Metropolis Sampling within Gibbs Sampling 1995-01-01
_[7] 간행물 How Many Iterations in the Gibbs Sampler?
_[8] 논문 Optimal scaling of random walk Metropolis algorithms using Bayesian large-sample asymptotics 2022-04-15
_[9] 논문 Equation of State Calculations by Fast Computing Machines
_[10] 논문 Monte Carlo Sampling Methods Using Markov Chains and Their Applications
_[11] 서적 Monte Carlo Statistical Methods Springer
_[12] 서적 Ergodic Behavior of Markov Processes: With Applications to Limit Theorems De Gruyter
_[13] 서적 Monte Carlo Methods in Statistical Physics Oxford University Press