凡人多烦事01

这个屌丝很懒，什么也没留下！

热门标签

hnws 和ivfpq详解

作者：凡人多烦事01 | 2024-06-10 12:11:10

踩

hnws

向量搜索简介

Ø Faiss : 索引库 - 库

Ø Milvus 服务引擎 – 工程，实现了一些自己的算法。

Ø NSG – 阿里，基于已建好的 knn 模型做优化，减掉一些临近点。

Ø Scann : google ，一枝独秀。

Ø Annoy: 树模型

Ø HNSW: 紧密图

Ø Vearch : 京东服务引擎 – 基于 faiss ，实现了工程化。

注：性能和效果对比：http://ann-benchmarks.com/

Faiss常见概念

Ø 评价指标 ：效果 ( 召回率 ) 、性能、内存占用。

Ø 查询向量 ：用户的查询向量。

Ø 样本向量：用于训练模型的向量样本集合 ( 训练时是根据中心点个数选取部分做训练 ) 。

Ø 中心向量 : 通过样本向量聚类产生，也可以理解为生成的模型 ( 中心向量不一定是在样本向量中，通过求平均得到 ) 。

Ø Flat : 暴力搜索 ( 搜索时，所有向量都参与计算 )

Ø Ip : INNER PRODUCT ( 向量內积 )

Ø IVF : 倒排

Ø PQ : Product Quantizer ( 乘积量化，后面详细介绍 )

Ø 残差 :

Ø 残差向量 ： query 向量和中心点的差，称为残差向量

Ø 残差空间：残差向量构成的空间。

Ø 空间转换 : query 向量减去对应中心点，把 query 向量映射到残差空间。

Ø 残差空间点的分布更秘，误差更小。

HNSW原理

Ø 第 0 层中包含图中 所有节点

Ø 向上节点数依次减少，遵循 指数衰减 概率分布。

Ø 建图时新加入的节点由指数衰减概率函数得出，该点最高 投影到第几 层，从最高的投影层向下的层中该点均 存在该点。

Ø 搜索时从上向下依次查询。

train

Ø 聚类

Ø 先有中心点：随机生成中心点 ( 从样本集中选取， 初始的样本点，会影响模型效果 ，可以多次更换初始中心点，获取做好的聚类效果 ) ，

Ø 更新中心点 ：根据当前中心点，每次取平均，生成新的中心点 ( 优化中心点，有些中心点周围没有值，有些值比较多，把值多的拆分为 2 个 ) 。

Ø Hnsw add 中心点

Ø 建立连接：在 IndexHNSW ::add 函数中完成，实际建连接在 Hnsw_add_vertices 中。

Ø 中心点选择 : 最终选择哪些中心点 add 到 hnws 中建立图索引，还是看哪个中心点聚类的效果更新 ( 标准 : 所有训练向量和对应的中心点的 距离和最小 ) 。

search

Ø 查询 query 向量在 hnsw 中对应的 中心点 。

Ø greedy_update_nearest 从 所有层 中查询距离 query 最近的中心点 。从最高层开始，在每一层查找最邻近的点。根据第0 层最邻近的点，查找 nprobe 个临近点 ( 后面详解 )

Ø search_from_candidates ( 性能好 ): 查询 候选集 对应的临近点，把临近点添加到候选集，再从候选集中选出距离 query 最小的中心点，重复这个过程，如果新的中心点 没有临近点 或者查询的 临近点个数 > efSearch ( 默认值 16) 退出。

Ø search_from_candidate_unbounded ( 效果好 ): 查询过程和 search_from_candidates 相识，只是不再做 efSearch 的判定了 ( 当所有临近点对应的向量没有更相近时推出 ) 。

IVFPQ原理

乘积量化（Product Quantization）

Ø 量化 : 指的就是将一个空间划分为多个区域，然后为每个区域编码标识

Ø 乘积：指的是高维空间由多个低纬空间表示。

Ø 优点：可以用 较少的训练集 ，表示较大的训练集； 内存占用少 。

举例

Ø 假设 1024 维度的向量；分 4 段，每段 256 维，比如 A ， B ， C ， D ，每段 256 维

Ø 如果有 200 个中心点 ( 和维度无关 ) ，则每个子空间都对应 200 个中心点，一共可以表示 200 * 200 * 200 * 200 个中心点。

train

Ø 入口函数 IndexIVFPQ :: train_residual ( idx_t n, const float *x)Ø 参与训练的向量集合，和 中心点个数 有关， 不是全集 ( 每个中心点对应 256 个向量 ) 。Ø How 预先计算距离 ( 后面详解 ) 。

add

Ø 在 一级量化器 中查询对应的中心点。

Ø 把向量转换为 残差向量。

Ø 把残差向量划分为几个 子空间 (PQ) 。

Ø 在每个子空间查找对应的中心点，得到中心点对应的 idx 。

Ø 所有子空间的 idx , 构成向量对应残差空间中心点的编码 (code)

Ø Key : 对应的一级量化器的 idx ， id : 向量的 id ， code : 二级量化器中的 idx 。

search

Ø 查询 一级量化器 对应中心点的 idx 及 distance( 每个向量查询 nprobe 个 ) 。

遍历 query 向量查询到的 nprobe 个中心点对应的倒排链，选出 topK 。

IVFPQ 距离计算详解

Ø 残差 :

Ø query 向量和中心点的差，相减之后把 query 向量映射到残差空间。

Ø why 残差空间点的分布更秘，误差更小。

Ø 距离计算详解

During IVFPQ search with by_residual, we compute

d = || x - y_C - y_R ||^2

x:query向量 y_c:一级量化器中心点，y_r:残差空间的中心点

d = || x - y_C ||^2 + || y_R ||^2 + 2 * (y_C|y_R) - 2 * (x|y_R)

x - y_C: 对应残差， (x - y_C) - y_R 残差距离

注: IndexIVFPQ.cpp中有详细的说明

优化

Ø Faiss 可以 同时查询 N 个 query ，每个 query 都查询 nprobe ？

Ø 是的，每个 query 一级量化器都返回 nprobe 个中心点

Ø Faiss 查询优化问题

Ø IndexIVF 存在几种模式 parallel_mode = 0 或 1 ， max_codes 代表扫描倒排链表时，遍历的最大向量数，只有模式为 1 时才生效。

Ø nprobe 是 Faiss 查询聚类中心的个数，一般值越小，查询效率越高

Ø faiss 内存申请和释放问题

Ø 可以用共享内存的方式，解决建库时全内存，单机建库数据量受限问题

Ø 建库和检索时，内存复用。

Ø 针对 hnsw 优化

Ø 采用 search_bounded_queue 这种模式，只有为 1 ，下面的设置才生效 .

Ø 开启 do_dis_check

Ø 调整 efSearch 的值

Ø 调整建索引时，每个节点的临近点数。

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/凡人多烦事01/article/detail/698697