ANN: Approximate Nearest Neighbor

이전에 Item2Vec이나 Matrix Factorization을 사용할 때, 벡터공간에 유저나 아이템을 투영시켜서 현재 아이템과 가장 가까운 벡터를 찾아 추천하는 방법을 사용했었다. 아이템의 개수가 100개 정도라면 모든 벡터와 현재 벡터를 비교해서 얼마나 유사한지, 얼마나 가까이 있는지 연산을 할 수가 있지만, 아이템의 개수가 1억 개가 넘어간다면 이를 어떻게 처리해야 할지도 생각해보아야 한다. 따라서 이번에는 완벽하게 가까운 벡터를 찾아낼 수는 없지만, 높은 정확도를 가지고 가까운 벡터를 찾도록 도와주는 ANN에 대해서 소개한다.

 

 

 

 

 

 

Brute Force KNN

 

K-NN은 현재 나(벡터)와 가장 가까운 $k$개의 벡터를 의미한다. 가장 단순하게 생각했을 때, 모든 벡터와의 거리 연산, 유사도 연산을 사용해서 짧은 거리가 먼저오도록 정렬하여 앞의 $k$개의 벡터를 찾아내면 된다. 하지만, 만약 벡터의 차원이 100차원이고, 그런 벡터가 100만 개 존재한다고 하면 모든 벡터와 연산하는 데 걸리는 시간은 46시간이 넘어간다.

 

 

 

 

시간이 아주 많아서 어떻게든 학습을 시켰다고 하더라도 실제 사용자들에게 서빙하는 것에는 무리가 있다. 이번 영상을 토대로 유사한 아이템들을 찾아주는데 매번 46시간이 걸린다고 생각하면 누가 이 서비스를 사용할까. 따라서 사람들은 정확도를 조금 포기하더라도 아주 빠른 속도로 현재 벡터와 가장 유사한 벡터를 찾는 방법을 고안하였다.

 

 

 

 

 

 

Approximate Nearest Neighbor Oh Yeah

 

꽤나 재미있는 이름을 가진 ANNOY는 ANN 알고리즘 중 하나로서 spotify에서 개발하였다. 빠른 탐색을 위해서 ANNOY는 벡터공간을 여러 개의 부분 공간(subspace)으로 나누고, 그 정보들을 트리에 저장하도록 하였다.

 

 

 

 

2차원 공간에 존재하는 벡터 (출처:https://erikbern.com/)

 

 

 

 

위의 그림은 임베딩 된 2차원 벡터공간에 존재하는 수많은 벡터들을 나타낸다. ANNOY는 먼저 임의로 2개의 벡터를 선택하여 둘을 가로지르는 초평면(hyperplane)을 그려 두 개의 subspace로 나눈다. 이때 초평면은 두 벡터를 정확히 절반으로 나누는 평면으로 그려야 한다.

 

 

 

 

2개의 subspace로 나눈 벡터 공간 (출처:https://erikbern.com/)

 

 

 

 

마찬가지로 나눠진 subspace 속에서 다시 같은 작업을 반복한다. 각 부분공간에서 임의의 2개의 벡터를 선택하고 초평면을 각각 그려나간다. 다음 단계에서는 나눠진 부분공간에서 각각 다시 2개로 나눠지기 때문에 총 4개의 subspace가 생기게 된다.

 

 

 

 

4개의 subspace로 나뉜 벡터 공간 (출처:https://erikbern.com/)

 

 

 

 

지금까지의 과정을 이진트리로 나타내볼 수도 있다. 각 트리의 정점을 subspace라고 한다면 1단계씩 깊어질 때마다 subspace는 2배씩 커져간다. 각 노드는 부분공간을 가리키고, 그 공간 속에 존재하는 벡터의 개수를 노드에 작성한다면 다음과 같다.

 

 

 

 

이진 트리의 표현 (출처:https://erikbern.com/)

 

 

 

 

 

이 과정을 각 subspace에 존재하는 벡터의 수가 $k$개 이하일 때까지 진행하면 깨진 유리창과 같은 형태를 띠게 된다. 아래는 $k=10$이라고 설정한 모습이다.

 

 

 

 

출처:https://erikbern.com/

 

 

 

 

그리고 이는 트리로 표현하면 좀 더 깊은 형태를 보여준다. 사각형 노드가 초평면에 의해 나눠질 subspace를 의미하며, 원형 노드는 부분공간에 존재하는 벡터의 수를 의미한다. 10개보다 많은 벡터를 가진 부분공간은 모두 다른 부분공간으로 나뉘어 내려가는 것을 확인할 수 있다.

 

 

 

 

출처:https://erikbern.com/

 

 

 

 

위와 같이 각 부분 공간에 속한 벡터가 10개 이하가 되도록 나누었다면, 이번에는 원래 목표인 가장 가까운 벡터를 찾는 방법을 살펴봐야 한다. 다행히 하나의 subspace 내에 존재하는 벡터들끼리는 모두 가까이 존재하며, 이진트리 구조에 의해서 어떤 subspace에 존재하는지 $\mathcal{O}(\log_2 N)$ 시간에 찾아낼 수 있다. 예를 들어, 특정 벡터가 존재하는 subspace를 아래와 같이 찾아낼 수 있다.

 

 

 

 

출처:https://erikbern.com/

 

 

 

 

위의 그림대로 subspace가 나눠졌다고 하면, 현재 타겟 벡터(❌)와 같은 subspace에 있는 벡터는 총 7개이다. 하지만, 만약 유사한 벡터를 7개 이상 얻어내고 싶다면 다른 subspace를 참고하는 것과 같은 다른 방법을 필요로 하게 된다. ANNOY에서는 크게 2가지 방법으로 이 문제를 해결해 나간다.

 

 

 

 

첫 번째 방법은 "우선순위 큐"를 사용하는 방법이다. 지금까지 타겟 벡터 (❌)가 속한 subspace를 찾아서 내려가기만 했다면, 이번에는 다른 경로로도 내려가보는 것이다. 임계값을 설정하여, 반대쪽으로 얼마나 내려가 볼 것인지 정한다. 그렇게 되면 반대쪽 노드도 가까이 있는 subspace에 속해있기 때문에 유사한 벡터로 사용할 수 있게 된다.

 

 

 

 

두 번째 방법은 트리를 여러 개 생성하는 것이다. ANNOY는 매번 임의의 두 벡터를 선택하여 공간을 나누기 때문에, 여러 개의 트리를 생성하게 되면 만들어지는 subspace의 형태도 모두 달라져 포함되는 벡터도 조금씩 차이가 발생한다. 따라서 여러 개의 트리로부터 만들어진 subspace를 참고하여 더 많은 유사한 벡터들을 찾아낼 수 있다.

 

 

 

 

출처:https://erikbern.com/

 

 

 

 

이제 마지막으로 각 벡터와의 거리를 구해서 가장 가까운 $k$개를 가장 유사한 벡터로 반환한다. 물론, 실제로 더 가까이 있는 벡터들이 있지만, 그 벡터들을 선택하지 못하는 경우도 있다. 하지만 초반에 살펴보았듯이, 정확도를 조금 포기하더라도 매우 빠른 속도로 벡터들을 선택하는 것이기 때문에 완벽하게 선택하는 것은 거의 불가능하다.

 

 

 

 

 

 

 

REFERENCES

 

https://erikbern.com/2015/10/01/nearest-neighbors-and-vector-models-part-2-how-to-search-in-high-dimensional-spaces.html

Nearest neighbors and vector models – part 2 – algorithms and data structures