[추천 시스템/RecSys] KNN과 ANN / ANNOY, HNSW, IVF 등의 방법론

KNN(K-Nearest Neighbor) 알고리즘은 Vector Space Model에서 내가 원하는 Query Vector와 가장 유사한 Vector를 찾는 알고리즘으로, 분류나 회귀 문제를 해결하기 위해 머신러닝에서 사용되는 기법 중 하나다. 추천 시스템을 구현하기 위한 기계학습 모델에서 상품 간 혹은 유저 간 근접 이웃(NN)을 구하기 위해 활용되기도 한다. 다만 이때 문제는, 데이터의 양이 많아질수록(유저 혹은 아이템의 수가 많아지는 경우) 연산량이 기하 급수적으로 늘어나 실제 서비스에서 활용하기 어렵다는 점이다. 이러한 문제를 해결하기 위한 접근이 ANN(Approximate Nearest Neighbor)으로, trade-off 관계인 정확도와 속도에서 정확도를 일부 포기하고 연산 속도 면에서 이점을 갖도록 근사하는 방법이다.

출처: https://github.com/erikbern/ann-benchmarks

위 이미지는 fashion-Mnist dataset에 적용한 다양한 ANN 모델들의 정확도와 초당 처리하는 query의 수의 관계를 나타낸 그래프이다. 극악의 처리 속도를 보이는 브루트포스 알고리즘에 비해, 훨씬 빠른 속도를 내면서도 꽤 준수한 정확도를 보일 수 있는 알고리즘을 택하는 것이 프로덕트 서빙 면에서는 더 좋은 선택일 수 있다. 이 글에서는 ANNOY를 비롯한 대표 ANN 기법들의 아이디어를 정리해본다.

 

1) ANNOY(Approximate Nearest Neighbor Oh Yeah)

이름이 귀엽다. spotify에서 개발하고 공개한 tree-based 기법으로, 주어진 벡터들을 여러 개의 subset으로 나누어 tree 형태의 자료 구조로 구성하고 이를 활용하여 탐색한다. 동작 원리는 아래와 같다.

 

① Vector Space에서 임의의 두 점을 선택한 뒤, 두 점의 사이의 hyperplane로 Vector Space를 나눔
② Subspace에 있는 점들의 개수를 node로 하여 binary tree 생성 혹은 갱신
③ Subspace 내에 점이 K개 초과로 존재한다면 해당 Subspace에 대해 ①과 ② 진행
→ ANN를 구하기 위해서는 현재 점을 binary tree에서 검색한 뒤 해당 subspace에서 NN을 search

출처: https://www.slideshare.net/erikbern/approximate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup

출처: https://www.slideshare.net/erikbern/approximate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup

이렇게 ANNOY를 활용하면 주어진 벡터들을 이진 트리의 구조 내에 저장할 수 있고, 근접 이웃을 찾는 시행하게 되면 해당 벡터가 속한 subspace를 찾아가 그 공간 내에 있는 점들에 대해 이웃을 탐색하게 된다. 이때 이진 트리에서 특정 벡터를 찾는 데에 O(logn)의 시간 복잡도를 필요로 하고, 이웃 탐색 또한 적은 대상을 후보로 진행하기 때문에 아래처럼 브루트포스에 비해 압도적인 Query performance를 보여줄 수 있는 것이다.

출처: https://www.slideshare.net/erikbern/approximate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup

다만 subspace를 매번 랜덤하게 나누어 나가기 때문에, 실제로는 아주 근접한 이웃이 다른 subspace에 속하는 상황이 발생할 수 있으며 이 경우에는 근접 이웃 탐색에서 제외될 수 있다. 이러한 문제를 해결하기 위해 query vector가 실제로 속한 subspace 외에도 추가로 인접한 다른 노드(subspace)를 탐색하도록 하거나, 아예 subspace들의 집합인 이진 트리 자체를 여러 개 생성하여 랜덤한 생성으로 인한 오차의 발생을 줄이는 등의 방법을 적용할 수 있다. 

출처: https://www.slideshare.net/erikbern/approximate-nearest-neighbor-methods-and-vector-models-nyc-ml-meetup

[하이퍼 파라미터]

- number_of_trees: 생성하는 binary tree의 개수
- search_k: NN을 구할 때 탐색하는 node의 개수

 

이렇게 하이퍼 파라미터로 정확도와 연산 속도를 각각 어느정도 포기하고 얻을 것인지 조절할 수 있다는 장점이 있지만, GPU 지원이 되지 않고 이미 생성한 이진 트리에 벡터를 추가하고 싶은 경우 아예 처음부터 연산을 다시 해야 한다는 단점이 있다.

 

공식 깃헙: https://github.com/spotify/annoy

GitHub - spotify/annoy: Approximate Nearest Neighbors in C++/Python optimized for memory usage and loading/saving to disk

 

2) HNSW(Hierarchical Navigable Small World Graphs)

이름 그대로 계층적이지만 서로 이동 가능한, 여러 Small World를 만들어 그 안에서 근접 이웃을 탐색하는 방법이다. 동작 원리는 아래와 같다.

 

① 벡터를 그래프의 node로 표현하고 인접한 벡터를 edge로 연결한다. 모든 노드가 존재하는 Layer 0을 시작으로, 여러 개의 Layer를 계층적으로 쌓되, 최상위 Layer로 갈수록 랜덤 샘플링을 통해 노드의 개수가 적어지도록 만든다. (아이디어가 제안된 논문에 따르면 exponentially decaying)

② 최상위 Layer에서 임의의 노드에서 탐색을 시작
③ 현재 Layer에서 타겟 노드와 가장 가까운 노드로 이동

④ 현재 Layer에서 더 가까워 질 수 없다면 하위 Layer로 이동
⑤ 타겟 노드에 도착할 때까지 ③과 ④ 반복
⑥ ③ ~ ⑤를 진행할 때 방문했던(traverse) 노드들만을 후보로 하여 NN을 탐색

출처: Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs(2016)

이러한 아이디어를 구현하여 제공하는 라이브러리는 nmslib, faiss 등이 있다.

https://nmslib.github.io/nmslib/quickstart.html

Python bindings for NMSLIB — nmslib 2.0.5 documentation

출처: https://www.pinecone.io/learn/vector-indexes/

faiss 라이브러리를 사용해 이를 구현하면 M, ef_search, ef_construction 등이 대표적인 하이퍼 파라미터가 되는데, 이에 따른 정확도를 시각화하면 위와 같다고 한다. 아래는 예시 코드.

# 출처: https://www.pinecone.io/learn/vector-indexes/
# set HNSW index parameters
M = 64  # number of connections each vertex will have
ef_search = 32  # depth of layers explored during search
ef_construction = 64  # depth of layers explored during index construction

# initialize index (d == 128)
index = faiss.IndexHNSWFlat(d, M)
# set efConstruction and efSearch parameters
index.hnsw.efConstruction = ef_construction
index.hnsw.efSearch = ef_search
# add data to index
index.add(wb)

# search as usual
D, I = index.search(wb, k)

3) Inverted File Index (IVF)

출처: 위키백과

벡터들을 k-means clustering 등의 방법을 이용해 n개의 cluster로 나누어, vector의 index를 cluster별 inverted list로 저장하였다가 query vector가 주어지면 해당 query가 포함되는 cluster를 찾고, 해당 inverted list 내에서 NN을 탐색하는 방법이다.

출처: https://www.pinecone.io/learn/vector-indexes/

다만 이렇게 1개의 cluster만을 탐색하게 되면(nprobe=1) 위 그림처럼 query와 근접 이웃이지만 다른 culster에 포함돼 후보에서 제외될 가능성이 있으므로, nprobe의 수를 늘려 이러한 문제를 보완할 수 있다. 아래는 예시 코드.

# 출처: https://www.pinecone.io/learn/vector-indexes/
nlist = 128  # number of cells/clusters to partition data into

quantizer = faiss.IndexFlatIP(d)  # how the vectors will be stored/compared
index = faiss.IndexIVFFlat(quantizer, d, nlist)
index.train(data)  # we must train the index to cluster into cells
index.add(data)

index.nprobe = 8  # set how many of nearest cells to search
D, I = index.search(xq, k)

 

아래는 Sift1M dataset에 대하여 ANN의 몇몇 방법론들의 성능을 비교한 표이다.

출처: https://www.pinecone.io/learn/vector-indexes/

[참고 영상]

https://youtu.be/B7wmo_NImgM