https://github.com/facebookresearch/faiss
FAISS (Fine-Grained Image Similarity Detection Using Facebook AI Similarity Search)
- 고속 벡터 검색 엔진으로 유사도 검색하기, Vector Search Engine
: 벡터화 된 데이터를 인덱싱하고 데이터에 대한 효율적인 검색을 수행하기 위해서 Facebook AI에서 구축한 C++ 기반 라이브러리이다.
- Faiss 는 벡터 검색 엔진이고 유사도 검색을 하거나 추천, 기계학습으로 만든 모델을 활용해서 응용 서비스를 만들 때 사용한다.
일반적으로 검색 엔진이라고 말하면 흔히 텍스트를 검색하는 것을 생각한다. 구글의 웹 검색, 네이버 검색, 다음 검색 같은 것은 검색 포털이다. 그게 아니면 ElasticSearch나 Lucene 같은 검색 엔진을 생각한다
하지만 벡터 검색은 텍스트가 아닌 벡터를 빠른 속도로 찾는 것을 말한다. 벡터는 수열을 말한다. 10개의 숫자가 묶여 있으면 이걸 10차원 벡터라고 한다. 숫자가 100개 있으면 100차원 벡터 1000개면 1000차원 벡터이다. 이런 것들이 수억개가 있고 수억개 중에 어떤 벡터와 가장 가까운 벡터를 찾아야 한다면 문제가 어려워진다. 가장 가까운 것을 주어진 입력 벡터와 수억 개의 벡터를 모두 하나씩 연결해서 서로의 거리를 계산한 다음 가장 가까운 것을 찾아야 하기 때문이다
만약 어떤 사용자가 온라인 서적 판매사이트에 접속했을 때 그 사람에게 책을 추천해줘야 하는데 추천할 책 목록을 검색하는데 10분씩 걸린다면 서비스에 적용하지 못합니다. 다른 서비스도 마찬가지구요.
Faiss는 인덱싱 방식을 다르게 해서 데이터가 많아도 짧게는 밀리초 단위 길게는 수초 이내에 결과를 찾아 줍니다. 즉 온라인 추천 서비스에 빠르게 적용하는 추천 시스템 등을 개발하는데 사용할 수 있습니다.
※ FAISS는 인덱싱을 도와주는 것이지 임베딩을 도와주는 것이 아님
What is FAISS
- facebook에서 만든, fast approximation을 위한 open-source library
- large scale의 passage를 다루는데 매우 효율적인
- backbone은 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로 출력
Nearest Neighbor와 Kth Nearest neighbor를 얻을 수 있다
한 번에 한 벡터가 아닌 여러 벡터를 검색할 수 있다. (Batch Processing), 여러 인덱스 타입들에서 여러 벡터를 차례로 검색하는 것보다 더 빠르다 정확도와 속도 간의 트레이드 오프가 존재한다. 예를 들어 10% 부정확한 결과를 얻는다고 할때, 10배 더 빠르거나, 10 더 적은 메모리를 사용할 수 있다. 유클리디안 거리 최소화 하는 검색이 아닌 Maximum inner product가 최대로 되는 방식으로 계산한다
query point에서 주어진 radius에 포함되는 모든 element들을 반환한다 인덱스는 디스크에 저장된다.
참고 : Coarse-Grained vs Fine-Grained
Coarse-Grained 의 사전적 정의 결이 거친, 조잡한 이다. 곡식을 낱알로 분리하는 작업을 Grain이라고 할 수 있는데 이를 거칠 큼직큼직하게 할지, 곱고 세밀하게 할지에 따라서 Coarse와 Fine으로 나누어 표현한다고 이해할 수 있다
Cifar10, CIfar100, MNIST 등의 데이터셋 사용해 classification하는 것
Fine-Grained : 하나의 작업을 작은 단위의 프로세스로 나눈뒤 다수의 호출을 통해 작업 결과를 생성하는 방식 Coarse-grained 보다 더 세밀하게 classification을 한다
Faiss Example
Faiss index 생성
: faiss에는 여러가지 인덱스 타입들이 있으며, 가장 단순하게 사용할 수 있는 알고리즘 Brute-force
L2 distance 검색하는 Index Flat L2
import numpy as np
d = 64 # dimension
nb = 100000 # database size
nq = 10000 # nb of queries
np.random.seed(1234) # make reproducible
xb = np.random.random((nb, d)).astype('float32')
xb[:, 0] += np.arange(nb) / 1000.
xq = np.random.random((nq, d)).astype('float32')
xq[:, 0] += np.arange(nq) / 1000.
import faiss # make faiss available
# Flat
index = faiss.IndexFlatL2(d) # build the index
print(index.is_trained) # True
index.add(xb) # add vectors to the index
print(index.ntotal) # 100000
k = 4 # we want to see 4 nearest neighbors
D, I = index.search(xb[:5], k) # sanity check
print(I)
'''
[[ 0 393 363 78]
[ 1 555 277 364]
[ 2 304 101 13]
[ 3 173 18 182]
[ 4 288 370 531]]
'''
print(D)
'''
[[0. 7.175174 7.2076287 7.251163 ]
[0. 6.323565 6.684582 6.799944 ]
[0. 5.7964087 6.3917365 7.2815127]
[0. 7.277905 7.5279875 7.6628447]
[0. 6.763804 7.295122 7.368814 ]]
'''
D, I = index.search(xq, k) # actual search
print(I[:5]) # neighbors of the 5 first queries
'''
[[ 381 207 210 477]
[ 526 911 142 72]
[ 838 527 1290 425]
[ 196 184 164 359]
[ 526 377 120 425]]
'''
print(I[-5:]) # neighbors of the 5 last queries
'''
[[ 9900 10500 9309 9831]
[11055 10895 10812 11321]
[11353 11103 10164 9787]
[10571 10664 10632 9638]
[ 9628 9554 10036 9582]]
'''
# IVFFlat
nlist = 100
quantizer = faiss.IndexFlatL2(d) # the other index
index = faiss.IndexIVFFlat(quantizer, d, nlist, faiss.METRIC_L2)
assert not index.is_trained
index.train(xb)
assert index.is_trained
index.add(xb) # add may be a bit slower as well
D, I = index.search(xq, k) # actual search
print(I[-5:]) # neighbors of the 5 last queries
'''
[[ 9900 9309 9810 10048]
[11055 10895 10812 11321]
[11353 10164 9787 10719]
[10571 10664 10632 10203]
[ 9628 9554 9582 10304]]
'''
index.nprobe = 10 # default nprobe is 1, try a few more
D, I = index.search(xq, k)
print(I[-5:]) # neighbors of the 5 last queries
'''
[[ 9900 10500 9309 9831]
[11055 10895 10812 11321]
[11353 11103 10164 9787]
[10571 10664 10632 9638]
[ 9628 9554 10036 9582]]
'''
# IVFOQ
nlist = 100
m = 8
k = 4
quantizer = faiss.IndexFlatL2(d) # this remains the same
index = faiss.IndexIVFPQ(quantizer, d, nlist, m, 8)
# 8 specifies that each sub-vector is encoded as 8 bits
index.train(xb)
index.add(xb)
D, I = index.search(xb[:5], k) # sanity check
print(I)
'''
[[ 0 78 424 159]
[ 1 555 706 1063]
[ 2 179 304 134]
[ 3 64 773 8]
[ 4 288 827 531]]
'''
print(D)
'''
[[1.5882268 6.331396 6.440189 6.473257 ]
[1.274326 5.728371 6.056792 6.1539173]
[1.7501019 6.1581926 6.310023 6.365546 ]
[1.8521194 6.6665597 6.978093 6.9924507]
[1.5939493 5.717939 6.3486733 6.374599 ]]
'''
index.nprobe = 10 # make comparable with experiment above
D, I = index.search(xq, k) # search
print(I[-5:])
'''
[[ 8746 9966 9853 9968]
[11373 10913 10240 10403]
[11291 10719 10494 10424]
[10122 10005 11276 11578]
[ 9644 9905 10370 9229]]
'''
댓글