[CS246] Finding Similar Items (4) - Locality Sensitive Hashing (LSH)

Recap: Shingling and Minhashing

$k$-shingles

document를 set으로 매핑. 아래 표는 $k=3$인 경우의 예시다.

Example for Shingling

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}$

 

Minhash

row의 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}$

Example of Minhash

Recap: Big Picture (Stanford CS264)

반응형

Locality-Sensitive Hashing (LSH)

minhash와 signature matrix를 이용하면 문서간 유사도를 효율적으로 구할 수 있었다.

다시 scaling의 문제로 돌아와서, 유사도 한쌍 계산하는 데 1 $\mu s$가 걸릴때, 100만개의 문서의 유사도 쌍을 계산하면 얼마나 걸릴까? 약 6일의 시간이 걸린다. 이러면 데이터 스케일이 크면 적용할 수 없다.

 

LSH는 candidate pair 개수를 줄이는 방법론이다. 정확히는 similar할 것 같은 pair를 찾는 알고리즘이라 할 수 있다.

 

From Signatures to Buckets

item을 해싱하는 방법을 확장하자. 유사한 item일 수록 같은 bucket에 들어올 것이다. (Why? $\Pr(\text{minhash is same}) = \text{Jaccard Similarity}$ !)

따라서 해싱되어 같은 bucket에 들어온 pair는 candidate이다. 다음과 같은 잠재적 이슈가 있다.

• false positive: 유사하지 않은 pair가 같은 bucket에 들어옴
• false negative: 유사한 pair가 같은 bucket에 들어오지 않음

해결방법은 나중에 알아보고, 먼저 유사한 pair를 bucket에 담는 방법을 알아보자.

 

Partition into Bands

Partition into Bands (Stanford CS246)

주어진 행렬 $M$을 각각 $r$개의 행을 가진 $b$개의 band로 나눈다. (즉 전체 행의 수 = $br$) 그리고 $k$개의 bucket을 가진 해시테이블을 만든다. ($k$는 가급적 큰 값으로 한다.)

 

각 band마다 해당 band에 해당하는 column 부분만큼 해싱하여 해시테이블의 bucket에 담는다.

(각 band마다 서로 다른, 독립인 해시테이블을 만든다)

 

$b, r$의 값을 조절하면서 similar pair끼리는 많이, nonsimilar pair는 적게 만든다.

Hash Function for One Bucket (Stanford CS246)

위 그림의 7개 컬럼을 예시로 설명해보면 다음과 같다.

• 2번과 6번 컬럼은 같은 bucket으로 매핑되었다. 이는 단순히 hash collision이 일어나서일 수도 있지만, 해당 부분이 완전히 같기 때문에(identical) 해시값이 같아서일 수 있다. (remind:  주제가 유사한 쌍을 찾는 것이 아니라 character-level에서 유사해야하므로 band로 나누어진 부분은 완전히 같을 것이다.)
• 6번과 7번 컬럼은 서로 다른 bucket으로 매핑되었다. 이는 확실이 서로 not-identical하다는 것이다.

Example: Bands

100K = 100,000개의 컬럼과, 100개의 정수로 이루어진 signature가 있다고 하자. 즉 signature matrix는 (100, 100000) 모양이고 메모리는 약 40MB이다. (4바이트 정수 이용)

 

80%-similar pair를 찾는다고 해보자. (80%이상이면 similar, 그렇지 않으면 dissimilar)

naive하게 유사도를 구한다면 $\dbinom{100,000}{2} \approx 5,000,000,000$개의 쌍에 대하여 자카드 유사도를 계산해야한다. 

 

이제 $b=20,\ r=5$를 적용하여 계산해보자.

• $C_1,\ C_2$가 실제로 80%의 유사도를 갖는다고 하자.
  • 어떤 band 내에서, 두 $C_1, C_2$가 일치할(identical) 확률은 $(0.8)^5 = 0.328$ 이다. (5개의 정수가 모두 일치)
  • 20개의 band에서 모두 not similar할 확률은 $(1-0.328)^5=0.00035$
  • 80% similarity 가정하에서 false negative일 확률은 $1/3000$ 이다.
• $C_1,\ C_2$가 실제로 40%의 유사도를 갖는다고 하자.
  • 어떤 band 내에서, 두 $C_1, C_2$가 일치할(identical) 확률은 $(0.4)^5 = 0.01$ 이다. (5개의 정수가 모두 일치)
  • 최소 1개 이상의 band 중에서 $C_1, C_2$가 일치할 확률을 $1-(0.99)^{20}<0.2$
  • false positive일 확률은 20%이며, 실제 유사도 40%보다도 적다.

Analysis of LSH

asdf

Stanford CS246

band의 개수를 $b$, band 내의 행의 개수를 $r$, 그리고 pair의 유사도를 $s$라 하자. 그렇다면

• 하나의 band내에서 모든 signature가 일치할 확률 = $s^r$
• 하나의 band내에서 최소 하나 이상의 행의 signature가 불일치할 확률 = $1-s^r$
• 모든 band내에서 최소 하나 이상의 행의 signature가 불일치할 확률 = $(1-s^r)^b$
• 최소 하나 이상의 band에서 모든 signature가 일치할 확률 = $1 - (1 - s^r)^b$

S-curve (MMDS textbook)

Example: $b=20,\ r=5$ (Stanford CS246)

$b, r$의 값과 상관없이, $s \approx (1/b)^{1/r}$이면 candidate일 확률은 항상 $1/2$ 이다.

 

Combining the Techniques

1. $k$를 고르고, 각 문서마다 $k$-shingle을 만든다.
   1. (Option) $k$-shingle을 해싱하여 정수로 변환한다.
2. document-shingle을 정렬한다.
3. 길이가 $n$인 minhash signature를 만든다.
4. similarity threshold $t$, band의 수 $b$, band 내의 행의 수 $r$을 지정하고(단, $n=br$)
   1. $(1/b)^{1/r} > t$ 이면 false positive는 줄어들 것이다. (false positive을 줄이는게 목표일 때)
   2. $(1/b)^{1/r} < t$ 이면 false negative는 줄어들 것이다. (false negative을 줄이는게 목표일 때)
5. Candidate pair를 만들고, $t$를 바탕으로 signature를 비교한다.
6. (Optional) 실제 두 문서가 유사한지(혹은 아닌지) 확인한다.