Jan 8, 2022
추천 시스템 6 — ScaNN을 이용한 벡터 유사도 검색
이번 글에서는 ScaNN을 이용해서 빠르게 벡터 유사도 검색을 하는 방법에 대해 알아보겠습니다. Retrieval Model을 구현하면서 사용한 BruteForce는 모든 영화 임베딩벡터와 내적한 뒤 가장 내적값이 큰 Top K개의 아이템을 얻었습니다. 이런 방법은 전체 아이템이 수백 수천만개 이상이 될 경우 심각한 성능 저하로 이어질 수 있습니다. TFRS는 함께 사용 가능한 ScaNN 패키지를 제공하는데, 이를 이용하면 빠르고 정확한 결과를 얻을 수 있습니다.
ANN
ScaNN은 BruteForce와는 달리 여러 최적화 방법을 사용해서 모든 임베딩 벡터와 비교하지 않습니다. 그렇기 때문에 ScaNN으로 찾은 유사한 유사한 벡터들은 실제값이 아닌 근사값입니다. 이런 벡터 유사도 검색을 ANN(Approximately Nearest Neighbor)이라고 부릅니다.
벡터간의 유사도를 평가할 때는 유클리디안 거리나 코사인 유사도 같은 여러가지 방법이 있는데, 추천 시스템에 많이 사용되는 내적값이 가장 큰 결과를 찾는 방식의 ANN은 MIPS(Maximum Inner Product Search)라고 부릅니다. MIPS에는 크게 2가지 최적화 기법이 사용됩니다. 계산량을 줄이는 방법과 양자화입니다.
계산량 줄이기
빠른 검색을 위해선 계산량을 줄여야합니다. 트리 기반의 검색 알고리즘이나, 해싱 알고리즘을 이용하여 멀리 떨어진 벡터는 배제하고 가까운 벡터끼리만 거리를 계산하는 방법입니다.
양자화
여기서 양자화란 값을 표현하는 경우의 수를 줄여서 벡터가 차지하는 메모리 크기를 줄이는 압축기법을 의미합니다. 데이터가 압축되면 수백 수천만개의 벡터들이 차지하는 메모리 사용량이 줄어들 뿐 아니라, CPU에 전달되는 메모리 대역폭 사용량도 줄어들고 CPU의 계산능력을 극대화할 수 있습니다.
ScaNN
ScaNN은 Google Research에서 2020년 발표한 보다 빠르고 효과적인 state-of-the-art 오픈소스 벡터 유사도 검색 라이브러리입니다. 블로그에서 보여준 성능 비교 그래프와 http://ann-benchmarks.com/ 에서 ANN 성능들을 벤치마크해보면 확실히 뛰어난 것을 알 수 있습니다.
ScaNN은 위에서 설명한 최적화 기법들을 사용합니다. Asymmetric Hashing를 이용해서 유사한 벡터를 빠르게 찾고, Anisotropic Vector Quantization라는 방식의 양자화를 통해 더 정확하고 빠르게 데이터를 압축합니다.
ScaNN 사용해보기
우선 자세히 알아보기 전에 간단하게 예제를 통해 ScaNN을 사용해보겠습니다. 예전 Basic Retrieval Model 예제에서 뒷부분의 BruteForce를 이용해서 검색하는 부분만 ScaNN으로 바꿔보았습니다. 전체 코드는 여기에 있습니다.
10개의 영화를 추천해봤는데, 상당히 비슷한 걸 알 수 있습니다. 그렇다면 실행성능은 어떨까요?
scann이 훨씬 빠른걸 알 수 있습니다.
ScaNN 자세히 살펴보기
ScaNN의 검색과정
우선 검색과정부터 알아보겠습니다. ScaNN은 검색할 쿼리 벡터가 주어졌을 때, 아래 3단계로 유사한 벡터를 찾습니다.
- 파티션 검색(Partitioning): ScaNN은 전체 데이터를 미리 파티셔닝하고(비슷한 값끼리 그룹화하는 것) 이들 중 쿼리 벡터와 유사한 파티션들을 찾아서 다음 단계로 넘깁니다.
- 점수매기기(Scoring): 파티션 내의 데이터와 거리를 측정해서 거리를 계산합니다. 이 때 Asymmetric Hashing(AH) 을 이용해서 빠르고 실제 거리와 거의 유사한(near-perfect) 값을 계산해냅니다.
- 다시 점수매기기(Rescoring): 1, 2단계를 거쳐 필터링된 벡터들의 거리를 바탕으로 Top K개의 값을 추려냅니다. 이후 다시 정확한 거리를 측정한 다음 정렬합니다.
ScaNN 튜닝하기
ScaNN 클래스의 생성자의 인자를 통해 속도를 높이고 정확도를 낮추거나 속도를 낮추고 정확도를 올리는 방법을 알아보겠습니다.
이 중 성능 튜닝을 위한 인자를 살펴보겠습니다.
- query_model: 입력을 임베딩 벡터로 바꿔주는 모델입니다.
- name: 레이어 이름입니다.
- k: 기본으로 유사한 벡터를 몇 개 받을지 지정합니다.
- num_leaves: 몇 개의 파티션으로 분할할 것인가를 지정합니다.
- num_leaves_to_search: 파티셔닝 단계에서 몇 개의 파티션을 찾아서 scoring단계로 넘길 지 지정합니다.
- dimensions_per_block(default 2): 데이터 압축 비율로, 클 수록 압축률이 높아집니다. 그렇지만 정확도는 낮아질 것입니다.
- num_reordering_candidates: rescoring단계에서 Top K개를 추린 후 다시 정확하게 거리를 측정해서 재정렬하는데, rescoring때 추릴 개수를 지정하는 인자입니다. 값이 클 수록 더 정확한 결과를 내려주지만, 속도는 떨어지게 됩니다. 지정하지 않으면 rescoring을 수행하지 않습니다. 이 값은 반드시 추천 개수를 지정하는 값인 k보다 커야합니다.
- parallelize_batch_searches: 쿼리를 병렬로 처리하게 합니다.
예를 들어 num_leaves가 100이고 num_leaves_to_search 10이면, 전체를 100개의 파티션으로 분할하고, 그 중 10개만 검색대상이 되므로, 전체 값 중 가능성이 높아보이는 10%만 검색하게 됩니다. num_leaves가 1000이고 num_leaves_to_search가 100이면, 동일하게 10%만 검색하게 되지만, 보다 정확하게 검색할 수 있게 됩니다.
권장사항(Rules of Thumb)
튜닝 인자가 꽤 있는데, ScaNN 깃허브에서는 아래와 같은 방식을 권장합니다.
- 데이터가 2만개 이하일 경우 Brute-Force 사용을 권장합니다. → ScaNN을 쓰는게 오히려 비효율적인 것 같습니다.
- 데이터가 10만개 이하일 경우 파티셔닝 없이 AH Scoring, Rescoring을 사용하기 → 파티셔닝이 필요없는걸로 보입니다.
- 10만개 이상일 경우는 파티셔닝과 AH Scoring, Rescoring을 사용하기.
- AH-Tree를 사용할 때는
dimensions_per_block을 2로 하는게 좋습니다. - 파티셔닝을 사용할 때는
num_leaves는 대략 데이터 개수의 제곱근이어야합니다.
권장사항 적용해보기
권장사항을 보고 적용해보겠습니다. TFRS의 ScaNN 레이어는 항상 AH Scoring을 사용하므로, dimensions_per_block은 2로 고정하고, 데이터 개수에 따라 num_leaves를 제곱근으로 정하거나 너무 적을 경우 BruteForce를 사용하면 될 것 같습니다. 이후 성능과 정확도를 보면서 num_leaves_to_search와 num_reordering_candidates를 조절하며 trade-off 하면 될 것 같습니다.
성능을 비교할 지표로는 재현률(recall)을 사용하겠습니다. BruteForce Top 100의 결과를 true label로 삼고, ScaNN Top 100과 얼마나 일치하는지를 의미합니다. 인자를 바꿔가며 확인해보겠습니다.
재밌는 점은 특정 인자의 값을 키우는 것이 반드시 성능향상/하락으로 이어지지 않는다는 것과. 여러 인자의 조합을 통해 더 적은 시간소모로 더 나은 recall을 얻을 수도 있다는 것입니다.
이번 글에서는 ScaNN을 이용하여 TFRS모델에서 더 빠르게 Retrieval을 수행하는 방법에 대해서 알아보았습니다. 다음 글에서는 이전 글에서 구현한 Retrieval Model과 Ranking Model을 개선해보겠습니다.
