ANN이란?

• ANN은 효과적이고 효율적인 서빙을 위해 정확도를 조금 포기하더라도 아주 빠른 속도로 주어진 벡터(Query Vector)의 근접 이웃을 찾는 알고리즘

ANN 기법

• ANNOY : 벡터 공간을 여러 개의 subset으로 나누어 이진 트리 형태의 자료구조를 만들고, 이를 활용하여 탐색하는 것 [하이퍼파라미터 : btree의 개수, 이웃을 구할 때 탐색하는 node의 개수]

  1. Vector Space에서 임의의 두 점을 선택한 뒤, 두 점 사이의 hyperplane으로 Vector Space를 나눔

     

  2. subspace에 있는 점들의 개수를 node로 하여 binary tree 생성(갱신)

     

  3. 만약 Subspace 내에 점이 K개 초과로 존재한다면, 해당 Subspace에 대해 (1)과 (2)를 진행

  • Annoy 문제 : 가장 근접한 점이 아슬아슬하게 다른 node에 있다면, 해당 점은 후보 subset에 포함되지 못함
    • btree를 여러 개 생성하여 병렬적으로 탐색(앙상블)하는 방법으로 해결한 수 있음

• Inverted File Index : 주어진 벡터들을 클러스터링(k-mean 등)하여 n개의 cluster로 저장하고, 벡터의 인덱스를 cluster별 inverted list로 저장(Query에 대해서 해당 cluster를 찾고, 해당 cluster의 inverted list 안에 있는 vector들에 대해서 탐색)

  

• …