Metropolis-Hastings algorithm

Metropolis-Hastings algorithm

메트로폴리스-해스팅스 알고리즘

 

지금 하고 있는 Evolutionary Simulation에서 Sampling을 할 때에 Metropolis-Hastings algorithm이 쓰입니다.

당연히도, 한국 싸이트에서 그닥 자세히 설명해져 있는 사이트가 많이 없어서 (제가 게을러서 제대로 찾아보지 못한것 일 수도 있구요.) 공부하면서 알아가는 내용을 여기에 적어보겠습니다.

 

오올~ 일단 위키피디아에 여기에 대한 한국어 사이트가 있군요.

메트로폴리스-해스팅스 위키피디아 한국어 사이트

 

전문을 옮겨보겠습니다.

 

메트로폴리스-해스팅스 알고리즘(Metropolis-Hastings algorithm)은 직접적으로 표본을 얻기 어려운 확률 분포로부터 표본의 수열을 생성하는 데 사용하는 기각 표본 추출 알고리즘이다. 이 수열은 주어진 분포에 근사하는 마르코프 연쇄 몬테 카를로를 모의실험하거나 예측치와 같은 적분을 계산하는 데 사용될 수 있다. 이 알고리즘은 1953년 볼츠만 분포의 특별한 경우를 위해 이것을 발표한 니콜라스 메트로폴리스와 이것을 1970년에 일반화한 해스팅스의 이름을 따서 명명되었다. 깁스 표집 알고리즘은 메트로폴리스 해스팅스 알고리즘의 특별한 경우이며, 일반적인 적용에는 제약이 있지만 보통 더욱 빠르고 사용하기 쉽다.

 

기각 표본 추출 알고리즘? 기각? 흠..... 잘 이해가 안되지만 일단은 직접적으로 표본을 얻기 어려운 확률 분포로부터 표본의 수열을 생성한다는 데에 있어서는 MCMC(Marcov Chain Monte Carlo)랑 비슷한것 같네요.

 

영문 위키피디아로 가보겠습니다.

한글 위키피디아의 전문은 영문 위키피디아의 첫 문단을 옮겨적은 것과 비슷하네요.

일단 메트로폴리스-해스팅스 알고리즘(이하 MHMCMC라고 부르겠습니다.)은 MCMC의 한 종류이고, 주로 다차원의 (multi-dimensional) 분포로부터 샘플링을 하는데 쓰여진다고 합니다. 특히 차원의 갯수가 많을 때 말이죠.

 

MHMCMC는 어떠한 확률분포로부터도 표본을 추출할 수 있습니다. Bayesian 방법으로는 표본을 추출하는 데에 있어 normalization factor를 신경써야되고, 이러한 normalization은 때대로 계산하기가 아주 복잡하고 힘들죠.

 

간단한(!) 과정은 이러합니다. 마르코프 연쇄에 연결된 표본들의 수열을 생성하는거죠. 이렇게 오랫동안 하다보면, 이 표본의 분포는 원래의 확률분포와 동일해 집니다.

조금만 더 자세히 들여다 볼까요?

 

첫번째로,  임의의 확률 분포 함수를 정합니다. Q(x'|x_t). 이때 이 확률 분포 함수는 x_t라는 표본이 주어졌을때 새로운 값 x'를 구할 수 있어야되고 symmetric 해야됩니다. [Q(x'|x_t) = Q(x_t|x')] 주로 쓰이는 이 임의의 확률 분포 함수는 가우시안 분포가 있다고 하네요.

그리고 임의의 한 값을 첫 표본으로 정합니다.

그리고 MCMC 스텝을 시작하죠.

1. 새로운 표본값 x'를 저희가 정한 임의의 확률 분포 Q(x'|x_t)로부터 구하고,

2. acceptance ratio를 a = P(x') / P(x_t) 로 계산합니다.

3. 만약에 이 a 가 1이상일 때에 x'를 다음 표본으로 정합니다.

4. 만약에 a가 1 이하일 때에는 x'를 a의 확률에 따라 다음 표본으로 수용할 껀지 안 할껀지 정합니다. 여기서 정할 때에는 1과0사이의 무작위의 수를 구해서 이 무작위의 수가 a보다 크면 거절, 작으면 수용합니다.

 

MHMCMC는 이런식으로 랜덤하게 표본사이를 뛰어(!) 다닙니다. 다음 단계로 갈 때도 있고, 안갈 때도 있구요. 그냥 MCMC랑 좀 비슷하네요. 여기서 중요한 개념이 이 acceptance ratio인데 이 ratio가 다음 단계로 갈 확률을 결정한다고 할 수 있지요.

 

그러니까 이 MHMCMC는 점프한다고 많이들 비유를 하는데요. 한가지 상태가 있으면 그다음 상태로 정해진 확률로 점프하는거죠. 점프하는 거리가 가까우면 확률도 늘어나고, 점프를 못하겠다 싶으면 그냥 그자리에 있는거에요.

 

이러한 MHMCMC는 어느정도의 약점도 가지고 있는데요.

1. 추출된 표본들이 모두 연결되어 있다는 점입니다. 길게보면 표본들이 저희가 추출하고자하는 확률분포를 나타낼 수 있지만, 가까이에 있는 표본들은 서로 연결되어있고, 확률분포의 일부분만을 나타내기때문에 만약에 저희가 두개의 독립된 표본을 구할려면 이 MCMC를 많이 돌려서 중간에 나온 표본들은 죄다 갖다 버려야 되는 단점이 있네요.

2. 그리고 한가지 더는 만약에 이 점프의 시작이 확률분포 상 적게 분포되어있는 곳에서 시작한다면, 확률분포를 적절하게 나타내게 될때까지 점프를 한두번 해서는 안된다는 문제가 있죠. 그래서 이렇게 좀 점프 맘대로 하게 놔두는 구간이 있는데, 이 구간을 'burn-in period'라고 합니다.

 

그럼 좀더 자세한 방법은 다음 글에서 계속 하도록 하죠.