728x90 반응형 sampling9 [Sampling] Markov Chain Monte Carlo (MCMC) (5) - Diagnosis MCMC diagnosis: convergence, correlations, CLT, effective sample size (ESS) MCMC: Pros and Cons(+) high dimensional data에서 잘 동작한다.(+) Metropolis-Hastings 알고리즘과 같이 general-purpose sampler로 확장이 쉽다(+) 구현이 쉬운 편이다(-) sequential한 성질 때문에 대규보 데이터로 확장이 어렵다 (not really scalable)(-) 어떤 chain이 target distribution에 도달하는지 명확하지 않다.(-) 수렴 지표가 명확하지 않다.그렇다면 무엇이 더 좋은 MCMC 알고리즘으로 만들까?좋은 MCMC는, high-density 영역에 오래 머.. 2024. 3. 19. [CS246] Sampling from a Data Stream Fixed-proportion, Fixed-size, Reservoir SamplingIntroductiondata stream은 전체 데이터를 저장할 수 없기 때문에, 샘플링을 이용한다.크게 2가지 방법이 있는데, fixed proportion 방법과 random sample of fixed size이다. Sampling a Fixed Proportiondata stream의 일정 비율(예를 들어 10% 등)만큼 샘플링하는 것이다. stream이 커질수록 sample 역시 커진다. Problem with Naive Approachstream data가 (user, query, time)이라는 tuple의 형태로 들어온다고 할 때, unique query의 비율을 추정해보자. 이때 당연히 중복되는 que.. 2023. 12. 4. [Sampling] Markov Chain Monte Carlo (MCMC) (4) - Slice sampling Slice Samplingproposal distribution 없이 $p(x)$ 또는 $\tilde{p}(x)$로부터 직접 샘플링하는 방법이다.일반적으로 univariate multi-modal distribution에 유용하다.(논문저자 Radford M. Neal에 따르면 multivariate의 경우에도 slice sampling을 변형하여 샘플링 할 수 있다. 여기서는 생략) Algorithmslice variable $u$를 도입한다. (책에 따라 auxiliary variable, additional variable이라고도 한다.)\[ p(x,u) = \cfrac{\mathbf {1}_{ \{ 0 \le u \le \tilde{p}(x) \} } }{Z}, \ \int_0^{\tilde{p}.. 2023. 10. 15. [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. 이전 1 2 다음 728x90 반응형
