[Statistics] MCMC(Markov Chain Monte Carlo)

MCMC(Markov Chain Monte Carlo)

target distribution을 stationary distribution으로 가지는 마코프 체인을 만드는 과정

- MCMC는 초기값에 영향을 받기 때문에 burn-in-time을 지나고 나면 target distribution을 따르는 샘플이 생성

• Monte Carlo = Simulation

  몬테 카를로 방법은 target function의 pdf or functional form은 알고 있지만, 그 함수에서 직접 샘플링 하는 것이 매우 어렵거나 불가능할 때, 효율적으로 샘플링하기 위해 사용되는 방법.

  - 수식만으로는 계산하기 어려운 문제가 있을 때 랜덤 샘플을 얻은 뒤, 그 랜덤 샘플을 이용해서 함수의 값을 확률적으로 계산하는 방법.

• Markov Chain : 마코프 체인에서 현재 상태 확률은 오로지 직전 시점의 확률에만 의존한다.

  - 마코프 체인이 특정 조건을 만족한 상태에서 마코프 연쇄를 반복하다 보면, 현재 상태의 확률이 직전 상태의 확률과 같아지게 된다. 즉, 이전 확률에 영향을 받지 않고, 하나의 확률에 수렴하게 된다. 이렇게 고정되어 움직이지 않아 평형 상태에 도달한 확률분포를 'Stationary Distribution'이라고 한다.

전통적인 Markov Chain은
1) Transition probability 이 주어졌을 때,
2) Stationary distribution을 알고 싶은 것.

MCMC는
1) Target stationary distribution이 알려져있을 때,
2) Stationary distribution에 도달하기 위한 효율적인 Transition rule(=Transiiton probability)을 규정하는 것에 관심.

MCMC 알고리즘의 대표적인 방법에는 Metropolis-Hastings , Gibbs Sampling이 있다.

---

Metropolis-Hastings Algorithm

trainsition kernel T(x*|x)가 대칭이 아닌 경우를 위해 Metropolis Algorithm을 확장한 것.

M-H algorithm에서 acceptance probability를 보정해주는 이유?
-> transition kernel이 symmetric하지 않기 때문에, Metropolis algorithm의 acceptance probability를 이용하게 되면, 한쪽에서만 너무 많은 샘플을 제안하게 되어 결국 샘플이 한쪽으로 치우치게 되고 bias가 생기기 때문에 이를 적절하게 보정하기 위한 것.

---

Gibbs Sampler

M-H algorithm의 특수한 경우

먼저, 확률변수 X를 d개의 요소로 분해할 수 있다고 가정
$x$ = { $x_{1}$, $x_{2}$,..., $x_{d}$ }
이때, 깁스 샘플러에서 각 요소는 1) systematically or 2) randomly으로 선택

만약 $x$의 현재 반복 상태가 아래와 같이 주어지면 Gibbs sampler는 다음을 반복해서 MC를 형성
$x^{(t)}$ = { $x_{1}^{(t)}$, $x_{2}^{(t)}$,..., $x_{d}^{(t)}$ }

1) Systematic Gibbs Sampling
target density f(x)의 full condition을 이용해서, 각 요소의 condition distribution을 구하고 이 각각의 분포들을 통해 샘플을 얻게 된다.
여기서 중요한 점은, 각각의 conditional distribution은 모두 closed form이라는 것!
(Gibbs sampling에서 d개의 conditional dist은 모두 우리가 알고 있는 standard한 분포를 따른다)
- 만약, 어느 하나의 conditional dist이라도 우리가 알지 못하는 분포이거나 standard한 분포를 따르지 않는다면, Gibbs sampling이 불가능

2) Randomly Gibbs Sampling
다음 상태를 뽑을 때 한꺼번에 모든 변수의 값을 정하는 것이 아니라, 변수 하나씩 값을 선택.
즉, 다른 모든 변수는 현재값으로 고정되어 있다고 가정했을 때, 이 변수가 가질 수 있는 값의 조건부 분포로부터 하나를 샘플링하는 것.

• Gibbs sampling이 좋은 이유?
  target density의 차원이 고차원이여도, 1차원으로 바꿔서 차원의 저주 문제를 해결할 수 있다.
  (Multivariate문제 -> Univariate 문제로 해결)

reference: https://blog.naver.com/jinis_stat/221689714417