[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.
