2022년 3월 7일(월)부터 11일(금)까지 네이버 부스트캠프(boostcamp) AI Tech 강의를 들으면서 중요하다고 생각되거나 짚고 넘어가야 할 핵심 내용들만 간단하게 메모한 내용입니다. 틀리거나 설명이 부족한 내용이 있을 수 있으며, 이는 학습을 진행하면서 꾸준히 내용을 수정하거나 추가해나갈 예정입니다. 강의 자료의 저작권은 네이버 커넥트재단 부스트캠프 AI Tech에 있습니다.
Approximate Nearest Neighbor(ANN)
Nearest Neighbor
주어진 vecor space model에서 자신이 원하는 query vector와 가장 유사한 vector를 찾는 알고리즘이다.
MF 모델을 가지고 추천 아이템을 서빙하는 경우를 생각해보자.
유저에게 아이템을 추천한다면 해당 유저 vector와 후보 아이템 vector들과의 유사도 연산이 필요하다.
비슷한 아이템을 연관 추천한다면 해당 아이템 vector와 다른 모든 후보 아이템 vector 간의 유사도 연산이 필요하다.
추천 모델 서빙은 모델 학습을 통해 구한 유저와 아이템의 vector가 주어질 때, 주어진 query vector의 인접한 이웃을 찾아주는 것과 일맥상통하다.
Brute Force KNN
NN을 정확하게 구하기 위해서는 나머지 모든 vector와 유사도 비교를 수행해야 한다.
Vector의 차원과 개수에 비례한 비교 연산 비용이 필요하다.
현실적으로 정확도를 조금 포기하고 아주 빠른 속도로 주어진 vector의 근접 이웃을 찾는 방법이 요구된다.
그래서 NN을 정확히 찾는 것이 아닌 Approximate NN을 구하는 방법이 등장한다.
ANNOY(Approximate Nearest Neighbors Oh Yeah)
spotify에서 개발한 tree-based ANN 기법이다.
주어진 벡터들을 여러 개의 subset으로 나누어 tree 형태의 자료 구조로 구성하고, 이를 활용하여 탐색한다.
- Vector Space에서 임의의 두 점을 선택한 후, 두 점 사이의 hyper plane으로 vector space를 나눈다. Hyper plane에서는 $n$차원에 대해서 정의 가능하다.
- Subspace에 있는 점들의 개수를 node로 하여 binary tree를 생성하거나 갱신한다.
- Subspace 내의 점이 K개 초과하여 존재하면 해당 subspace에 관해 1과 2를 진행한다.
ANN을 구하기 위해서는 현재 점을 binary tree에서 검색한 후 해당 subspace에 존재하는 벡터들과 유사도를 계산한다.
그러나 Subspace를 무작위로 나누므로 가장 근접한 점이 tree의 다른 Node에 있을 수도 있으며, 이 경우 해당 점은 후보 subset에 포함되지 못한다.
Priority queue를 사용하여 vector space 상에서 가까운 다른 Node를 탐색하거나, binary tree를 여러 개 생성하여 일종의 앙상블처럼 병렬적으로 탐색한다.
이를 반영하여 파라미터를 다음과 같이 생성할 수 있다.
- number_of_trees: 생성하는 binary tree의 개수
- search_k: NN을 구할 때 탐색하는 Node의 개수
Search Index를 생성하는 것이 다른 ANN 기법에 비해 간단하고 가볍다.
아이템 개수가 많지 않고 벡터의 차원이 100보다 낮은 경우 사용하기에 적합하다고 알려져있지만, GPU 연산은 지원하지 않는다.
Search 해야 할 이웃의 개수를 알고리즘이 보장한다.
파라미터를 조정해서 accuracy와 speed의 trade-off를 조정할 수 있다.
단, 기존 생성된 binary tree에 새로운 데이터를 추가할 수 없고, 다시 전체 데이터를 가지고 tree를 생성해야 한다.
다른 ANNOY 기법
Hierarchical Navigable Small World Graphs (HNSW)
벡터를 그래프의 node로 표현하고 인접한 벡터를 edge로 연결한다.
전체 vector들 간에서 물리적으로 가까이 존재하는 점들만 small world graph로 연결한 그래프이다.
유사한 node들끼리만 edge를 갖고, 유사하지 않은 node는 edge를 갖지 않는다.
Small World Graph를 연결해주는 long edge가 있어서 이를 통해 유사하지 않은(거리가 멀리 떨어져 있는) node들도 탐색할 수 있는데, 이를 Navigable Small World Graph라고 한다.
Navigable Small World Graph를 계층적으로 만들어준 것이 Hierarchical Navigable Small World Graphs이다.
계층으로 만든 이유는 계층적으로 이를 탐색해서 ANN search 속도를 향상시키기 위한 것이다.
계층이 올라갈수록 일부 벡터만 샘플링해서 레이어를 구성해주며, 가장 상위의 레이어에는 전체 계층에서 가장 적은 수의 벡터가 존재하게 된다.
ANN search 작동 방식은 다음과 같다.
- 최상위 layer의 임의의 노드에서 시작
- 현재 layer에서 임의의 노드에서 시작하여 타겟 노드와 가장 가까운 노드로 이동한다.
- 현재 layer에서 더 가까워질 수 없으면 하위 layer로 이동한다.
- 타겟 노드에 도착할 때까지 2와 3을 반복한다.
- 2에서 4를 진행할 때 방문했던 노드들만 후보로 하여 NN(Nearest Neighbors)을 탐색한다.
Inverted File Index(IVF)
Search space를 줄여서 ANN search 속도를 향상시키는 방법이다.
주어진 벡터를 clustering하여 n개의 cluser로 나눠서 저장하고, 이후 vector의 index를 cluster별 inverted list로 저장한다.
Query vector에 대해서 해당 cluster를 찾고, 해당 cluster의 invert list 안에 있는 vector들에 대해서 탐색한다.
그러나 Cluster의 경계에 근접한 vector들을 무시하게 될 수도 있으므로 탐색해야 하는 cluster를 늘려야 할 수 있다.
탐색해야 하는 cluster 개수를 증가시킬수록 accuracy와 speed의 trade-off이 발생한다.
IVF와 ANN의 차이
클러스터링하고 그 클러스팅 내의 벡터끼리 유사도를 구한다는 점에서 비슷하다.
그러나 INF는 vector의 index를 inverted list에 저장한다는 점에서 차이가 있다.
Product Quantization - Compression
Search space를 줄이는 방법과는 조금 다른 아이디어를 사용하는데, 기존 vector가 가지는 고유한 값들을 압축하여 표현한다.
vector를 압축하는 방법은 다음과 같다.
- 기존 vector를 $n$개의 sub-vector로 나눈다.
- 각 sub-vector 군에 관해 k-means clustering을 해서 cluster의 centroid를 구한다.
- 기존의 모든 vector를 $n$개의 centroid로 압축해서 표현한다.
미리 구한 centroid 사이의 유사도를 활용하므로 두 vector의 유사도를 구하는 연산이 거의 요구되지 않는다.
PQ와 IVF를 동시에 사용해서 더 빠르고 효율적인 ANN 수행이 가능하다.