faiss(2):理解product quantization算法

2023-12-02 11:08

本文主要是介绍faiss(2):理解product quantization算法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

近几年,深度学习技术被广泛用于图像识别、语音识别、自然语言处理等领域,能够把每个实体(图像、语音、文本)转换为对应的embedding向量。如这里千人千面智能淘宝店铺背后的算法研究登陆人工智能顶级会议AAAI 2017。而对于推荐、搜索或者广告投放问题,都可以描述为从大规模候选中给用户提供有限的展现结果。那么,这里就会涉及到向量检索的问题。

向量检索最简单的想法是暴力穷举法,如果全部实体的个数是n,n是千万量级甚至是上亿的规模,检索实体对应的向量是D,那么当要从这个实体集合中寻找某个实体的相似实体,暴力穷举的计算复杂度是O(n×D),这是一个非常大的计算量,该方法显然不可取。所以对大数据量下高维度数据的相似搜索场景,我们就需要一些高效的相似搜索技术,而PQ就是其中一类方法。

1. Product Quantization算法原理

假设有50,000张图片组成的图片集,使用 CNN 提取特征后,每张图片可以由1024维的特征表示。那么整个图片集由50000*1024的向量来表示。然后我们把1024维的向量平均分成m=8个子向量,每组子向量128维。如下图:

对于这8组子向量的,使用 kmeans 方法聚成k=256类。也就是说,每个子向量有256个中心点(centroids)。如下图:

在product quantization方法中,这256个中心点构成一个码本。这些码本的笛卡尔积就是原始D维向量对应的码本。用qj表示第j组子向量,用[Cj表示其对应学习到的聚类中心码本,那么原始D维向量对应的码本就是C=C1×C2×…×Cm,码本大小为km。 注意到每组子向量有其256个中心点,我们可以用中心点的 ID 来表示每组子向量中的每个向量。中心点的 ID只需要 8位来保存即可。这样,初始一个由32位浮点数组成的1,024维向量,可以转化为8个8位整数组成。

2. 最近邻搜索

对向量压缩后,有2种方法作相似搜索。一种是SDC(symmetric distance computation),另一种是ADC(asymmetric distance computation)。SDC算法和ADC算法的区别在于是否要对查询向量x做量化。如下图所示,x是查询向量(query vector),y是数据集中的某个向量,目标是要在数据集中找到x的相似向量。

公式1:

SDC算法:先用PQ量化器对x和y表示为对应的中心点q(x)和q(y),然后用公式1来近似d(x,y)。这里 q 表示 PQ量化过程。

公式2:

ADC算法:只对y表示为对应的中心点q(y),然后用下述公式2来近似d(x,y)。

3. python示例

  • 对初始向量按列平均分成 m 组,以每组作 kmeans 聚类:
vecs_sub = vecs[:, m * self.Ds : (m+1) * self.Ds]
self.codewords[m], _ = kmeans2(vecs_sub, self.Ks, iter=iter, minit='points')
  • 计算各分组子向量的每个向量的聚类的 ID 号。完成向量量化:

codes[:, m], _ = vq(vecs_sub, self.codewords[m])
  • 对于查询向量q,将q按列也分成 m 组后,计算与聚类中心的距离:
for m in range(self.M):query_sub = query[m * self.Ds : (m+1) * self.Ds]dtable[m, :] = np.linalg.norm(self.codewords[m] - query_sub, axis=1) ** 2
  • 按组将其与聚类中心的距离求和后,取其距离之和最小值所对应的聚类中心。聚类中心所对应的初始向量,即最近邻向量。
dists = np.sum(self.dtable[range(M), codes], axis=1)

4. 优化的PQ方法Optimized product quantization(OPQ)

Product Quantization的本质是将原始高维空间分解为有限数量的低维子空间的笛卡尔积,然后分别量化。OPQ 试图寻找一个正交矩阵,将原始矩阵旋转后再行分解,以使量化后的向量重建后,其误差最小。

原始的PQ:

改进的迭代式的ITQ:

优化的OPQ:

具体的解决方案,如何coupled R和 Ci:

方案1:

方案2(MSRA):

这里作者提供了一个非常具有说服力的实验:

 

这篇关于faiss(2):理解product quantization算法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/445104

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

深入理解Apache Airflow 调度器(最新推荐)

《深入理解ApacheAirflow调度器(最新推荐)》ApacheAirflow调度器是数据管道管理系统的关键组件,负责编排dag中任务的执行,通过理解调度器的角色和工作方式,正确配置调度器,并... 目录什么是Airflow 调度器?Airflow 调度器工作机制配置Airflow调度器调优及优化建议最

一文带你理解Python中import机制与importlib的妙用

《一文带你理解Python中import机制与importlib的妙用》在Python编程的世界里,import语句是开发者最常用的工具之一,它就像一把钥匙,打开了通往各种功能和库的大门,下面就跟随小... 目录一、python import机制概述1.1 import语句的基本用法1.2 模块缓存机制1.

深入理解C语言的void*

《深入理解C语言的void*》本文主要介绍了C语言的void*,包括它的任意性、编译器对void*的类型检查以及需要显式类型转换的规则,具有一定的参考价值,感兴趣的可以了解一下... 目录一、void* 的类型任意性二、编译器对 void* 的类型检查三、需要显式类型转换占用的字节四、总结一、void* 的

深入理解Redis大key的危害及解决方案

《深入理解Redis大key的危害及解决方案》本文主要介绍了深入理解Redis大key的危害及解决方案,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着... 目录一、背景二、什么是大key三、大key评价标准四、大key 产生的原因与场景五、大key影响与危

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1