Passage Retrieval - Scailing Up

Passage Retrieval and Similarity Search

복습 Retrieval with dense embedding
- 인퍼런스 : Passage와 query를 각각 임베딩한 후 query로부터 거리가 가까운 순서대로 passage에 순위를 매김
MIPS(Maximum Inner Product Search)
- 주어진 질문(query) 벡터 q에 대해 Passage 벡터 v들 중 가장 질문과 관련된 벡터를 찾아야함
- 여기서 관련성은 내적(inner product)이 가장 큰 것
- 4, 5강에서 사용한 검색 방법 : brute-force(exhaustive) search
  - 저장해둔 모든 Sparse/Dense 임베딩에 대해 일일히 내적값을 계산하여 가장 값이 큰 passage를 추출
MIPS in Passage Retrieval
MIPS & Challenges
- 실제로 검색해야할 데이터는 훨씬 방대함
  - 5백만 개(위키피디아)
  - 수십억, 조 단위까지 커질 수 있음
  - ⇒ 따라서 더이상 모든 문서 임베딩을 일일히 보면서 검색할 수 없음
Tradeoffs of similarity search
1. Search Speed
  - 쿼리당 유사한 벡터를 k개 찾는데 얼마나 걸리는지?
  - ⇒ 가지고 있는 벡터량이 클 수록 더 오래 걸림
2. Memory Usage
  - 벡터를 사용할 때, 어디에서 가져올 것 인지?
  - ⇒ RAM에 모두 올려둘 수 있으면 빠르지만, 많은 RAM 용량을 요구함
  - ⇒ 디스크에서 계속 불러와야한다면 속도가 느려짐
3. Accuracy
  - brute-force 검색 결과와 얼마나 비슷한지?
  - ⇒ 속도를 증가시키려면 정확도를 희생해야하는 경우가 많음
Tradeoff of search speed and accuracy
- 속도(search time)와 재현율(recall)의 관계
- 더 정확한 검색을 하려면 더 오랜 시간이 소모됨
Increasing search space by bigger corpus
- 코퍼스(corpus)의 크기가 커질 수록
  - 탐색 공간이 커지고 검색이 어려워짐
  - 저장해 둘 Memory space 또한 많이 요구됨
  - Sparse Embedding의 경우 이러한 문제가 훨씬 심함
  - 예) 1M docs, 500K distint terms = 2TB
    - 각 문서를 768차원의 벡터로 표현한 경우

Approximating Similarity Search

Compression - Scalar Quantization (SQ)
- Compression : vector를 압축하여, 하나의 vector가 적은 용량을 차지 ⇒ 압축량↑ ⇒ 메모리↓, 정보 손실↑
- ex) Scalar quantization : 4-byte floating point ⇒ 1-byte (8bit) usigned integer로 압축
Pruning - Inverted File (IVF)
- Pruning : Search space를 줄여 search 속도 개선 (dataset의 subset만 방문)
- ⇒ Clustering + Inverted file을 활용한 search
1. Clustering : 전체 vector space를 k개의 cluster로 나눔 (ex. k-means clustering)
2. Inverted file (IVF)
  - Vector의 index = inverted list structure
  - ⇒ (각 cluster의 centroid id)와 (해당 cluster의 vector들)이 연결되어있는 형태
  - Searching with clustering and IVF
  1. 주어진 query vector에 대해 근접한 centroid 벡터를 찾음
  2. 찾은 cluster의 inverted list 내 vector들에 대해 서치 수행

Introduction to FAISS

What is FAISS
- github : https://github.com/facebookresearch/faiss
- tutorial : https://github.com/facebookresearch/faiss/tree/main/tutorial/python
- FAISS : Library for efficient similarity search
  - indexing쪽 도움을 주고 encoding쪽 도움을 주고 있는 부분은 아님
Passage Retrieval with FAISS
1. Train index and map vectors
- train과 add 단계가 있음
1. Search based on FAISS index
  - nprobe : 몇 개의 가장 가까운 cluster를 방문하여 search 할 것인지

Scaling up with FAISS

FAISS Basics
- brute-force로 모든 벡터와 쿼리를 비교하는 가장 단순한 인덱스 만들기
- 준비하기
- 인덱스 만들기
- 검색하기
IVF with FAISS
- IVF 인덱스 만들기
- 클러스터링을 통해서 가까운 클러스터 내 벡터들만 비교함
- 빠른 검색 가능
- 클러스터 내에서는 여전히 전체 벡터와 거리 비교(Flat)
- IVF 인덱스
IVF-PQ with FAISS
- 벡터 압축 기법(PQ) 활용하기
- 전체 벡터를 저장하지 않고 압축된 벡터만을 저장
- 메모리 사용량을 줄일 수 있음
- IVF-PQ 인덱스
Using GPU with FAISS
- GPU의 빠른 연산 속도를 활용할 수 있음
  - 거리 계산을 위한 행렬곱 등에서 유리
- 다만, GPU 메모리 제한이나 메모리 random access 시간이 느린 것 등이 단점
- 단일 GPU 인덱스
Using Multiple GPUs with FAISS
- 여러 GPU를 활용하여 연산 속도를 한층 더 높일 수 있음
- 다중 GPU 인덱스

출처: 부스트캠프 AI Tech 4기(NAVER Connect Foundation)