annoy 라이브러리 소개 (nearest neighbor search, 벡터 유사도 검색)

오늘은 annoy라는 라이브러리를 소개해볼까 합니다.

annoy는 딥러닝을 직접적으로 활용하지는 않지만, 딥러닝을 활용함에 있어서 벡터 유사도 검색에 매우 유용한 라이브러리 입니다. 

개발자에 의하면 annoy는 Approximate Nearest Neighbors Oh Yeah의 줄임말이라고 합니다.

 

먼저 nearest neighbor는 많이 아실거라 생각합니다. 우리말로는 최근접 이웃이라고도 하는 이 알고리즘은 공간에서 가장 가까운 벡터를 찾는 알고리즘입니다.

nearest neighbor 알고리즘은 최근 딥러닝과 연관된 분야에서도 많이 활용되고 있습니다.

예를 들면, word2vec에서 유사한 단어를 검색할 때, vector간의 거리를 계산하거나 sentence vector 간의 거리를 계산할 때도 사용되고, 추천 시스템에서는 추출된 특징 벡터에 대해서 유사한 벡터를 찾아서 추천해줄때도 많이 사용되고 있습니다.

 

nearest neighbor 알고리즘을 추천 시스템에서 실시간으로 서비스를 할 때 사용한다고 생각해보겠습니다.

이 추천 시스템은 사용자의 사용 기록을 벡터화하고 유사한 벡터를 가진 사용 기록을 불러와서 추천을 해주는 시스템이라고 가정하겠습니다.

그러면, 추천을 해줄 때, 현재 사용자의 사용 기록을 벡터로 만든 다음에 다른 사용자들의 사용 기록에 대한 벡터와 nearest neighbor 알고리즘을 통해서 유사한 벡터를 검색을 해야합니다.

그러면 모든 사용자 사용 기록 벡터와 거리를 계산하고, 거리 순으로 정렬을 해서 거리가 가까운 벡터를 찾아야겠죠?

이 때, 사용자의 수가 적다면 상관 없겠지만 사용자가 백만명이라면? 시간이 매우 오래 걸리겠죠?

 

이럴 때 사용할 수 있는 라이브러리가 바로 annoy입니다. annoy는 spotify에서 만든 라이브러리로 유사한 벡터들을 빠르게 찾아주는 라이브러리입니다. spotify에서도 실제로 음악을 추천할 때 활용된다고 합니다.

https://github.com/spotify/annoy

spotify/annoy

유사한 벡터를 찾을 때는, tree 기반으로 동작한다고 합니다.

tree의 경우, 여러개를 사용할 수 있는데 tree 갯수가 많으면 동시에 여러 tree를 활용함으로써 속도는 빨라지지만, n개의 벡터를 찾을 때 각 tree에서 n/tree갯수 만큼 찾아서 반환하는 방식이라서 정확도는 조금 떨어질 수 있습니다.

annoy는 C++로 구현되어있어서 매우 빠르게 동작하고, 파이썬으로 패키징도 되어있어 쉽게 사용할 수 있습니다.

또한 mmap 파일 기반으로 동작하여 빠르면서 메모리를 많이 사용하지 않습니다.

 

python에서는 어떻게 사용하는지 예제를 보도록 하겠습니다.

"""
indexing.py
"""


from annoy import AnnoyIndex
import random


length_of_vector = 40
annoy_index = AnnoyIndex(length_of_vector, 'dot')  
for idx in range(1000):
    vector = [random.gauss(0, 1) for _ in range(length_of_vector)]
    annoy_index.add_item(idx, vector)

annoy_index.build(10) 
annoy_index.save('test.annoy')

indexing은 위와 같이 수행하면 됩니다. 위의 예제는 임의로 random vector를 생성하여 1000개의 vector를 indexing하는 예제입니다.

AnnoyIndex 객체를 생성할 때, vector의 크기와 vector간의 distance를 정해주어야 합니다. vector간 distance는 angular, euclidean, manhattan, hamming, dot 5가지 중에 하나를 선택할 수 있습니다.

그 후, indexing 할 vector를 add_item 함수를 활용하여 넣어주시면 되는데, add_item 함수는 index와 vector를 입력으로 받습니다. index는 non-negative integer만 입력으로 넣을 수 있습니다.

그 후에는 build를 하고 save를 해주셔야 합니다. build는 tree의 갯수를 입력으로 받고, save는 저장할 파일명을 입력으로 받습니다.

여기서 주의할 점은, build를 수행하고나면, 더 이상 변경이 절대로 안된다는 점입니다. 몇개의 vector를 추가하고 싶은 경우가 있다면, 처음부터 다시 수행하여 별도로 만들어주어야 합니다.

 

저렇게 빌드와 저장을 해두었으면 어떻게 불러와서 활용할 수 있는 지 보도록 하겠습니다.

"""
searching
"""

from annoy import AnnoyIndex
import random


length_of_vector = 40
new_annoy_index = AnnoyIndex(length_of_vector, 'dot')
new_annoy_index.load('test.annoy')

n = 100
idx = 0
print(new_annoy_index.get_nns_by_item(idx, n))

vector = [random.gauss(0, 1) for _ in range(length_of_vector)]
print(new_annoy_index.get_nns_by_vector(vector, n))

객체를 생성하는 부분은 동일하며, load 함수를 활용하여 저장된 파일을 불러옵니다.

그 후에는 get_nns_by_item이나 get_nns_by_vector 함수를 활용하여 n개의 가장 가까운 vector를 찾을 수 있습니다.

get_nns_by_item 함수는 idx와 n을 입력으로 받아 색인된 벡터 중에서 idx의 벡터와 가장 가까운 n개의 벡터에 대한 idx들을 반환하고, get_nns_by_vector는 입력으로 넣은 vector에 대해 가장 가까운 n개의 벡터를 반환합니다.

이 때, include_distances=True 옵션을 함수에 추가하면 distance도 함께 반환받을 수 있습니다.

 

annoy의 경우에는 index와 vector 정보만으로 동작하므로 각 vector에 대한 부가정보는 따로 저장을 해두어야합니다.

가장 간단하게는 index - value 형태로 데이터베이스에 따로 저장을 해두고 활용할 수 있으며 그런 경우에는 python의 lmdb와 같은 간단한 디비를 활용하실 수 있습니다.

 

벡터 유사도 검색은 annoy 뿐만 아니라, NMSLIB, FAISS, TOROS N2와 같은 라이브러리들도 있습니다.

중요도에 따라 비교하여 다른 라이브러리를 활용하시는 방법도 고려해보시면 좋겠습니다.