ChromaDB 에서 HNSW 를 이해하자

728x90

왜 쓰게 됬는가?

나라장터 공고를 분석해 선택된 특정 키워드에 맞춰 추천하는 시스템을 개발하고 있다.

그중 원문데이터를 쪼개서 임베딩할 수 있는 방법이 필요했고, ChormaDB를 선택해서

사용하였다.

왜 필요하냐면 원문데이터 자체로는 의미를 이용한 검색이 어렵다.

따라서 의미백터(임베딩)을 도입하였고, 이를 효율적으로 저장 검색하기 위해서

ChromaDB를 선택하였다.

왜 쪼개야 할까?

원문(문서, PDF, 로그, 가이드 등)은 보통:

너무 김
의미가 여러 개 섞여 있음
질문 하나에 전체 문서가 필요하지 않음

그래서 다음처럼 만들었다.

[원문] ↓ [chunk 단위로 분할] ↓ [각 chunk를 임베딩] ↓ [벡터 DB에 저장]

이렇게 만들고 구현은 했는데 사실 내부에서 어떻게 도는지에 대한 이해도가 너무나도 부족하여

공부를 하는중 빠르게 임베딩벡터를 가져오는 방법을 인덱스 알고리즘이 HNSW라는 기법을 이용한다는것을

알게되었고, 이를 이해한 문서이다.

HNSW?

Hierarchical Navigable Small World 라는 의미로

단어 의미

Hierarchical	계층적인 (여러 레이어 구조)
Navigable	탐색 가능한
Small World	소규모 세계 그래프 (짧은 경로 특성)

즉, 계층구조를 가진 탐색에 용의한 스몰월드 그래프인데

여깃 스몰월드 그래프라는것은 지구촌 모든사람을 건너건너면 6명안에 들어간다는

이야기가 있듯이 노드가 아무리 많아도 랜덤노드에서 랜덤노드까지 아주 적은 단계로

갈 수 잇는 그래프를 의미한다.

그래서 대부분은 사람들은 아주 작은 범위에서 관계를 가지고 있지만, 그중 한명씩 아주 먼 곳으로

점프할 수 있는 링크를 가지고 있듯이

똑같이 국소연결 + 소수의 장거리 연결을 통해 이루어진다고 이해할 수 있다.

여기서 장거리 링크가 필요한게 비유하자면 다음과 같다

내가만약 집에서 강남역까지 간다고한다면

작은길 , 동네길만있으면 매우 복잡하게 따라가고 훨씬더 오래걸릴것이다.

하지만, 지하철이나 고속도로처럼 한번에 긴거리를 갈 수있는 체계가 있으면 훨씬 빠르고 쉽게 갈수있는데

이것이 장거리 링크가 필요한이유다.

그렇다면 계층이란 무엇일까

계층 (Hierarchy)의 의미

HNSW는 그래프를 여러 층으로 쌓는다.

위층 (노드 적음, 연결 희소, 멀리 이동) ↓ 아래층 (노드 많음, 연결 촘촘, 정밀 탐색)

멀리 있을 때는

“정확함”보다 “방향”이 중요하고

가까워지면

“방향”보다 “정확함”이 중요하기 때문

그래서:

위층: 대충 방향 잡기 (빠름)
아래층: 정밀하게 찾기

→ 전체 탐색 없이도 log(N) 수준 탐색 가능

예를들어 강남에서 부산으로간다고 치면 일단 길을 보는게 아니라

남쪽으로간다. 부터 시작해서 가면갈 수록 더 정밀하게 찾아서 유사한 공간을 찾아내는 것을 의미한다.

BFS 같은건가? (https://arxiv.org/abs/1603.09320)

처음에 해당 개념에 대한 문서를 읽었을때 , 링크 참조

노드를 이용해서 아랫 단계로 내려간다는 걸로 이해해서 햇갈렸다 정리하자면 다른데

BFS 아니다

BFS는 레벨(간선 수) 기준
HNSW는 거리 기준
모든 노드를 다 보지 않는다

우리가 흔히쓰는 BFS는 레벨 개념에서 다음 노드로 내려가서 찾아내는 방식을 이용하는데

즉, 탐색 깊이 - 뎁스를 따라서 이동한다.

HNSW 는 레이어 라는 개념을 쓴다.

Layer 3 (아주 일부 벡터) Layer 2 Layer 1 Layer 0 (모든 벡터)

이런식으로 레이어를 나눠서 위에있는 적은 노드부터 아래층으로 따라가게 만드는건데

단위하나가 노드 즉, 벡터이고 여기서 연결을 엣지라고 이해할 수 있는것이다.

정리하면

HNSW 란?

벡터들을 노드로 하는

계층적(다층) 근접 그래프를 만들고

그 위를 탐색하는 알고리즘이다

즉, 이 알고리즘이 푸는 핵심적인 문제는

수많은 벡터 중에서 쿼리 벡터와 가장 비슷한 벡터 몇 개를 빠르게 찾고 싶다

근데 너무 많으니까 순진하게 O(N) 으로하면 (완전탐색) 엄청나게 오래걸릴 것이다.

따라서 등장하는게 근사 탐색인데, 정확하지는 않아도 거의 유사한 답을 찾는 다는 것이며

이것이 **ANN (Approximate Nearest Neighbor)**문제고,

HNSW는 그중에서도 그래프 기반 ANN 이다.

HNSW의 탐색방식

Greedy + Best-First 와 그외에 여러가지 알고리즘이 혼합된 방식을 사용한다.

휴리스틱

“이 노드가 쿼리에 더 가까워 보이는가?”

그리디

“그럼 지금 제일 가까운 노드로 이동하자”

Best-First (보완)

“좋아 보이는 후보 몇 개는 같이 들고 가자”

여기서 휴리스틱 이란 ‘기준’ 이고, 그리디는 ‘사용 방식’ 을 의마한다.

즉, 휴리스틱은 그리디에 포함되어있다고 이해할 수 있는데

이번에 사용한 chroma 에서의 HNSW 이를 거리기반 휴리스틱을 만들어

거리를 ‘기준’ 하여 그리디를 이용한 탐색을 하는데

이렇게만 하면 유사한 값에는 도달하겠지만, 만약 유사하다고 생각되어 들어갔는데

잘못된 경우를 대비한 Best-First 가 도입되어있으며

이를 ef 라고해서 주변을 더 확인할 수 있도록 구축할 수 있다.

따라서 정리하면

HNSW는 벡터 공간에 ‘길’을 만들고 그 길을 따라 빠르게 목적지 근처로 가는 알고리즘이다.

다음으로 알아볼것

왜 랜덤 레벨이 필요한가 (mL)

ef, M 파라미터 감각 잡기

ANN (Approximate Nearest Neighbor) 이란