query와 passage의 similarity search를 근사(approximation)시키는 법

1. scalar quantization

 

벡터를 압축하여 하나의 벡터가 원래보다 더 적은 용량을 차지하도록 compression하는 기술

 

당연하지만 압축량이 커질수록 요구되는 메모리공간은 작아지지만 그만큼 정보손실도 커진다

 

일반적으로 벡터 내 수치는 float32로 저장함

 

SQ8은 4byte float32를 1byte  int8이나 float8???로 저장하는 방식(quantization이면 int8이 더 어울리긴해)

 

그러면서 한 값의 저장용량을 1/4로 줄인다

 

강의에서는 4byte float32를 1byte unsigned int8로 압축한다고 나와있네

 

SQ8 도식화

 

 

각 수치가 4byte에서 1byte로 줄어들면서 크기가 줄어든것을 볼수 있음

 

 

보통 inner product에서 float32까지 필요한 경우는 많지 않아서

 

1byte로 approximation해서 계산해도 거의 대부분 정확해서 SQ8로 approximation을 많이 한다.

 

 

2. pruning - inverted file

 

vector space 상 벡터들을 정해진 cluster로 소속시켜 군집화를 일으킴

 

clustering된 vector space에 query가 들어오면 query와 가까운 군집들을 찾음

 

그러면 가까운 군집들의 내부에 있는 모든 passage vector들과만 inner product search를 수행함

 

먼 cluster의 점들은 top k내에 들어갈리가 없으니 cluster가 잘 되어있으면 query보다 먼 cluster는 굳이 볼 필요가 없다

 

예를 들어 100만개의 passage vector가 있고 1000개로 clustering되어 있으면 들어온 query가 10개 cluster와 가까운 경우

 

원래는 100만개 passage 모두와 inner product를 해봐야하지만 10개 cluster 내부의 vector들과만 inner product를 하여 approximation할 수 있다는 것

 

cluster내 vector수가 모두 동일하면 속도는 거의 100배차이겠지

 

 

 

네모로 된 query가 들어오면 가까운 군집(그림에서는 3곳)의 vector들과만 inner product를 통해 similarity를 검사함

 

 

3. 구체적인 IVF 방법

 

주어진 passage embedding vector space에서 k-means clustering을 수행함

 

만약 새로운 document vector가 들어오면 cluster에 소속시키면 된다

 

cluster한 것이 pruning처럼 전체 공간을 quantization하는 느낌임

 

위에서 passage vector들은 indexing되어 저장된다고 했잖아

 

각 cluster내에 passage vector들이 index로 연결되어 있는데 이것을 inverted file이라고 부름

 

 

 

 

 

 

 

이제 query가 들어오면 query와 가까운 cluster를 찾는다

 

cluster와 query의 사이 거리는 보통 cluster의 centroid와의 거리를 의미함

 

가까운 centroid를 적절하게 찾았으면 그 centroid와 연결된 inverted list 내의 passage vector들과만

 

inner product search를 하여 query와 가장 연관된 top k similar passage들을 찾는다

 

search space가 상당히 줄어들어 검색 속도가 상당히 증가함