passage의 indexing을 도와주는 FAISS 라이브러리 소개

1. introduction

 

facebook에서 만든 fast approximation open source library

 

효과적인 similarity search와 dense vector의 clustering을 지원함

 

사용이 편하고 어떤 size에도 가능하지만 large scale에 특화되어 있다고함

 

C++가 backbone이지만 python으로 wrapping되어 있어서 python으로도 쉽게 사용가능

 

passage vector의 indexing과정을 도와준다고함

 

FAISS는 indexing을 효과적으로 해준다고함??

 

 

 

2. 사용방법

 

train data로 passage vector를 준비하고 index train을 해야함

 

단순히 random하게 clustering을 하는 것이 아니라 데이터의 분포를 보고 적절하게 clustering을 해야함

 

이런 적절한 clustering을 위해서 passage embedding vector를 train하여 clustering을 수행하고

 

scalar quantization을 통해 float32에서 int8로 compression도 함

 

아주 넓은 범위의 float32에서 아주 좁은 범위의 0~255인 unsigned int8로 압축시키려면

 

사용하고있는 float의 max,min이나 scale 비율을 잘 알아야함.

 

결과적으로 최적으로 clustering을 하고 압축하는 방법을 찾기 위해서  train 과정이 필요한 것임

 

다음으로 실제 가지고 있는 vector들을 add하여 실제로 찾아낸 최적 clustering을 시키고 최적 SQ8 압축을 함

 

FAISS 기본 흐름

 

 

 

참고로 add데이터와 train데이터가 다를 수도 있다.

 

예를 들어 passage 데이터가 너무 많은 경우 전부 학습시키는 것이 비효율적으로 작용할 수 있는데 이럴때는

 

실제로 add할 데이터중 일부를 random sampling하여 training에 사용함

 

training후에는 가지고 있는 모든 데이터를 add함

 

 

3. inference

 

FAISS로 add까지 마치면 최종 inference 단계에서 query가 들어오면 query와 가까운 cluster를 찾는다

 

가까운 cluster 내의 vector들만 전부 방문하여 inner product score를 계산한 뒤 TOP-k vector들을 출력으로 내보낸다.

 

우리 주제가 MRC여서 passage를 강조했지만 FAISS는 어떠한 벡터든 사용가능한 알고리즘임

 

nprobe=10은 가까운 10개 cluster만 방문하겠다는 뜻

 

 

 

4. 코드로 살펴보는 FAISS

 

brute force로 모든 벡터와 쿼리를 비교하는 가장 단순한 인덱스 만들기

 

준비하기

 

d = 64         #벡터 차원
nb = 100000    #DB 크기
nq = 10000     #쿼리 개수
xb = np.random.random((nb,d)).astype('float32')   #DB 예시
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: 검색된 벡터의 인덱스

 

 

 

편의상 예시를 들기 위한 데이터와 parameter를 임의로 지정했음

 

IndexFlatL2로 dimension을 정의했음

 

IndexFlatL2가 vector indexing을 정의한다는 의미같아

 

위 코드에서 바로 add를 했다는 부분이 이상할 수 있는데

 

pruning에 의한 inverted file이나 quantization을 쓰지 않을 것이면 training을 하지 않고 바로 add해도 된다

 

add를 하면 index.search()로 xq와 가까운 벡터 k개를 뽑아준다

 

nlist = 100          #클러스터 개수
quantizer = faiss.IndexFlatL2(d)

index = faiss.IndexIVFFlat(quantizer, d, nlist)     #Inverted File 만들기
index.train(xb)    #클러스터 학습

index.add(xb)     #클러스터에 벡터 추가
D,I = index.search(xq,k)    #검색

 

 

IndexFlatL2로 clustering을 위해 L2기반의 distance로 vector간 거리를 측정하겠다고 선언을 하면서 indexing을 한 후

 

IndexIVFFlat를 이용해서, 정의한 IndexFlatL2를 이용해서 clustering을 수행하면서 inverted file과 동시에 quantize도 함

 

이를 위해 train을 한다는 점도 기억해야할 부분이고

 

train후에는 add를 통해 실제로 clustering을 수행시킴

 

index.search()를 통해 xq와 가까운 k개의 벡터를 찾아냄

 

참고로 train data xb는 너무 크면 일부만 sampling하여 train시키고

 

add할때는 xb 모두 더함(가지고 있는 데이터를 굳이 제거할 이유는 없잖아)

 

다음 코드의 IVFPQ는 SQ8보다 더욱 압축을 하는 방법

 

전체 벡터를 저장하지 않고 압축된 벡터만 저장하는 기법

 

SQ8이 4배정도 압축시켰다면 IVFPQ는 20배정도라고함

 

nlist = 100         #클러스터 개수
m = 8               #subquantizer 개수
quantizer = faiss.IndexFlatL2(d)

#각각의 sub vector가 8bit로 인코딩
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)

index.train(xb)
index.add(xb)

D,I = index.search(xq,k)   #검색

 

 

IVFPQ가 PQ기법 사용한거고 IVFFlat은 SQ8인가???

 

IndexFlatL2에는 gpu를 사용하여 GPU를 활용한 빠른 속도의 index build도 가능하게 한다고함

 

모든 벡터를 gpu에 올려서 exhaustive search를 상당히 빠르게 할수있지만 gpu memory 부담이 있을 수 있음

 

res = faiss.StandardGpuResources() #단일 GPU 사용

index_flat = faiss.IndexFlatL2(d)  #인덱스(cpu) 빌드

#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)  #검색

 

 

여러 GPU를 쓸수도 있다고는 하는데 (faiss.index_cpu_to_all_gpus) 많은 경우 하나만 써도 충분해

 

single을 쓰고 필요하다면 정말로 multi를 고려함

 

여러 GPU를 활용해서 연산 속도를 한층 더 높일 수는 있긴함

 

cpu_index = faiss.IndexFlatL2(d)

#gpu 인덱스로 옮기기
gpu_index = faiss.index_cpu_to_all_gpus(cpu_index)

gpu_index.add(xb)

D,I = gpu_index.search(xq,k) #검색