Kwangmin Kim - Ch.11 Basics of Markov Chain Simulation

1 개요 — MCMC 의 혁명

Ch.10 의 모든 도구 (격자·기각·중요도 샘플링) 는 저차원 또는 단순 구조에서 작동. 고차원·복잡 계층 모형은 이 한계를 넘는다. 해답이 MCMC (Markov chain Monte Carlo).

MCMC 의 핵심 아이디어

목표: 사후 $p(\theta \mid y)$ 에서 직접 추출 불가능할 때도 근사 추출.

전략:

현재 $\theta^{t-1}$ 에서 다음 $\theta^t$ 를 전이 분포 $T(\theta^t \mid \theta^{t-1})$ 로 추출.
$T$ 를 영리하게 설계해 장기 분포가 $p(\theta \mid y)$ 에 수렴하게 만든다.
충분히 오래 돌린 후 표본을 사후 표본으로 간주.

결과: $\{\theta^t\}$ 는 Markov chain (한 시점 전 값에만 의존). 연속된 표본은 상관 — 독립 표본이 아니지만, 장기 평균은 $p(\theta \mid y)$ 의 기댓값.

1.1 왜 이게 혁명인가

1970~1980년대: 베이즈 분석이 “이론적으로만 좋고 계산 불가능” 상태. 계층 모형·GLM·결측 데이터 모두 닫힌 형태 없음.

1990년: Gelfand-Smith 논문이 Gibbs sampling 을 베이즈에 체계적 적용. 이후 10 년 내 BUGS 소프트웨어 등장, 베이즈가 응용 가능 분야로 변모.

Ch.11 은 이 혁명의 기초 알고리즘을 다룬다.

1.2 Ch.11 의 구조

절	주제
11.1	Gibbs sampler — 조건부 공액 활용
11.2	Metropolis-Hastings — 임의 분포
11.3	Gibbs + Metropolis 조합
11.4	수렴 진단 $\hat{R}$
11.5	Effective sample size
11.6	8 학교 계층 정규 예제
11.7	참고문헌
11.8	연습문제

1.3 직관 — “접근법의 180 도 전환”

Ch.10 의 직접·기각·중요도 샘플링: “목표 분포를 그대로 샘플하자”. Ch.11 의 MCMC: “목표 분포로 수렴하는 과정을 만들자”.

근본적 차이:

직접: 한 번에 독립 표본 확보. 차원 저주 취약.
MCMC: 순차 근사. 차원 고차 OK, but 수렴 확인 필요.

이 tradeoff 가 Ch.11 의 모든 내용을 관통. 알고리즘 (11.1~11.3) + 진단 (11.4~11.5) 두 축이 항상 쌍.

2 MCMC 일반론

2.1 Markov Chain 의 수학

$\{\theta^t\}_{t=0, 1, 2, \ldots}$ 가 Markov chain 이면:

\[ p(\theta^t \mid \theta^{t-1}, \theta^{t-2}, \ldots, \theta^0) = p(\theta^t \mid \theta^{t-1}) = T(\theta^t \mid \theta^{t-1}) \]

“기억이 직전 한 단계뿐” — 전이 분포 $T$ 가 과거 전체 이력을 대체.

2.2 정상 분포 (Stationary Distribution)

분포 $\pi(\theta)$ 가 $T$ 의 정상 분포:

\[ \pi(\theta') = \int T(\theta' \mid \theta) \pi(\theta) d\theta \]

해석: “$\theta \sim \pi$ 에서 시작해 $T$ 로 한 번 전이해도 여전히 $\pi$”. 분포가 자기 자신으로 쓰인다.

2.3 MCMC 의 목표

$T$ 를 설계하여 정상 분포 $= p(\theta \mid y)$ 만족시킨다.

충분 조건 (detailed balance):

\[ p(\theta \mid y) T(\theta' \mid \theta) = p(\theta' \mid y) T(\theta \mid \theta') \]

이 대칭성이 성립하면 $p(\theta \mid y)$ 가 정상 분포. Metropolis-Hastings 수용 규칙이 정확히 이 조건 만족.

2.4 수렴 조건 — 3 요건

정상 분포 존재 + 유일 수렴에 필요:

Irreducible (조건부 도달 가능): 어떤 $\theta$ 에서 시작해도 유한 시간 내 다른 $\theta'$ 에 양의 확률로 도달.
Aperiodic (비주기적): 체인이 특정 주기로 갇히지 않음.
Not transient (정회 가능): 방문한 영역으로 무한히 돌아옴.

정상 random walk 에선 거의 자동 성립. 퇴행 사례 (확률 0 인 사후 영역에 갇힘) 제외.

직관 — 왜 3 조건이 수렴을 보장하는가

비유: 퍼즐 공간 탐색. 모든 조각에 도달 가능 (irreducible) + 주기적 덫 없음 (aperiodic) + 모든 영역으로 되돌아옴 (recurrent) → 장기적으로 모든 상태를 자주 방문.

Ergodic theorem: 이 조건 하에서 시간 평균 $= $ 공간 평균. 즉:

\[ \frac{1}{T} \sum_{t=1}^T h(\theta^t) \to \mathbb{E}_{\pi}[h(\theta)] \]

MCMC 의 이론적 정당성이 여기. 실무에서는 수렴까지 시간이 얼마나 걸리는가 (mixing time) 가 문제.

3 § 11.1 — Gibbs Sampler

3.1 아이디어 — 조건부 분포 순환

$\theta = (\theta_1, \ldots, \theta_d)$ 를 $d$ 블록으로 나눔. 각 반복에서 $d$ 블록을 순차적으로 업데이트:

$\theta_j$ 를 나머지 최신 값들 조건부 분포에서 추출.

반복 $t$ 의 단계 $j$:

\[ \theta_j^t \sim p(\theta_j \mid \theta_{-j}^{t-1}, y) \]

$\theta_{-j}^{t-1}$ 은 이미 이번 $t$ 에서 업데이트 된 것 + 아직 $t-1$ 값인 것:

\[ \theta_{-j}^{t-1} = (\theta_1^t, \ldots, \theta_{j-1}^t, \theta_{j+1}^{t-1}, \ldots, \theta_d^{t-1}) \]

3.2 왜 이게 작동하는가

각 조건부 추출이 그 구성요소의 정상 분포를 유지. $d$ 단계 전체가 종합 정상 분포를 유지.

Gibbs 가 Metropolis-Hastings 특수 케이스인 이유: 조건부 추출 = 수용 확률 1 의 점프.

3.3 언제 Gibbs 가 자연스러운가

조건부 공액 모형에서 절대적 강점. 계층 모형의 일반 구조:

\[ y \mid \theta, \sigma \sim \mathrm{N}(\theta, \sigma^2), \quad \theta \mid \mu, \tau \sim \mathrm{N}(\mu, \tau^2), \quad \ldots \]

각 조건부가 정규·역감마 등 표준 분포 → 직접 추출 가능. Gibbs 기본 선택.

3.4 한계 — 상관 시 느린 수렴

이변량 정규 $\rho = 0.8$ 에서 Gibbs 는 계단식 이동 (수평·수직만). 상관 축 (대각선) 을 따르려면 수많은 단계 필요.

일반 원리: 조건부 변수 간 강한 상관이면 Gibbs 느림. 이 경우 재매개변수화 (Ch.12) 또는 HMC.

직관 — Gibbs 의 “축 정렬 이동” 한계

Gibbs 는 각 반복에서 좌표축 방향으로만 이동. 사후가 축과 정렬되면 (독립) 효율적. 사후가 기울어지면 ($\rho$ 큼) 매우 비효율.

비유: 체스에서 룩 (rook) 만 사용 — 직선 이동만. 대각 이동 못 함. 복잡한 경로는 지그재그.

해결: bishop 역할의 HMC (Ch.12) 또는 회전 + 룩 재매개변수화.

4 § 11.2 — Metropolis-Hastings

4.1 Metropolis 알고리즘 — 대칭 점프

조건부 공액이 없을 때 범용 도구. 절차:

Metropolis 알고리즘

시작점 $\theta^0$ 선택, $p(\theta^0 \mid y) > 0$.
각 $t = 1, 2, \ldots$:
- 제안: $\theta^* \sim J_t(\theta^* \mid \theta^{t-1})$. 대칭 조건 $J_t(a \mid b) = J_t(b \mid a)$.
- 밀도비: \[ r = \frac{p(\theta^* \mid y)}{p(\theta^{t-1} \mid y)} \tag{11.1} \]
- 수용: $\theta^t = \theta^*$ 확률 $\min(r, 1)$, 아니면 $\theta^t = \theta^{t-1}$.

핵심: 밀도비로 수용 — 더 높은 밀도는 항상 수용, 낮은 밀도는 확률적으로만.

4.2 왜 작동하는가 — Detailed Balance

목표 분포 $p(\theta \mid y)$ 에서 시작한 $\theta^{t-1}$ 과 새 $\theta^t$ 의 결합 분포 고려.

두 점 $\theta_a, \theta_b$ 를 $p(\theta_b \mid y) \ge p(\theta_a \mid y)$ 로 라벨. $\theta_a \to \theta_b$ 전이:

\[ p(\theta^{t-1} = \theta_a, \theta^t = \theta_b) = p(\theta_a \mid y) J_t(\theta_b \mid \theta_a) \cdot \underbrace{1}_{\text{수용 확률}} \]

반대 $\theta_b \to \theta_a$:

\[ p(\theta^{t-1} = \theta_b, \theta^t = \theta_a) = p(\theta_b \mid y) J_t(\theta_a \mid \theta_b) \cdot \frac{p(\theta_a \mid y)}{p(\theta_b \mid y)} = p(\theta_a \mid y) J_t(\theta_a \mid \theta_b) \]

대칭성 $J_t(\theta_a \mid \theta_b) = J_t(\theta_b \mid \theta_a)$ 이므로 두 확률이 같음.

즉 $(\theta^{t-1}, \theta^t)$ 의 결합 분포가 대칭 → 주변 분포 동일 → $\theta^t$ 도 $p(\theta \mid y)$ 에서. $p$ 가 정상 분포.

4.3 Metropolis-Hastings — 비대칭 확장

대칭 제한 제거. 수용 비율:

\[ r = \frac{p(\theta^* \mid y) / J_t(\theta^* \mid \theta^{t-1})}{p(\theta^{t-1} \mid y) / J_t(\theta^{t-1} \mid \theta^*)} \tag{11.2} \]

“밀도비 $\times$ 역방향 점프 확률 / 정방향 점프 확률”. 비대칭 보정.

장점: 적응적 제안 가능 — 예를 들어 “경사를 타고 올라가는” 제안 분포 사용.

4.4 좋은 점프 분포 $J$ 의 조건

§ 11.2 말미:

$J$ 에서 쉽게 추출 가능.
비율 $r$ 쉽게 계산 — $\log J$ 값 계산 가능.
합리적 거리 점프 — 너무 작으면 느림.
과도한 기각 피함 — 수용률 모니터.

4.5 수용률의 최적 값

이론 (Roberts, Gelman, Gilks 1997):

고차원 isotropic 정규 목표 + 정규 점프 → 최적 수용률 $\approx 23.4\%$.
1 차원 목표 → $\approx 44\%$.

실무 목표:

수용률 10% 미만 → 점프 너무 큼. $J$ scale 축소.
수용률 70% 초과 → 점프 너무 작음. $J$ scale 확대.
적정: 20~40%.

직관 — 왜 수용률이 “중간” 이 좋은가

양 극단의 문제:

낮은 수용률 (점프 크고 대부분 거절): 체인이 오래 정체 → 같은 표본 반복 → 효율 낮음.
높은 수용률 (점프 작고 거의 수용): 체인이 천천히 이동 → 전 공간 탐색 오래.

최적: 공간을 빠르게 가로지르되 너무 멀리 뛰지 않음. 이론적으로 23.4% 는 고차원 정규에서 Markov chain 의 jump distance 의 기대값이 최대가 되는 지점.

이 튜닝이 Ch.12 의 주요 주제 — 자동 adaptive sampler.

5 § 11.3 — Gibbs 와 Metropolis 의 결합

5.1 블록별 업데이트

실제 모형은 일부 조건부는 공액, 일부는 아님. 해결: 블록별로 다른 샘플러.

$\theta = (\theta_1, \theta_2, \theta_3, \theta_4)$ 에서:

$\theta_1 \mid \theta_{-1}, y$: 정규 공액 → Gibbs.
$\theta_2 \mid \theta_{-2}, y$: 비공액 → Metropolis 1 차원.
$(\theta_3, \theta_4)$: 상관 — 결합 Metropolis 블록.

각 단계가 조건부 정상 분포 유지 → 전체도 정상 분포 유지.

5.2 재매개변수화의 힘

강한 상관 사후에서 원래 좌표의 Gibbs 가 느림. 해결: 선형 변환으로 상관 제거.

예: $\rho = 0.99$ 인 $(\theta_1, \theta_2)$ → $\phi_1 = \theta_1 + \theta_2, \phi_2 = \theta_1 - \theta_2$ 로 변환 → 대략 독립. Gibbs 가 빨라짐.

Ch.12 의 non-centered parameterization 이 계층 모형에 이 원리를 일반화.

6 § 11.4 — 수렴 진단

6.1 왜 진단이 필요한가

MCMC 의 함정: “작동하지만 수렴 안 했을 때”. 체인이 특정 영역에 갇혀 이동 안 하면, 관측된 표본이 사후의 한 영역만 반영.

Figure 11.1a vs 11.1b: 50 반복 vs 1000 반복. 50 반복에선 명백히 덜 수렴.

6.2 $\hat{R}$ (Potential Scale Reduction)

여러 독립 체인을 과분산 시작점에서 실행. 체인 간 일치를 정량화.

$m$ 체인, 각각 $n$ 반복. 스칼라 추정량 $\psi$ (예: $\theta_1$, 또는 $\log p(\theta \mid y)$):

체인 내 분산 $W$: 각 체인의 분산의 평균.

\[ W = \frac{1}{m} \sum_{j=1}^m s_j^2, \quad s_j^2 = \frac{1}{n-1} \sum_i (\psi_{ij} - \bar{\psi}_{\cdot j})^2 \]

체인 간 분산 $B$: 체인 평균들의 분산.

\[ B = \frac{n}{m-1} \sum_{j=1}^m (\bar{\psi}_{\cdot j} - \bar{\psi}_{\cdot \cdot})^2 \]

주변 분산 추정:

\[ \widehat{\mathrm{var}}^+(\psi \mid y) = \frac{n-1}{n} W + \frac{1}{n} B \]

수렴하면 $W$ 와 $\widehat{\mathrm{var}}^+$ 가 같아짐. $\hat{R}$ 은 이 비율:

\[ \hat{R} = \sqrt{\frac{\widehat{\mathrm{var}}^+(\psi \mid y)}{W}} \]

6.3 해석

$\hat{R} = 1$: 수렴 완료.
$\hat{R} \approx 1.01{-}1.05$: 충분히 수렴 (실무 기준).
$\hat{R} > 1.1$: 수렴 안 됨 — 더 돌려라.
$\hat{R} > 1.5$: 심각. 모형·알고리즘 재검토.

직관 — $\hat{R}$ 의 의미

“여러 체인의 평균 흩뿌림 (B)” 과 “각 체인 내부 흩뿌림 (W)” 비교.

수렴 전: 체인들이 서로 다른 영역 탐색 → $B \gg W$ → $\hat{R} \gg 1$.
수렴 후: 모든 체인이 같은 분포 → $B \approx W$ → $\hat{R} \approx 1$.

$\hat{R} > 1$ 은 “더 오래 돌리면 사후 분산이 더 커질 것” 을 의미. 즉 현재 추정이 실제보다 좁음 (덜 탐색).

6.4 Split-$\hat{R}$

강화판: 각 체인을 전반부·후반부로 나눠 $\hat{R}$ 계산.

체인 내부도 정상성 가정 검증.
초기 burn-in 이 남아 있으면 split-$\hat{R}$ 로 감지.

6.5 Burn-in 과 Warm-up

첫 부분 버리는 전통: 시작점의 영향 제거.

실무:

전통적: 전체 반복의 절반 버림.
현대 (Stan): warm-up 에서 adaptation 병행, 그 후 본 샘플링.

7 § 11.5 — Effective Sample Size

7.1 왜 필요한가

MCMC 표본은 상관. 독립 표본 $n$ 개와 같은 정보를 얻으려면 MCMC 표본이 더 많이 필요.

예: $n = 1000$ MCMC 표본이 사실상 200 독립 표본과 동등.

7.2 정의

자기상관 함수 $\rho_t = \mathrm{Cor}(\psi^s, \psi^{s+t})$ (시차 $t$). 자기상관 시간:

\[ \tau = 1 + 2 \sum_{t=1}^\infty \rho_t \]

Effective sample size:

\[ n_{\mathrm{eff}} = \frac{mn}{\tau} \]

실무 근사 (Gelman et al. 2014):

\[ \hat{n}_{\mathrm{eff}} = \frac{mn}{1 + 2 \sum_{t=1}^T \hat{\rho}_t} \]

$T$ = 자기상관이 무시 수준이 되는 시차.

7.3 해석

$n_{\mathrm{eff}} / mn \approx 1$: 거의 독립 샘플.
$0.1 \sim 1$: 정상.
$< 0.1$: 효율 낮음 — 재매개변수화 고려.

Stan·PyMC 는 자동 계산·경고.

직관 — 자기상관이 왜 표본 효율을 떨어뜨리는가

$\theta^t$ 가 $\theta^{t-1}$ 과 비슷하면, 두 표본이 “거의 같은 정보”. $n$ 표본 얻었어도 실제 정보량은 $n/\tau$ 개.

극단: $\tau = 100$ 이면 $n_{\mathrm{eff}} = n/100$. 1000 표본이 사실상 10 개 독립 표본 수준. Monte Carlo 오차가 $\sqrt{10}$ 만 감소 — 실망적.

해결: 재매개변수화로 상관 감소 (Ch.12), 또는 더 긴 체인. 근본적으로는 알고리즘 교체 (Gibbs → HMC).

7.4 MCMC 표준오차

$\hat{\psi} = \bar{\psi}_{\mathrm{all chains}}$ 의 오차:

\[ \mathrm{SE}_{\mathrm{MCMC}}[\hat{\psi}] = \frac{s_\psi}{\sqrt{n_{\mathrm{eff}}}} \]

$n_{\mathrm{eff}}$ 가 독립 표본과 같은 역할. Ch.10.5 의 $s_\theta / \sqrt{S}$ 와 같은 공식 — $S \to n_{\mathrm{eff}}$ 로 치환.

7.5 권고

사후 평균·중앙값: $n_{\mathrm{eff}} \ge 400$.
사후 구간 끝: $n_{\mathrm{eff}} \ge 1000$.
희귀 사건: $n_{\mathrm{eff}} \ge 10000$.

Ch.10.5 의 수치와 정합.

8 § 11.6 — 8 학교 계층 정규 예제

8.1 모형 복습

$J = 8$ 학교, 처치 효과 $y_j$, 표준 오차 $\sigma_j$ 알려짐. 계층:

\[ y_j \mid \theta_j \sim \mathrm{N}(\theta_j, \sigma_j^2), \quad \theta_j \mid \mu, \tau \sim \mathrm{N}(\mu, \tau^2) \]

Prior: $p(\mu, \tau) \propto 1$ (uniform on $\tau$).

8.2 Gibbs Sampler 전개

각 조건부가 공액 → Gibbs.

$\theta_j \mid \mu, \tau, y$: 정규 공액.

\[ \theta_j \mid \mu, \tau, y \sim \mathrm{N}\!\left(\frac{y_j/\sigma_j^2 + \mu/\tau^2}{1/\sigma_j^2 + 1/\tau^2}, \frac{1}{1/\sigma_j^2 + 1/\tau^2}\right) \]

$\mu \mid \theta, \tau, y$: $\theta_j$ 들의 평균.

\[ \mu \mid \theta, \tau, y \sim \mathrm{N}(\bar{\theta}, \tau^2/J) \]

$\tau \mid \theta, \mu, y$: 공액 아님 (비정규) — 역감마 계열 또는 grid 샘플링.

각 반복:

$\theta_j$ 8 개 업데이트 (정규 공액).
$\mu$ 업데이트.
$\tau$ 업데이트 (grid 또는 Metropolis).

8.3 Figure 관찰

수렴 후 $\tau$ 가 0 근처에서 약간 positive 집중 → 완전 풀링과 풀링 없음 중간. Ch.5.5 의 shrinkage 패턴 재확인.

8.4 Non-centered 파라미터화 예고

$\tau$ 가 0 근처로 가면 $\theta_j$ 공간이 깔대기 (funnel): 낮은 $\tau$ 에서 $\theta_j$ 공간이 매우 좁아짐 → MCMC 에 기하학적 장애.

해결: $\theta_j = \mu + \tau \cdot \eta_j$ where $\eta_j \sim \mathrm{N}(0, 1)$. Ch.12 의 핵심 주제.

9 통합 관점 — MCMC 알고리즘 선택 지도

알고리즘	조건	장점	단점
Gibbs	조건부 공액	간단, 수용률 100%	상관 시 느림
Metropolis	임의 사후	범용	튜닝 필요
Metropolis-Hastings	비대칭 제안	유연	더 복잡한 튜닝
Gibbs + Metropolis 블록	혼합 구조	실용	수렴 보장 주의
HMC/NUTS (Ch.12)	미분 가능 사후	상관·고차원 효율	미분 계산
변분 추론 (Ch.13)	초대형	고속	근사

Ch.11 의 메시지: 간단한 문제부터 Gibbs, 점차 Metropolis → HMC. 진단 (11.4~11.5) 은 항상 필수.

10 응용 분야

분야	MCMC 의 역할
계층 모형	교육·의료·경제의 다단 구조
GLM·비선형 회귀	비공액 likelihood 범용 도구
결측 데이터	결측 imputation 통합
공간 통계	Gaussian process, CAR 모형
시계열	상태공간 모형
유전체학	계통수 추정, 동적 모형
기계학습	Bayesian neural networks, LDA
경제·금융	확률적 변동성, DSGE

11 실전 체크리스트

MCMC 를 실무에 녹이는 12 단계.

알고리즘 선택 — 조건부 공액이면 Gibbs, 아니면 Metropolis/HMC.
여러 체인 — 최소 4 개 독립 체인, 과분산 시작점.
충분한 반복 — 처음엔 $n = 1000$, 진단 후 조정.
Warm-up/burn-in — 전반부 (또는 warm-up) 버림.
$\hat{R}$ 확인 — 모든 모수에서 $< 1.01$ 목표.
Split-$\hat{R}$ — 더 엄격한 진단.
$n_{\mathrm{eff}}$ 확인 — 최소 400, 꼬리는 1000+.
Trace plot — 육안으로 체인 혼합 확인.
수용률 모니터 — Metropolis 는 20~40%.
비효율 시 재매개변수화 — non-centered 등.
자동 도구 우선 — Stan, PyMC 사용.
사후 예측 점검 — Ch.6 도구로 fit 검증.

12 관련 주제

선행 지식

Bayesian Part III 개관 — Ch.10~13 지도
Ch.10 Overview (02-10-0) — MCMC 이전 도구들
Ch.5 Hierarchical Models — MCMC 가 가장 유용한 분야
Ch.7 § 7.1~7.4 심화 — log-posterior 의 scoring rules

Ch.11 세부 절 (후속 작성 예정)

02-11-1-* — § 11.1~11.3 심화 (Gibbs·Metropolis 수식 유도 + 증명)
02-11-2-* — § 11.4~11.6 심화 (진단 정밀 + 8 학교 구현 상세)
02-11-3-* — § 11.7~11.8 심화 (문헌·연습)

후속 주제

Ch.12 Efficient MCMC — HMC, NUTS, Stan 상세
Ch.13 Variational Inference — MCMC 대안 근사
Ch.15 Hierarchical Regression — MCMC 가 본격 활용되는 곳

관련 개념

Geman & Geman (1984) — Gibbs sampler 원저 (이미지 처리)
Gelfand & Smith (1990) — 베이즈 통계에 Gibbs 도입
Metropolis et al. (1953) — Metropolis 알고리즘 원저
Hastings (1970) — Metropolis-Hastings 일반화
Gelman & Rubin (1992) — $\hat{R}$ 원저
Roberts, Gelman, Gilks (1997) — Metropolis 최적 수용률 23.4%
Roberts & Rosenthal (1998) — MCMC 수렴 이론
Liu (2001) — Monte Carlo 전반
Brooks, Gelman, Jones, Meng (2011), Handbook of MCMC — 종합 참고서