[ODQA] 6. Passage Retrieval - Scaling Up

1. Passage Retrieval and Similarity Search
2. Approximating Similarity Search
3. Introduction to FAISS

 

실제 문서 검색이 이루어지길 원하는 실제 상황에서는 그 문서의 수가 기하급수적으로 늘어나게 된다. 위키피디아 문서에서 검색하는 상황을 가정하더라도 5백만 개 이상의 문서에서 검색을 수행해야 하고, 실제로는 수천만 ~ 억 개의 문서가 존재할 수 있다. 이런 상황에서는 모든 문서들에 대해 검색을 수행하는 방법이 굉장히 오랜 시간과 많은 자원을 요구하게 된다.

이렇게 scale이 커진 상황에서 어떻게 효율적으로 검색을 수행할 수 있을지에 대해 정리하고 보다 효율적인 approximate search가 무엇인지 그리고 approximate search를 편리하게 사용할 수 있도록 도와주는 FAISS를 활용하는 방법에 대해 정리하였다.

 

1. Passage Retrieval ans Similarity Search

실제 문서 검색이 이루어지길 원하는 실제 상황에서는 그 문서의 수가 기하급수적으로 늘어나게 된다. 위키피디아 문서에서 검색하는 상황을 가정하더라도 5백만 개 이상의 문서에서 검색을 수행해야 하고, 실제로는 수천만 ~ 억 개의 문서가 존재할 수 있다. 이런 상황에서는 모든 문서들에 대해 검색을 수행하는 방법이 굉장히 오랜 시간과 많은 자원을 요구하게 된다.

이렇게 scale이 커진 상황에서 어떻게 효율적으로 검색을 수행할 수 있을까?

 

▮ MIPS (Maximum Inner Product Search)

• Nearest Neighbor Search보다 Inner Porduct Search가 많이 사용된다.
  • L2 Distanche를 측정하는 것보다 Dot Product를 계산하여 최댓값을 찾는 문제가 더 효율적이다.
• 그러나 Brute-force(Exhaustive) Search 방식은 문서의 양이 많아질 수록 비효율적이다!

 

 

▮ Tradeoffs of Similarity Search

1. Search Speed
   • 쿼리 당 유사한 벡터 K개를 찾는데 얼마나 걸리는가?
     → 가지고 있는 벡터량이 클 수록 더 오래걸린다.
2. Memory Usage
   • 벡터를 사용할 때 어디서 가져올 것인가?
     → RAM에 모두 올려둘 수 있으면 빠르지만 많은 RAM 용량이 필요하다.
     → 디스크에서 계속 불러와야한다면 속도가 느려진다.
     
3. Accuracy
   • Brute-force 검색 결과와 얼마나 비슷한가?
     → 속도를 증가시키려면 정확도를 희생시켜야한다.

 

accuracy를 높이기 위해서는 어떻게하면 검색을 더 효율적으로 할 것인가에 대해서 고민을 해야한다.

memory를 줄이기 위해서는 Compression을 고민해야한다. 

Search Speed를 올리기 위해서는 inference time때 pruning 같은 mechanism을 활용해 approximation을 더 많이 하는 대신 경우에 따라서는 정확성을 좀 잃더라도 필요한 속도를 확보할 수 있다.

 

• Tradeoff of Search Speed and Accuracy
  • 더 정확한 검색을 하려면 더 오랜 시간이 소모된다.
• Increasing Search space by Bigger corpus
  • 코퍼스의 크기가 커질수록
    • 탐색 공간이 커지고 검색이 어려워진다.
    • 저장해 둘 Memory space 또한 많이 요구된다.
    • Sparse Embedding 의 경우 이러한 문제가 훨씬 심하다.

 

 

2. Approximating Similarity Search

▮ Compression - Scalar Quantization (SQ)

• Compression 기법
  각각 수치를 Qunatize 해  용량을 줄인다.
  
• Vector를 압축해 하나의 Vector가 적은 용량을 차지 → 압축량 ↑ → 메모리 ↓, 정보 손실 ↑

4-byte floating point → 1-byte (8bit) unsigned integer로 압축

Inner product search를 하는 경우, 4byte까지 필요한 경우가 많지 않다. 보통 1byte로 approximate해도 정확하다.

 

 

▮ Inverted File (IVF)

• Pruning 기법
  점들을 정해진 클러스터에 소속시켜 군집을 만든다.
  쿼리가 들어왔을 때, 쿼리와 근접한 클러스터만 확인하는 방식이다.
  근접한 클러스트 내에서는 Exhaustive Search로 다 확인한다.
• Search Space를 줄여 Search 속도를 개선시키는 방법이다. (Data의 Subset만 방문)

1) Clustering

• 전체 Vector Space를 K개의 cluster로 나눈다. (ex. k-means clustering)

2) Inverted file (IVF)

• Vector의 index = inverted list structure
  → 각 cluster의 centroid id와 해당 cluster의 vector 들이 연결되어있는 형태

 

3) Searching with Clustering & IVF

• 주어진 Query 벡터에 대한 근접한 Centroid 벡터를 찾는다.
• 찾은 Cluster의 inverted list 내의 Vector들에 대해 Search를 수행한다.

 

 

 

3. Introduction to FAISS

• FAISS는 facebook에서 만든 efficient similarity search를 위한 라이브러리이다.
• Indexing 부분에 도움을 준다. (Encoding부분은 전혀 상관없다!)

 

▮ Passage Retrieval with FAISS

1. Train Index & Map Vectors

 

어떤 vector들을 확보하게 되면 학습단계가 선행되어야 한다.

1. 학습을 하는 이유는 FAISS를 활용하려면 pruning, 즉 cluster들을 확보해야하는데 당연히 random하게 cluster 를 지정하게 되면 상당히 비효율적일 것이다. 그래서 cluster들은 data point들의 분포를 보고 적절한 cluster를 지정해야 한다.
2. Scalar Quantization하는 과정에서도 (float32(4byte) → int8(1byte)) 아주 range가 큰 float number를 integer 0~255 사이로 압축시키기 때문에 float number의 max가 얼마인지 minimum이 얼마인지, 그리고 얼마로 scale하고 얼만큼을 upset 할 것인지에 대해서 파악해야 하기 때문에 FAISS로 index를 building 할 때 학습단계가 필요하다.

 

학습을 통해 Cluster와 SQ8이 정의되면 실제로 cluster와 cluster내의 vector들을 SQ8형태로 투입한다.

train 단계와 adding 단계가 있는데, 대부분의 경우 train과 add하는 데이터를 따로 구분하지는 않는다.

다만 데이터가 너무 많은 경우에는 더할 데이터가 너무 많아 전부를 학습하기에는 비효율적일 때 add할 데이터의 일부를 sampling해서 학습데이터로 활용한다.

정말 데이터가 커지는 경우는 대충 40분의 1 정도의 크기나 샘플링해서 쓰는 경우도 있다.

 

2. Search based on FAISS index 

• nrpobe : 몇 개의 가장 가까운 cluster를 방문하여 search 할 것인지

Query와 가장 근접한 Cluster를 찾고 Cluster 내에 있는 벡터들을 Exhuastive Search해서 가장 유사한 Top-k개의 벡터를 찾아낸다.

 

 

 

▮ How to Use FAISS 

!pip install faiss-cpu

import faiss

d = 64                                            # 벡터의 차원
nb = 100000                                       # 데이터베이스 크기
nq = 10000                                        # 쿼리 개수
xb = np.random.random((nb, d)).astype('float32')  # 데이터베이스 예시
xq = np.random.random((nq, d)).astype('float32')  # 쿼리 예시

 

Brute-force로 모든 벡터와 쿼리를 비교하는 단순한 인덱스 생성

faiss.IndexFlatL2()라는 함수를 이용해서 dimension을 정의해주고 더해준다.

여기서는 Pruning과 Scalar Quantization을 활용하지 않기 때문에 학습이 필요없다.

그래서 index.add만 하는 것이다.

index = faiss.IndexFlatL2(d)      # 인덱스 빌드하기
index.add(xb)                     # 인덱스에 백터 추가하기

top-k로 몇개를 retrieval 할지를 설정하고 index.search()를 통해 해당하는 쿼리와  k 값을 넣어 D(쿼리와의 실제 거리), I(Passage의 index id)를 도출한다.

k = 4                             # 가장 가까운 벡터 4개를 찾고 싶음
D, I = index.search(xq, k)        # 검색하기
# D: 쿼리와의 거리
# I: 검색된 벡터의 인덱스

 

 

IVF with FAISS

클러스터링을 통해 가까운 클러스터 내 벡터들만 비교한다.

 

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

quantizer는 클러스터에서 거리를 계산할 때 어떻게 계산할 지에 관한 것이다.
클러스터끼리 거리를 계산하는 방법은 L2 방식(거리를 계산)으로 할 것이고 exhaustive하게 거리를 계산하기때문에 IndexFlatL2를 활용해서 quantizer를 생성하였다.

 

이렇게 클러스터와 쿼리의 거리를 계산하는 방법론을 정의했으면 quantizer를 활용해서 faiss.IndexIVFFlat() 클래스로 초기화해준다. 즉, quantizer를 활용해서 클러스터를 만들겠다는 의미이다.

여기서 nlist라는 파라미터는 클러스터의 개수를 정의한다.

 

그리고나서 train을 통해 IndexIVFFlat이 학습데이터 xb를 활용해서 nlist 개수만큼 클러스터를 k-means 알고리즘으로 생성한다.

 

그 다음에 다시 index.add(xb)를 해준다.

위에서 설명해준 것 처럼 train과 add하는 xb가 꼭 다를 필요는 없고
만약 xb가 너무 큰 경우 학습할 때 너무 오래걸릴 수 있으므로 xb의 일부를 sampling 해서 train을 해주고
retrieval 하는 대상을 뺄 수 없으므로 add하는 것은 xb를 모두 사용해준다.

 

그 다음으로는 쿼리가 들어왔을 때 search를 한다.

 

 

IVF-PQ with FAISS

• 벡터 압축 기법 PQ
• SQ보다 압축량을 더 높일 수 있는 방법

nlist = 100                                         # 클러스터 개수
m = 8                                               # subquantizer 개수

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

index.train(xb)
index.add(xb)
D, I = index.search(xq, k)                          # 검색하기

 

 

Using GPU with FAISS

• GPU의 빠른 연산속도를 활용
• 그러나 IndexFlatL2만 가능하다.

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

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