量化编码的分层可通航小世界图（HNSW）笔记

Posted on In

引言

两种改进方法

HNSW内存开销大，基于量化编码的检索算法能够压缩数据集向量，大幅度降低内存占用。将量化编码与HNSW结合，有两种改进方法：

  1. 使用标量量化编码向量的HNSWSQ算法
  2. 使用乘积量化编码向量的HNSWPQ算法

HNSW内存开销大的原因

  1. 需要存储全部的数据集元素
  2. 需要存储每一层中节点之间的连接关系

乘积量化

PQ乘积量化

建立码本和量化编码

将N * 128的数据集进行切分，划分为4个子空间，每个子空间中向量的维数为32，得到N * 4 * 32。每个字段（子空间）同样有N个向量，对这N个向量进行聚类得到256个类中心，这样4个字段一共有4 * 256个类中心。每个子空间的所有N个向量都可以用该子空间的256个类中心的某一向量表示，对256个类中心进行编码只需8位即可，从而任一向量在该子空间的子向量的编码就可以用该子向量所属的类中心的编码来表示。

待编码样本如何编码？

对于待编码的样本，将它进行相同的切分，然后在各个子空间里逐一找到距离它们最近的类中心，然后用类中心的id来表示它们，即完成了待编码样本的编码。

码字的搜索算法

对于某个查询向量，要查询离其最近的k个向量，关键就是计算查询向量与dataset中的样本距离了。暴力方法就是计算数据集中所有的样本与查询向量的距离，然后进行排序，选出top@k个最近的样本返回。对数据集进行PQ乘积量化编码后，这个过程就变成下面的方式：

将查询向量进行切分，切分方式与对数据集切分的相同，计算查询向量的每个子向量在相应的子空间中到256个类中心的距离，从而得到4 * 256的距离矩阵。某个样本到查询向量的距离就可以通过以下方式得到（不需单独计算了）：

比如该样本的编码是(124, 56, 132, 222)，在4 * 256的距离矩阵中依次找出（查表）查询向量的相应子向量到编码为124（第一个子空间），编码为56（第二个子空间），编码为132（第三个子空间），编码为222（第四个子空间）的类中心的距离，将这4个距离相加的和作为该样本（编码是(124, 56, 132, 222)）到查询向量的距离。

PQ乘积量化能够加速索引的原理

  • 将全样本的距离计算，转化为到子空间类中心的距离计算（加快查询）
  • 对特征进行编码后，可以用一个相对比较短的编码来表示样本（降低内存消耗）
  • 存储时只需存储类中心的向量值（计算距离时只需要它们 ）

注：暴力搜索的距离计算的次数随样本数目N成线性增长，对于上面的例子，PQ乘积量化只需4 * 256次距离计算。

HNSWPQ算法

与原始的HNSW算法相比，不再需要在内存中保持原始向量。将HNSW算法作为索引算法，采用PQ算法进行向量编码，由于使用PQ算法对原始向量编码，需要将HNSW算法插入过程中与近邻点距离的计算相应地修改为PQ的距离计算。

HNSWPQ的构建过程

  1. 对原始向量量化编码建立码本存储在内存中
  2. 新插入的结点作为查询结点，得到其能达到的最大层（指数衰减概率分布）
  3. 选邻居时，计算某结点与查询向量的距离应为PQ的距离计算

与原HNSW算法相比，主要有两方面的不同：

  • 原HNSW算法直接在原始向量上构建，而HNSWPQ算法需要先对原始向量进行量化编码建立码本在此基础上再逐个插入结点构建（增加了一步）
  • 原HNSW算法计算距离时是直接计算，而HNSWPQ算法采用PQ距离计算方法（计算速度快）

HNSWSQ算法

标量量化（SQ）对向量的每一维都进行量化，HNSWSQ算法采用最大最小量化方法。对于向量的第 $ i $ 维，通过样本集训练获取该维出现的最大值 $ vmax[i] $ 和最小值 $ vmin[i] $ ，然后将向量 $ \vec{a} $ 第 $ i $ 维的值量化为:
$$
\frac{x_i - vmin[i]} {vmax[i]}
$$
其中，$ i = 1, …, n $ ，量化后的值编码存储，假设每一维编码为１个字节，则进一步处理为：
$$
f(x_i) = \lfloor \varphi( \frac{x_i - vmin[i]} {vmax[i]} ) \times 255\rfloor
$$
其中：

$$
\varphi(x) = \begin{cases}
1 & x \geq 1\
x & 0 < x < 1\
0 & x \leq 0
\end{cases}
$$
HNSWSQ算法在插入结点计算距离时，首先将编码后的向量解码还原，然后计算查询向量与解码向量的距离。

量化后性能分析

HNSWPQ算法性能分析

与原始的HNSW算法相比，HNSWPQ算法在同样查询时间下Recall@1准确率要低很多，内存占用几乎只有 HNSW算法的一半（主要是结点连接关系），构建索引耗时是HNSW的几倍，主要是编码引起。

随着PQ子量化器（子空间）的增多，由于量化误差的降低，各算法的Recall@1准确率逐步提高。

HNSWSQ算法性能分析

在GIST-1M数据集上HNSWSQ8的内存开销只有HNSW算法的29.5%，两者性能相当；在SIFT-1M数据集上，两者性能相当，构建索引耗时相当，HNSWSQ8的内存占用比HNSW低45%。

参考文献

[1]李秋珍,白兴强,李立夏,王赢.量化编码的分层可通航小世界图算法[J].计算机工程与科学,2019,41(04):618-625.
[2]Yong Yuan, 图像检索：再叙ANN Search, http://yongyuan.name/blog/ann-search.html, 2019.7.30.

稀罕作者