728x90 반응형 스터디/확률과 통계56 [Sampling] Markov Chain Monte Carlo (MCMC) (3) - Gibbs sampling Gibbs SamplingGibbs sampling은 MCMC 기법 중에서 Metropolis-Hastings 알고리즘의 특수한 형태이다.확률변수가 다음과 같을 때 사용할 수 있다.$x = [x_1, x_2, \dots, x_d]^\top$이고 target distribution이 $p(x)$일 때 다음을 만족하면 Gibbs sampling을 적용할 수 있다.\[ x_i \sim p(x_i | x_1, \dots, x_{i-1}, x_{i+1}, \dots, x_d) \]$x_i$가 $x \setminus x_i$ condition에서 샘플링되는 조건이다.Gibbs sampling algorithm랜덤하게 $x^{(1)}$를 초기화한다.for $t=1, \dots$ do $x^{(t+1)} = x^.. 2023. 10. 14. [Sampling] Markov Chain Monte Carlo (MCMC) (2) - Metropolis-Hastings Algorithm Metropolis-HastingsMCMC에서 가장 많이 사용되는 알고리즘 중 하나이다.임의의 target distribution에 대하여 이 알고리즘을 적용할 수 있다는 것이 장점이다.물론 proposal distribution $q(x'|x)$와 unnormalized distribution $\tilde{p}(x)$는 필요하다.그러나 full target distribution $p(x)$는 필요하지 않다.이 알고리즘의 퀄리티는 proposal distribution $q(x'|x)$에 달려있다. Metropolis-Hastings Algorithm$x^{(1)}$을 랜덤하기 초기화한다.for $t=1, \dots$ do Propose $x' \sim q(x'|x^{(t)})$ accep.. 2023. 10. 4. [Sampling] Markov Chain Monte Carlo (MCMC) (1) - Markov chains Motivation(앞에서와 마찬가지로) Monte-Carlo method로 기댓값을 근사하고 싶다.\[ \cfrac{1}{n} \sum_{i=1}^{n} f(x_i) \overset{\text{a.s.}}{\to} \mathbb{E}_{p(x)}[f(x)], \quad x_1, \dots, x_n \overset{\text{i.i.d.}}{\sim} p(x) \] rejection sampling과 importance sampling은 $p(x)$ 대신 샘플링이 쉬운 $q(x)$를 이용했다. (indirectly sample from distributions easier to sample) 그러나 i.i.d. 샘플링은 고차원 데이터(high-dimensional data)에는 적합하지 않다. 이전 샘플.. 2023. 9. 28. [Sampling] Importance Sampling Motivation여태 샘플링 기법을 배운 이유는, 기댓값을 계산(혹은 근사)하기 위한 단계였다.\[ \mathbb{E}_{p(x)}[f(x)] \approx \cfrac{1}{m}\sum_{s=1}^{m} f(x_s), \quad x_1, \dots, x_m \overset{\text{i.i.d.}}{\sim} p(x) \] 그렇다면, 샘플링 없이 $p(x)$로부터 직접 기댓값을 구할 수 있는 방법은 없을까? Importance Sampling (IS)Method$q(x)$는 proposal distribution으로 샘플링이 쉬운 분포라 하자.그리고 $q(x)=0$이면 $p(x)=0$이고, $q(x) \neq 0$이면 역시 $p(x) \neq 0$라 하자. (비율을 정의하기 위함)그러면 기댓값은 다음.. 2023. 9. 27. [Sampling] Rejection Sampling Rejection SamplingIntroduction이제 샘플링 할 분포가 간단한 분포함수가 아니고 매우 복잡한 분포라고 하자. 심지어 적분도 쉽지 않다면 정규화 상수도 구할 수 없다.베이지안으로 예를 들면, posterior를 계산할 때 이런일이 발생한다.\[ p(\theta | X) = \cfrac{p(X | \theta) p(\theta)}{p(X)} \]이때 분모의 $p(X)$는 marginal을 구하는 것인데 $p(X) = \int p(X, \theta) d \theta$를 구하는 것은 많은 경우에 불가능하다. 일반적인 notation으로, 우리가 알고 있는 분포(PDF가 아니어도 된다.)를 $\tilde{p}(x)$라 하고, 적분값이 $1$이 되도록하는 정규화상수를 $Z$라 한다. 이때 ta.. 2023. 9. 26. [Sampling] Sampling from standard distributions Why sampling is important?bayesian inference는 기댓값은 계산하는 방법이다. (discrete한 경우엔 적분이 아니라 합계가 된다.)\[ \mathbb{E}_{p(\theta | X)}[f(\theta)] = \int f(\theta) p(\theta | X) d\theta \] 그러나 위 정의대로 정확히 계산하는 것은 불가능(exact inference is intractable)한 경우가 많기 때문에, 우리는 Monte Carlo method를 이용하여 기댓값을 근사한다.\[ \mathbb{E}_{p(\theta | X)}[f(\theta)] \approx \cfrac{1}{m}\sum_{s=1}^{m}f(\theta_s), \quad \theta_1, \dots \.. 2023. 9. 25. 이전 1 2 3 4 5 6 ··· 10 다음 728x90 반응형