(6강) Scaling up with FAISS

scale이 커진 상황에서 효율적인 검색을 수행하기 위한 방법
similarity search의 개념 복습
approximate search 이해
faiss 활용법
[Reference & Further Reading]
FAISS blog
FAISS github
FAISS tutorial
Getting started with Faiss

1. passage retrieval and similarity search

1.1. review

실시간으로 유사도를 측정하기 위한 검색 기법에 대해 알아본다

1.2. MIPS(Maximum Inner Product Search)

주어진 질문(query) 벡터 q에 대해 passage 벡터 v들 중 가장 질문과 관련된 벡터를 찾아야함 -> 여기서 관련성을 내적(inner product)이 가장 큰 것

4,5 강에서는 brute-force(exhaustive) search를 사용하였다. 이는 저장해둔 모든 sparse/ dense 임베딩에 대해 일일히 내적값을 계산하여 가장 값이 큰 passage를 추출하는 것으로 passage 갯수가 방대해짐에 따라 원하는 속도를 얻을 수 없게 된다.

하여 passage를 indexing하여 벡터를 저장하고, 인덱싱된 벡터들 중 질문벡터와 가장 내적값이 큰 상위 k개의 벡터를 찾는 과정을 거친다.

$\underset{v_i\in V}{argmax} (q^Tv_i)$

하지만 인덱싱을 함에도 실제로 검색해야하는 데이터는 훨씬 방대하다. 5백만 개의 위키피티아 데이터 뿐만 아니라 수십억, 조 단위로 커질 수 있다.

1.3. Tradeoffs of similarity search

Search speed
- 쿼리당 유사한 벡터를 k개 찾는데 얼마나 걸리는지
- Pruning
Memory Usage
- RAM에 모두 올려둘 수 있으면 빠르지만, 많은 RAM 용량을 요구함
- Compression
Accuracy
- brute-force 검색 결과와 얼마나 비슷한지?
- 속도를 위해 정확도를 포기하는 경우도 있음
- Exhaustice search

1.4. Increasing search space by bigger corpus

Corpus의 크기가 커질수록 탐색공간이 커지고, 검색이 어려워지며, Memory Space가 많이 필요하다. 또한 Sparse Embedding의 경우는 용량 문제가 더 크다고 볼 수 있다.

2. Approximation Similarity Search

용량과 속도측면의 문제를 해결하기 위한 방법에 대해 알아본다.

2.1. Compression - Scalar Quantization (SQ)

vector를 압축하여, 하나의 vector가 적은 용량을 차지하도록 한다.
이를 통해 압축량은 증가하고, 사용되는 메모리 감소하지만 정보 손실이 증가한다.
ex) Scalar quantization: 4-byte floating point -> 1-byte unsigned integer로 압축

💭 sparse 대신 dense를 쓰는 것 같은 느낌?

2.2. Pruning - Inverted File (IVF)

Search space를 줄여 search 속도 개선 (dataset의 subset만 방문)

-> Clustering + Inverted file을 활용한 search

Clustering: 전체 vector space를 k개의 cluster로 나눔(k-means clustering)

Inverted File (IVF)
- Vector의 index => inverted list structure
- 각 cluster의 centroid id 와 해당 cluster의 vector들 이 연결되어있는 형태

💭 단순히 index를 주는 것과 군집형태로 하는 것이 가지는 차이가 무엇인가..?? 결국 해당하는 군집을 찾는다는 개념이면 데이터 양이 커짐에 따라 같은 문제가 발생하는게 아닌가??

주어진 query vector에 근접한 centroid 벡터를 찾고,
찾은 clusterd의 inverted list내 vector들에 대해 서치를 수행한다.

💭 mrc 할 때보면 우선 passage를 찾고 그 안에서 정답을 찾는것처럼 일단 군집을 찾고 그 안에서 vector를 찾는 개념

3. Introduction to FAISS

3.1. FAISS

Facebook에서 만든 속도향상을 위한 오픈소스 라이브러리
인덱싱쪽에 도움을 줌

3.2. 활용방법

Train index and map vectors

데이터 분포를 보고 Cluster를 나누기 위한 학습이 필요함. index.train()
Scalar Quantization 과정에서도 어느정도로 할 지를 정하기 위해 학습이 필요하다.
그 후 cluster안에 vector들을 넣어주게 된다.
- 보통은 train과 add를 동일한 데이터로 하지만, 데이터양이 너무 크다면 1/40로 하는 경우도 있음.