728x90 반응형 전체 글266 [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. [CS246] CURE Algorithm: Extension of k-means to clusters of arbitrary shapes Motivationk-mean과 BFR 알고리즘은 convex하거나 fixed-axis와 같은 클러스터 shape에 여러 가정이 있었다.CURE 알고리즘은 이러한 cluster shape에 어떠한 가정을 하지 않고 유클리드 거리만을 가정한다. 데이터가 정규분포일 필요도 없고, 고정된 축일 필요도 없다. 따라서 centroid 개념도 필요하지 않다. 대신에, collection of representative points가 클러스터의 표현을 나타낸다.클러스터 개수는 $k$개라고 가정한다. CURE는 Clustering Using REpresentatives의 앞글자를 따온 것이고, 원래 논문의 제목은 "CURE: An Efficient Clustering Algorithm for Large Databas.. 2023. 10. 2. [CS246] BFR Algorithm: Extension of k-means to large data Motivationk-mean 알고리즘은 모든 데이터를 메모리에 올리고 클러스터링 알고리즘을 수행한다.그러나 현실세계의 데이터는 너무 커서(데이터베이스로 관리 등) 메인메모리에 올릴 수 없다.BFR 알고리즘을 매우 큰 데이터(disk-resident data sets)에 k-mean 클러스터링을 적용하는 알고리즘이다. BFR은 논문의 세 저자 Paul S. Bradley, Usama M. Fayyad, Cory A. Reina의 앞글자를 딴 것이다.(논문: Scaling Clustering Algorithms to Large Database)BFR OverviewAssume모든 클러스터는 axis-aligned ellipse이다. (그러나 각 axis마다 표준편차가 다른 것은 허용된다)Ideadata p.. 2023. 10. 1. Python의 round는 사사오입? 오사오입? 초등학교와 중학교에서 배운 반올림은 5이상에서 올리고, 5미만에서 버린다. 사사오입이라고도 부른다.파이썬에서 반올림은 `round` 함수가 있는데, 사사오입이 아니라 오사오입이다. (banker's rounding이라고도 한다)※ 올림과 버림은 음수로 오면 헷갈리기 쉽다. 수학적으로 각각 ceil과 floor이다.※ 반올림의 수학적 표현은 floor(x+0.5) 이다. 이게 무엇인가 하면, 5미만은 버림, 5초과에서 올린다. 5의 경우 앞자리가 짝수면 버리고, 홀수면 올린다.예를 들면, 2.5의 경우 5의 앞자리가 2인 짝수로 버린다. 즉 round(2.5)=2 이다.3.5의 경우, 5의 앞자리가 3인 홀수로 올린다. 즉 round(3.5)=3 이다. 음수의 경우, 절댓값에 반올림을 적용하고, 다시 음수.. 2023. 10. 1. [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 ··· 11 12 13 14 15 16 17 ··· 45 다음 728x90 반응형
