Min-Hashing / LSH(Locality Sensitive Hashing)

100만개(10^6)의 문서에 대해 중복 검사한다고 해보자.

이때 두 문서간 80%정도만 같으면 중복문서라고 가정한다.

가장 쉬우면서도 정확한 방법(Naive)으로는 두 문서를 뽑아서 Jaccard Similarity를 구하면 되는데, 두 문서의 비교작업만 5*10^11번 필요하고, 한 문서를 shingling한 dimention도 무시할 수 없으므로 time and space complexity 모두 어마어마한 작업이 된다.

참고로 Jaccard Similarity(Jaccard Index) 두셋(set)의 유사성을 표현하는 방법으로 (A,B의 교집합/A,B의 합집합) 으로 표현할 수 있다.

A={1,2,3,4,5}

B={1,3,5,7,9}

교집합={1,3,5}

합집합={1,2,3,4,5,7,9}

J(A,B)=3/7

먼저, 다음과 같이 문서를 shingling(우리말로 번역하면 기왓장?)하여 다차원의 키워드 vector로 변환해보자.

문서 c1에 'my name is jack', 문서 c2에 'your name is heidi'이란 문장이 있다면

2-gram shingling한 결과로 다음과 같은 셋을 얻게된다.

c1: 'my name','name is','is jack'

c2: 'your name','name is','is heidi'

이런식으로 2-gram단위의 연속된 단어로 묶어 쪼갠후 중복을 제거한 상태를 말한다.

shingling한 단어들로 다음과 같은 bit vector를 생성할 수 있다.

    | 'my name' | 'your name' | 'name is' | 'is jack' | 'is heidi' |

c1  |         1       |         0         |         1     |      1     |      0     |

c2  |         0       |         1         |         1     |      0     |      1     | 

XOR, AND의 bit연산만으로 쉽게 jaccard계수(1/5)를 구할 수 있지만, 아직 dimension이 줄어든 상태는 아니다.

min-hashing을 적용하여 5-dimension 문서에서 3-dimension signature를 구하는 과정은 다음과 같다.

    | A | B | C | D | E |

c1 | 1 | 0 | 1 | 1 | 0 |

c2 | 0 | 1 | 1 | 0 | 1 |

첫번째 함수(h1): 1>2>3>4>5 로 섞은후 가장 처음 0이 아닌 값을 반환

두번째 함수(h2): 5>4>3>2>1 로 섞은후 가장 처음 0이 아닌 값을 반환

세번째 함수(h3): 3>4>5>1>2 로 섞은후 가장 처음 0이 아닌 값을 반환

다음과 같은 결과를 얻을 수 있다.

    | h1 | h2 | h3 |

c1 |  A |  D |  C |

c2 |  B |  E |  C |

혹은 다음과 같이 표현할수도 있다.

c1 |  1 |  4 |  3 |

c2 |  2 |  5 |  3 |

 

hash function갯수만큼의 dimension을 가진 signature가 생성되었고, 이론적으로 두 hash의 값이 동일할 확률은 두 문서의 jaccard계수와 같으므로, 이렇게 생성된 signature로 두 문서를 비교하도록 한다.

(이게 왜 이론적으로 동일한지는 위키문서를 참조)

이때 hash function 내부적으로 min-value를 뽑아내기위한 permutation을 발생시켜야 하는데, 이걸 random하게 해버리면 중복된 signature가 생성될 수 있으므로 문제가 있다. 그래서 permutation값이 중복되지 않고 골고루 발생시키며, 함수 서로간에도 순서가 동일하지 않도록 universal hashing기법이 사용된다.

가령, 7의 배수를 10으로 나누면 0~9까지의 숫자가 골고루 나오는데(7,4,1,8,5,2,9,6,3,0) 여기서 착안한 알고리즘이라고 하면 대충 감이 올것이다.

이제 차원은 줄었는데, 문서를 비교하는 횟수를 줄이는 숙제는 여전히 남아있다.

가령 min-hashing으로 차원(dimension)을 100까지 줄였다면, 이를 다시 5개 row(r)씩 20개의 band(b)으로 나눈후, 각 band별로 다시 해싱하여 두 문서의 동일한 위치의 band의 해싱값이 동일하면 두 밴드는 동일하다(identical)고 본다.

서울 공덕동 사는 김모씨가 서울사는지 알아보고 싶은데, 공덕동 사는 사람들 모두가 맞다고 한다면 굳이 신사동사람한테는 안물어보는 식이다.

80%의 유사성을 가진 두개의 문서를 예로 들면 false negative(두 문서가 80%의 유사성을 가지고 있지만, 20개의 band중 하나도 일치하지 않을 확률)일 확률은 다음과 같이 계산 가능하다.

두 band가 일치할 확률: 0.8^5 (row가 5개이므로) = 0.328

모든 band에서 일치하지 않을 확률: (1-0.328)^20 (band는 20개) = 0.00035

즉, 단 하나의 band만 일치해도(hash값이 동일) 99.965%의 확률로 문서는 80% 일치한다고 말할 수 있단 얘기다.

반대로 30%의 유사성을 가진 문서가 하나이상의 band가 일치할 확률(false positive)은 4.74%이다. (계산과정은 위와 비슷하므로 생략)

여기서 다음 공식을 유도할 수 있다.

p=1-(1-t^r)^b

p: 하나이상의 band가 일치할 확률

t: 두 문서의 유사도

r과 b가 주어지면 위 그래프는 계단형 그래프를 그린다는 사실을 알 수 있는데.. (t가 작으면 거의 0이다가 t가 어느임계점을 돌파하면 급격히 1에 가까워지는)

여기서 우리가 원하는 t값을 상수 s로 정의하면(두 문서가 80%만 맞으면 유사하다고 본다와 같이), 이상적인 r과 b의 값을 다음과 같이 유도해낼 수 있다.

s~(1/b)^(1/r)

ref: http://www.stanford.edu/class/cs246/slides/03-lsh.pdf