Monte Carlo와 MCMC

Single-chain Metropolis-Hastings sampling. chains=1 에서 각 iteration마다 scalar state 하나를 기록하고, draws=100 , 1000 , 10000 으로 얻은 posterior sample을 red density histogram으로 나타냄. PyMC에서 draws 는 각 chain에서 tuning 이후 저장하는 sample 수이고, chains 는 독립적으로 실행하는 Markov chain 수이므로 전체 retained sample 수는 draws x chains 임. Blue curve는 target distribution이며, draw 수가 증가할수록 empirical distribution이 이에 가까워짐. Red histogram의 y-axis는 sample count가 아니라 probability density이므로 narrow bin에 sample이 집중되면 높이가 1을 초과할 수 있으며, 전체 histogram의 area는 1로 normalized됨.

 

Monte Carlo

Monte Carlo는

• random sample을 반복 생성하여
• expectation, probability, integral 등을
• numerical approximation하는 방법의 총칭.

다음과 같이 목표분포 $\pi$에서 직접 sampling이 가능한 경우:

$$
X_1, X_2, \ldots, X_N
\overset{\mathrm{IID}}{\sim}
\pi
$$

• $X_i$: $i$번째 sample
• $i$: sampling index
• $N$: 전체 sample 수
• $\pi$: target distribution

IID(independent and identically distributed) 이므로 다음을 만족:

 

각 $X_i$는

• 동일한 target distribution에서 생성되며
• 서로 independent함.

IID 관련  자료: https://dsaint31.tistory.com/671#%EC%B0%B8%EA%B3%A0%3A%20independent%20and%20identically%20distributed%20(i.i.d.)%20%EC%99%80%EC%9D%98%20%EA%B4%80%EA%B3%84-1-1

[Math] Random Sampling

 

따라서, Monte Carlo에선 

• sampling index는 생성 순서만 표시함.
• MC에서는 순서(index) 자체에 특별한 statistical meaning이 없음.

생성된 sample을 이용하여 expectation을 다음과 같이 approximation함.

$$
E_{\pi}[f(X)]
\approx
\frac{1}{N}
\sum_{i=1}^{N} f(X_i)
$$

---

예: Dataset을 반복 생성하는 Monte Carlo simulation

한 번의 Monte Carlo iteration에서 100개 instance로 구성된 dataset 하나를 생성한다고 가정.

$$
\mathcal{D}_r = \{X_{r,1},X_{r,2},\ldots,X_{r,100}\}
$$

• $r$: Monte Carlo iteration index
• $i$: dataset 내부의 instance index
• $X_{r,i}$: $r$번째 iteration에서 생성된 $i$번째 instance
• $\mathcal{D}_r$: $r$번째 iteration에서 생성된 dataset

1000회 반복한 경우:

$$
\mathcal{D}_1,\mathcal{D}_2,\ldots,\mathcal{D}_{1000}
$$

1000번째 dataset:

$$
\mathcal{D}_{1000} = {X_{1000,1},X_{1000,2},\ldots,X_{1000,100}}
$$

일반적인 Monte Carlo simulation에서는 각 dataset이 서로 다음과 같이 independently generated됨.

$$
\mathcal{D}_r \perp \mathcal{D}_{r+1}
$$

같은 dataset 내부의 $X_{r,n}$ instance 와 $X_{r,n+1}$가 independent한지는 data-generating model에 따라 달라짐.

 

즉,

• Repeated measurement, cluster, longitudinal data 등을 simulation한다면
• 같은 dataset 내부의 instance가 correlated될 수 있음.

이는 Monte Carlo iteration 사이의
dependence와는 별개의 문제.

---

MCMC

MCMC는 Markov Chain Monte Carlo의 약자.

• Target distribution에서 직접 sampling하기 어려운 경우,
• 해당 distribution을 stationary distribution으로 가지는 Markov chain을 구성하여
• sample을 생성하는 Monte Carlo method.

Markov chain:

$$
S_0,S_1,S_2,\ldots
$$

• $t$: MCMC iteration index
• $S_t$: $t$번째 iteration의 chain state
• $S_0$: initial state

2022.10.14 - [.../Math] - [LA] Markov Chain

[LA] Markov Chain

 

Markov chain에서 다음 state는 현재 state를 기반으로 생성됨.

$$
S_{t+1} \sim P(S_{t+1}\mid S_t)
$$

 

따라서 MCMC sample $S_t$와 $S_{t+1}$은 일반적으로 independent하지 않음

(MC와의 차이점).

 

이처럼 iteration index를 따라 가까운 sample들이 correlated되는 현상을
serial correlation 또는 autocorrelation이라 함.

---

Parameter vector를 sampling하는 경우

Bayesian model에서 하나의 chain state는 여러 parameter로 구성될 수 있음.

$$
S_t = (\mu_t,\sigma_t,\beta_t)
$$

 

Autocorrelation은 동일한 parameter를 iteration 방향으로 비교한 관계에서 성립:

 

이 경우,

• $\mu_t$ 와 $\mu_{t+1}$ 은 serial correlation 관계임.
• $\sigma_t$ 와 $\sigma_{t+1}$도 serial correlation 관계임.

반면 "같은 iteration"의 $\mu_{t}$와 $\sigma_t$의 관계는 autocorrelation이 아니라 posterior correlation 임.

 

2025.05.27 - [.../Math] - Bayes' Theorem (Update Your Beliefs with Evidence): Bayesian

Bayes' Theorem (Update Your Beliefs with Evidence): Bayesian

 

---

예: Dataset 전체가 chain state인 경우

하나의 chain state가 100개 instance로 구성된 dataset이라고 가정.

$$
S_t = \mathcal{D}_t = \{X_{t,1},X_{t,2},\ldots,X_{t,100}\}
$$

 

MCMC autocorrelation은 다음에서 성립:

• $\mathcal{D}_t$ 와 $\mathcal{D}_{t+1}$
• $X_{t,n}$ 과 $X_{t+1,n}$ (같은 component 기준)

반면, $X_{t,n}$ 과 $X_{x,n+1}은 같은 iteration 내부의 서로 다른 instance 이므로 MCMC autocorrelation과 관계없음.

 

즉, 다음이 성립.

• 두 instance 사이의 correlation은 data-generating model에 의해 결정되며,
• MCMC autocorrelation을 의미하지 않음.

---

Burn-in과 convergence

앞서 살펴본 MCMC의 속성상

• 초기 iteration에서는 chain이 initial state의 영향을 크게 받을 수 있음.

따라서 초기 sample 일부를 burn-in 또는 warm-up으로 제외함.

 

적절한 조건이 만족되면 $t$가 증가할수록 $S_t$의 distribution은 target distribution에 수렴함.

 

다만 burn-in 이후의
sample도
일반적으로 IID가 아님.

 

확인해야 할 주요 diagnostic:

• Convergence
• Autocorrelation
• Effective sample size
• Chain mixing
• Divergence

---

대표적인 MCMC algorithm

• Metropolis algorithm
• Metropolis-Hastings algorithm
• Gibbs sampling
• Hamiltonian Monte Carlo, HMC
• No-U-Turn Sampler, NUTS

MCMC를 가능케 해주는 PyMC의 기본 알고리즘인 NUTS는 HMC를 확장한 algorithm임:

• HMC는 gradient와 Hamiltonian dynamics를 이용하여 posterior space를 탐색하는 trajectory lenght가 hyper-parameter임.
• NUTS는 trajectory가 되돌아오기 시작하는 시점을 감지하여 trajectory length를 자동으로 결정해줘서 더 실용적임.

PyMC에서는
continuous parameter를 포함한
일반적인 Bayesian model에
주로 NUTS가 사용됨.

---

Monte Carlo와 MCMC의 차이

구분	Monte Carlo	MCMC
Sampling	Target distribution에서 직접 sampling	Markov chain을 통해 간접 sampling
Sample 관계	일반적으로 IID	일반적으로 autocorrelated
이전 sample 사용	사용하지 않음	다음 sample 생성에 사용
Index 의미	생성 순서만 표시	Chain iteration을 표시
Index 순서	일반적으로 중요하지 않음	중요함
주요 사용 조건	Direct sampling이 가능함	Direct sampling이 어려움
추가 고려사항	Monte Carlo error	Burn-in, convergence, autocorrelation, ESS

• Monte Carlo는 random sample을 이용한 numerical approximation의 전체 범주.
• MCMC는 Markov chain을 이용하여 target distribution으로부터 correlated sample을 생성하는 Monte Carlo method.

---

같이보면 좋은 자료들

https://gist.github.com/dsaint31x/ddade891d7ee5a5646d83e2745971569

pymc_mcmc.ipynb

https://liveyourit.tistory.com/147

MCMC (Markov Chain Monte Carlo) 샘플링