Approximate Nearest Neighbors
좋은 글 소개
"Vector모델에서 가장 근접한 Vector를 효율적으로 찾기"에 관한 좋은 글이 있어서 간단히 소개 보고자 한다.
Approximate Nearest Neighbors & Vector models
글쓴이(Erik)는 5년 동안 스포티파이에서 ML팀을 이끌었고, 현재는 better.com의 CTO이다.(개인적으로 추천 시스템에 관한 글은 글쓴이인 Erik의 글과 넷플릭스에서 엔지니어였던 Xavier amatriain의 Slideshare글을 매우 좋아한다.)
이 글은 처음 읽었을 때 개인화 추천 시스템을 만들 때 실질적으로 고민했던 문제에 대하여 정말 성의 있게(??) 풀었다는 생각이 들었다. 이런 디테일이 있어야 좋은 추천 시스템이 되겠구나~라고 다시 생각해 보는 계기가 되는 글이었다.
본론으로 들어가서, 추천 시스템이나 NLP 등의 Vector Space Model에서 내가 원하는 Vector와 최근접 Vector를 찾는 Nearest Neighbors 연산은 거의 필수로 사용된다. 그런데 이 비용이 꽤 세다. 그냥 brute force 연산을 하면 Vector의 개수만큼 유사도 비교 연산 비용을 필요로 한다. Vector의 수가 별로 많지 않다면 문제가 없지만, Vector의 수가 1M 이상 넘어가게 되면 점점 서버로 때우기 어려워진다. 여기에 더하여 일반적인 서비스에서 사용하는 수준에서는 Vector를 Dense하게 차원 축소 하더라도 100~1000차원 정도로 Vector를 표현되기 때문에 실제 Nearest Neighbors의 연산은 데이터 규모에 비례하여 엄청나게 늘어 난다.
이런 이유로 실질적으로 추천 시스템에서 Nearest Neighbors연산 구간이 Bottleneck으로 자주 발생된다. 이와 유사하게 softmax 연산도 비슷한 형태로 bottleneck이 되는듯하다.
이 글은 이러한 Bottleneck을 해결하기 위해 100% 정확도가 아닌 높은 정확도로 근접한 Vector를 빠르게 찾아주는 Spotify의 오픈소스 Annoy(Approximate Nearest Neighbors Oh Yeah)에 대한 발표자료이다. https://github.com/spotify/annoy
간단히 요약해 보자면 Vector공간을 권역으로 잘게 나눈다.(vector가 100개 정도씩 포함되도록)
잘게 나누어진 공간을 binary tree로 구성한다.
Nearest Neighbors연산을 하고자 하면, 해당 vector가 포함되는 공간을 tree 검색으로 찾고
찾은 권역 내에서 Nearest Neighbors 연산을 하는 방식이다. 여기서 정확도를 더 높이가 위해 tree route에서 가까운 node를 여러개 찾기도하고, tree를 여러개 만들어 인접 공간을 많이 찾는 방법도 사용한다.
좀 더 구체적으로 기술적인 실험과 풀이 과정에 대하여 잘 설명하고 있으니 해당 문서를 꼭 정독 해 보길 바란다.
