Faiss为啥这么快?原来是量化器在做怪!2

简介: Faiss为啥这么快?原来是量化器在做怪!

Faiss为啥这么快?原来是量化器在做怪!1:https://developer.aliyun.com/article/1507793

2.乘积量化(Product Quantization)

       PQ是一种用于高维向量压缩和相似性搜索的技术,特别适用于大规模向量数据集的近似最近邻搜索。PQ 技术将高维向量分解为多个子空间,并对每个子空间进行独立的向量量化,从而实现高效的向量压缩和搜索。下面将对量化和检索两个方面进行介绍:

PQ的论文地址:

https://arxiv.org/pdf/2401.08281.pdf

(1)PQ量化

       量化过程有如下3个步骤:

       1. 向量分解:将原始高维向量分解为多个子向量,每个子向量属于一个子空间。

       2. 子空间量化:对每个子空间进行独立的向量量化,将连续的向量空间划分为离散的子空间。

       3. 编码:将原始向量编码为子空间的离散码字,以表示原始向量在每个子空间中的位置。


       下面来看一个例子:

       数据集是一个1000x1024的矩阵,每个向量维度1024:

       向量分解:先将每个1024维的向量平均分成8个128维的子向量,如下图所示:

       子空间量化:然后对这8组子向量分别使用k-means聚成256类。下图中(1)竖着的一列为一组,每组进行聚类,聚类成256个簇,形成8x256的码表(2)。然后将每个128维的原向量转换成簇的中心点,如下图中的(3)

       编码:接下来将每一个格中的128维向量根据(2)量化成一个簇ID(0-256 占8bit),这样原始1024维浮点数(32位)向量便压缩成8个8位整数,即下图(4)中粉色矩阵中的一行。

       在上面的例子中,子向量数量和每个子向量簇的数量是两个超参数,经过实验子向量数量选择8和簇的数量选择256通常是最佳的。

(2)PQ检索

       检索过程非常类似于找回+排序:

       1. 量化查询向量:使用上面的压缩过程将查询向量转换成中心点ID矩阵。

       2.召回:将查询的 PQ 编码与码本中的所有 PQ 编码进行比较,寻找与查询编码最接近的候选向量,比如计算海明距离。

       3.排序:对于每个候选编码,找到对应的原始向量,然后精确计算相似度,进行排序。

       这个流程大致如下:

       上图中M=8,nlist=8

       Faiss中PQ相关的有如下相关算法:

image.png

image.png

代码示例如下:

"""
乘积量化示例
"""
 
import numpy as np
import faiss
import time
 
 
def test_pq():
    # 设定量化器参数
    quantizer = faiss.ProductQuantizer(d, M, nlist)
 
    # 对示例数据进行训练
    quantizer.train(data)
 
    # 进行量化
    codes = quantizer.compute_codes(data)
    print("data0:", data[0])
    print("codes0:", codes[0])
 
 
def test_index():
    # 向索引中添加数据
    t = time.time()
    index.train(data)
    index.add(data)
    cost1 = time.time() - t
 
    # 进行近似最近邻搜索
    k = 50  # 返回最近邻的数量
    t = time.time()
    D, I = index.search(query, k)
    cost2 = time.time() - t
    return D, I, cost1, cost2
 
 
if __name__ == '__main__':
    d = 1024
    M = 8
    nbits = 8
    nlist = 500
    nbits_per_idx = 4
    n = 100000
    np.random.seed(0)
    # 生成一些随机向量作为示例数据
    data = np.random.rand(n, d).astype(np.float32)
    # 定义查询向量
    query = np.random.rand(1, d).astype(np.float32)
 
    # 量化器的示例
    # test_pq()
 
    # 暴力检索的示例
    index = faiss.IndexFlat(d, faiss.METRIC_L2)
    D, I, cost1, cost2 = test_index()
    print("Flat索引 最近邻的距离:", D)
    print("Flat索引 最近邻的索引:", I)
    print("Flat索引 耗时:", cost1, cost2)
 
    # PQ索引的示例
    index = faiss.IndexPQ(d, M, nbits, faiss.METRIC_L2)
    D, I, cost1, cost2 = test_index()
    print("PQ索引 最近邻的距离:", D)
    print("PQ索引 最近邻的索引:", I)
    print("PQ索引 耗时:", cost1, cost2)
 
    # IVF+PQ的示例
    # quantizer = faiss.IndexPQ(d, M, nbits, faiss.METRIC_L2)
    quantizer = faiss.IndexFlat(d, faiss.METRIC_L2)
    index = faiss.IndexIVFPQ(quantizer, d, nlist, M, nbits_per_idx, faiss.METRIC_L2)
    D, I, cost1, cost2 = test_index()
    print("IVF+PQ索引 最近邻的距离:", D)
    print("IVF+PQ索引 最近邻的索引:", I)
    print("IVF+PQ索引 耗时:", cost1, cost2)

3.加法量化

       加法量化(Additive Quantization)的基本思想是将原始向量表示为多个部分的和,每个部分都可以独立进行量化。在加法量化中,每个部分由一个码本表示,最终的量化结果是这些部分码本的加和。


       Faiss中AQ相关的算法有ResidualQuantizer、LocalSearchQuantizer和AdditiveQuantizer,其中AdditiveQuantizer是ResidualQuantizer和LocalSearchQuantizer的父类。

(1)残差量化(Residual Quantizer)

       残差量化,涉及对数据进行多次量化,每次量化(通常使用的是简单的标量量化)都使用相同的量化级别,但重建过程中会考虑前一次量化产生的误差。这种方法的关键在于,通过只处理量化过程产生的误差,可以更有效地压缩数据,同时尽量减少信息损失。


       过程包括以下步骤:

       a.初步量化:对数据进行一次简单的量化(K-means),将其划分到有限数量的级别中。

       b.计算残差:计算初步量化后的数据与原始数据之间的差异,这些差异被称为“残差”。

       c.再次量化:对计算出的残差进行再次量化,这次量化可以更加精确,因为残差通常比原始数据小很多。

       d.迭代过程:b、c两个步骤迭代进行,即对残差的量化结果再次计算残差,并进行量化。


 Faiss中残差量化相关的有如下相关算法:

image.png

image.png    代码示例:

"""
残差量化示例
"""
 
import numpy as np
import faiss
import time
 
 
def test_rq():
    # 设定量化器参数
    quantizer = faiss.ResidualQuantizer(d, M, nbits)
 
    # 对示例数据进行训练
    quantizer.train(data)
 
    # 进行量化
    codes = quantizer.compute_codes(data)
    print("data0:", data[0])
    print('shape:', codes.shape)
    print("codes0:", codes[0])
 
 
def test_index():
    # 向索引中添加数据
    t = time.time()
    index.train(data)
    index.add(data)
    cost1 = time.time() - t
 
    # 进行近似最近邻搜索
    k = 50  # 返回最近邻的数量
    t = time.time()
    D, I = index.search(query, k)
    cost2 = time.time() - t
    return D, I, cost1, cost2
 
 
if __name__ == '__main__':
    d = 1024
    M = 3
    nbits = 8
    nlist = 100
    n = 100000
    np.random.seed(0)
    # 生成一些随机向量作为示例数据
    data = np.random.rand(n, d).astype(np.float32)
    # 定义查询向量
    query = np.random.rand(1, d).astype(np.float32)
 
    # 量化器的示例
    test_rq()
 
    # 暴力检索的示例
    index = faiss.IndexFlat(d, faiss.METRIC_L2)
    D, I, cost1, cost2 = test_index()
    print("Flat索引 最近邻的距离:", D)
    print("Flat索引 最近邻的索引:", I)
    print("Flat索引 耗时:", cost1, cost2)
 
    # SQ索引的示例
    index = faiss.IndexResidualQuantizer(d, M, nbits, faiss.METRIC_L2)
    D, I, cost1, cost2 = test_index()
    print("RQ索引 最近邻的距离:", D)
    print("RQ索引 最近邻的索引:", I)
    print("RQ索引 耗时:", cost1, cost2)
 
    # IVF+SQ的示例
    # quantizer = faiss.IndexResidualQuantizer(d, M, nlist, faiss.METRIC_L2)
    quantizer = faiss.IndexFlat(d, faiss.METRIC_L2)
    index = faiss.IndexIVFResidualQuantizer(quantizer, d, nlist, M, nbits, faiss.METRIC_L2, faiss.ResidualQuantizer.ST_norm_qint8)
    D, I, cost1, cost2 = test_index()
    print("IVF+SQ索引 最近邻的距离:", D)
    print("IVF+SQ索引 最近邻的索引:", I)
    print("IVF+SQ索引 耗时:", cost1, cost2)

(2)局部检索量化(LocalSearchQuantizer)

       局部检索量化,先使用k-means将原始高维向量空间划分为若干个簇,然后将原始的高维向量其映射到最近的簇心,最后再使用量化方法将高维向量转换成一个代表性的低维向量。检索的时候使用局部搜索的方法在这些低维向量上进行最近邻搜索。


       LocalSearchQuantizer是下面两篇论文的实现:


       Revisiting additive quantization Julieta Martinez, et al. ECCV 2016


       LSQ++: Lower running time and higher recall in multi-codebook quantization Julieta Martinez, et al. ECCV 2018        


示例代码如下:

"""
局部检索量化示例
"""
 
import numpy as np
import faiss
import time
 
 
def test_lsq():
    # 设定量化器参数
    quantizer = faiss.LocalSearchQuantizer(d, M, nbits)
 
    # 对示例数据进行训练
    quantizer.train(data)
 
    # 进行量化
    codes = quantizer.compute_codes(data)
    print("data0:", data[0])
    print('shape:', codes.shape)
    print("codes0:", codes[0])
 
 
def test_index():
    # 向索引中添加数据
    t = time.time()
    index.train(data)
    index.add(data)
    cost1 = time.time() - t
 
    # 进行近似最近邻搜索
    k = 50  # 返回最近邻的数量
    t = time.time()
    D, I = index.search(query, k)
    cost2 = time.time() - t
    return D, I, cost1, cost2
 
 
if __name__ == '__main__':
    d = 1024
    M = 3
    nbits = 8
    nlist = 100
    n = 10000
    np.random.seed(0)
    # 生成一些随机向量作为示例数据
    data = np.random.rand(n, d).astype(np.float32)
    # 定义查询向量
    query = np.random.rand(1, d).astype(np.float32)
 
    # 量化器的示例
    test_lsq()
 
    # 暴力检索的示例
    index = faiss.IndexFlat(d, faiss.METRIC_L2)
    D, I, cost1, cost2 = test_index()
    print("Flat索引 最近邻的距离:", D)
    print("Flat索引 最近邻的索引:", I)
    print("Flat索引 耗时:", cost1, cost2)
 
    # LSQ索引的示例
    index = faiss.IndexLocalSearchQuantizer(d, M, nbits, faiss.METRIC_L2)
    D, I, cost1, cost2 = test_index()
    print("LSQ索引 最近邻的距离:", D)
    print("LSQ索引 最近邻的索引:", I)
    print("LSQ索引 耗时:", cost1, cost2)
 
    # IVF+LSQ的示例
    quantizer = faiss.IndexFlat(d, faiss.METRIC_L2)
    index = faiss.IndexIVFLocalSearchQuantizer(quantizer, d, nlist, M, nbits, faiss.METRIC_L2, faiss.ResidualQuantizer.ST_norm_qint8)
    D, I, cost1, cost2 = test_index()
    print("IVF+LSQ索引 最近邻的距离:", D)
    print("IVF+LSQ索引 最近邻的索引:", I)
    print("IVF+LSQ索引 耗时:", cost1, cost2)

       (3)加法量化(Additive Quantizer)

       Faiss中的AdditiveQuantizer是将残差量化或者局部量化的结果加起来作为向量的量化结果,不过用的不是很多,就不介绍了。

       Faiss中还有一些量化器,是上面这些量化器的排列组合,看名字就知道功能,使用频率也不是很高:

类名 描述
faiss.AdditiveQuantizer 加法量化
faiss.AdditiveQuantizerFastScan 使用了FastScan的加法量化
faiss.ProductLocalSearchQuantizer 乘积量化+局部检索量化
faiss.ProductResidualQuantizer 乘积量化+残差量化

faiss.ProductResidualQuantizerFastScan使用了FastScan的乘积量化+残差量化faiss.ProductLocalSearchQuantizerFastScan使用了FastScan的乘积量化+局部检索量化

      最后一句话总结,如果向量维度不是很大(1024以内),数据量也不是很多(100w以内),内存允许的情况下可以使用Flat暴力搜索,效率其实可以接受;如果维度和数据量都很大,还是老老实实用量化吧,比如IndexIVFPQ还是很香的。


       Faiss中的量化器就介绍到这里,欢迎点赞、收藏,关注不迷路(*^__^*)  

目录
打赏
0
1
1
0
20
分享
相关文章
Faiss为啥这么快?原来是量化器在做怪!1
Faiss为啥这么快?原来是量化器在做怪!
478 0
白话Elasticsearch24- 深度探秘搜索技术之TF&IDF算法/向量空间模型算法/lucene的相关度分数算法
白话Elasticsearch24- 深度探秘搜索技术之TF&IDF算法/向量空间模型算法/lucene的相关度分数算法
106 0
彻底反转:号称「碾压」LLaMA的Falcon实测得分仅49.08,HuggingFace决定重写排行榜代码
彻底反转:号称「碾压」LLaMA的Falcon实测得分仅49.08,HuggingFace决定重写排行榜代码
212 0
彻底反转:号称「碾压」LLaMA的Falcon实测得分仅49.08,HuggingFace决定重写排行榜代码
【Pytorch神经网络理论篇】 10 优化器模块+退化学习率
反向传播的意义在于告诉模型我们需要将权重修改到什么数值可以得到最优解,在开始探索合适权重的过程中,正向传播所生成的结果与实际标签的目标值存在误差,反向传播通过这个误差传递给权重,要求权重进行适当的调整来达到一个合适的输出,最终使得正向传播所预测的结果与标签的目标值的误差达到最小,以上即为反向传播的核心思想
188 0
用神经架构搜索给LLM瘦身,模型变小,准确度有时反而更高
【6月更文挑战第20天】研究人员运用神经架构搜索(NAS)压缩LLM,如LLaMA2-7B,找到小而精准的子网,降低内存与计算成本,保持甚至提升性能。实验显示在多个任务上,模型大小减半,速度加快,精度不变或提升。NAS虽需大量计算资源,但结合量化技术,能有效优化大型语言模型。[论文链接](https://arxiv.org/pdf/2405.18377)**
89 3
推荐系统[二]:召回算法超详细讲解[召回模型演化过程、召回模型主流常见算法(DeepMF_TDM_Airbnb Embedding_Item2vec等)、召回路径简介、多路召回融合]
推荐系统[二]:召回算法超详细讲解[召回模型演化过程、召回模型主流常见算法(DeepMF_TDM_Airbnb Embedding_Item2vec等)、召回路径简介、多路召回融合]
推荐系统[二]:召回算法超详细讲解[召回模型演化过程、召回模型主流常见算法(DeepMF_TDM_Airbnb Embedding_Item2vec等)、召回路径简介、多路召回融合]
向量检索/向量相似性计算方法(持续更新ing...)
本文介绍各种用于向量检索的向量相似性计算方法,将会简单介绍各种方法的优缺点等信息,并用toy example给出代码示例。
向量检索/向量相似性计算方法(持续更新ing...)
当随机采样遇见插值,微软亚研提出节省推理计算量的新范式
同一张图像的不同区域空间冗余度是不一样的,背景部分的冗余度往往低于人物区域。如何利用这种特性来节省模型推理的计算量呢?在一篇 ECCV 2020 Oral 论文中,来自微软亚洲研究院等机构的研究者提出了一种随机采样与插值相结合的新方法,可以有效降低节省推理的计算量。
251 0
当随机采样遇见插值,微软亚研提出节省推理计算量的新范式

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等