Vector Quantization(벡터 양자화)

PQ

벡터의 차원을 하위 차원으로 나누어 각각에 대한 벡터 양자화 진행

탐색 공간을 제한하는 기존 방식들과 다르게, 구역마다 포함된 벡터를 Centroid로 뭉개버리는 방식

1. 기존 vector를 n개의 sub-vector로 나눈다.
2. 각 sub-vector 군에 대해 k-means clustering을 통해 centroid를 구한다.
3. 기존의 모든 vector를 n개의 centroid로 압축해서 표현

• 두 vector의 유사도를 구하는 연산이 거의 요구되지 않는다.

  미리 구한 centroid 사이의 유사도를 활용한다.

• PQ와 IVF를 동시에 사용해서 더 빠르고 효율적인 ANN 수행이 가능 (faiss 라이브러리 제공)

장점

• 벡터 표현력의 증가

  벡터 양자화: 중심점의 개수 $k$

  프로덕트 양자화: 중심점의 개수^하위 차원의 개수$k^m$

• 차원의 저주 문제 감소

PQ 최적화 방법

• Optimized PQ
• Locally Optimized PQ
• Online PQ