MCMC (metropolis-hastings)

▶Markov Chain Monte Carlo​

간단히 말하면,

markov chain은 그 전에 몇 번 시행했든 간에 바로 이전 시행에 대해서만 영향을 받는다는 거고,

monte carlo는 이상한 pdf의 분포를 구하기 어려울 때, 해당하는 pdf의 x를 많이 sampling해서 근사화시켜서 표본평균과 표본분산을 구하는 과정을 말한다.

​

그림으로 설명하자면,

 

가령, f(x)라는 분포의 기댓값, 분산을 알고 싶다고 하자.

이때 이 분포가 모양이 특이하면 (봉우리가 여러 개 있는 등), 적분하기 상당히 까다로울 것이다.

이럴 때 정규 분포를 따르는 h(x)를 하나 씌워서 여기서 data point를 무작위로 뽑아서

근사시켜서 표본 평균, 표본 분산을 구하는 식으로 기댓값과 분산을 유추할 수 있다.

​

구체적으로,

정규분포를 따르는 h(x)에서 한 data point를 뽑았는데 우연히 저기가 뽑혔다고 가정하자.
이때 f(x)가 h(x)보다 작으면 (하트가 음수이면) 해당 data point는 reject하고 같은 정규 분포에서 다시 data를 추출한다.

​

새로 추출한 data point에서 f(x) > h(x) 이므로 accept한다.

 

accept하면 해당 data point를 중심으로 정규분포를 다시 가정하게 된다.

새로 가정한 정규분포에서 위와 같이 data point를 다시 무작위로 뽑았다.

​

그런데 f(x)가 h(x)보다 크면 해당 data를 accept하고 다시 그 지점으로 이동하여 새 정규분포를 가정하는 것이다.

​

이런식으로 acceptance-rejection을 반복하면서 accept된 data point들을 차곡차곡 모아 놓은다.
그러다 보면, 왼쪽 봉우리에서 data point가 추출될 수 있다.

​

그러면 오른쪽 봉우리에서 했던 것처럼 여기서도 똑같이 acceptance-rejection을 반복하면 된다.

​

이런식으로 몇 번의 알고리즘을 반복한 후 추출된 data point들의 히스토그램을 그리면 다음과 같은 모양을 띈다.
이때 이 data point들의 평균을 구하여 표본 평균과 표본 분산을 구할 수 있게 된다.