Minhashing in Practice

해당 포스팅은 스탠포드의 Jeff Ullman 교수님의 강의 와 Mining of Massive Datasets(Jure Leskovec, Anand Rajaraman, Jeff Ullman) 책 을 참고하였습니다.

이전 포스팅에서 언급한 대로 minhashing 을 수행하는 것은 어렵습니다.

작업을 수행하기 위해서는 우선 행의 숫자 만큼의 무작위 순열을 만들어야 합니다.

중복된 순열이 없이 행의 수, 수 천만개 이상의 순열을 만드는 것은 시간이 많이 소요되는 작업입니다.

이 방식은 개념적으로는 적합하지만, 실제로 사용하기 어렵습니다.

Random Hash Function

그래서 하나의 순열을 사용하는 대신, 하나의 해시 함수를 사용합니다.

0부터 k-1 까지의 버킷으로 매핑이 되는 해시함수를 사용하여

각 행의 인덱스를 인자로, 0~k-1 사이의 출력이 나오게 합니다.

이 출력값을 순열의 숫자와 동일한 방식으로 사용하면 됩니다.

행의 수 n 만큼의 해시 함수를 미리 계산한 후에

이 함수 중 무작위로 선택하여 순열과 같이 사용하면 됩니다.

그리고 행의 위에서 부터 내려오면서 signature 를 찾습니다.

다음과 같은 알고리즘으로 작동합니다.

1. 해시함수 h_1(r),h_2(r),\dots , h_n(r) 을 계산한다.
2. 각 칼럼 c 에 대해
   • c가 r 행에서 0을 갖는 경우, 아무것도 하지 않는다.
   • c가 r 행에서 1을 갖는 경우, 각 $i = 1,2, \dots, n$ 집합 SIG(i,c) 와 $h_i(r)$ 을 비교 하여 작은 것으로 업데이트한다.

예시를 봅시다.

위와 같이 n = 4개의 집합과 k=5 개의 행이 있습니다.

해시함수 $h_1,h_2$는 우측과 같이 계산이 되어 있습니다.

처음에는 $\infty$ 로 초기화 되어 있습니다.

첫번째 행을 거치면

S_1,S_2 는 1 이고 $h_1(0) = 1$ , $h_2(0) = 1$ 으로 값이 변경됩니다.

두번째 행을 거치면

S_3 만 1이므로 $h_1(1) = 2$ , $h_2(1) = 4$ 의 값을 갖습니다.

세번째 행을 거치면

$S_2, S_4$ 가 1을 갖어 $S_2$는 값이 바뀌고,

$S_4$ 의 경우 둘 다 1이 더 작으므로 값이 변경되지 않습니다.

네번째 행을 거치면

$S_1, S_3, S_4$ 가 1을 갖고 $h_2(3) = 0 $ 이므로

두번째 signature 가 바뀝니다.

다섯 번째 행을 거치면

다음과 같은 결과를 얻습니다.

Speeding Up Minhashing

행렬 M 의 전체 k 행을 각 해시 함수에다 검사하는데는 많은 시간이 소요됩니다.

이전 포스팅에서 순열의 끝까지 모두 계산하지 않고, k 개 중 첫번째 m 개의 행들만 보았습니다.

그리고 그 작업의 결과도, 자카드 유사도에 어느 정도 수렴하는 것을 보았습니다.

k 를 전부 사용하지 않고 보다 작은 m 만 사용하여 속도를 높일 수 있습니다.

그러나 m 을 작게 만드는 것은 단점이 있습니다. 각 칼럼이 적어도 하나의 1을 갖는 한, m번째 이후 행들이 어떠한 민해시 값에 영향이 없어야하고 그것이 없을 수도 있습니다.

그러나 m번째 행 모두가 0인 칼럼이 있는 경우,

이 칼럼에는 minhash 값을 갖을 수 없습니다.

대신 기호 $\infty$ 를 사용하여 표현합니다.

이렇게 만들어진 minhash signature 를 비교할 때,

$\infty$ 와 관련하여 3가지 경우로 나눠서 처리할 수 있습니다.

1. 주어진 행에서 두 칼럼 모두 $\infty$ 이 아닌 경우 : 기존과 동일하게 처리합니다.
2. 한 칼럼만 $\infty$ 을 갖는 경우 : 기존 행렬 M의 모든 행들을 사용한다면, $\infty$ 가 있는 칼럼은 나중엔 특정 값을 갖게 됩니다.
   그리고 그 행 번호는 m 이후 행 번호 중 하나가 됩니다.
   $\infty$가 아닌 칼럼은 m 행들 중 하나인 한 값을 갖고 있습니다.
   이 경우에서는 두 칼럼의 minhash 값이 다르다는 것을 알 수 있습니다. (A: m에서 k 사이의 값, B: m 이내의 값 )
3. 둘다 $\infty$ 인 경우 : 이 칼럼들에 대한 자카드 유사도 정보가 없습니다.
   이들의 유사도는 k-m 이후 행들의 함수에 있습니다.
   정보가 없으므로, signature matrix 를 계산할 때, 이 행을 배제합니다. 동일한 값도 아니고 다른 값으로도 계산하지 않습니다.

세번째 케이스로 인해 자카드 유사도 추정의 정확도가 낮아 질 수 있습니다.
그러나 시간이 많이 단축되었기 때문에, 해시함수를 더 추가하여 정확도를 다시 높일 수 있습니다.

해시 함수를 추가하는 것도 시간이 소요되지만 전체 행의 수 k 에 대해 계산하는 것보단 덜 소요됩니다.

위의 알고리즘에서 보면 m의 크기에 따른 작업은 외부 루프이고,
각 해시 함수에 대한 작업은 내부 루프입니다.
전체 작업량이 동일하더라도 내부 루프의 경우 메모리에서 더 빠르게 처리됩니다.

Speedup Using Hash Function

세번째, m 까지 둘다 0 인 경우는 자카드 유사도 추정을 낮출 수 있습니다.

그러나 3.3.5와 비슷한 전략이 더 필요할 것입니다. 현재 M 의 행들은 고정되어 있고, 치환되지 않았습니다. 우리는 행 숫자들을 해시하는 해시 함수를 선택하고, 처음 m개의 행들에 대해서만 해시값을 계산합니다.

어떤 칼럼은 m 행까지 모두 0일 수 있기 때문에 일부 민해시값이 $\infty$ 일 수 잇습니다. m이 충분하게 커서 $\infty$ 민해시 값은 거의 드물다고 가정해보면, 우리는 여전히 이 시그니처 행렬의 컬럼을 비교함으로서 집합의 자카드 유사도를 잘 추정할 수 있습니다. T가 처음부터 m번 까지의 행을 표현하는 M 의 부분이라 가정해봅시다.
S1,S2 는 M의 두 칼럼을 입니다.
여기서 M의 첫번째 m 행들의 집합은 $S_1 \cap T$ ,$S_2 \cap T$ 로 표현합니다.
이 두 칼럼에서 모두 공집합이면 , minhash 함수는 두 칼럼에서 $\infty$ 일것입니다.
이는 자카드 유사도를 추정할 때 무시됩니다.

$S_1 \cap T$ , $S_2 \cap T$ 가 적어도 하나가 존재한다면,
minhash 함수에 대해 동일한 값을 갖을 확률은 두 집합의 자카드 유사도와 같고 이는 다음과 같습니다.

\[\frac{|S_1 \cap S_2 \cap T |}{|(S_1\cup S_2)\cap T |}\]

T가 전체 집합의 랜덤 부분집합으로 선택된다면,
이 분할의 기대값은 S1,S2의 자카드 유사도 값과 됩니다.
T에 따라 일부 편차가 있을 것이고,
X 행과 Y 행의 평균 숫자와는 조금 차이가 있을 것입니다.

이 차이를 줄이기 위해,
우리는 각 minhashing에서 동일한 T 집합을 사용하지 않습니다.
대신 M의 행들을 k/m 그룹으로 나눠 여러개를 사용합니다.
각 해시 함수에 대해, m 행들에 대해서만 값을 계산합니다.
두번째 m 행들에 대해서는 다른 해시 값이 계산됩니다. 이렇게 k/m 개의 minhash 값들을 얻습니다.

k/m 이 충분히 크면, 시그니처 행렬의 모든 행에 대해 얻을 수 있습니다.

여러개의 minhash 값을 얻으므로써,
3번째 경우서 발생하는 에러는 조정됩니다.

X 타입의 모든 행들은, k/m 집합에 분배되어 있고, Y 도 마찬가지 입니다. 그래서 m 행들 중 하나의 집합이 평균보다 더 많은 타입을 갖더라도, 그러면 다른 집합에서 평균보다 더 적은 수의 타입을 갖게됩니다.

example 3.5

k=8 이고 m을 4인 상황으로 가정해봅시다.
동일한 해시함수를 사용하여 첫번째 행 값을 기반으로한 하나의 minhash 값과, 두번째 행을 기반으로한 minhash 값을 얻습니다.
다음과 같이 해시 값을 얻습니다.

세 집합의 자카드 유사도는 다음과 같습니다. $SIM(S_1,S_2)$ = 1/2, $SIM(S_1,S_3)$ = 1/5 , $SIM(S_2,S_3)$ = 1/2

우선 첫번째 4개의 행들만 봅시다.
어떤 해시함수를 쓰든, S1에 대한 민해시 값은 $\infty$ 일 것입니다.
S2 는 4번째 행의 해시 값일 것입니다.
그래서, 첫번째 부분에서 S1,S2에 대한 minhash 값은 일치하지 않습니다.

이 첫번째 부분만 보면 $SIM(S_1\cap T,S_2 \cap T) = 0$ 이므로, minhash 로 얻은 정보와 일치합니다.
두번째 부분에서 S1,S2 가 일치할 확률은 2/3 입니다.
첫번째 부분와 두번째 부분의 평균은 , (0 +2/3)/2 = 1/3 이고,
이는 실제 1/2 과는 차이가 있지만 크지 않습니다. 규모가 커질수록 근사됩니다.

S_1,S_3 를 보면, 첫번째 부분의 유사도는 0, 두번째의 부분의 유사도는 1/3 입니다.
이 평균은 1/6 이고 실제 값 1/5 와 유사하다는 것을 볼 수 있습니다.

이번 포스팅에서는 minhashing 을 효율적으로 구현하기 위한
몇가지 방법들에 대해 다뤄보았습니다.

다음 포스팅에서는 이렇게 만들어진 signature matrix 를 비교할 때,
후보쌍을 만들어 비교를 줄이는 방식, Locality Sensitive Hashing 에 대해 다루겠습니다.