Passage Retrieval - Scaling up, FAISS

passage들을 embedding한 벡터들을 저장해두고 꺼내오는 방법을 공부했다. passage들이 굉장히 많아질 경우 질문-지문 유사도를 계산하는 시간과 양도 매우 커진다. FAISS라이브러리를 활용해서 scale up하는 방법을 알아본다.

두 벡터간의 거리를 계산할 때 점과의 거리를 구할 수도 있지만 inner product를 더 자주 사용한다. (Maximum Inner Product Search)

방대한 문서 집합에서 query가 들어올 때마다 유사도를 전부 계산하기에는 부담스러울 수 있다.

문서가 많을 수록 search speed는 당연히 느지며 memory에 다 올려두기 힘들것이고 disk에서 불러온다면 시간이 오래걸릴 것이다. accuracy를 양보하더라도 더 효율적인 방법을 살펴보자.

1. Compression - Scalar Quantization

floating point를 저장하는데 4byte를 사용하는데 Inner product를 할때는 이만큼 정확도가 필요하지 않다. 4byte를 1byte의 unsigned interger로 압축해서 문서양 대비 필요 메모리 양을 줄일 수 있다.

 

2. Pruning - IVF(Inverted File Index)

문서들간의 clustering이 잘 되어있다면 모든 passage들을 둘러볼 것이 아니라 subset만 방문해서 search space를 줄일 수 있다.

각 클러스터에 대한 인덱스를 만들어 검색 성능을 향상시키는 방법으로 Inverted file Index 라고 한다. cluster내부에서는 일반적인 brute-force search를 수행한다.

 

3. FAISS

Faiss는 opensource로 dense vector간의 효율적인 similarity seach and clustering을 도와주는 라이브러리이다.

우리가 확보한 dense vector들을 가지고 clustering을 위한 학습이 필요하다. (quantization도 결국 학습데이터들의 float range를 알아야한다.) 정말 데이터가 큰 경우에는 모든 데이터를 가지고 학습할 수 없기 때문에 100개중 40개는 학습에 활용하고 구축한 cluster에 나머지 60개를 삽입해준다.

query가 들어오면 가까운 cluster들을 visit하며 top-k개의 유사하다고 판단된 vector를 반환한다.