Locality Sensitive Hashing

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

minhashing 을 사용하여 기존 집합을 시그니처로 압축하였습니다.

유사도 속성을 보존하면서 행렬의 행의 차원을 줄였습니다.

그러나 이러한 방식을 사용하더라도 대규모 데이터셋을 다루는 것은 어렵습니다.

문서의 수가 많아 많은 비교를 수행해야합니다.

n개의 문서가 있다면 전체 쌍은 $\frac{n(n-1)}{2}$ 번 비교해야 합니다.

지난 포스팅에서 minhashing 를 사용해 입력 행렬의 행에 관련하여 처리를 하였었고,

이번 포스팅에서는 Locality Sensitive Hashing로 행렬의 열에 대한 효율적인 처리를 하는 방식에 대해 다룹니다.

Locality Sensitive Hashing

만약 우리의 목표가 모든 쌍에 대해 유사도 값을 찾아 놓는 작업이라면, 이 작업을 줄일 수 있는 방법은 없습니다.

그러나, 우리는 종종 어느 정도 이상의 유사한 노드 쌍 만 원할 때가 있습니다.

그렇다면 우리는 모든 데이터가 아닌 유사할것 같은 쌍만 고려하면 됩니다.

이렇게 유사할 것 같은 것을 어떻게 제공하는지에 대한 일반적인 이론이 LSH, near-neighbor search 입니다.

LSH 에는 여러가지 형태가 있는데, 우선, 여기에서는 shingle 집합으로 만들어서, 시그니처로 변환한 데이터를 처리할 때 사용하는 형태만 다루겠습니다.

LSH for Minhash Signatures

LSH 의 기본 원리는 hash 입니다.

유사한 문서, 아이템의 시그니처는 동일할 확률이 높습니다.

동일한 시그니처 값을 가진 아이템들은 동일한 버킷으로 해시됩니다.

이 원리를 사용합니다.

해시를 여러번하면, 유사한 아이템끼리는 동일한 버킷에 해시될 가능성이 높아집니다.

이 동일한 버킷에 있는 아이템들은 후보쌍(=candidate pair) 이라고 하고,

이 후보쌍에 대해서만 유사도를 확인합니다.

때문에 유사도 확인하는 작업을 크게 줄일 수 있습니다.

해싱을 효율적으로 하기 위해서는

그림과 같이, 시그니처 행렬을 r개의 행으로 구성된 b개의 밴드(=band)들로 나눠서 수행을 해야합니다. ($n = r\times b$)

각 밴드마다 해시 함수가 있고,

해시 함수는 밴드 안의 하나의 칼럼인, r 차원의 벡터를 인자로 받아 버킷 숫자로 변환합니다.

이렇게 하면, 밴드에서 서로 일치하는 칼럼은 동일한 버킷으로 가게됩니다.(후보 쌍이 된다.)

두 칼럼이 일치하다는 것은, 두 칼럼이 유사할 확률이 있다는 것이고,

이 칼럼들을 후보 쌍을으로 사용하는 것입니다.

위의그림에서,

2번째와 4번째 칼럼은 둘다 [0,2,1] 의 벡터를 갖습니다. 이 둘은 동일한 버킷에 해시가 됩니다.

나머지 밴드에서의 칼럼이 어떤지와는 무관하게, 이 칼럼의 쌍은 후보 쌍이 됩니다.

서로 다른 칼럼, 첫번째와 두번째 칼럼 [1,3,0] [0,2,1] 는 벡터가 다르지만 해시되어 동일한 버킷에 들어갈 수도 있습니다.

그러나 칼럼 벡터가 다르기 때문에 해시가 충돌할 확률은 매우 낮습니다.

모든 밴드에 대해 각각 해시를 하고

최종으로 각 밴드의 버킷들에 있는 쌍, 후보 쌍들을 모두 비교하면됩니다.

각 밴드마다 해시함수가 있지만,

그 해시함수들은 모두 동일한 것으로 사용해도 무관합니다.

밴드 별로 버킷만 별도로 저장하면 됩니다.

동일한 칼럼이더라도 밴드마다 값의 차이가 있기 때문에

같은 칼럼에 해시함수가 동일해도 다른 값이 나옵니다.

특정 밴드 내에서만 유사한 쌍을 고려하기 위한 것이기 때문에

밴드마다 별도의 버킷을 사용하는 것입니다.

공통된 버킷을 사용하게 되면 행이 다르지만 패턴이 동일한 경우(유사하지 않은 경우) 도 같은 버킷에 들어가는 상황이 발생합니다.

이 작업은 확률을 사용하기 때문에

다음과 같은 두가지 상황이 발생할 가능성이 있습니다.

• False Negative : 실제로는 유사하지만 같은 버킷에 해시되지 않은 상황
• False Positive : 유사하지 않은 쌍이 같은 버킷에 해시되어 있는 상황

이 두가지 상황은 trade-off 관계이고,

몇가지 파라미터를 통해 조절할 수 있습니다.

Analysis of the Banding Technique

LSH 에서 이상적으로, 유사도의 임계값 t 가 넘으면

버킷에 있을 확률이 1 이 되어야 하고

넘지 않으면, 0이되어야 합니다.

그림@@

그러나 실제 데이터는 다음과 같이

그림@@

두개의 집합의 유사도 s 가 높을수록, 같은 버킷으로 해시 될 확률이 높아집니다.

이런 상황에서는

t 이전의 것들은, 실제로 유사하더라도 버킷을 공유 할 수 없고,(False positive)

t 이후의 것들은, 실제

위의 그래프에서 임의의 t 를 설정하면 문제가 발생합니다.

이렇게 되면 유사하지 않지만 버킷을 공유할 확률이 생기고,(False positive)

유사하더라도 버킷을 공유할 확률이 1이 아니기 때문에 버킷에 못 들어 갈 수 있습니다.(False negative)

이러한 상황을 최소화하기 위해서

기존의 선형식을 S-curve 로 변환 시킨 것이 banding 기법입니다.

우리가 b 개의 밴드를 사용하고, 각 밴드는 r개의 행을 갖습니다.

그리고 자카드 유사도가 s 인 특정 문서 쌍이 하나 있다고 생각해 봅시다.

자카드 유사도가 s 이므로 minhash signature 일치하는 확률은 s 입니다.

우리는 이 문서들이 후보쌍이 될 확률을 다음과 같이 계산할 수 있습니다.

1. 한 밴드에서 모든 행에 있는 시그니처가 일치하는 확률은 $s^r$ 이다.
2. 한 밴드에서 적어도 하나의 행에서 시그니처가 다른 확률은 1-$s^r$ 이다.
3. 각 밴드들에서 적어도 하나의 행에서 시그니처가 다른 확률은 $(1-s^r)^b$ 이다.
4. 적어도 하나의 밴드에서 모든 행에 있는 시그니처가 일치하는 확률,
   즉, 후보쌍이 될 확률은 $1-(1-s^r)^b$ 이 됩니다.

상수 b와 r 과는 독립적으로 이 확률 함수는 다음과 같이 S-curve 의 형태를 갖습니다.

여기서 임계값 t 를 중간의 가파른 부분에 위치시키게 되면

기존 선형식보다 False positive, False negative 의 확률이 줄어들게 됩니다.

이 가파른 부분의 근사치는 $(1/b)^{1/r}$ 으로 t 를 이 근사치로 두어 사용할 수 있습니다.

즉, b와 r 을 조절하여 임계값을 만드는 것입니다.

예를 들어 b=16, r=4 인 경우,

t = 1/2 가 되고, S-curve 의 가파른 부분이 1/2 지점이 됩니다.

이런식으로 임계값을 조절하여 적절하게 후보쌍을 얻을 수 있습니다.

지금까지 포스팅 내용을 정리해 보자면 다음과 같습니다.

1. k 를 하나 고르고 각 문서로부터 k-shingle 을 구성합니다. + k-shingle 을 더 짧은 버킷으로 해시할 수 있습니다.

2. shingle으로 document-shingle 쌍을 정렬합니다.

3. minhash signature에 대한 길이 n 을 선택합니다. 정렬된 리스트에 대해 모든 문서에 대해 minhash signature를 계산합니다.

4. 임계값 t 를 설정합니다. 이는 문서의 유사도 쌍을 어떻게 간주할 것인가를 정의합니다. b와 r을 선택하고 t의 임계값 대략적으로 $(1/b)^{1/r}$ 을 설정합니다. False negative 를 피하는것이 중요하다면, b 와 r을 조정해 t 를 보다 작게 설정합니다. 빠른 속도로 처리하고 False positive를 피하도록 한다면, 임계값을 기존보다 높게 잡으면 됩니다.

5. 나눠진 밴드를 사용해 LSH 로 후보쌍을 구성합니다.

6. 각 후보쌍의 시그니처를 검사하고,구성 요소의 비율이 t 이상인지 확인합니다.

   +: 만약 시그니처가 충분히 유사하면, 문서가 실제로 유사한지 확인합니다. 단순히 유사한 시그니처만 갖고있는게 아닌지 확인하는 것입니다.