Post

Posterior Estimation (1) Monte Carlo Simulation

Based on the lecture “Bayesian Modeling (2024-1)” by Prof. Yeo Jin Chung, Dept. of AI, Big Data & Management, College of Business Administration, Kookmin Univ.

Posted
Preview Image
By jayarnim
11 min read

Monte Carlo Simulation

  • 정의 : 복잡한 시스템이나 수학적 문제의 결과를 예측하기 위해 확률적 샘플링을 사용하는 방법

  • 절차 : 무작위 샘플을 반복 생성하여 문제의 수치적 근사치를 얻음

    • 문제 정의 : 해결하려는 문제를 수학적 모형으로 정의함
    • 확률분포 설정 : 변수들에 대한 무작위 샘플을 생성하기 위해 각 변수들의 확률분포를 설정함
    • 샘플링 : 설정된 확률분포에서 무작위 샘플을 반복하여 추출함
    • 모형 계산 : 각 샘플을 모형에 투입하여 결과를 계산함
    • 결과 분석

example 원주율 구하기

한 변의 길이가 2인 정사각형 내부에 점을 무작위로 찍었을 때, 그 점이 정사각형에 내접하는 원의 내부에 위치할 확률 실험을 전개하여, 원주율 $\pi$ 를 추론하시오.

  • 좌표평면 상에서 주어진 조건을 만족하는 원
    • 정의 : \(C = \{ (x, y) \mid x^2 + y^2 = r^2 \}\)
    • 면적 : $\pi r^2 = \pi \quad (\because 2r=2)$
  • 좌표평면 상에서 주어진 조건을 만족하는 정사각형
    • 정의 : $R = { (x, y) \mid -1 \le x \le 1, -1 \le y \le 1} $
    • 면적 : $(2r)^2=4$

  • 정사각형 내부에 점을 무작위로 찍었을 때, 점이 원 내부에 위치할 가능성

    \[\begin{aligned} P((x,y) \in C) &=\displaystyle\frac{N_{circle}}{N}\\ &=\displaystyle\frac{\pi r^2}{(2r)^2}\\ &=\displaystyle\frac{\pi}{4} \end{aligned}\]
    • $N$ : 실행 횟수
    • $N_{circle}$ : 성공 횟수(원 내부에 위치한 횟수)

  • Monte Carlo Simulation 을 통한 $\pi$ 추론값 도출

    01

    • 실행 횟수(num)가 증가할수록 $\pi$ 의 추론값이 $3.141592\cdots$ 에 근접해감

Rejection Sampling

02

  • 정의 : 제안 분포로부터 추출한 관측치를 적절하게 거절하는 과정을 반복하여 표본 분포를 목표 분포와 유사한 형태로 만드는 방법

  • 절차
    • 제안 분포 $q(\psi)$ 로부터 파라미터 $\psi$ 샘플링

    • 목표 분포 $p(\theta \mid \mathcal{D})$, 제안 분포 $q(\psi)$, 스케일링 팩터 $M$ 에 대하여, 다음 조건을 만족하지 않으면 $\psi$ 를 샘플로 채택하지 않음

      \[u \le \displaystyle\frac{p(\psi \mid \mathcal{D})}{M \cdot q(\psi)} \quad \text{s.t.} \quad u \sim \text{Uniform}(0,1)\]

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

    \[p(\theta \mid \mathcal{D}) \propto p(\mathcal{D} \mid \theta) \cdot p(\theta)\]
    • $\theta$ : 파라미터
    • $p(\mathcal{D} \mid \theta)$ : 파라미터 $\theta$ 의 우도 함수
    • $p(\theta)$ : 파라미터 $\theta$ 의 사전 확률 분포

  • 제안 분포(Proposal Dist.)

    \[q(\psi)\]
    • $\psi$ : 파라미터로서 고려되는 샘플
    • $q(\psi)$ 는 $p(\psi \mid \mathcal{D})$ 와 위치 및 분포가 비슷해야 함
    • 상수 $M$ 에 대하여, $p(\psi \mid \mathcal{D}) \le M \cdot q(\psi)$ 를 만족해야 함

  • 거절 확률(Rejection Prob.)

    \[\frac{p(\psi \mid \mathcal{D})}{M \cdot q(\psi)} \propto \frac{p(\mathcal{D} \mid \psi) \cdot p(\psi)}{M \cdot q(\psi)}\]

Markov Chain Monte Carlo

03

  • Markov Chain Monte Carlo(MCMC)
    • 정의 : 이전 단계에서 추출한 표본을 기반으로 다음 단계의 표본을 순차로 추출하는 방법
    • 장점 : 차원이 높아질수록 표본 분포가 목표 분포로 수렴하는 속도가 지연되는 문제를 완화함
    • 단점 : 모든 표본($x^{(t)}$)이 이전 단계에서 추출한 표본($x^{(t-1)}$)에 의존함
    • 종류
      • Metropolis Hastings Method
      • Gibbs Sampling

Markov Chain

  • 정의 : 어떤 시스템에 대하여 해당 시스템이 상태 공간 $S$ 에서 이산적인 시점($t=0,1,2,\cdots$)에서만 상태 전이가 발생한다고 했을 때, 이 시스템이 마르코프 성질을 만족한다면, 이 시스템은 마르코프 체인이라고 볼 수 있음

    • 마르코프 성질 : 미래의 상태가 현재 상태에만 의존하며 과거의 상태는 고려하지 않는 성질

      \[\begin{aligned} P(X_{n+1}=j \mid X_{n}=i,X_{n-1}=i_{n-1},\cdots,X_{0}=i_{0}) = P(X_{n+1}=j \mid X_{n}=i) \end{aligned}\]
      • $X_{n}$ : 시점 $n$ 에서 시스템이 취하는 상태
      • $i,j \in S$ : 특정 상태

  • 전이확률행렬(Transition Probability Matrix) : 각 상태에서 다른 상태로의 전이 확률을 나타내는 행렬

    \[\mathbf{P}_{n \times n} = \{p_{i,j} \mid i,j \in n, p_{i,j} \in S\}\]

    • $p_{i,j} \in S$ : 상태 $i$ 에서 $j$ 로의 전이확률

      • $0 \le p_{i,j} \le 1$
      • $\sum_{j}{p_{i,j}}=1$ : 상태 $i$ 에서 다른 상태로 전이될 확률의 합은 1임

  • 정상확률(Steady-State Probability; $\pi_{j}$) : 마르코프 체인이 장기적으로 상태 $j$ 를 취할 확률

    \[\pi_{j}=\sum_{i}{\pi_{i}\cdot p_{i,j}}\]
    • 상태 $j$ 의 정상확률 $\pi_{j}$ 는 상태 $i$ 에서 $j$ 로 전이할 확률의 기대값($E(x)=\sum{x\cdot P(x)}$)임

  • 정상확률분포(Steady-State Probability Distribution; $\overrightarrow{\pi}$) : 마르코프 체인이 각 상태를 취할 확률이 시간에 따라 변하지 않고 일정하게 유지되는, 장기적인 확률 분포

    \[\overrightarrow{\pi}=\overrightarrow{\pi}\cdot\mathbf{P}\]

Metropolis Hastings Method

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

  • 절차

    • 특정 위치에서 샘플링 시작하기

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

    • 근방의 조약돌 분포를 조사하여 새로 이동할 위치 $\psi$ 탐색하기

      \[\psi=\theta^{(t)}+\varepsilon \quad \text{s.t.} \quad \varepsilon \sim N(0, \sigma^2)\]

    • 새로운 조약돌이 해당 위치 $\psi$ 에서 발견될 가능성을 조사하여 해당 위치를 수락할지 판단하기

      \[\theta^{(t+1)} =\begin{cases}\begin{aligned} \psi, \quad &\text{if} \; 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)})\]
    • $\theta^{(t)}$ : $t$ 번째 파라미터
    • $p(\theta^{(t)})$ : 파라미터 $\theta^{(t)}$ 의 사전 확률 분포
    • $p(\mathcal{D} \mid \theta^{(t)})$ : 파라미터 $\theta^{(t)}$ 의 우도 함수

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

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

    • 제안 분포가 $\theta^{(t)}$ 을 중심으로 하는 종형 분포인 경우, 다음을 만족함

      \[q(\psi \mid \theta^{(t)}) = q(\theta^{(t)} \mid \psi)\]
      • $q(\psi \mid \theta^{(t)})$ : 시점 $t$ 에서 조약돌을 수집한 위치가 $\theta^{(t)}$ 일 때, 다음 시점 $t+1$ 에서 조약돌을 수집할 위치가 $y$ 일 가능성
      • $q(\theta^{(t)} \mid \psi)$ : 시점 $t-1$ 에서 조약돌을 수집한 위치가 $\psi$ 일 때, 다음 시점 $t$ 에서 조약돌을 수집할 위치가 $\theta^{(t)}$ 일 가능성

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

      04

  • 수락 확률(Acception Prob.) : $\psi$ 를 다음 시점 $t+1$ 에서 조약돌을 수집할 위치 $\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 \mid \theta^{(t)} \sim 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}\]
    • $p(\psi \mid \mathcal{D}) \propto p(\psi) \cdot p(\mathcal{D} \mid \psi)$ : 목표 분포 $p$ 에 대하여 샘플 $\psi$ 의 사후 확률로서, 다음 시점에서 조약돌을 수집할 위치가 $\psi$ 일 가능성
    • $p(\theta^{(t)} \mid \mathcal{D}) \propto p(\theta^{(t)}) \cdot p(\mathcal{D} \mid \theta^{(t)})$ : 목표 분포 $p$ 에 대하여 $t$ 번째 파라미터 $\theta^{(t)}$ 의 사후 확률로서, 다음 시점에서 조약돌을 수집할 위치가 $\theta^{(t)}$ 일 가능성

Auto-Correlation

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

    05

    • $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)

      06

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

    07

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

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

    08

이미지 출처

  • https://www.statlect.com/fundamentals-of-statistics/Markov-Chain-Monte-Carlo
Statistical Techs, Bayesian Modeling
Statistics Bayesian Rejection Sampling Markov Chain Monte Carlo Markov Chain Monte Carlo Simulation
This post is licensed under CC BY 4.0 by the author.