ANNS 算法
本文最后更新于 506 天前,其中的信息可能已经有所发展或是发生改变。

项目需要,先开个坑,啥时候填完也不知道

Product Quantization

PQ(Product Quantization)是一种压缩技术,由 Herve Jegou 等学者在 PAMI2011 上发表了该算法的第一篇正式论文,用于解决相似搜索问题(Similarity Search)。其核心思想是将空间分解为若干个低维子空间的笛卡尔乘积(Cartesian product ),并对每一个子空间进行量化(Quantization),基本原理可以用下图展示。

假设原始数据集的大小为 n,向量维度为 D,数据首先会被切分D/mm 维的子向量。对每一组子向量,可以使用 K-means 聚类得到 K 个聚类中心,这些中心点被称为码本(Codebook)

对于每个样本向量,可以利用码本找到距离其每个子向量最近的中心点,从而使用中心点 ID 来表示子向量,完成样本的编码。假设聚类了 K 个中心点,则需要用到 n_k 位来记录中心点 ID,那么原始向量只需要使用 m * n_k 位来表示,从而大大降低了存储开销。

基于 PQ 的相似搜索有两种方法:一种是 SDC(Symmetric Distance Computation),即将查询向量进行量化,再与量化后的样本数据进行距离度量;另一种是 ADC(Asymmetric Distance Computation),直接使用原始向量和量化后的样本进行距离度量。上图展示了这两种方式,其中 xy 分别表示查询向量和样本向量,q(x)q(y) 表示使用码本量化后的向量。

对于 ADC 算法,距离的期望误差上界只与量化误差有关,与输入的 x 无关。而对于 SDC 算法,距离的期望误差上界是 ADC 的两倍,因此通常更倾向于使用 ADC 算法。

Inverted Multi-Index

2014年发表在TPAMI上的论文 The Inverted Multi-Index 提出了一种基于倒排索引的改进聚类算法Inverted Multi-Index(IMI)索引。在同等条件下,IMI 相比传统的 Inverted File(IVF)索引具有更高的性能表现和更好的召回率,并且内存空间占用更小。

传统的倒排索引虽然可以有效地过滤大量数据点,然而在海量数据(十亿级别)的情况下,IVF 对数据空间的划分仍然不够均衡,查询会返回一个相当大的列表,并且这个列表中的数据是相当稀疏、倾斜的(也就是返回的数据仍然不够聚集),而提高码本的大小又会降低查询的性能。

如上图所示,左图是使用倒排索引进行聚类时的查询结果,其中蓝色和红色点分别代表两次查询获得的列表。可以看到 IVF 返回的数据相当分散,尤其是当查询点落在接近聚类边缘的时候,会漏掉很多近邻数据(在使用 IVF 时通常会查询多个列表来缓解这个问题),这种情况在高维数据上更为频繁)。而右图是 IMI 算法得到的查询结果,可以看到红点和蓝点更加聚集,返回的数据更能满足实际应用需求。

受到PQ算法的启发,IMI 同样将 M 维数据空间划分为 k 个子空间,并在每个子空间内通过 K-means 算法学习得到一个大小为 l 的码本 {w_1, w_2, \dots, w_l}。生成聚类中心后,需要将每个部分的聚类中心拼接以后才能完全代表数据集中的数据,因此总共存在 l^k 个列表。为避免过多的列表,通常会选择 k=2

对于每条原始数据,将其分为 k 个子向量,并通过之前学习得到的码本找到每个子向量对应的最近聚类中心 i,拼接这些聚类中心后,就能得到对应的列表 {i_1, i_2, \dots, i_k} 。整个向量的距离计算方式为每个子向量距离的和。

IMI 的搜索过程也很简单。如上图所示,将查询向量同样分为 k 段,对每段向量使用 ADC 算法,计算并选取其中 T 个相似度最高的中心,图中选择了 T=6。将每个子向量获得中心列表进行拼接,得到 T^l 个子列表,最后在这些子列表中找到距离查询向量最近的 top T 个结果。该过程的时间复杂度为 O(T)。更详细的搜索流程请参考原论文。

上面描述的查询流程中,距离的计算使用的是 ADC,对应的算法成为 Multi-ADC。为了提高精度,论文中还提出了一种优化:将每个向量本身和聚类中心之间的残差向量再通过 Multi-ADC 编码进行保存,称为 Multi-D-ADC。Multi-D-ADC 比 Multi-ADC 有更高的召回率,Multi-ADC 则比 Multi-D-ADC 的计算速度更快,具体使用哪种方式需要根据场景权衡。

IVF-HNSW

这篇发表于 2018 年 ECCV 会议上的论文 Revisiting the inverted indices for billion-scale approximate nearest neighbors 分析了在大规模数据上,倒排索引相对于 Inverted Multi-Index(IMI)的优势,并通过使用 HNSW 算法缓解其不足,从而实现了更优秀的近似最近邻搜索算法。

虽然 Inverted Multi-Index 在精度上更为优秀,但其存在的问题是:因为不同子空间之间可能高度相关,划分得到的很多子区域中都没有数据点,这会导致有效区域数量较少,使搜索花费大量时间在空区域中。虽然 IMI 能够获得更精确的候选列表,并且在 K 较小时查询效率高,但随着 K 的增加,IMI 存在大量随机内存访问,同时内存消耗急剧增加,而倒排索引对数据量的扩展性更好。因此,在大数据量的场合下,倒排索引具有更大的潜力。基于此,作者提出了对 IVF 的优化算法——IVF-HNSW。

IVF 使用聚类的方法将数据划分成多个区域(region),而 IVF-HNSW 在此基础上进一步将每个区域划分为多个子区域(subregion)。与第一次划分不同的是,为了避免过高的内存需求,IVF-HNSW 提出了一种不依赖于 K-means 的子区域划分算法,称为"grouping"。

grouping 对于每个区域都是独立进行的,假设某区域聚类得到的中心为 c,对应的数据为 {x_1, x_2, \dots, x_n},记 s_1, \dots, s_L \in Cc 最邻近的 L 个中心。

我们令区域的子中心为 {c+\alpha (s_l -c)}, l=1,\dots,L,其中 \alpha 的取值放在后面描述。对于每个 x_i,可以获得距离最近的子中心:

$$
l_i = argmin || x_i - (c + \alpha(s_l - c)) ||^2
$$

之后就可以按照 IVF-ADC 的思路,对 x_i − (c + \alpha(s_li − c)) 进行量化,使用了子中心后,偏移量相对于 IVF-ADC 会小不少,因此压缩效果也会更好。

上图中,绿色点就是聚类获得的中心,而红色点就是每个聚类计算得到的子中心,这里取 L=5

对于任意的查询 q,其和每个子区域的中心距离 \left\Vert q - c - \alpha(s_l - c) \right\Vert ^ 2 可以通过一些预计算快速得到(怎么快速计算的就不展开了,主要是这破wp写latex太好用了)。如果总共需要访问 k 个区域,那么其中包含了 kL 个子区域,通过测试发现,即使通过距离过滤掉一半的子区域,准确率也不会下降特别严重。因此设置了一个参数 \tau,指定访问子区域的比例,如上图右中,\tau = 0.4

剩下的问题就在于如何确定 \alpha 的取值,对于每个区域来说,我们希望通过求解如下问题来获得最优的 \alpha 参数:

也就是希望使每一个数据点和最近子中心的距离都尽可能小,这个问题的求解相对复杂,这里给出了一种近似求解方式:

首先对每个数据点 x_i 通过如下最优化问题计算最优的子中心 s_i

对于每个子问题,可以对 l_i 进行枚举:对于每个固定的 l_i 都可以计算出最优的 \alpha 值,待回原式就能得到每个 x_i 对应的 l_i。最后,将计算出的所有 s_i 值待会原式,求解得到 \alpha

那么问题来了,HNSW 在哪?由于这里考虑的是 billion 级的数据量,因此 IVF 聚类的中心数量也会相当多,为了提高码本的搜索速度,使用了 HNSW 来对所有中心构建索引,能够在几乎不降低准确率的情况下大大提高查询效率。

HNSW

DiskANN

https://suhasjs.github.io/files/diskann_neurips19.pdf

SPANN

https://arxiv.org/abs/2111.08566

FreshDiskANN

HNSW-FINGER

https://assets.amazon.science/74/56/d9c1550a4afab9020fb063336769/finger-fast-inference-for-graph-based-approximate-nearest-neighbor-search.pdf

参考

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇