본문 바로가기
728x90
반응형

분류 전체보기249

[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.
[CS246] Finding Similar Items (6) - LSH Family for Cosine Distance 이전까지 LSH를 구할 때 자카드 유사도를 이용했다. 이번 포스트에서는 여러가지 유클리드/비유클리드 distance를 소개하고, 코사인 거리를 이용한 LSH를 알아보자. ※ 정확히는 자카드 유사도는 거리는 아니다. (자카드 거리) = 1 - (자카드 유사도) 이다. Distance Measures Axioms of a Distance Measure $d$가 아래 4가지 조건을 충족하면 distance measure(거리 측도)라고 한다. $d(x, y) \ge 0$ $d(x,y)=0 \text{ iff } x=y$ $d(x, y) = d(y,x)$ (symmetric, 대칭성) $d(x,y) \le d(x,z) + d(z,y)$ (triangle inequality, 삼각부등식) 다양한 유클리드/비유클리.. 2023. 9. 23.
[CS246] Finding Similar Items (5) - LSH Family Locality-Sensitive Family Meanings of Sensitivity Values family of $F$ of function은 다음을 만족하면 $(d_1, d_2, p_1, p_2)$-sensitive라고 부른다. 모든 함수 $f \in F$와 점 $x,y$에 대하여 $d(x,y) \le d_1$이면, $f(x)=f(y)$일 확률은 최소 $p_1$이다. $d(x,y) \ge d_1$이면, $f(x)=f(y)$일 확률은 최대 $p_2$이다. $d$가 Jaccard distance라면 $d = 1-\text{sim}(x,y)$이므로 $d(x,y) \le d_1 \Rightarrow 1 - \text{sim}(x, y) \le d_1 \Rightarrow 1 - d_1 \le \text.. 2023. 9. 22.
728x90
반응형

티스토리툴바