근사 최근접 이웃

근사 최근접 이웃은 아주 많은 벡터 가운데 주어진 벡터와 가까운 것을 빨리 골라 줍니다. 전부 하나씩 견주지 않고 가까울 만한 후보만 살펴봅니다. 그래서 가장 가까운 것을 가끔 놓칩니다. 그 대신 벡터가 수억 개 쌓인 저장소에서도 검색이 짧게 끝납니다.

상세

이 절은 근사 최근접 이웃이 푸는 문제를 먼저 정합니다. 이어서 정확한 풀이에 왜 시간이 많이 드는지, 근사가 무엇을 내주고 무엇을 얻는지 봅니다. 끝으로 후보를 추리는 대표 방법 넷과 쓰는 때를 봅니다.

벡터를 점으로 보는 법

벡터는 숫자를 정해진 개수만큼 늘어놓은 목록입니다. [3, 4] 는 숫자 둘짜리 벡터입니다. 숫자의 개수를 차원이라고 부릅니다. 이 벡터는 2차원입니다.

2차원 벡터는 평면 위의 점 하나로 볼 수 있습니다. [3, 4] 는 가로로 3, 세로로 4 만큼 간 점입니다. 숫자가 천 개인 벡터는 천 차원 공간의 점입니다. 머릿속에 그릴 수는 없지만 계산은 똑같이 합니다.

점 둘이 얼마나 가까운지는 수 하나로 잽니다. 가장 흔한 것은 두 점을 곧게 이은 길이인 유클리드 거리입니다. 두 벡터가 가리키는 방향이 얼마나 같은지를 보는 코사인 유사도도 많이 씁니다. 이 항목에서는 어느 척도를 쓰든 「가깝다」라는 말로 묶어 부릅니다.

가장 가까운 점을 찾는 문제

최근접 이웃 검색은 점 여럿 가운데 주어진 점과 가장 가까운 점을 찾는 문제입니다. 입력은 저장된 벡터 n 개와 쿼리 벡터 하나입니다. 쿼리 벡터는 「이것과 닮은 것을 찾아 달라」며 건네는 기준 벡터입니다. 출력은 쿼리 벡터와 가장 가까운 벡터입니다.

가장 가까운 것 하나가 아니라 k 개를 찾으면 k-최근접 이웃(k-NN, k-Nearest Neighbors) 검색입니다. k 는 몇 개를 돌려받을지 부르는 쪽이 정합니다. 추천 목록 열 칸을 채우려면 k 는 10 입니다.

이 문제가 흔해진 것은 임베딩 때문입니다. 임베딩은 글·이미지·상품 같은 데이터를 벡터로 바꾼 것입니다. 잘 학습한 모델은 뜻이 비슷한 데이터에 가까운 벡터를 줍니다. 그래서 「이것과 비슷한 것 찾기」가 곧 가장 가까운 벡터 찾기가 됩니다.

「차량 수리」라는 검색어와 「자동차 정비 안내」라는 글은 낱말이 하나도 안 겹칩니다. 그래도 임베딩은 둘을 가까운 점으로 놓습니다. 검색어 벡터와 가장 가까운 벡터를 찾으면 이 글이 나옵니다.

전부 견주는 정확한 풀이

가장 쉬운 풀이는 쿼리 벡터와 저장된 벡터 전부의 거리를 하나씩 재는 것입니다. 이 풀이를 완전 탐색이라고 부릅니다. 완전 탐색은 가장 가까운 벡터를 언제나 빠짐없이 찾습니다.

비용은 벡터 수 n 과 차원 d 가 정합니다. 벡터 둘의 거리를 재려면 숫자 d 쌍을 계산합니다. 이것을 n 번 하므로 검색 한 번에 O(n·d) 가 듭니다. O(n·d) 는 비용이 n 과 d 의 곱에 비례한다는 뜻입니다.

n 이 1억이고 d 가 1,000 이면 검색 한 번에 곱셈이 천억 번 듭니다. 요청마다 이만큼 계산하면 응답이 너무 늦습니다. 근사 최근접 이웃은 이 비용을 줄이려고 나왔습니다.

공간을 나눠도 안 줄어드는 비용

전부 견주지 않으려면 먼 벡터를 미리 걸러 내야 합니다. 차원이 낮으면 k-d 트리가 이 일을 잘합니다. k-d 트리는 공간을 구역으로 잘게 나눠 두는 트리입니다. 검색할 때 쿼리에서 먼 구역은 열지 않고 건너뜁니다.

차원이 수백을 넘으면 이 건너뛰기가 듣지 않습니다. 고차원에서는 쿼리와 모든 점 사이의 거리가 서로 비슷해지기 때문입니다. 어느 구역도 멀다고 버릴 수 없으니 결국 대부분을 견주게 됩니다.

차원이 높아질수록 공간을 나누는 방법이 이렇게 힘을 잃는 현상을 차원의 저주라고 부릅니다. 고차원에서는 늘 정확하면서 완전 탐색보다 크게 빠른 방법을 찾기 어렵습니다. 그래서 정확함을 조금 내려놓는 쪽으로 갑니다.

조금 놓치고 크게 줄이는 근사

근사 최근접 이웃(ANN, Approximate Nearest Neighbor)은 이 문제를 근사로 풉니다. 가장 가까운 k 개를 대부분 찾되 가끔 놓치는 것을 받아들입니다. 그 대신 저장된 벡터 가운데 일부만 견줍니다.

ANN 은 머신러닝에서 인공 신경망(Artificial Neural Network)의 줄임말로도 씁니다. 벡터 검색을 다루는 글에서 ANN 이라고 하면 대개 근사 최근접 이웃입니다.

이론에서는 근사를 거리로 정합니다. 진짜 최근접 이웃까지의 거리가 r 이면 r 의 (1 + ε) 배 안에 있는 점을 돌려주면 답으로 칩니다. ε 은 얼마나 봐줄지를 정하는 작은 양수입니다. ε 이 0.1 이면 진짜 답까지 거리의 1.1 배 안에 드는 점을 답으로 인정합니다.

실무에서는 재현율로 잽니다. 재현율은 완전 탐색이 찾을 k 개 가운데 근사 검색도 찾아낸 몫입니다. 아래 코드는 k 가 10 일 때 재현율을 셉니다.

exact  = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
approx = {1, 2, 3, 4, 5, 6, 7, 8, 9, 42}

hit = exact & approx
len(hit)                # 9
len(hit) / len(exact)   # 0.9

exact 는 완전 탐색이 찾은 벡터 번호입니다. approx 는 근사 검색이 찾은 번호입니다. 근사 검색은 10번 대신 42번을 돌려줬습니다. 재현율 0.9 는 정답 열 개 가운데 아홉을 찾았다는 뜻입니다.

재현율은 쿼리마다 다릅니다. 같은 설정이어도 어떤 쿼리는 열 개를 다 맞히고 어떤 쿼리는 여럿 놓칩니다. 그래서 재현율은 쿼리 여럿을 돌려 평균으로 잽니다. 평균이 0.9 여도 몇몇 쿼리는 그보다 훨씬 많이 놓칠 수 있습니다.

후보를 더 많이 살펴보면 재현율이 오릅니다. 그 대신 검색은 느려집니다. 둘 사이의 균형은 검색할 때 후보를 얼마나 넓게 살펴볼지 정하는 설정값으로 고릅니다. 재현율을 1 에 붙이려 할수록 살펴보는 벡터가 늘어 완전 탐색에 가까워집니다.

인덱스를 먼저 짓는 두 단계

근사 최근접 이웃은 검색 전에 준비를 합니다. 저장된 벡터를 미리 정리해 인덱스를 지어 둡니다. 인덱스는 나중에 빨리 찾으려고 데이터를 미리 정리해 둔 구조입니다.

검색할 때는 인덱스를 따라 쿼리 근처의 후보만 추립니다. 후보끼리만 거리를 재고 가까운 k 개를 돌려줍니다. 인덱스는 한 번 짓습니다. 검색은 요청마다 합니다. 그래서 짓는 데 드는 시간을 검색 여러 번이 나눠 냅니다.

후보를 추리는 네 갈래

후보를 어떻게 추리느냐에 따라 방법이 갈립니다. 흔히 넷으로 묶습니다. 아래 표가 넷을 나란히 보입니다. 표 다음 문단에서 하나씩 봅니다.

그래프 방식은 벡터마다 가까운 벡터 몇 개를 이웃으로 이어 둡니다. 검색은 이 선을 따라 쿼리 쪽으로 걷습니다. 출발점은 미리 정해 둔 점 하나를 쓰거나 아무 점이나 고릅니다. 아래 그림이 검색 한 번을 보입니다.

flowchart TD
    S["출발점에 선다"] --> N["지금 점의 이웃들과 쿼리 사이의 거리를 잰다"]
    N --> Q{"지금 점보다 쿼리에 가까운 이웃이 있나"}
    Q -->|"있다"| M["가장 가까운 이웃으로 옮긴다"]
    M --> N
    Q -->|"없다"| E["지금 점을 답으로 낸다"]

이 걷기가 근사인 까닭은 이웃만 보고 판단하기 때문입니다. 멈춘 점보다 가까운 점이 그래프의 다른 쪽에 있을 수 있습니다.

덜 놓치려면 지금까지 본 점 가운데 쿼리에 가까운 것 여럿을 목록으로 들고 다닙니다. 그 목록에 든 점들의 이웃을 모두 살핍니다. 목록이 길수록 덜 놓치는 대신 느려집니다. 이 목록의 길이가 앞에서 말한 설정값입니다.

그래프 방식의 대표는 HNSW(Hierarchical Navigable Small World)입니다. HNSW 는 이런 그래프를 층으로 쌓습니다. 위층일수록 점을 적게 남겨서 이웃 사이가 멉니다.

검색은 맨 위층에서 시작해 크게 건너뜁니다. 한 층씩 내려가며 범위를 좁힙니다. 모든 점이 있는 맨 아래층에서 답을 고릅니다.

군집 방식은 벡터를 가까운 것끼리 묶음 여럿으로 나눠 둡니다. 나누는 데는 k-평균 군집화를 흔히 씁니다. 묶음마다 한가운데를 대표하는 벡터를 하나씩 정합니다. 검색할 때는 쿼리와 대표 벡터가 가까운 묶음 몇 개만 엽니다.

답이 열지 않은 옆 묶음에 들어 있으면 놓칩니다. 여는 묶음 수를 늘리면 덜 놓칩니다. 검색은 느려집니다. 군집 방식의 대표는 IVF(Inverted File, 역파일)입니다.

해싱 방식은 해시 함수를 거꾸로 씁니다. 보통 해시 함수는 비슷한 입력도 서로 다른 칸으로 흩어 놓습니다. 지역 민감 해싱(LSH, Locality-Sensitive Hashing)은 가까운 벡터일수록 같은 칸에 떨어질 확률이 높도록 만든 해시입니다.

검색할 때는 쿼리와 같은 칸에 든 벡터만 봅니다. 가까운 벡터도 운이 나쁘면 다른 칸에 떨어집니다. 그래서 해시를 여러 벌 두고 어느 한 벌에서라도 같은 칸이면 후보로 넣습니다.

양자화 방식은 벡터를 더 적은 비트로 줄여 담습니다. 바탕이 되는 양자화는 숫자 하나를 대표값 몇 개 가운데 가장 가까운 것으로 바꿔 적는 일입니다. 대표값은 미리 정해 둡니다. 대표값이 256 개뿐이면 숫자 하나를 대표값의 번호, 곧 8비트로 적을 수 있습니다.

곱 양자화(PQ, Product Quantization)는 같은 일을 숫자 하나가 아니라 벡터 토막 하나에 합니다. 벡터를 토막 여럿으로 나눕니다. 토막마다 대표 토막 가운데 가장 가까운 것을 찾아 그 번호만 적습니다. 대표 토막은 인덱스를 지을 때 저장된 벡터들의 토막에서 미리 뽑아 둡니다.

벡터 하나는 이렇게 번호 몇 개의 목록이 됩니다. 이 번호 목록을 그 벡터의 코드라고 합니다. 코드는 원래 벡터보다 메모리를 훨씬 적게 차지합니다. 코드로는 거리도 빨리 어림합니다.

어림이라 순위가 조금 어긋날 수 있습니다. 양자화는 홀로 쓰기보다 군집 방식과 겹쳐 쓰는 일이 많습니다. 연 묶음 안의 벡터를 코드로 견주는 식입니다.

검색 한 번의 비용

두 풀이의 비용을 나란히 놓으면 아래와 같습니다. n 은 벡터 수, d 는 차원입니다.

근사 인덱스는 n 개 가운데 일부만 견줍니다. 그래서 벡터가 열 배 늘어도 견주는 수는 열 배만큼 늘지 않습니다. 얼마나 덜 느는지는 방법과 설정값마다 다릅니다.

공간은 벡터를 담는 몫에 인덱스 몫이 더 붙습니다. 그래프 방식은 벡터마다 이웃 목록을 더 담습니다. 양자화 방식은 반대로 벡터 대신 코드를 담아 공간을 줄입니다.

쓰는 때와 안 쓰는 때

벡터가 많아서 완전 탐색으로는 응답 시간이 모자랄 때 씁니다. 결과를 조금 놓쳐도 쓸모가 남는 검색이어야 합니다. 비슷한 상품 추천이나 뜻으로 찾는 시맨틱 검색이 그렇습니다.

검색 증강 생성(RAG, Retrieval-Augmented Generation)도 이 검색을 씁니다. 검색 증강 생성은 대규모 언어 모델이 답하기 전에 질문과 관련된 문서를 찾아 함께 건네는 방식입니다. 그 문서를 찾는 단계가 근사 최근접 이웃 검색입니다.

벡터가 적으면 쓰지 않습니다. 완전 탐색으로도 충분히 빠르면 인덱스를 지을 까닭이 없습니다. 하나라도 놓치면 안 되는 검색에도 맞지 않습니다.

벡터를 자주 지우거나 바꾸는 데이터에서는 인덱스를 고치는 비용이 붙습니다. 방법에 따라 지운 벡터를 표시만 해 두었다가 나중에 인덱스를 다시 짓기도 합니다.

가격이나 날짜 같은 조건으로 거르면서 가까운 것을 찾을 때도 조심해야 합니다. 인덱스가 추린 후보를 조건이 또 깎아 내므로 k 개를 못 채우거나 놓침이 늘기도 합니다.

관련 항목

근사 최근접 이웃이 속하는 상위 분류

최근접 이웃 검색 · 벡터 검색 · 유사도 검색 · 시맨틱 검색 · 검색 · 근사 알고리즘

근사 최근접 이웃과 맞세워지는 정확한 풀이

완전 탐색 · k-최근접 이웃 · k-d 트리 · 볼 트리 · 공간 분할 · 차원의 저주 · 힙

근사 최근접 이웃이 후보를 추리는 인덱스 방식

HNSW · 탐색 가능 스몰 월드 · IVF · k-평균 군집화 · 지역 민감 해싱 · 곱 양자화 · 양자화 · 스칼라 양자화 · DiskANN

벡터 사이 가까움을 재는 척도

유클리드 거리 · 코사인 유사도 · 내적 · 벡터 정규화 · 거리 함수

근사의 품질과 속도를 재는 지표

재현율 · 정밀도와 재현율 · 지연 · 처리량 · 초당 쿼리 수

근사 최근접 이웃이 다루는 데이터와 표현

벡터 · 차원 · 임베딩 · 임베딩 모델 · 밀집 벡터 · 고차원 벡터 · 색인

근사 최근접 이웃을 구현한 라이브러리와 저장소

FAISS · Annoy · ScaNN · pgvector · 벡터 데이터베이스 · Milvus · Qdrant · Elasticsearch · OpenSearch

근사 최근접 이웃이 받치는 서비스 기능

검색 증강 생성 · 추천 시스템 · 이미지 검색 · 중복 탐지 · 하이브리드 검색 · 대규모 언어 모델