추천에서 ‘유사’하다는 개념은 상당히 중요하며, 그 ‘유사한 아이템’을 찾는 시스템을 ‘실질적으로 구현’하는 문제 역시 매우 중요하다. 특정 아이템을 소비한 사용자에게 그 다음 아이템을 추천하는 상황을 생각해보자. 내용적으로 유사한 아이템을 추천할 수도 있고, 같은 아이템을 소비한 다른 사람들이 주로 소비한 아이템을 추천해줄 수도 있다. 추천팀 김성진(nick.kim)님의 발표에서는 내용적(특성적)으로 비슷한 아이템을 추천하는 경우에 집중해 카카오의 k-최근접이웃 라이브러리(k-Nearest Neighbor library)인 TOROS N2에 대한 설명이 진행되었다.

유사 아이템 찾기

벡터 모델은 각 아이템을 f-차원의 벡터(vector)로 표현해, 아이템간 거리를 계산할 수 있도록 하는 모델이다. 이와 같이 거리 계산이 가능해지면 유사한 아이템을 추천해 준다는 것은 결국 벡터 공간에서 거리가 가장 가까운 아이템을 찾는 것이 된다. 물론 이때, 각 아이템들은 비슷한 것들은 비슷한 것끼리 모여 있고, 서로 다른 것들은 상대적으로 거리가 멀도록 벡터 모델링이 제대로 되어있다는 전제가 있어야 한다. 텍스트라면 워드 임베딩(word embedding), 이미지나 오디오라면 학습된 네트워크에서 특정 레이어의 값들을 가져오는 방법 등으로 벡터 모델링이 잘 되어있다고 하자. 그럼 유사 아이템(글, 사진, 사용자 등)을 찾아야 하는 그 기준을 쿼리 벡터(query vector)로 표현한 뒤, 벡터 스페이스(vector space) 상에서 인접한 이웃을 찾아주면 끝이 나게 된다.

그런데 쿼리 벡터에 대해 벡터 스페이스 상의 모든 아이템에 대한 거리를 구하는 무작위 방법(brute force)으로 거리를 모두 구하려면 시간이 너무 오래 걸린다. 왜냐하면 실제 추천 시스템에서는 하나의 쿼리 벡터가 아니라, 존재하는 모든 벡터를 쿼리 벡터로 생각해 k-최근접이웃을 구해주어야 하는 경우들이 있기 때문이다. 예를 들어 발표에서처럼 100차원 벡터 100만 개가 있다면, 모든 아이템의 최근접 이웃을 무작위 방법을 통해 구한다면 좋은 장비(이를 테면 AWS c5.4xlarge)로도 27.7시간이 걸려 현실적으로 사용이 불가능하다. 그렇다면 무작위 방법보다 빠른 속도로 찾는 방법은 없을까?

있다. 트레이드오프(trade-off)를 감수한다면 말이다. 최근접이웃 중 일부는 제대로 못 찾아도 괜찮으니, 재현율(Recall)을 살짝 희생하는 대신 훨씬 빠른 속도로 찾는 방법을 근사 k-최근접이웃 탐색(Approximate k-Nearest Neighbor search, AkNN)이라고 한다. k개를 찾았을 때 실제 정답을 맞히는 비율을 80% 이상 정도로만 해도, 100배 빠르면 충분히 괜찮다는 현실적인 절충이다.

[그림 1] AkNN 예시 – 여기서 정확도는 정답에 대해 맞힌 비율이므로 재현율(Recall)의 개념이다

무작위 방법론에 비해, AkNN 을 쓰게 되면 재현율을 일부 잃는 대신 속도는 100배 이상 빨라지게 되므로, 위 에서 예를 들었던 100차원 벡터 100만 개의 경우에 모든 아이템의 근사 k-최근접이웃을 찾는데 16.6분이 걸리게 된다. 현재 가장 좋은 알고리즘을 기준으로 보면 대략 90%의 정확도로 100배 이상 빠르게 찾을 수 있다고 한다.

AkNN 패키지

AkNN 패키지들 중 카카오 추천팀이 주목한 라이브러리는 Annoy(Approximate Nearest Neighbors Oh Yeah)*1와 NMSLIB(Non-Metric Space Library)*2 이다. Annoy 는 스포티파이(Spotify)에서 만든 것으로, 트리 구조를 가진다. 랜덤 포레스트처럼 트리를 여러 개 만들어 돌리는 방식으로, 랜덤 프로젝션해서 나온 결과들의 합집합 안에서 k-최근접이웃을 무작위 방법으로 돌리는 것이다. 하이퍼 파라미터가 하나라 쓰기 편하고, Read-only MMaped data structure, MMap 를 지원해 메모리를 효율적으로 운용할 수 있으나 최신 라이브러리들에 비해 속도와 재현율이 떨어지는 단점이 있다.

[그림 2] MMap 이 지원되지 않는 경우와 지원되는 경우의 메모리 효율 차이

AkNN은 빠른 쿼리 처리를 위해 인덱스를 파일로 만들어서 디스크에 올려두고 메모리에 파일을 로드해 사용하는 과정을 거치는데, MMap이 지원되는 경우는 프로세스를 여러 개 띄우더라도 이미 매핑된 부분은 따로 메모리를 잡지 않아도 되어, 메모리를 정해놓고 CPU만 늘려서 처리가 가능하다.

NMSLIB 은 속도와 정확도가 우수한 HNSW(Hierarchical Navigable Small World graphs)*3 알고리즘을 지원하고, 속도 및 정확도에서 Annoy를 압도하는, 현재로서 가장 좋은 알고리즘이다. 그러나 MMap을 미지원하고, 카카오에서 사용하던 당시 설치 및 운용이 다소 복잡한 단점이 있었다(현재는 개선되었다고 한다).

TOROS N2(Nearest Neighbor)

따라서 Annoy와 NMSLIB 둘의 장점만 가져오고 싶어 카카오에서 직접 만들어낸 AkNN 알고리즘이 바로 TOROS N2*4 이다. N2의 장점은 HNSW 알고리즘 지원, MMap 지원, 빠른 인덱스 빌드 속도, 설치 및 사용 간편, Python 및 Go binding 지원을 들 수 있다. 단점은 NMSLIB 에 비해 탐색 속도가 밀린다는 점인데, 이는 빌드 속도와 트레이드오프가 가능한 수준이다. TOROS N2 가 출시된 후 NMSLIB 도 개선이 되어 현재는 [그림 3]과 같은 비교를 할 수 있다고 한다.

[그림 3] 카카오의 AkNN 사용 및 개발 타임라인 / NMSLIB 2017, 2018 과 TOROS N2의 비교

여기서 잠깐. 왜 N2가 HNSW를 지원하도록 만들어졌는지 이해하기 위해 앞에서 얘기한 HNSW(Hierarchical Navigable Small World graphs)에 대한 발표자님의 간략하고 명쾌한 설명을 짚고 가자. [그림 4]와 같이, 긴 엣지가 없는 Small World graph를 navigable 하게 만들어준 게 NSW(Navigable Small World graph)*5이고, 그것을 계층적으로 쌓은 것을 HNSW라 한다.

[그림 4] HNSW 의 개념 설명 그림

즉 HNSW에는 레이어가 여러 개 있는데, 레이어 0으로 내려갈수록 노드 밀집도는 증가, 노드간 거리는 감소하게 된다. 또 각 노드에 연결되는 엣지 최대 개수가 제한되어, 허브가 없다보니 로그 스케일 복잡도를 보장해줄 수 있다.(삽입도 서치도 로그 스케일) 레이어 0 에는 모든 노드가 존재하고, 그 중 일부가 상위 레벨에도 존재하며 각 노드의 레벨은 인덱스 시점에 랜덤으로 결정되는 것이다.

이제 HNSW 에서의 그래프 횡단(graph traverse)에 대해 살펴보자. [그림 5]에서 엔터 포인트(빨간 점)는 그래프 횡단을 하는 시작점으로서, 랜덤하게 결정되며 최상위 레이어에 존재한다. 최상위 레이어의 엔터 포인트로부터 출발하여, 각 레이어에서 쿼리 벡터와 가장 인접한 노드까지 이동한 뒤, 하위 레이어로 이동해 다시 쿼리 벡터와 가장 인접한 노드까지 이동하는 과정을 최하위 레이어(레이어 0)까지 반복해 진행한다.

[그림 5] HNSW 에서의 그래프 횡단 과정 도식

이때 룩업(look-up)을 몇 개까지 할 것인지 파라미터로 주게 되는데, 이것이 횡단을 끝내는 기준이 될 것이고(그 안에 쿼리 벡터에 도달하면 다시 밖으로 나가면서 진행한다), 횡단 과정 중 만났던 노드들에 대해서는 거리 정보가 모아지므로 모아진 정보들을 바탕으로 결국 k-최근접이웃을 계산할 수 있게 되는 것이다.

[그림 6] 서울에서 자갈치 시장 찾아가는 과정으로의 그래프 횡단 비유

결국 위의 과정들을 비유해서 표현하자면, 서울에서 부산에 위치한 자갈치 시장에 가는 과정으로 생각해 볼 수 있을 것이다. 시 단위에서는 서울에서 부산으로 비행기로 크게 이동하고(레이어 2에서 서울보다 부산이 자갈치시장에 가깝기 때문에), 부산에서는 지하철로 자갈치 시장 인근의 역까지 이동한 후, 그 다음은 걸어서 자갈치 시장에 도달하는 과정과 비슷한 것이다. NSW 그래프를 위계적으로 쌓았기 때문에 엔터 포인트로부터 크게 점프하며 계산의 대상을 획기적으로 줄이는 이점을 얻을 수 있다.

[그림 7] TOROS N2와 NMSLIB 의 인덱스 빌드 시간 비교

[그림 7]은 HNSW를 지원하는 N2가 NMSLIB 대비 인덱스 빌드 시간에서 우세한 것을 보여준다. 그래프가 곧 인덱스이고, 그 인덱스를 만드는데 시간이 얼마나 걸렸는지를 보주는 것이기 때문에 인덱스 빌드 타임(y축)은 작을수록 좋고, x축은 각 파라미터 세팅을 바꾸면서 실행한 차이를 의미한다. 코드 리팩토링(code refactoring)과 메모리 프리페치(memory prefetch, CPU에서 사용할 데이터를 메인 메모리에서 캐시 메모리로 미리 올려두는 것)를 통해 인덱스 빌드 타임 최적화를 한 결과 [그림 7]에서 보다시피 N2가 NMSLIB 보다 55퍼센트 가량 빠르다고 한다. 한편 초기에 그래프를 얼마나 정교하게 만들지 세팅할 수 있는데, x축의 차이로부터 알 수 있는 것은 빌드 타임에서 시간을 더 많이 들여 그래프를 정교하게 만들수록, 탐색할 때 같은 탐색 시간이라도 정확도가 더 높게 나올 수 있다는 사실이다.

N2의 MMap 지원을 통한 메모리의 효율적인 사용, 간편한 설치 및 사용 코드 예시를 직접 확인할 수 있는 슬라이드로 발표가 마무리 되었다. TOROS N2 는 지금도 강력하지만 여전히 개선의 여지가 있어 더욱 주목할 만하다. 탐색 속도의 개선과 더불어, 빌드 시 메모리 더블링의 이슈 해결과 항상 k개 결과 보장의 개선이 해결해야 할 과제로 제시되었다. 더 좋은 라이브러리가 필요해 직접 만들었고, 이미 충분히 좋지만 만족하지 않는다. 해결책을 밖에서가 아닌, 안에서 직접 찾으려 하는 모습이 인상적인 세션이었다.

본문에 삽입된 슬라이드 자료는 'if kakao 2018' 개발자 콘퍼런스 발표자료에서 인용하였습니다.
(출처: https://if.kakao.com)

콘퍼런스 발표 | 김성진 nick.kim@kakaocorp.com

글 | 김태훈 th.kim@snu.ac.kr

서울대학교 음악오디오연구실에서 음악을 비롯한 콘텐츠 추천 시스템을 연구하고 있습니다. 추천 시스템의 발전은 창작하는 사람과 향유하는 사람 사이의 피드백 선순환을 일으켜 양질의 콘텐츠 생산에 기여할 수 있다고 믿고, 기술로써 그에 조금이나마 보탬이 되기 위해 노력 중입니다.

참고문헌

*1 참고 | https://github.com/spotify/annoy/

*2 참고 | https://github.com/nmslib/nmslib/

*3 참고 | Malkov, Y. A., & Yashunin, D. A. (2016). Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs. arXiv preprint arXiv:1603.09320.

*4 참고 | https://github.com/kakao/n2

*5 참고 | Malkov, Y., Ponomarenko, A., Logvinov, A., & Krylov, V. (2014). Approximate nearest neighbor algorithm based on navigable small world graphs. Information Systems, 45, 61-68.

브런치는 최신 브라우저에 최적화 되어있습니다. IE chrome safari