[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(거리 측도)라고 한다.

1. $d(x, y) \ge 0$
2. $d(x,y)=0 \text{ iff } x=y$
3. $d(x, y) = d(y,x)$ (symmetric, 대칭성)
4. $d(x,y) \le d(x,z) + d(z,y)$ (triangle inequality, 삼각부등식)

다양한 유클리드/비유클리드 거리가 있지만, 이번 포스팅에서는 코사인 거리만 간단히 소개한다.

Cosine Distance

$n$차원인 두 벡터 $x=[x_1, \dots, x_n]$ $y=[y_1, \dots, y_n]$에 대하여 코사인 거리는 두 벡터가 이루는 각으로 정의한다. 

\[ d(x, y) = \theta = \cos^{-1}\left( \cfrac{x \cdot y}{\| x \| \| y \|} \right) \]

※ Angular distance 이지만, CS246과 MMDS에서는 이것을 코사인 거리로 정의하고 있다.

※ Wiki에서 정의한 angular distance는 다음과 같다: $D_{\theta}=\cfrac{\arccos(\text{cosine similarity})}{\pi} = \cfrac{\theta}{\pi}$

LSH Family for Cosine Distance

Random Hyperplanes

코사인 거리를 이용하면 minhashing으로 signature를 생성하는 것과 비슷한 테크닉을 구현할 수 있다. 이를 random hyperplane이라 한다.

어떤 hyperplane의 법선 벡터를 $v$라 하자. 두 벡터 $x, y$가 hyperplane의 같은 방향에 있다고 하면 해당 hyperplane의 법선벡터와의 내적의 값의 부호가 같다. 즉 $\text{sgn}(v \cdot x) = \text{sgn}(v \cdot y)$

아래 그림에서 파란색, 주황색 hyperplane은 각각 두 벡터 $x, y$가 서로 같은/다른 방향에 위치한 것을 나타낸 것이다.

Two types of hyperplanes through the origin

반응형

hyperplane이 두 벡터를 같은 영역에 둘 확률은 $\theta / 180$이고, 반대로 다른 영역에 두게 할 확률은 $1-\theta/180$ 이다.

Two vectors make an angle $\theta$

즉, 어떤 hash function $f$를 randomly chosen 벡터 $v$를 $v_f$라 하자. 그리고 $f(x)=f(y)$를 두 벡터와의 내적의 부호가 같으면 $\text{sgn}(v \cdot x) = \text{sgn}(v \cdot y) \Leftrightarrow f(x)=f(x)$라 정의하자.

이 경우 $F$는 $(d_1, d_2, 1-d_1/180, 1-d_2/180)$-sensitive 라 한다.

 

※ 어떤 벡터를 고르면, 벡터의 내적을 해시함수로, 그리고 내적의 결과값은 signature로 간주할 수 있다.

 

그리고 random vector를 고를때, 벡터의 모든 원소를 고를 필요가 없다. 우리는 벡터 내적의 부호에만 관심이 있으므로, random vector $v_f$의 원소는 $1, \ -1$이기만 하면 된다. (e.g. $v=[1,\ 1,\ -1])$