필터 가능한 HNSW

필터 가능한 HNSW (Filterable HNSW)

벡터 공간에서 비슷한 객체를 찾아야 할 때가 있죠. 임베딩이나 매칭 NN이 제공하는 그런 공간 말이에요. 이런 경우 Annoy, FAISS, NMSLib 같은 라이브러리들을 고를 수 있고, 어느 공간에서든 빠른 근사 최근접 이웃 검색을 제공해 줘요.

그런데 검색에 제약 조건을 더해야 한다면 어떨까요? 예를 들어 특정 카테고리의 상품만 검색한다거나, 특정 브랜드와 가장 비슷한 고객을 골라야 하는 상황이요. 이 문제에 대한 간단한 해법을 찾지 못했어요. 이런 논의들이 있긴 했는데, 대부분 검색 결과 상위를 돌면서 사후에 조건을 적용하라는 방식뿐이었어요.

출처: 공식문서

한번 생각해 볼게요. ANN 알고리즘 중 하나를 수정해서 검색 자체가 진행되는 동안 제약을 적용하게 만들 수는 없을까.

Annoy는 랜덤 프로젝션 위에 트리 인덱스를 만드는데, 트리 인덱스는 관계형 데이터베이스에서 만나는 그 문제를 그대로 갖고 와요. 필드 인덱스가 독립적으로 구축됐다면 한 번에 하나만 사용할 수밖에 없다는 문제요. 아직 아무도 이 문제를 풀지 못했으니, 쉬운 접근법은 없어 보이네요.

벤치마크에서 최상위 결과를 보여 주는 또 다른 알고리즘이 있어요. Hierarchical Navigable Small World의 줄임말인 HNSW라고 불러요.

원래 논문은 잘 쓰여 있고 읽기도 쉽기 때문에, 여기서는 핵심 아이디어만 설명할게요. 모든 인덱스된 포인트 사이에 탐색 그래프를 만드는 게 목표예요. 그래프 위의 탐욕 검색이 가장 가까운 포인트로 우리를 이끌도록요. 이 그래프는 이전에 추가된 포인트에 고정된 수의 엣지로 연결된 포인트들을 순차적으로 추가하면서 구축돼요. 결과 그래프에서 각 포인트의 엣지 수는 주어진 임계값 $m$을 넘지 않으면서, 항상 고려된 가장 가까운 포인트들을 포함하죠.

어떻게 수정할 수 있을까?

그래프의 노드에 필터 기준을 그냥 적용하고, 탐욕 검색에서 이 기준을 만족하는 노드만 사용하면 어떨까요? 이 단순한 수정만으로도 몇몇 사용 사례를 커버할 수 있다는 게 밝혀졌어요.

그 중 하나는 기준이 벡터 의미론과 상관관계가 없는 경우예요. 예를 들어 옷 이름에 대해 벡터 검색을 하면서 일부 사이즈를 걸러 내고 싶다고 해 보죠. 그 경우 노드들은 클러스터 구조 전체에서 균일하게 걸러지게 돼요. 그래서 퍼콜레이션 이론(Percolation theory)에서 얻은 이론적 결론을 적용할 수 있게 됩니다.

퍼콜레이션은 그래프(네트워크라고도 함)의 견고성과 관련됩니다. $n$개의 노드와 평균 차수 $\langle k\rangle$를 가진 랜덤 그래프가 주어졌다고 해 보죠. 다음으로 노드의 $1-p$ 비율을 무작위로 제거하고 $p$ 비율만 남깁니다. 그러면 임계 퍼콜레이션 값 $ pc = \frac{1}{\langle k\rangle} $ 이 존재하는데, 이 값 아래에서는 네트워크가 조각나고 $pc$ 위에서는 거대 연결 컴포넌트가 존재합니다.

이 주장은 실험으로도 확인됐어요.

검색이 실패하기 시작하는 분명한 임계값이 있어요. 이 임계값은 그래프가 작은 연결 컴포넌트로 분해되기 때문에 나타나요. 그래프는 또한 이 임계값이 알고리즘의 $m$ 파라미터(노드의 차수를 담당)를 늘리면 이동할 수 있다는 것도 보여 줍니다.

검색에 적용하고 싶을 법한 다른 필터 조건들도 생각해 볼게요.

• 카테고리 필터링(Categorical filtering)
  • 특정 카테고리의 포인트만 선택
  • 특정 카테고리 부분집합에 속하는 포인트 선택
  • 특정 라벨 집합을 가진 포인트 선택
• 숫자 범위(Numerical range)
• 특정 지리적 영역 내 선택

첫 번째 경우는, 각 카테고리 안에서 같은 그래프 구축 알고리즘으로 추가 엣지를 만든 다음 원래 그래프에 합치면 HNSW 그래프가 연결됨을 보장할 수 있어요. 이 경우 전체 엣지 수는 카테고리 수와 무관하게 최대 2배까지만 늘어나요.

두 번째 경우는 조금 더 까다로워요. 두 카테고리가 서로 다른 클러스터에 있으면 연결이 끊어질 수 있거든요.

여기서의 아이디어는 같은 탐색 그래프를 노드 사이가 아니라 카테고리 사이에 만드는 거예요. 두 카테고리 사이의 거리는 카테고리 진입점 사이의 거리로 정의할 수 있어요(더 정확하게 하려면 랜덤 샘플 간 평균 거리로). 그러면 예상 그래프 연결성을 노드가 아니라 배제된 카테고리 수로 추정할 수 있어요. 여전히 두 랜덤 카테고리가 연결된다는 보장은 없지만, 연결성 임계값을 넘었다면 각 카테고리에서 여러 번의 검색으로 전환할 수 있게 해 줘요. 어떤 경우에는 병렬 처리를 활용하면 여러 번의 검색이 오히려 더 빨라질 수도 있어요.

세 번째 경우는 고전적인 데이터베이스에서 해결하는 것과 같은 방식으로 풀 수 있어요. 라벨링된 부분집합의 크기 비율에 따라 다음 시나리오 중 하나를 선택합니다.

• 부분집합 중 적어도 하나가 작으면: 가장 작은 부분집합을 포함하는 라벨로 검색을 수행하고 포인트를 사후에 필터링.
• 큰 부분집합들이 큰 교집합을 만들면: 교집합 크기가 연결성 임계값에 맞는다고 기대하며 제약을 가진 일반 검색 수행.
• 큰 부분집합들이 작은 교집합을 만들면: 교집합이 시간 안에 처리될 만큼 작기를 기대하며 선형 검색 수행.

숫자 범위의 경우는, 숫자 범위를 같은 수의 포인트를 담는 버킷들로 나누면 앞선 경우로 환원할 수 있어요. 그다음 인접 버킷들을 연결해 그래프 연결성을 확보합니다. 경계 버킷에 있어 실제 제약을 만족하지 못하는 결과 중 일부는 여전히 필터링해야 하지만, 그 양은 버킷 크기로 조절할 수 있어요.

지리적 경우는 숫자 경우와 아주 비슷해요. 일반적인 지리 검색은 geohash를 사용하는데, 어떤 지리 포인트든 고정 길이 식별자에 매핑해 주죠.

이 식별자들을 카테고리로 사용하고, 추가로 인접한 geohash 사이에 연결을 만들어 주면 돼요. 그러면 선택한 어떤 지리 영역이든 연결된 HNSW 그래프를 포함하게 됩니다.

결론

HNSW 알고리즘을 개선해서 첫 번째 검색 단계에서 포인트 필터링을 지원하도록 만들 수 있어요. 필터링은 카테고리 소속을 기준으로 수행할 수 있고, 이는 다시 숫자 범위와 지리 같은 인기 있는 경우로 일반화됩니다.

실험은 알고리즘의 파이썬 구현을 수정해서 진행했지만, 실제 프로덕션 시스템에는 NMSLib 같은 훨씬 빠른 버전이 필요해요.

더 알아보기 (Learn more)

• HNSW 원본 논문 (arxiv 1603.09320)
• ann-benchmarks — 근사 최근접 이웃 알고리즘 벤치마크
• HNSW 파이썬 구현 (실험에 사용)
• NMSLib — 프로덕션급 고속 ANN 라이브러리
• Percolation theory (위키백과)