Markov Chain Monte Carlo

Markov Chain Monte Carlo

---

• 마르코프 체인 몬테 카를로(Markov Chain Monte Carlo) : 이전 단계에서 추출한 표본을 기반으로 다음 단계의 표본을 순차로 추출하는 방법으로서, 차원이 높아질수록 표본 분포가 목표 분포로 수렴하는 속도가 지연되는 문제를 완화하나, 자기상관 문제에서 자유롭지 못하고 역전파 학습이 불가능함

  • Metropolis Hastings Method
  • Gibbs Sampling

Metropolis Hastings Method

---

• 메트로폴리스 헤이스팅스 방법(Metropolis Hastings Method) : 목표 분포의 산 모양을 추정하기 위하여, 확률 밀도가 높은 지역일수록(봉우리가 높은 지역일수록) 그 근방에서 더 많은 조약돌을 모으는 방법

  • inital sample:

    \[\theta^{(t=0)}\]

  • sampling candidate state $\psi$:

    \[\psi \sim \mathcal{N}(\theta^{(t)},\sigma^2)\]

  • conditional acceptance:

    \[\theta^{(t+1)} =\begin{cases}\begin{aligned} \psi, \quad &\text{if} \quad u<\alpha(\theta^{(t)},\psi) \quad \text{for} \quad u \sim \text{Uniform}(0,1)\\ \theta^{(t)}, \quad &\text{otherwise} \end{aligned}\end{cases}\]

• 목표 분포(Target Dist.) : 파라미터 $\theta^{(t)}$ 의 사후 확률 분포

  \[p(\theta^{(t)}\mid \mathcal{D}) \propto p(\theta^{(t)}) \cdot p(\mathcal{D} \mid \theta^{(t)})\]

• 제안 분포(Proposal Dist.) : 시점 $t$ 에서 수락된 파라미터 샘플 $\theta^{(t)}$ 에 기반하여 다음 시점 $t+1$ 에서 샘플링 위치 $\psi$ 를 제안하는 분포

  \[q(\psi \mid \theta^{(t)}) = \mathcal{N}(\theta^{(t)},\sigma^2)\]

  • 제안 분포가 $\theta^{(t)}$ 을 중심으로 하는 종형 분포인 경우:

    \[q(\psi \mid \theta^{(t)}) = q(\theta^{(t)} \mid \psi)\]

  • $\sigma^2$ 의 크기와 샘플링 수렴 여부의 관계:

    

• 수락 확률(Acceptance Prob.) : $\psi$ 를 다음 시점의 샘플 $\theta^{(t+1)}$ 로 수락할 확률

  \[\begin{aligned} \alpha(\theta^{(t)}, \psi) &= \min{\left[1, \frac{p(\psi \mid \mathcal{D})}{p(\theta^{(t)} \mid \mathcal{D})} \cdot \frac{q(\theta^{(t)} \mid \psi)}{q(\psi \mid \theta^{(t)})}\right]}\\ &= \min{\left[1, \frac{p(\psi \mid \mathcal{D})}{p(\theta^{(t)} \mid \mathcal{D})}\right]} \quad \text{s.t.} \quad \psi \sim \mathcal{N}(\theta^{(t)},\sigma^2)\\ &\propto \min{\left[1, \frac{p(\psi) \cdot p(\mathcal{D} \mid \psi)}{p(\theta^{(t)}) \cdot p(\mathcal{D} \mid \theta^{(t)})}\right]} \end{aligned}\]

Auto-Correlation

---

• 자기상관(Auto-Correlation) : 순차로 발생한 일련의 관측치 ${x^{(t)} \mid t\text{ is time point}}$ 간에 존재하는 상관관계

  

  • $x^{(t)} \sim N(0,1) \quad \text{for} \quad x^{(0)} = 0$
  • $y^{(t)} \sim N(y^{(t-1)},1) \quad \text{for} \quad y^{(0)} = 0$

• 자기상관계수(Auto-Correlation Coefficient) : 순서에 의미가 있는 데이터에서, 현재 시점의 값 $x^{(t)}$ 과 그 과거 또는 미래의 값 $x^{(t-k)}$ 간의 상관관계를 측정하는 지표

  \[R(k)=\text{Corr}(x^{(t)},x^{(t-k)})\]

  • $k$ : 시간 간격(Lag)

    

• 솎아내기(Thinning) : 매 $k$ 번째 표본을 선택함으로써 자기상관을 줄이는 방법

  

  • 통상 $k \le 10$ 으로 설정함

• 선행 구간(Burn-in Period) : 수렴 상태에 도달하기 전, 초기값 $x^{(t=0)}$ 의 영향력을 최소화하기 위해 일부 반복을 무시하는 구간

  

---

Source

• https://www.statlect.com/fundamentals-of-statistics/Markov-Chain-Monte-Carlo