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) 또는 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 p~(x)는 필요하다.그러나 full target distribution p(x)는 필요하지 않다.이 알고리즘의 퀄리티는 proposal distribution q(x′|x)에 달려있다. Metropolis-Hastings Algorithmx(1)을 랜덤하기 초기화한다.for t=1,… do Propose x′∼q(x′|x(t)) accep.. 2023. 10. 4. [Sampling] Markov Chain Monte Carlo (MCMC) (1) - Markov chains Motivation(앞에서와 마찬가지로) Monte-Carlo method로 기댓값을 근사하고 싶다.1n∑i=1nf(xi)→a.s.Ep(x)[f(x)],x1,…,xn∼i.i.d.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여태 샘플링 기법을 배운 이유는, 기댓값을 계산(혹은 근사)하기 위한 단계였다.Ep(x)[f(x)]≈1m∑s=1mf(xs),x1,…,xm∼i.i.d.p(x) 그렇다면, 샘플링 없이 p(x)로부터 직접 기댓값을 구할 수 있는 방법은 없을까? Importance Sampling (IS)Methodq(x)는 proposal distribution으로 샘플링이 쉬운 분포라 하자.그리고 q(x)=0이면 p(x)=0이고, q(x)≠0이면 역시 p(x)≠0라 하자. (비율을 정의하기 위함)그러면 기댓값은 다음.. 2023. 9. 27. 이전 1 2 다음 728x90 반응형
