深入解析RaBitQ向量压缩算法：原理、流程与应用实践

RaBitQ（Random Binary Quantization with Theoretical Error Bound）是一种用于高维向量压缩的先进算法，旨在实现高压缩率的同时，确保近似最近邻搜索 (ANN) 的准确性和理论可控的误差。它属于二值量化方法的范畴。

核心思想

RaBitQ 的核心思想围绕三个关键点展开：

1. 随机投影与二值化：
   首先，算法对原始高维向量 v 执行随机线性投影 Wv，将其映射到一个较低维度的空间。投影矩阵 W 的元素通常从标准正态分布中采样。接着，通过符号函数 sign 将投影结果转换为二进制码（+1 或 -1）。

2. 理论误差界限：
   传统二值量化方法缺乏理论误差保证。RaBitQ 的创新在于利用随机投影的性质和特定的无偏距离估计器，为量化后距离与原始距离之间的误差提供了理论界限，从而能更好地控制精度损失。

3. 无偏估计器：
   为了基于压缩后的二进制码可靠地估计原始向量间的距离（如内积或欧氏距离），RaBitQ 引入了一个无偏估计器。它能够有效利用二值码信息进行近似计算，并最小化重构误差。

压缩后向量距离计算流程

在 RaBitQ 中，向量被压缩为二进制码 b。对于查询向量 q 和数据库向量 v，我们通过它们的二进制码 b_q 和 b_v 来计算近似距离。

1. 计算二值码之间的距离：
   由于是二值码，距离计算可以被极大加速，通常使用汉明距离或基于汉明距离的内积估计。

   • 汉明距离：统计两个二进制码中不同位的数量，可通过高效的位运算（如 XOR 后计算 popcount）完成。
   • 内积估计：RaBitQ 更关注通过二值码估计原始向量的内积。两个二值码的点积（相关性）与汉明距离有直接关系：相关性 = (码长 - 汉明距离) / 码长。

2. 使用无偏估计器估计原始距离：
   RaBitQ 使用二值码的相关性，通过一个非线性变换（例如 f(x) = sin(πx/2) 或其他函数）来校正二值化带来的偏差，从而无偏地估计原始内积 s = <q, v>。
   这个过程可以概括为：s_est = 无偏估计器( b_q 与 b_v 的相关性 )。这样，算法在牺牲少量精度的前提下，实现了高压缩率下的快速、误差可控的近似计算。

量化后与量化前计算结果的偏差

量化误差指的是近似距离 d_est 与原始距离 d_true 之间的差异。

1. 系统误差：
   RaBitQ 使用的距离估计器是一个无偏估计器。这意味着在多次随机投影的平均意义上，估计值的期望等于真实值，有效消除了系统性偏差。

2. 随机误差：
   对于单次量化，估计值会围绕真实值波动。RaBitQ 为这种随机误差的方差提供了理论界限：Var(d_est) ≤ O(1/m)，其中 m 是码长。这表明，随着码长增加，误差会指数级下降。这个理论保证使得通过选择合适的码长来控制搜索的召回率成为可能。理解这类误差控制机制，对于设计和优化检索系统至关重要，可以参考算法与数据结构相关的理论。

为什么通常不需要归一化？

在许多向量搜索场景中，归一化是常见步骤。但 RaBitQ 通常不需要对输入向量进行显式归一化，原因在于其混合处理策略：

1. 长度信息分离存储：RaBitQ 不直接对长度信息进行高损耗的二值量化，而是将原始向量的长度（范数）作为少量额外数据进行精确或低损耗存储。
2. 距离重构能力：在计算时，算法结合量化得到的内积估计值和单独存储的长度信息，可以重构出原始向量间的各种相似度度量。
   • 例如，余弦相似度估计为：cos_sim_est = s_est / (||q|| * ||v||)，其中 ||q|| 和 ||v|| 是存储的长度。

总结：RaBitQ 对方向信息进行高效的二值量化压缩，而对长度信息进行独立存储。这种策略避免了预归一化可能造成的信息损失，同时保留了精确计算余弦相似度的能力。

精确理解存储与计算策略

可以这样精确理解 RaBitQ 的策略：它不存储完整的原始高维向量，而是存储其压缩表示，包括：

1. 核心压缩数据：量化后的二进制码（用于方向/角度信息）。
2. 辅助校正数据：原始向量的长度标量（用于长度信息）。

在相似度计算时，完全依赖这些存储的压缩表示（二进制码 + 长度标量），通过快速位运算和校正公式得到近似结果，无需访问原始向量。这正是在大规模人工智能应用中实现高效向量检索的关键。只有在构建索引或对少量候选进行最终精确重排时，才可能需要用到原始向量。