Dense Embedding의 경우 100개, 1000개 더 나아가 수억개 이상을 문서들을 다룰때 scaling up에 대해서 하는 방법을 알아본다.
Passage Retrieval and Similarity Search
이전 포스트에서 알아본 Dense Embedding은 결국 vector space에 표현된 질의와 수 많은 Passage의 벡터들의 사이의 유사도를 계산하는 것 이다. 그렇다면 Passage들이 매우 많아지게 된다면 어떻게 효율적으로 찾을 수 있을지가 오늘 포스트의 주제이다. 보통 이 과정을 Similarity search라고 부르며 검색을 상당히 빠르게 하는 과정을 의미한다.
기본적으로 가장 관련된 pair를 찾는 방법으로 MIPS(Maximum Inner Product Search)를 사용하게 된다. 연산으로는 두개의 벡터 중 하나를 전치한 후 행렬곱하여 score를 내주게 된다.
지난 포스트에서는 brute-force(exhaustive)한 방식을 사용하여 모든 값에 대해 계산하는 것을 알아보았다. 하지만 이 방식을 개수가 증가할수록 불가능에 가깝기 때문에 실제로 검색할 수 없을 수 있다.
이렇게 빠르게 문서를 검색하기 위해선 다양한 Trade-off를 고려해야 한다.
-
Search Speed
쿼리 당 유사한 벡터를 k개 찾는데 얼마나 걸리는지?- 가지고 있는 벡터량이 클수록 오래 걸림
-
Memory Usage
벡터를 사용할 때, 어디에서 가져올 것 인지?- RAM에 모두 올려둘 수 있으면 빠르지만, 많은 RAM 용량을 요구한다.
- 디스크에서 계속 불러와야 한다면 속도가 느려짐
-
Accuracy
brute-force 검색 결과와 얼마나 비슷한지?- 속도를 증가시키려면 정확도를 희생해야하는 경우가 많음
Approximating Similarity Search
그렇다면 어떻게 Approximation할 수 있을지 알아본다.
Compression - Scalar Quantization(SQ)
vertor를 압축하여, 하나의 vector가 적은 용량을 차지하도록 하여 메모리 사용량을 줄이는 방법이다. 예를들어 4byte floating point가 아닌 1byte의 unsigned integer로 압축할 수 있다.
Pruning - Inverted File (IVF)
Search space를 줄여 search 속도 개선 (dataset의 subset만 방문)할 수 있으며 Clustering과 Inverted file을 활용할 수 있다.
clustering 기법은 어떤 query의 근접한 cluster들만 방문하여 exhaustive search하는 방법을 말한다.
Inverted file은 각 클러스터에 속해있는 point들을 역으로 index를 가지고 있는 구조로 변경하는 방법을 말한다.
이 두가지를 활용하여 주어진 query vector와 근접한 cluster centroid를 찾은후 찾은 cluster의 inverted list내 vector들에 대해 서치를 수행하여 속도를 비약적으로 상승시킬 수 있다.
Introduction to FAISS
fast approximation을 위한 라이브러리로 위의 설명에서 Indexing쪽의 도움을 주는 라이브러리이다.
우선 적절한 클러스터를 나누고 SQ8로 압축하기 위하여 학습을 진행하게 되고 그 후 ADD하는 작업을 통해 벡터들을 추가하게 된다.
이렇게 만들어진 FAISS index는 nprobe 옵션을 통해 방문할 클러스터를 방문하여 SQ8 형태로 벡터들을 검색하고 Top K만큼 결과를 내주는 형태이다.
Scaling up with FAISS
brute-force 방식으로 모든 벡터와 쿼리를 비교하는 단순한 인덱스 만들기
d = 64 # 벡터의 차원
nb = 100000 # 데이터베이스 크기
nq = 10000 # 쿼리 개수
xb = np.random.random((nb, d)).astype('float32') # 데이터베이스 예시
xq = np.random.random((nq, d)).astype('float32') # 쿼리예시
# 인덱스 만들기
index = faiss.IndexFlatL2(d) # 인덱스 빌드하기
index.add(xb) # 인덱스에 벡터 추가하기
# 검색하기
k = 4 # 가까운 벡터 4개
D, I = index.search(xq, k) # 검색하기
# D : 쿼리와의 거리
# I : 검색된 벡터의 인덱스위에서 index.train()을 하지 않는 이유는 SQ와 pruning을 하지 않기 때문에 학습할 필요가 없다.
IVF with FAISS
- IVF 인덱스 만들기
- 클러스터링을 통해서 가까운 클러스터 내 벡터들만 비교함
- 빠른 검색 가능
- 클러스터 내에서는 여전히 전체 벡터와 거리 비교 (Flat)
# 클러스터 개수
nlist = 100
# 클러스터끼리의 거리를 재는 방법 정의
quantizer = faiss.IndexFlatL2(d)
# Inverted File 만들기(k-means로 생성)
index = faiss.IndexIVFFlat(quantizer, d, nlist)
# 클러스터 학습하기
index.train(xb)
index.add(xb)
D, I = index.search(xq, k)IVF-PQ with FAISS
- 벡터 압축 기법(PQ) 활용하기
- 전체 벡터를 저장하지 않고 압축된 벡터만을 저장
- 메모리 사용량을 줄일 수 있음
- SQ보다 더 적게 줄일 수 있다. 기본적으로 SQ방식을 사용하고 필요하다면 PQ를 사용하는 것이 좋을 수 있다.
Using GPU with FAISS
- GPU의 빠른 연산 속도를 활용할 수 있다.
- GPU의 메모리 제한이나 메모리 random access 시간이 느린 것이 단점이다.
# 단일 GPU 사용
res = faiss.StandardGpuResources()
# 인덱스(CPU) 빌드
index_flat = faiss.IndexFlatL2(d)
# GPU로 옮기기
gpu_index_flat = faiss.index_cpu_to_gpu(res, 0, index_flat)
gpu_index_flat.add(xb)
D, I = gpu_index_flat.search(xq, k)