본문 바로가기
728x90
반응형

전체 글266

[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 MeasuresAxioms 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 FamilyMeanings of Sensitivity Valuesfamily 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{sim}(.. 2023. 9. 22.
[CS246] Finding Similar Items (4) - Locality Sensitive Hashing (LSH) Recap: Shingling and Minhashing$k$-shinglesdocument를 set으로 매핑. 아래 표는 $k=3$인 경우의 예시다.Jaccard Similarity두 집합의 유사도를 구하는 방법 중 하나.$J(S, T) = \text{sim}(S, T) = \cfrac{|S \cap T|}{S \cup T}$$\text{sim}(S_1, S_3) = \cfrac{2}{3}$ Minhashrow의 random permutation을 하나 고르고, 처음으로 1이 나오는 row index를 minhash value로 한다.$h(S_1)=0,\ h(S_2)=2,\ h(S_3)=1$$\Pr(\text{minhash is same}) = \text{Jaccard Similarity}$Locali.. 2023. 9. 21.
[CS246] Finding Similar Items (3) - Minhashing Jaccard Similarity자카드 유사도는 두 집합의 유사도를 구하는 방법 중 하나이다.두 집합 $A,\ B$의 자카드 유사도를 구하면 다음과 같다.\[ J(A,\ B) = \cfrac{|A \cap B|}{ |A \cup B| } = \cfrac{|A \cap B|}{|A| + |B| - |A \cap B|} \] ※ 자카드 거리(Jaccard distance)는 $d_J(A,\ B) = 1 - J(A,\ B)$ 이다.※ IoU(Intersection over Union) 과 식이 유사하지만 보통 IoU는 region, bounding box 에서 사용되는 용어이다. 자카드 유사도는 앞서 설명한 characteristic matrix의 column similarity를 계산하는데 사용된다. (컬럼.. 2023. 9. 20.
728x90
반응형

티스토리툴바