Friday, February 13, 2015

Minhash for Jaccard Similarity

출처 : POSTECH 한욱신 교수님의 글(minhash for dummies|Andy Han)

참고자료 : 
University of Utah - Jeff M Phillips의 자료

1. 기초

두 개의 set A, B가 주어질 때, 두 set의 유사성을 계산하는 measure로 Jaccard Similarity라는 것을 쓴다. JS(A,B) = |A intersect B|/|A union B|로 정의된다.

이것을 구하기 위해서는, A의 원소를 정렬하고 B의 원소를 정렬한 후에, 두 정렬된 셋(즉, 리스트)를 머지하면서 구하면 된다. 그런데, 이렇게 구하면 O(|A|log|A|+|B|log|B|)의 time complexity가 생기는데, 이것을 줄이기 위해서 나온 것이 minhash이다.

왜 minhash라고 했을까? 즉, 주어진 집합의 모든 원소들을 hash한 후, 가장 작은 hash값을 가지는 원소를 hash값으로 사용하겠다는 것이다. 이를 위해, random permutation 함수 phi를 생각해 보자.
즉, phi는 {1, 2, ..., N} -> {1, 2, ...,N}으로 hash하는 함수이다.
집합 A의 모든 원소에 대해서 phi를 적용한 후, 제일 작은 값을 가지는 원소를 hash 값으로 사용한다. 예를 들어, A={2, 7}로 주어졌는데, phi(2)=3, phi(7)=2로 나오면, minhash(A)=7이 된다.

예제 1: A={1,2}, B={1,3}, C={2,4}라고 하자. 그러면, 모든 원소들의 universe는 {1,2,3,4}가 된다. 즉, 바로 위의 paragraph에서 N이 4가 되는 것이다. 두 가지 random permutation 함수 p1, p2를 생각해보자.
p1(1)=2, p1(2)=1, p1(3)=4, p1(4)=3이고, p2(1)=3, p2(2)=2, p2(3)=1, p2(4)=4라고 하자.
p1에 대해서 A에 대한 minhash값(즉, minhash(A))는 2이 된다. 즉, A의 원소인 1, 2에 대해서 p1(1)(=2) > p1(2)(=1)이므로, 2값을 minhash 값으로 정하게 된다. A에 대해서 p2를 적용한 minhash값은 같은 논리로 2가 minhash로 정해진다.

random하게 phi를 정하게 되면, A에 있는 모든 원소가 확률적으로 동일하게 minhash 값으로 선정될 수 있다. 왜 이것을 사용하면 JS를 구할 수 있을까?

이는 P[minhash(A)=minhash(B)] = JS(A,B) (수식 1)라는 중요한 성질이 존재하기 때문이다. 어떻게 이런 성질이 나오나 생각하면 아래와 같다.

우선, minhash(A)=x 라는 수식을 다른 말로 해석하면, A에서 하나의 random sample을 뽑았는데 그게 x이다라고 생각할 수 있다. 따라서, P[minhash(A)=minhash(B)] = P[x in A and x in B] for a randomly chosen x from A union B (수식 2)라는 중요한 공식이 성립한다.

마지막으로 P[x in A and x in B]= |A intersect B|/|A union B| (수식 3)가 된다.

따라서, 수식 1~3에 의해서 P[minhash(A)=minhash(B)] = JS(A,B)이 된다.

2. 알고리즘과의 연계

그럼 P[x in A and x in B]는 알고리즘으로 표현하면 무엇과 동일한가?

1: hit = 0;
2: for i = 1 to M
3:  get a random sample x from AUB
4   if x is in X and in Y, hit++
5: return hit/M
로 표현할 수 있다. 즉 return값은 궁극적으로 JS(A, B)가 된다.

AUB에서 하나의 random sample을 뽑았는데 그게 A와 B에 모두 있을 확률은 P[minhash(A)=x and minhash(B)=x] 라는 표현할 수 있으므로, 위 알고리즘은 아래와 같이 최종적으로 바뀌고 그게 minhash 알고리즘이 된다.

hit = 0;
for i = 1 to M
   if minhash_i(A)=minhash_i(B), hit++
return hit/M

M을 무한대로 보내면 확률값을 구하게 된다. 일반적으로 M은 |AUB|의 값보다 훨씬 작은 값을 사용한다. 예를 들어, 100?

3. 질문

(Q1) random permutation이랑 무슨 상관?

random permutation을 사용하기 때문에, AUB의 모든 원소가 동일한 확률로 제일 작은 min hash값을 가질 수 있다. 즉, "get a random sample x from AUB"를 하기 위해서 random permutation의 개념을 사용한 것이다.

No comments:

Post a Comment