Ch.12 Computationally Efficient MCMC — 무작위 보행을 넘어서

1 개요 — Ch.11 의 한계와 Ch.12 의 해법

Ch.11 의 기본 MCMC (Gibbs, Metropolis) 는 임의 사후에서 샘플링을 가능하게 했지만, 여전히 무작위 보행의 느림이 있다. Figure 11.1, 11.2 에서 보이는 지그재그 패턴:

• \(\rho = 0.8\) 이변량 정규 Gibbs: 자기상관 시간 \(\tau_{\mathrm{ac}} \approx 3\) — 효율 36%.
• 고차원 상관 사후: \(\tau_{\mathrm{ac}}\) 가 수백~수천. 실용 불가.

Ch.12 는 이 한계를 세 축 으로 돌파.

Ch.12 의 세 축

1. 재매개변수화 (§ 12.1, 12.3) — 사후를 더 “샘플하기 쉬운” 좌표로 변환.
2. 점프 최적화 (§ 12.2) — Metropolis 의 step size 튜닝.
3. HMC (§ 12.4~12.6) — 무작위 보행 자체를 포기하고 물리 역학 활용.

앞 둘은 알고리즘 수정, 마지막은 교체.

1.1 Ch.12 의 구조

절	주제
12.1	Efficient Gibbs — 재매개변수화, 보조 변수, parameter expansion
12.2	Efficient Metropolis — \(c = 2.4/\sqrt{d}\), 수용률, 적응
12.3	Slice sampling, reversible jump
12.4	Hamiltonian Monte Carlo
12.5	HMC for hierarchical model
12.6	Stan
12.7	참고문헌
12.8	연습문제

1.2 직관 — 왜 HMC 가 혁명적인가

Gibbs 와 Metropolis 의 본질은 “주변 탐색 → 가끔 점프”. 지역적 무작위 보행이 전체 공간을 커버하려면 공간 대각선의 길이의 제곱 만큼의 단계 필요 (Brown 운동의 확산 시간).

HMC 는 모멘텀 을 추가해 일관된 방향으로 오래 이동. 물리 비유: 공을 던지면 Brown 운동보다 훨씬 빠르게 움직임. 고차원에서 이 차이가 수백~수천 배.

이 발견 (Duane et al. 1987, Neal 2011) 이 베이즈 통계를 뇌영상·유전체학·심리학의 수백~수천 모수 모형에 실용화.

2 § 12.1 — Efficient Gibbs Samplers

2.1 재매개변수화 — 상관 제거

Gibbs 가 느린 주된 원인: 사후 성분 간 상관. 해결: 독립에 가까운 좌표로 변환.

선형 변환: \(\phi = A\theta\) where \(A\) 는 사후 공분산의 고유벡터 행렬. 새 좌표에서 공분산 대각 → Gibbs 효율 최대.

실무: 사후 공분산 추정 → eigenvalue decomposition → Gibbs 좌표 변환.

2.2 Non-centered Parameterization

계층 모형의 funnel 문제 해결. 전통 (centered):

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

\(\tau\) 가 작아지면 \(\theta_j\) 공간이 깔대기 로 좁아져 MCMC 이동 곤란.

Non-centered:

\[ \eta_j \sim \mathrm{N}(0, 1), \quad \theta_j = \mu + \tau \eta_j \]

\(\eta_j\) 가 \((\mu, \tau)\) 와 독립. MCMC 는 \(\eta_j\) 공간에서 샘플.

직관 — Centered vs Non-centered 의 기하학

Centered: \(\theta_j\) 의 조건부 분포가 \((\mu, \tau)\) 에 강하게 의존 — \(\tau\) 작으면 \(\theta_j\) 영역 축소.

Non-centered: \(\eta_j\) 의 조건부 분포가 항상 표준 정규 — \((\mu, \tau)\) 가 바뀌어도 \(\eta_j\) 공간은 변화 없음.

8 학교 예제 에서 non-centered 가 종종 10 배 이상 빠름. Stan 이 자동 권장.

일반 원리: “데이터가 모수를 약하게 식별하는 층” 에서는 non-centered 가 유리.

2.3 보조 변수 — Data Augmentation

아이디어: 모형에 추가 변수 를 도입해 공액 구조 회복.

대표 예: \(t\) 분포를 정규 혼합으로.

\[ y_i \sim t_\nu(\mu, \sigma^2) \iff y_i \sim \mathrm{N}(\mu, V_i), \quad V_i \sim \mathrm{Inv}\text{-}\chi^2(\nu, \sigma^2) \tag{12.1} \]

\(V_i\) 를 잠재 변수 로 도입. 확장 모형 \(p(\mu, \sigma^2, V \mid y)\) 에서 Gibbs:

1. \(V_i \mid \mu, \sigma^2, y\): Inv-\(\chi^2\) 공액.
2. \(\mu \mid \sigma^2, V, y\): 정규 공액 (각 관측마다 다른 분산).
3. \(\sigma^2 \mid \mu, V, y\): Gamma.

\(t\) 분포의 “직접 샘플링 불가” 문제가 해결.

2.4 Parameter Expansion

더 큰 파라미터 공간에서 샘플링해 상관 해소. 역설적이지만 효과적.

\(t\) 모형 확장:

\[ y_i \sim \mathrm{N}(\mu, \alpha^2 U_i), \quad U_i \sim \mathrm{Inv}\text{-}\chi^2(\nu, \tau^2) \]

새 파라미터 \(\alpha\) 는 아이덴티티에 무관. \(\alpha^2 U_i = V_i\), \(\alpha \tau = \sigma\). 원래 모수와 1-to-many.

효과: Gibbs 가 \(\alpha\) 차원 자유도 활용해 stuck 상태 탈출. 특히 \(\sigma\) 가 0 근처일 때 중요.

3 § 12.2 — Efficient Metropolis Jumping Rules

3.1 최적 점프 스케일

이론 (Roberts, Gelman, Gilks 1997): 고차원 isotropic 정규 목표 + 정규 점프 하에서:

\[ J(\theta^* \mid \theta) = \mathrm{N}(\theta, c^2 \Sigma) \]

최적 \(c\):

\[ c^* = \frac{2.4}{\sqrt{d}} \]

이때 수용률 \(\approx 0.234\).

저차원 일반화:

• \(d = 1\): 수용률 \(\approx 44\%\).
• \(d \ge 5\): 수용률 \(\approx 23\%\).

\(\Sigma\) 선택: 사후 공분산 추정. Laplace 근사 또는 예비 MCMC.

직관 — 왜 \(2.4/\sqrt{d}\) 인가

고차원에서 점프 크기의 trade-off:

• 너무 작음: 공간 탐색 느림.
• 너무 큼: 대부분 거절 (낮은 밀도 영역 제안).

최적점: 제안의 평균 제곱 점프 거리 가 최대화되는 지점. 정규 목표 + 정규 점프에서 해석적으로 풀림 — \(c^* = 2.4/\sqrt{d}\).

실무: 초기 run 에서 수용률 측정 후 \(c\) 조정. 너무 낮으면 \(c\) 축소, 너무 높으면 확대. 현대 자동화 (Stan, PyMC 의 adapt) 가 이를 자동 수행.

3.2 Adaptive MCMC 의 이론적 주의

아이디어: \(c\) 를 반복 중에 자동 조정. 매우 매력적이지만 함정.

문제: 조정 과정이 Markov 성질 깨트림 — 정상 분포 보장 안 됨.

해결:

1. Warm-up 중에만 조정, 본 샘플링엔 고정.
2. Diminishing adaptation: \(c\) 변화 속도가 \(t \to \infty\) 에서 0 으로 수렴.
3. 검증된 알고리즘 만 사용 (Andrieu-Thoms 2008 의 theorem 준수).

Stan·PyMC 의 warm-up 단계가 이 원리. 수렴 후 adaptation 동결.

4 § 12.3 — 추가 확장

4.1 Slice Sampling

아이디어: 밀도 아래 영역에서 균등 추출.

\(u \mid \theta \sim \mathrm{Uniform}(0, p(\theta \mid y))\), \(\theta \mid u \sim \mathrm{Uniform}\{\theta : p(\theta \mid y) \ge u\}\).

결합 분포 \((u, \theta)\) 의 주변이 \(p(\theta \mid y)\). Gibbs 처럼 순환 샘플.

장점: 튜닝 없음, 수용률 1. 단점: “밀도 \(\ge u\) 인 영역” 찾기가 일반적으로 어려움 (다봉에서 까다로움).

대표 응용: WinBUGS/OpenBUGS 의 기본 샘플러 (Neal 2003).

4.2 Reversible Jump

차원 변하는 모형 간 이동. 예: 혼합 모형의 성분 수 \(K\) 를 미지로.

\((\theta_K, K)\) 결합 샘플링. MH 확장으로 \(K\) 증감 제안 + 차원 변경의 Jacobian 보정.

적용: 모델 평균화, 베이즈 비모수, 변화점 탐지.

5 § 12.4~12.6 — Hamiltonian Monte Carlo

5.1 HMC 의 핵심 아이디어

Gibbs·Metropolis 의 근본 한계: 무작위 보행 으로 탐색. 공간 대각선 건너가려면 \(O(d^2)\) 단계.

HMC 는 물리학에서 영감:

• \(\theta\) 를 입자 위치.
• 모멘텀 \(\phi\) 변수 추가.
• Hamiltonian 역학으로 \((\theta, \phi)\) 진화 → 에너지 보존된 궤적.

이 궤적이 일관된 방향 — 공간 대각선을 \(O(d)\) 단계에 건너감.

5.2 증강 사후

목표 분포를 확장:

\[ p(\theta, \phi \mid y) = p(\phi) \cdot p(\theta \mid y) \]

모멘텀 분포 \(p(\phi) = \mathrm{N}(0, M)\). \(M\) 은 “mass matrix” — 일반적으로 대각.

\(\phi\) 는 보조 변수: 샘플링만을 위한 도구, 관심 대상 아님.

5.3 Leapfrog Integrator

HMC 반복 핵심: 시간 \(t\) 동안 \((\theta, \phi)\) 를 Hamiltonian 방정식 따라 진화.

\[ \frac{d\theta}{dt} = M^{-1} \phi, \quad \frac{d\phi}{dt} = \frac{d \log p(\theta \mid y)}{d\theta} \]

연속 방정식을 이산 leapfrog 로 근사. 한 leapfrog step (크기 \(\epsilon\)):

(a) Half-step \(\phi\):

\[ \phi \leftarrow \phi + \frac{\epsilon}{2} \frac{d \log p(\theta \mid y)}{d\theta} \]

(b) Full-step \(\theta\):

\[ \theta \leftarrow \theta + \epsilon M^{-1} \phi \]

(c) Half-step \(\phi\):

\[ \phi \leftarrow \phi + \frac{\epsilon}{2} \frac{d \log p(\theta \mid y)}{d\theta} \]

\(L\) 번 반복 → 총 이동 \(L \epsilon\). 긴 궤적 가능.

5.4 HMC 한 반복의 구조

1. 모멘텀 재추출: \(\phi \sim \mathrm{N}(0, M)\) (이전 \(\phi\) 버림).
2. Leapfrog \(L\) 단계: \((\theta, \phi) \to (\theta^*, \phi^*)\).
3. Metropolis 수용:

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

\(\min(r, 1)\) 로 수용/기각.

5.5 왜 이게 작동하는가 — 에너지 보존

Leapfrog 는 연속 Hamiltonian 역학의 이산 근사. 연속 역학은 \(\log p(\theta, \phi \mid y)\) (전체 “에너지”) 보존.

이산에서는 \(\epsilon\) 크기 만큼 오차. \(\epsilon \to 0\) 에서 \(r \to 1\) — 항상 수용.

실무 \(\epsilon\): 수용률이 65~85% 되도록 조정. Gibbs (100%) 보다 낮지만 Metropolis (23%) 보다 훨씬 높으며, 한 반복의 이동 거리 가 훨씬 큼.

직관 — 왜 HMC 가 고차원에서 빠른가

Metropolis 의 random walk: 공간 대각선 \(R\) 을 \(O(R^2/\epsilon^2)\) 단계로 건너감.

HMC: 한 반복에 \(L \epsilon\) 거리 이동. 대각선 \(R\) 을 \(O(R/L\epsilon)\) 단계.

차이: random walk 는 \(R^2\), HMC 는 \(R\). 고차원에서 수백~수천 배.

물리 비유: 구름 속에서 길을 찾는 것과 비행기로 가는 것. Brown 운동 vs 직선 비행.

구체 수치: \(d = 1000\) 차원 정규 사후에서 Metropolis 는 수만 반복 필요, HMC 는 수백 반복으로 같은 효과.

5.6 튜닝 — \(M, \epsilon, L\)

HMC 의 3 파라미터.

파라미터	역할	설정
\(M\) (mass matrix)	공간 스케일	사후 공분산의 역수에 근사
\(\epsilon\) (step size)	이산화 정밀도	수용률 65~85% 목표
\(L\) (leapfrog steps)	궤적 길이	\(L \epsilon\) 이 공간 스케일 정도

수동 튜닝의 어려움: \(\epsilon, L\) 이 상호 의존. 너무 많은 \(L\) → 궤적이 U-turn 해 기각.

5.7 NUTS — No-U-Turn Sampler

Hoffman & Gelman (2014) 의 자동 튜닝 알고리즘.

아이디어: 궤적이 U-turn (원점으로 되돌아오기 시작) 하기 직전까지 \(L\) 자동 조정. 각 반복의 \(L\) 이 다름.

알고리즘 (간략):

1. Leapfrog 양방향 (시간 앞뒤) 확장.
2. 궤적의 양 끝이 수렴하기 시작하면 중단.
3. 전체 궤적에서 무작위 선택으로 다음 표본.

결과: \(\epsilon\) 만 warm-up 에서 조정, \(L\) 자동. Stan 의 기본 알고리즘.

5.8 § 12.5 — HMC 계층 정규

8 학교 모형에 HMC 적용. Centered \(\theta_j \sim \mathrm{N}(\mu, \tau^2)\) 에서 funnel 문제 발생.

해결: Non-centered \(\eta_j \sim \mathrm{N}(0, 1), \theta_j = \mu + \tau \eta_j\). HMC 는 이 변환된 공간에서 매끄럽게 작동.

수치: 8 학교에서 centered HMC 는 divergent transitions 많음, non-centered HMC 는 안정적.

5.9 § 12.6 — Stan

Stan (Stanislaw Ulam 에서 명명): HMC/NUTS 기반 범용 베이즈 추론 소프트웨어.

구성:

• 모델 언어: Bugs 와 유사, 하지만 정적 타이핑.
• C++ 백엔드: 고속.
• 자동 미분 (autodiff): \(d \log p / d\theta\) 를 해석적으로 계산 (chain rule).
• 인터페이스: R (rstan, cmdstanr), Python (PyStan, cmdstanpy), Julia.

Gelman 의 평가: “Stan 으로 우리가 작성·적합하는 모형의 복잡도가 10 년 전에는 불가능했던 수준.”

5.10 자동 미분의 중요성

HMC 의 핵심 요구: 기울기 \(\nabla \log p(\theta \mid y)\).

수치 미분: \(d\) 차원에 \(d+1\) 회 함수 평가 → \(d \gg 100\) 에서 너무 느림.

자동 미분: 계산 그래프 역전파. 1 회 함수 평가의 상수배 비용.

이게 Stan 의 핵심 성능 이점.

6 통합 관점 — MCMC 알고리즘 지도 (확장판)

Ch.11 의 선택 지도에 Ch.12 의 진보 추가.

알고리즘	조건	상대 속도	튜닝
Gibbs (naïve)	조건부 공액	1	없음
Gibbs + 재매개변수화	상관 제거 가능	2~10	중간
Metropolis (random walk)	임의 사후	0.3	\(c\) 조정
Metropolis + 적응 \(c\)	임의 사후	0.5	자동
HMC (수동 튜닝)	미분 가능	10~100	어려움
HMC + NUTS	미분 가능	10~100	자동
변분 추론 (Ch.13)	대규모	100+	근사 편향

실무 추천: 기본으로 Stan/PyMC NUTS. 특수 문제에서만 수동.

7 응용 분야

분야	Ch.12 도구의 역할
계층 회귀	Non-centered HMC 표준
역학·유전체	수천 모수 GLM — Stan 없이 불가능
경제학	DSGE, 상태 공간 모형
심리 측정	IRT, 다단 요인 분석
뇌영상	fMRI 시공간 분석
공간 통계	Gaussian process, CAR
네트워크	ERGM, dynamic graphs
기계 학습	Bayesian neural networks (소규모)

8 실전 체크리스트

MCMC 효율 개선 12 단계.

1. Stan/PyMC 기본 — 수동 구현 피하기.
2. \(\log p\) 로 작업 — HMC 도 overflow 방지.
3. 자동 미분 활용 — Stan autodiff.
4. Non-centered 먼저 시도 — 계층 모형 표준.
5. Mass matrix \(M\) — 사후 공분산 역수 근사.
6. \(\epsilon\) 수용률 65~85% — NUTS 자동.
7. Divergent transitions 모니터 — funnel 경고.
8. \(\hat{R}, n_{\mathrm{eff}}\) 확인 — Ch.11 의 진단은 그대로.
9. Warm-up 1000~2000 — Stan 기본.
10. 여러 체인 — 병렬 실행.
11. Posterior predictive 점검 — Ch.6 의 검증.
12. 수렴 안 하면 재매개변수화 — Ch.12.1 의 기법.

9 관련 주제

선행 지식

• Ch.11 Overview (02-11-0) — MCMC 기초
• Ch.10 Overview (02-10-0) — Bayesian computation 출발점
• Bayesian Part III 개관 — Ch.10~13 지도

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

• 02-12-1-* — § 12.1~12.3 심화 (재매개변수화·auxiliary·slice)
• 02-12-2-* — § 12.4~12.6 심화 (HMC leapfrog·NUTS·Stan 상세)
• 02-12-3-* — § 12.7~12.8 심화 (문헌·연습)

후속 주제

• Ch.13 Variational Inference — MCMC 대안 근사
• Ch.15 Hierarchical Linear Models — HMC 본격 활용
• Ch.22 Finite Mixture Models — reversible jump 응용

관련 개념

• Duane, Kennedy, Pendleton, Roweth (1987) — HMC 원저 (물리학)
• Neal (2011), MCMC using Hamiltonian Dynamics — 통계학 도입
• Hoffman & Gelman (2014) — NUTS
• Carpenter et al. (2017) — Stan
• Betancourt (2017) — A Conceptual Introduction to HMC
• Papaspiliopoulos, Roberts, Sköld (2007) — Non-centered parameterization
• Roberts, Gelman, Gilks (1997) — 최적 수용률 이론
• Neal (2003) — Slice sampling
• Green (1995) — Reversible jump MCMC
• Andrieu & Thoms (2008) — Adaptive MCMC 이론