Gemeni 가 1M 토큰 컨텍스트를 들고 나왔지만 잘 정리된 논문 같아서 읽어보았습니다. Pinecone의 research scientist 가 작성한 논문 Foundations of Vector Retrieval 입니다.

아래는 공부하면서 정리한 노트입니다.

35/203

Inner product은 데이터 전처리를 해주면 cosine similarity, Euclidean distance 와 같아져 그 둘의 일반화이다. 단 거리로서의 기준인 non negativity, coincidence (자기 자신이 자기 자신과 유사도가 가장 높은 벡터이다), triangular inequality 는 만족하지 않음. 다만 높은 확률로 실제 데이터에선 coincidence 가 성립함.

40/203

차원 d 가 커지면
– 임의의 데이터 x와 쿼리 q간의 거리가 모두 다 비슷해진다.
– Inner product의 경우 조건을 제한해주면 <x, q>=0 이 되버린다.

(무한하게 큰 벡터 2개을 생각해보면 직관적으로 위와 같은 결과를 예상할 수 있다.)

따라서 고차원에서 kNN의 approximation 이란건 가망없다. 모든 데이터를 다 뒤지는 것만큼 느리다.

반면 데이터가 cluster 되어있고 q 가 임의 cluster 에 속한다면 k nearest cluster 는 동작함. 하지만 클러스터 안에서 가까운 kNN은 다시 앞의 문제에 다시 빠짐.

47/203

Branch and bound algorithm들.

Binary search tree 만들듯이 레벨마다 특정 dim을 정하고 axis에 평행하게 median 을 기준으로 나눈다: k-d tree. query q 가 속한 leaf 가 아닌 옆 노드에 nearest neighbor가 있을 수 있어 옆 노드까지 보다보면 high dim 에서 결국 전체 데이터를 다 보는 상황이 될 수 있다.

임의 방향으로 적당히 반정도 되게 나눈다: randomized trees. intrinsic dim에 따라 (우연히) 나눌 가능성이 높아진다. 옆 노드를 뒤지지 않으면 오류는 있지만 이런 트리를 여러개 쓰면 된다. 여기서부터는 inner product 을 dist 로 사용 가능

parition 하지말고 적당히 겹치게 나눈다: spill tree. 그럼 옆 노드 말고 내 노드에 nn 이 있을 가능성이 높아진다.

k-d tree, random tree, spill tree는 hyperplane 으로 데이터를 나눈다. 거리를 기준으로 데이터를 찾는거면 공간을 sphere 로 나눠야하지 않을까? 레벨 l은 특정 데이터를 중심으로 한 반지름 2^l 의 구. child로 가면서 반지름을 절반씩 줄이고 구의 중심은 특정 데이터. 이것이 cover tree.

91/204

LSH.

거리를 점차 늘려가면서 그 거리안에 들어오는 데이터가 있는지 보는 것으로 kNN 을 구한다.

질의 q의 NN이 u* 라 할때 d(q, v) <= d(q, u*) * (1+ε)인 v 를 구하는걸 ε approximation 이라 칭한다. 그런데 LSH family 는 거리 r이 사전에 주어져야한다. 최소거리 r을 사전에 알 방법은 없으니까 r을 키워가면서 그 안에 들어오는 data가 있나 없나를 찾는 decision problem 으로 바꿔 kNN을 한다. 이렇게 할때 subpolynomial time에 답이 나온다.

122/204

Graph algorithm.

Graph 위 점들을 edge를 따라 navigate 하되 greedy search 를 해서 답을 찾겠단 아이디어. 이런 성질을 만족하는 Delaunay graph는 voronoi region 의 vertex를 연결하는 그래프로 만들 수 있다.

일단 그래프만 만들어지면 그래프의 아무데서나 출발해 neighbor가 현재 노드보다 질의 q에 가깝다면 해당 노드를 탐색. 그렇지 않다면 stop하는 방식으로 정확히 kNN을 할 수 있다.

그러나 고차원의 대량 데이터의 경우 이런 그래프를 만드는데  오래걸리고 (O(|X|^3) 도 나온다), 고차원에서는 모든 점이 거의 같은 거리에 있다는 차원 저주에 시달리기 때문에 결국엔 이 그래프를 어떻게든 approximate 해보고, 탐색의 속도를 높이기 위해 edge를 더 많이 추가하는게 이 장의 주 내용이다.

한가지 예로 Relative Neighborhood Graph는 모든 u, v pair를 보면서 서로가 서로에게 nearest neighbor 이면 edge를 추가하는 방식. 이 그래프는 Delaunay graph의 subgraph이지만 당연하게도 Delaunay 처럼 greedy로 탐색 할 때 exact answer는 나오지 않는다.

Pinecone은 이러한 그래프 알고리즘 중 하나인 Hierarchical Navigable Small Worlds (HNSW)를 제공한다. Pinecone 의 그래프는 지속적으로 업데이트 가능해야하고, 클라우드에서 서빙해야하는 등의 조건이 있어 practical solution 을 찾아야 한다. 따라서 반드시 이론적으로 최선이거나 벤치마크에서 가장 빠른 알고리즘을 선택하진 않는다.

129/204

Clustering.

데이터를 k means 등으로 클러스터링 뒤, 질의 q와 centroid 가 가까운 m 개의 클러스터를 선택하고 각 클러스터 내 데이터 모두와 거리 비교하면서 kNN. 클러스터링 방식이나, 몇개의 클러스터와 비교해야하는지 등은 연구가 안됨.

143/204

Sampling.

Inner Product은 데이터 transformation 을 통해서 Consine이나 Euclidean distance 문제로 변환할 수 있다. 변환후에는 상대적으로 쉬운 그들 문제를 풀면 되고.

반면 Inner Product이 가지는 특징을 사용해 데이터를 주어진 쿼리와 inner product이 높을 확률에 따라 샘플링 한 뒤, 샘플링이 자주된 k’ 개 데이터와 inner product을 계산하여 k개의 NN을 찾는게 sampling 의 주 아이디어.

Inner product을 계산하진 않으면서도 inner product 이 높을 확률을 구하기 위한 모델 설정이 매우 흥미롭다.

이 뒤는 compression 인데 해당 부분은 읽어보지 않았습니다.