向量相似性搜索是从特定嵌入空间中的给定向量列表中找到相似的向量。它能有效地从大型数据集中检索相关信息,在各个领域和应用中发挥着至关重要的作用。
向量相似性搜索需要大量的内存资源来实现高效搜索,特别是在处理密集的向量数据集时。而压缩的主要作用是压缩高维向量来优化内存存储。
IVFPQ 是一种用于数据检索的索引方法,它结合了倒排索引(Inverted File)和乘积量化(Product Quantization)的技术。这个方法通常应用在大规模数据检索任务中,特别是在处理非常大的数据数据库时表现出色。
IVFPQ 中包含了两个关键概念:
倒排索引是搜索引擎中用到的非常多的技术,我们这里就不详细介绍了,这里主要介绍下Product Quantization
首先说一下量化,量化是一种用于降维而不丢失重要信息的过程。
乘积量化是如何工作的?它可分为以下几个步骤:
1、将一个大的、高维的向量分成大小相等的块,创建子向量。
2、为每个子向量确定最近的质心,将其称为再现或重建值。
3、用代表相应质心的唯一id替换这些再现值。
让我们看看它在实现中是如何工作的,我们将创建一个大小为12的随机数组,并保持块大小为3。
import random
#consider this as a high dimensional vector
vec = v = [random.randint(1,20)) for i in range(12)]
chunk_count = 4
vector_size = len(vec)
# vector_size must be divisable by chunk_size
assert vector_size % chunk_count == 0
# length of each subvector will be vector_size/ chunk_count
subvector_size = int(vector_size / chunk_count)
# subvectors
sub_vectors = [vec[row: row+subvector_size] for row in range(0, vector_size, subvector_size)]
sub_vectors
输入类似如下的结果
[[13, 3, 2], [5, 13, 5], [17, 8, 5], [3, 12, 9]]
4、这些子向量被指定的称为再现值的质心向量取代,因为它有助于识别每个子向量。然后用一个唯一的ID来代替这个质心向量。
k = 2**5
assert k % chunk_count == 0
k_ = int(k/chunk_count)
from random import randint
# reproduction values
c = []
for j in range(chunk_count):
# each j represents a subvector position
c_j = []
for i in range(k_):
# each i represents a cluster/reproduction value position
c_ji = [randint(0, 9) for _ in range(subvector_size)]
c_j.append(c_ji) # add cluster centroid to subspace list
# add subspace list of centroids
c.append(c_j)
#helper function to calculate euclidean distance
def euclidean(v, u):
distance = sum((x - y) ** 2 for x, y in zip(v, u)) ** .5
return distance
#helper function to create unique ids
def nearest(c_j, chunk_j):
distance = 9e9
for i in range(k_):
new_dist = euclidean(c_j[i], chunk_j)
if new_dist < distance:
nearest_idx = i
distance = new_dist
return nearest_idx
我们演示如何使用辅助函数来获得唯一的质心id
ids = []
# unique centroid IDs for each subvector
for j in range(chunk_count):
i = nearest(c[j], sub_vectors[j])
ids.append(i)
print(ids)
输出如下:
[5, 6, 7, 7]
总结来说就是:当PQ处理一个向量时,会把它分成子向量。然后对这些子向量进行处理,并将其链接到各自子簇内最接近的质心(也称为再现值)。
并且没有使用质心来保存量化向量,而是用一个唯一的质心ID来代替它。每个质心都有其特定的ID,这样在后面可以将这些ID值映射回完整的质心。
下面就是使用质心id重建的矢量
quantized = []
for j in range(chunk_count):
c_ji = c[j][ids[j]]
quantized.extend(c_ji)
print(quantized)
#[9, 9, 2, 5, 7, 6, 8, 3, 5, 2, 9, 4]
我们将一个12维向量浓缩成一个由id表示的4维向量(为了简单起见,这里选择了较小的维度,这可能会使该技术的优势不那么明显)
如果你仔细观察的话,可以看到重建的向量与原始向量不相同。这种差异是由于所有压缩算法在压缩和重构过程中固有的损失造成的,也就是量化的损失这是不可避免的。
可以看到 IVFPQ 在原始特征空间中使用乘积量化来量化特征向量,并在量化后的空间中建立倒排索引。这样一来,检索时可以在量化后的空间中快速定位相似的数据,然后再在原始特征空间中进行更准确的匹配。
IVFPQ的搜索流程结合了乘积量化和倒排索引的优势,通过在低维度的码本上建立倒排索引,既提高了搜索效率,又在倒排列表剪枝和精确匹配阶段进行了优化,以实现在大规模数据数据库中的快速数据检索。这种方法在保持搜索效率的同时,能够提供较高的检索准确性。
我们可以尝试将 IVFPQ 技术应用于检索增强生成(RAG)的文本生成流程中:
本文分享自 DeepHub IMBA 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!