추천 시스템에서의 근사 최근접 이웃 검색
소개
2024년 2월, 우리는 SF Unstructured Data Meetup에서 Yury Malkov로부터 Approximate Nearest Neighbor (ANN)와 추천 시스템에서의 핵심 역할에 대해 들었습니다. ANN 검색은 이미 세계에서 가장 인기 있는 도구들의 프로덕션 스택에 통합되어 있습니다. Yury는 대규모 추천 시스템에서 ANN의 도입을 이끌어 온 핵심 개념과 배경을 이해하도록 도와줍니다.
Yury Malkov의 발표 YouTube 다시보기 링크: YouTube에서 발표 보기
왜 ANN에 관심을 가져야 할까요?
Yuri Malkov는 말 그대로 천재입니다. 믿기지 않는다면 그의 Google Scholar 목록을 확인해 보세요 https://scholar.google.com/citations?user=KvAyakQAAAAJ&hl=en. 물리학자, 레이저 연구자, 그리고 현재 모든 주요 벡터 데이터베이스에 기본적으로 통합된 그래프 기반 인덱싱 알고리즘인 HNSW의 발명가입니다. 그는 현재 OpenAI에서 Research Scientist로 일하고 있습니다. 이게 2024년에 그럴듯한 Tony Stark 약력처럼 들리지 않는다고 말해 보세요.
그럼 이제 Yuri의 “추천 시스템에서의 Approximate Nearest Neighbor 검색” 발표를 살펴보겠습니다.
ANN 검색이란 무엇인가요?
ANN 검색의 기본 사항은 이미 간단히 그리고 자세히 다룬 바 있으므로 여기서는 짧게 설명하겠습니다.
최근접 이웃 검색은 머신 러닝 또는 데이터 과학 애플리케이션에서 유사도 검색을 수행하는 데 사용할 수 있는 통계 기법의 집합입니다. 검색을 완료할 때 시스템의 모든 데이터 포인트를 서로 비교하는 특별한 K 맛 사촌 KNN과 달리, ANN 검색 알고리즘은 다양한 인덱싱 기법을 사용해 근사 최근접 이웃을 반환합니다. ANN 검색은 오늘날 고객이 직접 사용하는 많은 애플리케이션과 기술의 핵심이 되었습니다. 검색 엔진(벡터 검색이 아니라 Google 같은 것)부터 소셜 미디어 사이트에 이르기까지, ANN과 추천 시스템은 이미 프로덕션 환경에서 스택 전반에 통합되어 있습니다.
ANN이 추천 시스템을 위한 유일한 해결책은 아니었습니다. 그렇다면 우리는 어떻게 여기까지 왔을까요? 오늘날 시장에 있는 성숙한 ANN 솔루션들, 추천 시스템이 최근접 이웃 알고리즘에게 어려운 문제가 되는 이유, 개발자들이 추천 시스템을 어떻게 구조화해 왔는지, 그리고 연구자들이 ANN을 사용해 추천 시스템 스택을 어떻게 다시 쓰고 있는지 살펴보겠습니다. Yuri는 발표에서 성숙한 ANN 솔루션이 많이 존재한다고 언급합니다. 이러한 주제 중 다수는 우리의 벡터 인덱스 선택을 위한 비주얼 가이드에서 심층적으로 다루었지만, 여기서는 Yuri의 발표에 나열된 도구들을 표로 정리했습니다.
언급된 ANN 인덱스 표
| ANN 인덱스 | 분류 | 시나리오 |
|---|---|---|
| LSH | 그래프 기반 인덱스 | - 크고 매우 복잡한 다차원 데이터셋 - 유클리드 거리를 사용하여 데이터 포인트를 버킷화 - 가장 가까운 결과만 반환 |
| HNSW | 그래프 기반 인덱스 | - 매우 빠른 쿼리 - 가능한 한 높은 재현율 필요 - 대용량 메모리 리소스 |
| SCANN | 양자화 기반 인덱스 | - 매우 빠른 쿼리 - 가능한 한 높은 재현율 필요 - 대용량 메모리 리소스 |
| IVF_PQ | 양자화 기반 인덱스(역색인) | - 역색인 - 매우 빠른 쿼리 - 제한된 메모리 리소스 - 재현율에서 상당한 타협 허용 |
| IVF_HSNW | 그래프 기반 인덱스(역색인) | - 역색인 - HSNW 기반 - 가능한 한 높은 재현율 필요 - 대용량 메모리 리소스 |
| DiskANN | 다중 최근접 이웃 인덱스 | - ANN 검색을 위한 ANN 수정 사항 및 툴킷 |
| ANNOY | 다중 최근접 이웃 인덱스 | - LSH 또는 KDtrees 구현 - 고차원 공간에서 메모리 효율적이고 빠른 검색 |
| Many More | - | - FAISS, cuHNSW, ngt, song |
ANN 벤치마크 소개
Yuri는 ANN 벤치마킹을 번개처럼 빠르게 훑고 지나가며 ANNBenchmarks를 가리키지만, 역 ANN 알고리즘 벤치마킹은 까다로울 수 있다는 주의점을 덧붙입니다. 이를 좀 더 천천히 살펴봅시다:
ANN-Benchmarks란 무엇인가요?
ANN-Benchmarks는 다양한 근사 최근접 이웃 검색 알고리즘을 평가하는 벤치마킹 환경으로, 웹사이트에서 거리 측정 방식과 데이터셋별로 나뉜 결과를 제공합니다. 벤치마크는 재현율 및 초당 쿼리 수와 같은 성능 지표를 표시하며, 사용자는 GitHub 풀 리퀘스트를 통해 코드를 제출하여 기여할 수 있습니다.
ANN 알고리즘 벤치마킹 데이터는 여러 곳(github, ANN-Benchmarks, 심지어 제품 문서)에서 찾을 수 있지만, 항상 QPS - 초당 쿼리 수를 표시한 차트를 보게 될 것입니다. QPS가 높을수록 더 좋습니다! 부릉부릉!
ANN(및 기타 벡터 검색) 알고리즘 선택에 대한 참고 사항
알고리즘 벤치마킹을 보면 머리가 아파진다면, 당신만 그런 것은 아닙니다. 그래서 Milvus 팀은 Knowhere를 만들었습니다. Knowhere 는 Faiss, Hnswlib, Annoy를 포함한 여러 벡터 유사도 검색 라이브러리를 통합한 Milvus의 핵심 오픈소스 벡터 실행 엔진입니다. Knowhere는 인덱스 구축 및 검색 요청을 어떤 하드웨어(CPU 또는 GPU)에서 실행할지 제어합니다. 이것이 Knowhere라는 이름의 유래입니다. 즉, 작업을 어디에서 실행할지 아는 것입니다. DPU 및 TPU를 포함한 더 많은 유형의 하드웨어가 향후 릴리스에서 지원될 예정입니다.
Knowhere를 기반으로 Zilliz Cloud 팀은 Zilliz의 핵심 벡터 검색 엔진인 Cardinal을 출시했습니다. 이 검색 엔진은 이미 이전 버전 대비 세 배의 성능 향상을 입증했으며, Milvus의 열 배에 달하는 검색 성능(QPS)을 제공합니다. ANN 검색은 오랫동안 추천 시스템에 통합되어 왔습니다. ANN 검색 알고리즘이 프로덕션 환경의 추천 시스템에서 왜 그렇게 인기를 얻게 되었는지 알아보려면, 한 걸음 물러서서 ANN이 경쟁에서 앞선 동기, 아키텍처, 그리고 새로운 솔루션들을 살펴볼 필요가 있습니다.
대규모 추천 시스템 애플리케이션: 동기와 과제
목표: 모든 추천 시스템의 기본 목표는 쿼리(사용자, 애플리케이션, 컨텍스트)에 대해 아이템(동영상, 제품, 문서, 메시지)을 반환하는 것입니다. 이 아이템-쿼리 관계를 기억하세요. 이는 검색(추천) 알고리즘을 이해하는 데 중요합니다.
시장: 추천 기술은 소비자 행동을 유도하는 능력 덕분에 큰 시장을 형성해 왔고, 현재도 큰 시장을 대표합니다.
대규모 환경의 일반적인 과제:
범용성:
- 전통적으로 추천 시스템은 범용성이 낮았습니다. 이는 주로 내부 데이터, 모델, 인프라에 의존했기 때문입니다.
거대한 코퍼스:
대규모 데이터셋(수백만에서 수조 개의 아이템, 쿼리)은 큰 추론 비용을 발생시킵니다.
효율성과 추론 비용을 제한하는 것은 매우 중요합니다.
무거운 동영상 및 이미지 처리는 인프라를 유지관리할 전담 엔지니어를 필요로 해 왔습니다.
솔루션, 성숙도:
자체 개발 솔루션/인프라는 보통 자체적으로 구축됩니다(예: Google, Meta, X,)
일반적으로 추론 비용을 절감하기 위해 다단계 추천 퍼널(아래 참조)을 사용합니다
벡터 데이터베이스와 LLM의 부상 속에서 즉시 사용 가능한 도구들이 인기를 얻고 주목받고 있습니다.
일반적인 다단계 퍼널
Yuri는 프로덕션 환경의 일반적인 추천 시스템 다이어그램을 자세히 살펴봅니다. 아래 동영상 추천 예시에서 애플리케이션은 아이템과 쿼리를 전달받고, 동영상 추천 핀을 반환해야 합니다. 이러한 애플리케이션은 아이템 후보가 생성되고 연속적인 랭킹 모델을 거쳐 검색 결과를 정제하는 다단계 퍼널입니다.
1단계: 후보 생성 - ANN + Light Model
이 초기 단계에서 시스템은 근사 최근접 이웃을 사용해 방대한 동영상 데이터베이스를 빠르게 훑고, 사용자의 쿼리와 관련 있는 예비 후보 동영상 목록을 식별합니다. 이 프로세스는 빠르고 효율적으로 설계되어 있으며, 쿼리 특성과 일치할 가능성이 가장 높은 항목에 집중함으로써 잠재적으로 수백만 개의 아이템을 처리합니다. 이 단계에서 사용되는 'Light Model'은 일반적으로 더 단순하고 계산 집약도가 낮은 모델로, 후보 풀을 사용자의 관심사나 검색어와 가장 잘 부합하는 항목으로 좁히는 데 도움을 줍니다.
2단계: 경량 랭킹 - Brute Force + Middle Model
후보 집합이 생성되면, 다음 단계에서는 이 후보들을 더 자세히 검토합니다. 이는 각 후보를 'Middle Model'을 사용해 더 철저히 평가하는 'Brute Force' 접근 방식으로 수행되며, 이 모델은 첫 번째 단계에서 사용된 Light Model보다 더 복잡합니다. 이 모델은 사용자 참여 지표, 컨텍스트 관련성, 콘텐츠 품질과 같은 추가 특징을 고려하여 후보의 순위를 매기고, 가장 관련성 높은 동영상이 추천 목록의 상단으로 올라가도록 합니다. 이 단계는 성능과 정밀도 사이의 균형을 맞추며, 품질과 관련성에 더 집중하여 선택을 정제합니다.
3단계: 전체 랭킹 - Brute Force + Heavy Model
추천 프로세스의 마지막 단계는 Full Ranking 단계로, 사용된 모델 중 가장 정교하고 리소스를 많이 소모하는 'Heavy Model'을 사용합니다. 이 모델은 더 심층적인 사용자 프로필 분석, 장기 선호도, 상세한 콘텐츠 분석, 그리고 현재 시청 트렌드와 같은 실시간 데이터까지 포함할 수 있는 광범위한 신호와 데이터 포인트를 통합합니다. 여기서 적용되는 Brute Force 방법은 각 동영상이 종합적으로 점수화되고 순위가 매겨지도록 하여, 최종 추천이 매우 개인화되고 관련성이 높도록 보장합니다. 이 단계는 최고 품질의 추천을 보장하지만 더 많은 처리 능력과 시간이 필요하므로, 추천 목록의 최종 정제에 적합합니다.
전통적인 추천 시스템에서 HSNW가 어려움을 겪는 이유와 (불완전한) 해결책 대규모 프로덕션 추천 시스템이 방대한 데이터셋과 그에 수반되는 비용의 제약을 받는다는 점을 알고 있는 Yuri는 아이템과 쿼리가 두 개의 - 호환되지 않는 평면 위에 놓여 있다고 주장합니다. 쿼리와 아이템이 서로 다르고 호환되지 않는 공간에 존재할 때, Hierarchical Navigable Small World (HNSW)와 같은 전통적인 유사도 검색 알고리즘은 어려움에 직면합니다. 이러한 알고리즘은 쿼리와 아이템 간의 측정 가능한 관계 또는 거리 함수에 직접 의존하기 때문입니다. 근접성을 평가할 명확한 기준이 없으면, HNSW는 쿼리와 가장 가까운 일치 항목을 찾기 위해 아이템 그래프를 탐색하는 본래 기능을 효과적으로 수행할 수 없습니다.****
아이템-쿼리 비호환성에 대한 새로운 해결책 검토
데이터 벡터에 대한 L2 거리
작동 방식: 벡터화된 데이터 입력 간의 L2 거리를 사용하여 추천 시스템을 위한 대체 그래프 구조를 생성합니다.
장점: 간단한 거리 계산을 사용하여 프로세스를 단순화하며, 후보 생성 및 재순위화 단계에서 속도상의 이점을 제공합니다.
단점: 더 정교한 모델만큼 아이템과 쿼리 간의 복잡한 관계나 미묘한 차이를 효과적으로 포착하지 못할 수 있으며, 잠재적으로 덜 개인화된 추천으로 이어질 수 있습니다.
이분 그래프 랭킹
작동 방식: 아이템과 쿼리를 이분 그래프로 투영하여, 아이템이 가장 가까운 사용자 또는 쿼리와 연결되도록 하고 이러한 관계를 기반으로 엣지가 생성되게 합니다.
장점: 사용자와 아이템 간의 관계형 데이터를 구조화하는 데 효과적이지만, 다른 방법과의 직접적인 비교는 제한적입니다.
단점: 이분 그래프의 구축과 유지관리는 리소스를 많이 소모할 수 있으며, 효과는 그래프 연결의 밀도와 품질에 따라 크게 달라질 수 있습니다.
이미지 출처: https://www.vldb.org/pvldb/vol15/p794-tan.pdf
그래프 재순위화 (텍스트 중심)
작동 방식: 후보 생성을 위해 벡터로부터 생성된 그래프를 활용하고, 텍스트 검색을 위해 그래프에 직접 heavy ranker를 적용하여 결과 품질을 향상시킵니다.
장점: 전통적인 다단계 퍼널을 제거하여, 후보 필터링의 초기 단계에서 발생한 오류를 수정할 수 있게 합니다.
단점: 주로 텍스트 기반 검색에 효과적이며, 비텍스트 특성이 지배적인 다른 맥락에서는 그만큼 효과적이지 않을 수 있어 적용 가능성이 제한됩니다.
이미지 출처: https://arxiv.org/pdf/2208.08942
계단식 그래프 검색
작동 방식: 초기 검색에는 가벼운 거리 함수를 사용해 시작하고, 검색 과정 중에 더 무거운 거리 함수로 매끄럽게 전환합니다.
장점: 실시간으로 거리 함수를 조정하여 유연성을 제공하며, 검색 과정 전반에서 속도와 정확도를 모두 최적화합니다.
단점: 두 가지 거리 함수를 관리하고 최적화하는 복잡성으로 인해 시스템의 계산 오버헤드와 복잡성이 증가할 수 있으며, 잠재적으로 확장성에 영향을 줄 수 있습니다.
이미지 출처: https://arxiv.org/pdf/2202.10226
ANN Search가 왜 그렇게 인기 있을까요?
이 모든 것을 종합하면 – Yuri는 ANN 알고리즘이 특히 고차원 데이터셋을 다루는 애플리케이션(예: 대규모 추천 시스템)에서 왜 그렇게 폭넓게 구현되어 왔는지 잘 설명해 주었습니다.
충분히 좋은(또는 더 나은) 매칭 - 완벽한 매칭이 필요하지 않다면, ANN 방식은 거의 항상 다른 NN 알고리즘보다 더 나은 해결책입니다.
유연성 - 다양한 구현 방식이 있어 개발자가 비용을 선택할 수 있습니다
성숙도 - ANN은 모든 주요 프로그래밍 언어로 구현되어 왔으며, ANN 검색을 선택하고 실행하기 위한 여러 인기 프레임워크가 있습니다.
추가 자료
https://zilliz.com/learn/Local-Sensitivity-Hashing-A-Comprehensive-Guide
https://zilliz.com/learn/how-to-pick-a-vector-index-in-milvus-visual-guide
Yury Malkov 강연의 YouTube 다시보기 링크: YouTube에서 강연 보기
계속 읽기
Introducing Business Critical Plan: Enterprise-Grade Security and Compliance for Mission-Critical AI Applications
Discover Zilliz Cloud’s Business Critical Plan—offering advanced security, compliance, and uptime for mission-critical AI and vector database workloads.
Why Not All VectorDBs Are Agent-Ready
Explore why choosing the right vector database is critical for scaling AI agents, and why traditional solutions fall short in production.
Democratizing AI: Making Vector Search Powerful and Affordable
Zilliz democratizes AI vector search with Milvus 2.6 and Zilliz Cloud for powerful, affordable scalability, cutting costs in infrastructure, operations, and development.