(6강) Scaling up with FAISS(Scailing Up)

newbie·2021년 10월 14일
0

강의소개

앞선 4, 5강에서 sparse / dense embedding을 활용해 문서 검색을 하는 방법에 대해 실습해보았습니다. 실습에서는 수만개 단위의 데이터였지만, 실제 문서 검색이 이루어지길 원하는 실제 상황에서는 그 문서의 수가 기하급수적으로 늘어나게 됩니다. 위키피디아 문서에서 검색하는 상황을 가정하더라도 5백만개 이상의 문서에서 검색을 수행해야 하고, 실제로는 수천만 ~ 억개의 문서가 존재할 수 있습니다. 이런 상황에서는 앞선 강의에서 배운 모든 문서들에 대해 검색을 수행하는 방법이 굉장히 오랜 시간과 많은 자원을 요구하게 됩니다.

이번 6강에서는 이렇게 scale이 커진 상황에서 어떻게 효율적으로 검색을 수행할 수 있을지에 대해 배워볼 예정입니다. 먼저 similarity search의 개념에 대해 간략하게 복습해본 후, 보다 효율적인 approximate search가 무엇인지 알아보겠습니다. 그리고 approximate search를 편리하게 사용할 수 있도록 도와주는 FAISS를 활용하는 방법에 대해 알아보고 실습해보겠습니다.

Further Reading


Passage Retrieval and Similarity Search

  • similarity search 기본 개념 복습

복습: Retrieval with dense embedding

  • question encoder - question의 representation vector 생성
  • passage encoder - 각 passage에 대한 representation vector 생성
  • 이후 question과 passage의 representation vector의 similiarity를 계산하여 score가 높은 top k개의 passage 선택

문제는, passage 개수가 많아질수록 연산량이 증가하게 된다. 따라서 어떻게하면 real time으로 원하는 passage를 찾을 수 있을까?**

  • 주어진 질문(query) 벡터 q에 대해 Passage 벡터 v들 중 가장 질문과 관련된 벡터를 찾아야 함
  • 여기서 관련성은 내적(inner Product)이 가장 큰 것
  • 4,5강에서 사용한 방법 : brute-force(exhautive) search
    • 저장해둔 모든 Sparse/Dense 임베딩에 대해 일일이 내적값을 계산하여 가장 큰 값의 passage 출력
    • Passage가 많아질수록 비효율적

MIPS & Challenges

  • 실제로 검색해야 할 데이터는 방대함
    • 5백만 개(위키피디아)
    • 수식억, 조 단위까지 커질 수 있음
  • 따라서 모든 문서 임베딩을 일일이 비교 불가
  • 1) Search Speed(ms per vector)
    • query마다 유사한 벡터를 K개 찾는데 얼마나 오래 걸릴지
      • 가지고 있는 벡터량이 클수록 오래 걸림
    • Pruning을 고려
  • 2) Memory(RAM) Usage, bytes per vector
    • 벡터를 사용할 때, 어디에서 가져올 수 있을지
      • RAM에 모두 올려둘 수 있으면 빠르지만, 많은 RAM용량을 요구함
      • 디스크에서 계속 불러와야한다면 속도가 느려짐
    • Compression 방법론 고려
  • 3) Accuracy( % of actual nearest neighbors found at rank 1)
    • brute-force 검색 결과와 얼마나 비슷한지
      • 속도를 증가시키려면 정확도를 희생해야 하는 경우가 많음
    • Exhaustive search 방법론 고려(검색 효율을 향상시켜야 함)

Approximating Similarity Search

  • 검색 방법론 approximation 및 속도 개선 및 문서 탐색방법 학습

Compression - Scalar Quantization(SQ)

  • compression: vector를 압축하여, 하나의 vector가 적은 용량을 차지 => 압축량 증가 시 메모리 감소 및 정보 손실 증가
    • e.g.) 4-byte floating point를 1 byte unsigned interger로 압축

Pruning - Inverted File(IVF)

  • Pruning: search space를 줄여 search 속도 개선(dataset의 subset만 방문)
    • clustering + inverted file을 활용한 search
      • clustering : 전체 vector space를 k개의 cluster로 나눔
        • e.g.) k-means clustering
      • inverted file(IVF) : vector의 index = inverted list structure
        • '각 cluster의 centroid id'와 '해당 cluster의 vector들'이 연결되어있는 형태

Introduction to FAISS

  • FAISS 라이브러리를 활용한 scail up 학습

What is FAISS

  • facebook에서 만든, fast approximation을 위한 open-source library
  • large scale의 passage를 다루는데 매우 효율적임
  • backone은 C++이지만, wrapping은 python으로 되어 있기에 쉽게 사용 활용 가능
  • faiss encoding보단 indexing에 도움을 주는 라이브러리

Passage Retrieval with FAISS

  • 1) Train index and map vectors
    • FAISS를 사용하기 위해선 cluster를 확보해야 함
    • 이 때 각 passage의 encoding vector값이 랜덤하게 지정하면 비효율적으로 clustering을 하므로 학습 데이터가 필요
    • 그리고 SQ(float32->int)를 해야 하는데, Quantization 시 float의 max, mean값이 몇이며, 이걸 얼마로 scaling할 지를 파악할 필요가 있음
    • 즉, train 후 add를 통해 mapping을 위한 준비를 완료함
  • 2) search based on FAISS index
    • nprobe를 정하고, 가장 가까운 nprobe만큼의 cluster를 방문하여 search
    • top-k개를 search result로 출력

Scaling up with FAISS

  • 실습

FAISS Basics

# brute-force로 모든 벡터와 쿼리를 비교하는 가장 단순한 인덱스 만들기
#pruning과 SQ을 활용하지 않기에 학습이 불필요함

# 준비
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) # 인덱스 빌드하기, dimension 정의
index.add(xb)                # 인덱스에 벡터 추가하기

# 검색하기
k = 4                      # top-k : 4개
D, I = index.search(xq, k) # 검색하기
# D : 쿼리와의 거리
# I : 검색된 passage 벡터의 인덱스

IVF with FAISS

# IVF 인덱스 만들기
# 클러스터링을 통해서 가까운 클러스너 내 벡터들만 비교
# 빠른 검색 가능
# 클러스터 내에서는 여전히 전체 벡터와 거리 비교(flat)

# IVF 인덱스
nlist = 100                                     # 클러스터 개수
quantizer = faiss.IndexFlatL2(d)                # 클러스터에서 거리를 재는 방법을 지정(여기선 L2)
index = faiss.IndexIVFFlat(quantizer, d, nlist) # Inverted FIle 만들기
# quantizer를 이용하여 n개의 클러스터를 만들기 위한 사전 준비 작업

index.train(xb)                                 # 클러스터 학습하기
#xb가 매우 큰 경우 일부만 샘플링하여 train 시킴
#단, add 시에는 모든 xb 사용

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

# 검색하기
k = 4                      # top-k : 4개
D, I = index.search(xq, k) # 검색하기

IVF-PQ with FAISS

# 벡터 압축 기법(PQ) 활용하기
# SQ보다 더 압축이 많이 되지만, 일단은 SQ를 해보고 필요할 경우 PQ를 이용해보아요..
# 전체 벡터를 저장하지 않고 압축된 벡터만을 저장
# 메모리 사용량을 줄일 수 있음

# IVF-PQ 인덱스
nlist = 100                                     # 클러스터 개수
m = 8                                           # subquantizer 개수
quantizer = faiss.IndexFlatL2(d)                # 클러스터에서 거리를 재는 방법을 지정(여기선 L2)
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8) # 각각의 sub-vector가 8bits로 인코딩 됨
# quantizer를 이용하여 n개의 클러스터를 만들기 위한 사전 준비 작업

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

# 검색하기
k = 4                      # top-k : 4개
D, I = index.search(xq, k) # 검색하기

Using GPU with FAISS

# GPU의 빠른 연산속도를 활용할 수 있음
  # gpu에 모든 vector를 올리는 것이기에, exhaustive search 등 거리 계산을 위해 행렬곱 등에서 유리
# 다만, GPU 메모리 제한이나 메모리 random access 시간이 느린 것이 단점

# 또한 gpu를 사용하므로써 라이브러리를 제한적으로 사용해야 함
  # IndexFlatL2만 사용 가능하며, 다른 search 알고리즘을 사용하기 어려움
# 단일 GPU 인덱스
res = faiss.StandardGpuResources()              # 단일 GPU 사용하기
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 = index.search(xq, k)                       # 검색하기

Using Multiple GPUs with FAISS

# 여러 GPU를 활용하여 연산 속도를 한층 더 높일 수 있음
# 대부분의 경우 Multi GPUs까지는 불필요하므로 일단 싱글 GPU 방법부터 적용

cpu_index = faiss.IndexFlatL2(d)

#gpu 인덱스로 옮기기
gpu_index_flat = faiss.index_cpu_to_all_gpus(cpu_index)
gpu_index_flat.add(xb)
D,I = index.search(xq, k)                       # 검색하기

profile
DL, NLP Engineer to be....

0개의 댓글