locality sensitive hashing

비슷한 벡터일수록 같은 해시 버킷에 들어갈 확률이 높아지도록 설계한 해싱 기법이다. ANN 검색의 한 방법으로 쓴다.

일반적인 해시 함수는 입력이 조금만 달라도 결과가 완전히 달라지도록 설계된다. 충돌을 피하는 것이 목적이기 때문이다. LSH 는 정반대로, 가까운 것끼리 일부러 충돌시키는 것이 목적이다.

왜 필요한가

차원이 높아지면 모든 점 사이의 거리가 서로 비슷해져서 “가까운 이웃” 이라는 개념 자체가 흐려진다(curse of dimensionality). k-Nearest Neighbors 처럼 전수 비교하는 방식은 정확하지만 데이터가 $n$ 개일 때 질의마다 $O(n)$ 이라 규모가 커지면 감당이 안 된다.

LSH 는 정확도를 조금 포기하는 대신, 질의 벡터를 해싱해서 같은 버킷에 든 후보만 비교한다. 후보 수가 전체보다 훨씬 적으므로 질의 시간이 데이터 크기에 거의 비례하지 않게 된다.

조건과 대표 함수족

해시 함수족 $\mathcal{H}$ 가 LSH 이려면, 거리 $d_1<d_2$ 와 확률 $p_1>p_2$ 에 대해 다음을 만족해야 한다.

• $d(x,y)\le d_1$ 이면 $P[h(x)=h(y)]\ge p_1$
• $d(x,y)\ge d_2$ 이면 $P[h(x)=h(y)]\le p_2$

가까우면 충돌 확률이 높고 멀면 낮다는 것을 형식적으로 적은 것이다.

유사도	해시 함수
코사인	random hyperplane. 무작위 벡터 $r$ 을 뽑아 $\text{sign}(r\cdot x)$ 를 비트로 쓴다
자카드	MinHash. 무작위 순열에서 집합의 최소 원소를 해시로 쓴다
유클리드	무작위 방향에 사영한 뒤 일정 폭으로 자른다

한 개의 해시로는 구분력이 약해서, 여러 개를 이어붙여 하나의 키로 만들고($k$ 개 AND) 그런 테이블을 여러 벌 둔다($L$ 개 OR). $k$ 를 키우면 가짜 후보가 줄고, $L$ 을 키우면 진짜 이웃을 놓칠 확률이 줄어든다.

내적 검색에서의 변형

MIPS 는 거리 대신 내적을 최대화하는 문제라 LSH 를 그대로 쓸 수 없다. 내적은 거리 함수가 아니어서, 자기 자신과의 내적이 가장 크다는 보장조차 없기 때문이다.

Asymmetric LSH 는 질의 벡터와 데이터 벡터에 서로 다른 변환을 걸어 내적 문제를 거리 문제로 바꾼다. 데이터 벡터에 노름 정보를 담는 차원을 덧붙이는 식이다. Norm-Ranging LSH 는 노름 크기별로 데이터를 나눠 각 구간에서 따로 해싱해, 노름 편차가 클 때 생기는 정확도 손실을 줄인다.

실제 쓰임

구현이 단순하고 이론적 보장이 있다는 점이 장점이지만, 같은 정확도에서 HNSW 같은 그래프 기반 방식이 더 빠른 것으로 알려지면서 벡터 검색의 기본 선택지 자리는 내줬다. 중복 문서 탐지처럼 MinHash 로 자카드 유사도를 다루는 쪽에서는 여전히 표준으로 쓰인다.