MRC(8) : FAISS

SeongGyun Hong·2024년 10월 7일
IVF-PQMIPSMRCfaissnaverboostcamp

NaverBoostCamp

목록 보기
8/64

0. Preview...

이전까지 Sparse / Dense Embedding 방식을 배웠는데, 기본적으로 위와 같은 방식들은 문서 파싱을 할 때 수만개 단위에서야 작동하겠지만, 실제 프로젝트에 적용할 때 수십, 수백만 더 많게는 억개의 단위의 문서들 속에서 정상적으로 효용성 있게 작동할지는 미지수다.
따라서 이러한 scale 이슈에서 대처할 수 있게 보다 효과적인 방법을 알아보자.

1. 질문과 문서간 유사도를 측정하는 방법

기본 전제이다.
들어오는 질문(Query)과 해당 질문이 탐색할 문서 뭉텅이들(Passage)들을 같은 Vector Space에 Embedding 시켜준다.

그리고 해당 Embedding space에서 Query와 각 Passage들을 내적시키거나 기타 방법들을 이용하여 Similarity Score를 구하는 것.
(현재 Inner Product 즉 내적이 많이 쓰이고, Nearest Neighbor는 덜 쓰이는 추세)

그렇구해진 Similarity Score를 정렬시키면 해당 Query에 관련성이 높은 Context들이 정렬되게 된다.

위와 같은 과정을 Similarity Search라고 한다.

1.1 Inner Product

간단히 말해 내적이다. 두 벡터의 유사도를 측정하는 데 사용되며, 두 벡터의 크기를 곱한 값의 합으로 계산된다.

1.2 Nearest Neighbor

데이터 분류 또는 군집화 하는데 사용되는 기법이다. 주어진 데이터 포인트와 가장 가까운 데이터 포인트를 찾아내어 분류하거나 예측한다.
최근에 복잡한 데이터셋 또는 고차원 데이터에 대한 머신러닝을 진행할 때에 계산비용이 많이 들기 떄문에 내적과 같은 효율적인 방법이 많이 선호된다.

Query와 Passage 각각을 모두 동일 공간의 Vector Space로 Embedding 시키고 해당 두 값을 모두 내적하여 가장 내적갑싱 큰 Passage를 정렬시키는 방식.

그러나 brute-force 방식의 searching은 실제 상황 속에서 부딪히는 제약사항이 너무 많다. 예컨데, 실제 위키피디아 문서만 해도 5백만개이다. 여기서 어떻게 일일이 다 유사도 검색을 진행할 수 있을까?
즉, 모든 문서를 임베딩 해보며 검색하는 것은 너무나 순진한 이야기가 될 수 있다.


2. Maximum Inner Product Search (MIPS)

MIPS란 Maximum Inner Product Search의 줄임말로, 머신러닝 데이터 사이언스에서 매우 중요한 개념이다.

MIPS는 주어진 Query 벡터와 가장 높은 Inner Product를 갖는 벡터를 대규모 데이터베이스 또는 데이터셋에서 찾는 것을 목표로 한다.

2.1 MIPS의 정의

데이터베이스 S에 있는 벡터들 xix_i와 쿼리 벡터 qq가 주어졌을 때, 다음을 만족하는 ii를 찾는 것

arg max⁡i∈S⟨xi,q⟩\underset{i \in S}{\operatorname{arg\,max}} \langle x_i, q \rangle
여기서 ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle은 둘의 내적을 나타냄.

위와 같은 MIPS의 개념은 추천 시스템, 자연어처리, 컴퓨터 비전 등에서 다양하게 활용된다.

2.2 MIPS의 알고리즘

1. 선형 검색

모든 벡터와 쿼리의 Inner Product 즉, 내적을 계산하는 것이다. 다만 위 방법의 경우에는 데이터셋이 큰 경우에 비용이 크게 증가한다.(Sparse Embedding된 경우에는 문제가 훨씬 심함)

2. 변환 기반 방법

MIPS 문제에 대해서 NNS 즉, Nearest Neighbor Search로 해결하려고 한다. 예컨데, 벡터에 추가 차원을 더하여 유클리드 거리 최소화 문제로 바꾸는 방식이다.

3. BanditMIPS

최근 제안된 방법으로 BanditMIPS 알고리즘의 경우 차원 d에 독립적인 복잡도를 가지게 된다. 위 이론은 Multi-Armed Bandit 이론에 기반하여 적응적으로 좌표를 샘플링 한다.
실제 Vector Space가 100차원이라고 하더라도, 100차원 전체를 계산하지 않고 효율적으로 최적의 제안이 가능한 것.

  • 실제 MovieLens 데이터셋을 대상으로 기존의 방식들 보다 20배 빠른 성능을 보임.


3. Similarity Search 알고리즘 고려 사항

정확도 메모리 검색속도

위 세가지는 서로 Trade-Off 관계에 있고 이것을 최적화 하는 것이 Similarity Search의 핵심이다.

  • 정확도
    높은 정확도 유지를 위해 모든 경우의수를 탐색한다는 것은 Exhaustive Search를 진행한다는 의미인데, 위의 경우에는 많은 메모리와 시간을 요한다.

  • 메모리 사용량(RAM)
    그렇다고 메모리를 줄이기 위해 벡터당 필요로 하는 메모리의 양(바이트)을 줄인다? 즉, Compression, 압축을 진행한다는 것은 저장 공간을 절약하는 효과가 있는 방면, 압축과정에서의 손실에 의해 데이터 정확도가 떨어질 수가 있다.
  • 검색 속도(Search Speed)
    또한 검색속도를 높히기 위해 사용하는 Pruning 등의 기법들의 경우에도 마찬가지로 불필요한 계산을 줄여 빠른 검색을 가능하게 하지만, 정확도를 희생하는 측면이 있다.

따라서 Similarity Search를 구현할 때응 위 세가지의 Trade-off 관계를 최적화하고 충분히 고려하여 기능을 구현해야하는 측면이 있다.

4. 구체적인 최적화 방안

4.1 Compression : 메모리 최적화

보통 숫자를 저장할 때에 사용하는 float32라는 4-byte floating point를 시용하는데, 이를 1-byte로 압축하는 등 메모리를 최적화 하는 것.

4.2 Pruning : 검색속도 향상

프루닝은 기본적으로 불필요한 데이터를 제거하여 속도를 향상시키는 기법을 의미한다.
Similarity Search에서 Pruning을 한다는 것은 Search Space 자체를 줄여 search 속도를 개선한다는 것을 의미한다.

  • dataset의 subset에 대해서만 접근 하는 것이 키워드 !

4.2.1 clustreing

전체 Vector Space를 K개의 cluster로 나누는 K-means clustering 기법 등을 사용한다.
query가 가장 근접한 cluster에 대해서만 접근하기 위해 군집화 시키는 것.

4.2.2 Inverted file(IVF)

  1. 근접한 Centroid Vector 찾기
    clustering을 통해 클러스터들을 생성한 후에, 주어진 query vector에 대해서 해당 query vector와 근접한 centroid 벡터를 찾는다.

    이때 centroid vector란 각 군집의 중심점을 의미한다. 즉, 클러스터 내 모든 데이터 포인트 간의 평균 위치를 나타내는 점이다.

  2. Inverted List를 사용한 Search
    해당 군집에서 centroid vector를 포함하는 inverted list 내 vector들에 대해서만 search를 수행한다.

    쉽게 말해 query가 속한 군집에 대해서만 search

    참고 : Inverted list와 Posting list

    예시:
    만약 문서 A, B, C가 있고, 각각 아래와 같은 내용을 포함한다고 가정한다면,

    문서 A: "I like apple."

    문서 B: "Apple is good for health."

    문서 C: "Oranges are also good."

    이 경우, inverted list와 posting list는 다음과 같다:

    Inverted List:
    apple -> [A, B]

    Posting List:
    apple -> [(A, 위치 3), (B, 위치 1)]


5. FAISS

FAISS란, 고차원 벡터 데이터에서 효율적인 유사성 검색 및 클러스터링(군집화)를 수행하기 위해 FaceBook AI Research 팀에서 개발한 라이브러리를 의미한다.

유클리드 거리, 코사인 유사도 등의 다양한 거리 측정 방식을 지원하며, 밀리초 내에서 수백만 개의 vector를 검색할 수 있는 알고리즘을 가지고 있으며, GPU 기반 병렬 연산을 지원하기에 처리 속도가 굉장히 빠르다.

활용 분야

  • 텍스트 분류 및 클러스터링
  • 이미지 검색
  • 이상 탐지
  • 추천 시스템

5.1 Index 유형

5.1.1 Flat 인덱스

모든 벡터 간 거리를 계산하는 기본적인 방식
구현이 간단하고 작은 데이터셋에 적합하다.

5.1.2 Hierarchical 인덱스

벡터 공간은 여러 계층으로 나누어 검색을 최적화하는 방식
1. 벡터 공간을 여러 클러스터로 나누고
2. 각 클러스터 내에서 다시 서브클러스터로 나눈다.
3. 이 과정을 반복해서 트리 구조를 형성한다.

5.1.3 Product 인덱스

여러 벡터를 조합하여 더 복잡한 벡터를 생성하고 인덱스화 하는 방식
1. 벡터를 여러 부분 벡터로 나눈다.
2. 각 부분 벡터를 독립적으로 양자화한다.
3. 양자화된 코드를 조합하여 원본 벡터를 근사한다.

5.1.4 HNSW

ANN(Approximate Nearest Neighbors) 검색에서 가장 널리 사용되는 알고리즘
1. 다층 그래프 구조를 생성한다.
2. 상위 레이어에서 대략적인 검색을 수행한 후에 하위 레이어로 이동하며 정밀한 검색을 수행한다.

다층 그래프 구조?
복잡한 네트워크 시스템을 여러 계층으로 표현하는 방식을 의미한다. 이는 단일 계층의 그래프로는 표현하기 어려운 복잡한 관계와 구조를 더 효과적으로 모델링할 수 있게 해준다.

  • 특징
    • 여러 계층으로 구성
      다층 그래프는 여러 개의 서브 그래프(층)으로 구성되며, 각 층은 특정 유형의 관계나 상호작용을 나타낸다.
    • 계층 간 연결
      서로 다른 층의 노드들 사이에서도 연결이 존재할 수 있어, 복잡한 상호작용 표현이 가능하다.
    • 계층적 구조
      상위 계층과 하위 계층 간의 관계 표현이 가능하다. 따라서 시스템의 계층적 특성을 모델링할 수 있다.
    • 다차원 데이터 표현
      각 층이 각기 다른 유형의 데이터나 그 관계를 나타낼 수 있어서 다차원적인 데이터를 효과적으로 표현 가능하다.

5.2 Vector Quantization

고차원 벡터를 컴팩트한 코드로 압축하는 것으로 이를 통해 메모리 사용량을 크게 줄일 수 있다.

5.2.1 SQ : Scalar Quantization

각 벡터의 차원을 독립적으로 양자화하는 방법을 의미한다.
1. 각 차원의 값 범위를 여러 구간으로 나누고
2. 각 값을 해당하는 구간의 대표값으로 대체한다.

# 예시코드 - FAISS 라이브러리 사용 X
import numpy as np

def scalar_quantize(vector, num_bits=8):
    min_val, max_val = vector.min(), vector.max()
    step = (max_val - min_val) / (2**num_bits - 1)
    quantized = np.round((vector - min_val) / step).astype(int)
    return quantized, min_val, step

def scalar_dequantize(quantized, min_val, step):
    return quantized * step + min_val

# 사용 예
vector = np.random.rand(128)
quantized, min_val, step = scalar_quantize(vector)
dequantized = scalar_dequantize(quantized, min_val, step)

print(f"Original size: {vector.nbytes} bytes")
print(f"Quantized size: {quantized.nbytes} bytes")
print(f"Mean squared error: {np.mean((vector - dequantized)**2)}")
# 예시코드 - FAISS 라이브러리 사용 O
import numpy as np
import faiss

# 데이터 생성
d = 128  # 벡터 차원
nb = 10000  # 벡터 개수
np.random.seed(1234)
xb = np.random.random((nb, d)).astype('float32')

# 스칼라 양자화 인덱스 생성 (8비트)
index = faiss.IndexScalarQuantizer(d, faiss.ScalarQuantizer.QT_8bit)

# 벡터 추가
index.train(xb)
index.add(xb)

# 검색 수행
k = 5  # 상위 k개 결과 검색
xq = np.random.random((1, d)).astype('float32')
D, I = index.search(xq, k)

print(f"검색 결과 거리: {D}")
print(f"검색 결과 인덱스: {I}")

5.2.2 PQ : Product Quantization

벡터를 여러 부분으로 나누고, 각 부분 벡터를 독립적으로 양자화하는 방법이다.
1. 벡터를 여러 부분벡터로 나누고
2. 각 부분 벡터 공간에서 k-means 클러스터링을 수행한다.
3. 각 부분 벡터를 가장 가까운 centroid의 인덱스로 대체한다.

# 예시코드 - FAISS 라이브러리 사용 X
import numpy as np
from sklearn.cluster import KMeans

def product_quantize(vectors, num_subvectors=4, num_clusters=256):
    n, d = vectors.shape
    subvector_dim = d // num_subvectors
    
    quantized = np.zeros((n, num_subvectors), dtype=np.uint8)
    codebooks = []
    
    for i in range(num_subvectors):
        start = i * subvector_dim
        end = (i + 1) * subvector_dim
        subvectors = vectors[:, start:end]
        
        kmeans = KMeans(n_clusters=num_clusters, n_init=1)
        labels = kmeans.fit_predict(subvectors)
        
        quantized[:, i] = labels
        codebooks.append(kmeans.cluster_centers_)
    
    return quantized, codebooks

# 사용 예
vectors = np.random.rand(1000, 128)
quantized, codebooks = product_quantize(vectors)

print(f"Original size: {vectors.nbytes} bytes")
print(f"Quantized size: {quantized.nbytes + sum(cb.nbytes for cb in codebooks)} bytes")
# 예시코드 - FAISS 라이브러리 사용 O
import numpy as np
import faiss

# 데이터 생성
d = 128  # 벡터 차원
nb = 10000  # 벡터 개수
np.random.seed(1234)
xb = np.random.random((nb, d)).astype('float32')

# 프로덕트 양자화 인덱스 생성
m = 8  # 서브벡터 수
bits = 8  # 각 서브벡터당 비트 수
index = faiss.IndexPQ(d, m, bits)

# 벡터 추가
index.train(xb)
index.add(xb)

# 검색 수행
k = 5  # 상위 k개 결과 검색
xq = np.random.random((1, d)).astype('float32')
D, I = index.search(xq, k)

print(f"검색 결과 거리: {D}")
print(f"검색 결과 인덱스: {I}")
profile
SeongGyun Hong
헤매는 만큼 자기 땅이다.
이전 포스트

MRC(7) : Retrieval - Dense Embedding

다음 포스트

MRC(9) : ODQA

0개의 댓글