PQ(product quantization) 算法---(一)

2024-05-12 18:32
文章标签 算法 product quantization pq

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

转自:http://vividfree.github.io/   

1. 引言

Product quantization,国内有人直译为乘积量化,这里的乘积是指笛卡尔积(Cartesian product),意思是指把原来的向量空间分解为若干个低维向量空间的笛卡尔积,并对分解得到的低维向量空间分别做量化(quantization)。这样每个向量就能由多个低维空间的量化code组合表示。为简洁描述起见,下文用PQ作为product quantization的简称。

The idea is to decomposes the space into a Cartesian product of low dimensional subspaces and to quantize each subspace separately. A vector is represented by a short code composed of its subspace quantization indices.

2011年,Herve Jegou等学者在PAMI上发表了PQ方法的第一篇正式paper[1],用于解决相似搜索问题(similarity search)或者也可以说是近邻搜索(nearest neighbor search)问题。其实这几位作者在2009年的INRIA(即法国国家信息与自动化研究所)的技术报告上已经发表PQ方法。这里插一段题外话,[1]的一作Herve Jegou和二作Matthijs Douze均在2015年跳槽去了Facebook AI research,并在今年3月份合作开源了Faiss相似搜索工具[4]。

近几年,深度学习技术被广泛用于图像识别、语音识别、自然语言处理等领域,能够把每个实体(图像、语音、文本)转换为对应的embedding向量。一般来说,相似的实体转换得到的embedding向量也是相似的。对于相似搜索问题,最简单的想法是暴力穷举法,如果全部实体的个数是nn是千万量级甚至是上亿的规模,每个实体对应的向量是D,那么当要从这个实体集合中寻找某个实体的相似实体,暴力穷举的计算复杂度是O(n×D),这是一个非常大的计算量,该方法显然不可取。所以对大数据量下高维度数据的相似搜索场景,我们就需要一些高效的相似搜索技术,而PQ就是其中一类方法。

PQ是一种量化(quantization)方法,本质上是数据的一种压缩表达方法(其实通信学科的一个主要研究工作就是研究信号的压缩表达),所以该方法除了可以用在相似搜索外,还可以用于模型压缩,特别是深度神经网络的模型压缩上。由于相似搜索不仅要考虑如何量化的问题,还要考虑如何检索(search)的问题,而模型压缩可能更主要的是考虑如何量化的问题,不用太关注如何检索这个问题,所以这篇文章会主要站在相似搜索上的应用来介绍PQ方法。至于模型压缩,可以找找近几年研究神经网络模型压缩的paper或者一些互联网公司(比如百度, Snap等)发出的一些资料[3]。

2. 相似搜索的若干种方法

参考文献[5][6]很好的总结了相似搜索的几类方法,这里简要总结几个核心点。可以将方法分为三大类:

  • 基于树的方法
    • KD树是其下的经典算法。一般而言,在空间维度比较低时,KD树的查找性能还是比较高效的;但当空间维度较高时,该方法会退化为暴力枚举,性能较差,这时一般会采用下面的哈希方法或者矢量量化方法。
  • 哈希方法
    • LSH(Locality-Sensitive Hashing)是其下的代表算法。文献[7]是一篇非常好的LSH入门资料。
    • 对于小数据集和中规模的数据集(几个million-几十个million),基于LSH的方法的效果和性能都还不错。这方面有2个开源工具FALCONN和NMSLIB。
  • 矢量量化方法
    • 矢量量化方法,即vector quantization。在矢量量化编码中,关键是码本的建立和码字搜索算法。比如常见的聚类算法,就是一种矢量量化方法。而在相似搜索中,向量量化方法又以PQ方法最为典型。
    • 对于大规模数据集(几百个million以上),基于矢量量化的方法是一个明智的选择,可以用用Faiss开源工具。

3. Product Quantization算法的核心

文献[1]详细介绍了PQ算法的过程和时间复杂度分析,这篇博客的第3节和第4节简要总结下其中的若干要点。

在介绍PQ算法前,先简要介绍vector quantization。在信息论里,quantization是一个被充分研究的概念。Vector quantization定义了一个量化器quantizer,即一个映射函数q,它将一个D维向量x转换码本cookbook中的一个向量,这个码本的大小用k表示。

Quantization is a destructive process which has been extensively studied in information theory. Its purpose is to reduce the cardinality of the representation space, in particular when the input data is real-valued. Formally, a quantizer is a function q mapping a D-dimensional vector xRD to a vector q(x)C=ci;iI, where the index set I is from now on assumed to be finite: I=0,,k1. The reproduction values ci are called centroids. The set of reproduction values C is the codebook of size k.

如果希望量化器达到最优,那么需要量化器满足Lloyd最优化条件。而这个最优量化器,恰巧就能对应到机器学习领域最常用的kmeans聚类算法。需要注意的是kmeans算法的损失函数不是凸函数,受初始点设置的影响,算法可能会收敛到不同的聚类中心点(局部最优解),当然有kmeans++等方法来解决这个问题,对这个问题,这篇文章就不多做描述。一般来说,码本的大小k一般会是2的幂次方,那么就可以用log2k bit对应的向量来表示码本的每个值。

有了vector quantization算法的铺垫,就好理解PQ算法。其实PQ算法可以理解为是对vector quantization做了一次分治,首先把原始的向量空间分解为m个低维向量空间的笛卡尔积,并对分解得到的低维向量空间分别做量化,那如何对低维向量空间做量化呢?恰巧又正是用kmeans算法。所以换句话描述就是,把原始D维向量(比如D=128)分成m组(比如m=4),每组就是D=D/m维的子向量(比如D=D/m=128/4=32),各自用kmeans算法学习到一个码本,然后这些码本的笛卡尔积就是原始D维向量对应的码本。用qj表示第j组子向量,用Cj表示其对应学习到的码本,那么原始D维向量对应的码本就是C=C1×C2××Cm。用k表示子向量的聚类中心点数或者说码本大小,那么原始D维向量对应的聚类中心点数或者说码本大小就是k=(k)m。可以看到m=1或者m=D是PQ算法的2种极端情况,对m=1,PQ算法就回退到vector quantization,对m=D,PQ算法相当于对原始向量的每一维都用kmeans算出码本。

The strength of a product quantizer is to produce a large set of centroids from several small sets of centroids: those associated with the subquantizers. When learning the subquantizers using Lloyd’s algorithm, a limited number of vectors is used, but the codebook is, to some extent, still adapted to the data distribution to represent. The complexity of learning the quantizer is m times the complexity of performing k-means clustering with k centroids of dimension D.

如图1所示,论文作者在一些数据集上调试km,综合考虑向量的编码长度和平方误差,最后得到一个结论或者说默认配置,k=256m=8。像这样一种默认配置,相当于用 m×log2k=8×log2256=64 bits=8 bytes来表示一个原始向量。图2是在这个默认配置下对128维的原始数据用PQ算法的示意图。

 
图1 量化误差与m和k*之间的关系 
 
图2 PQ算法的示意图 

上面介绍了如何建立PQ的量化器,下面将介绍如何基于这些量化器做相似搜索。有2种方法做相似搜索,一种是SDC(symmetric distance computation),另一种是ADC(asymmetric distance computation)。SDC算法和ADC算法的区别在于是否要对查询向量x做量化,参见公式1和公式2。如图3所示,x是查询向量(query vector),y是数据集中的某个向量,目标是要在数据集中找到x的相似向量。

 
图3 SDC和ADC的示意图 

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

d^(x,y)=d(q(x),q(y))=jd(qj(x),qj(y))2(1)

对SDC的2点补充说明:

  1. 为提高计算速度,一般会提前算好d(cj,i,cj,i)2,然后在检索时就是查表,以O(1)的复杂度查出结果。
  2. d^(x,y)d(x,y)的近似计算,一般会先用相似计算方法选出top N近邻,然后再做rerank以拿到最终的近邻排序结果。

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

d˜(x,y)=d(x,q(y))=jd(uj(x),qj(uj(y)))2(2)

对ADC的2点补充说明:

  1. 为提高计算速度,一般会在检索前提前算好d(uj(x),cj,i)2:j=1,,m,i=1,,k,然后在检索时就是查表,以O(1)的复杂度查出结果。
  2. d˜(x,y)也是d(x,y)的近似计算,与SDC类似,一般会先用相似计算方法选出top N近邻,然后再做rerank以拿到最终的近邻排序结果。

图4对比了SDC算法和ADC算法的各阶段复杂度,当n>kD时,计算瓶颈存在于公式1和公式2的计算上,它们的复杂度都是O(n×m)

 
图4 对比SDC和ADC的各阶段计算复杂度 

文献[1]还对SDC和ADC算法做了两点更深入的分析,第一点是对距离的期望误差的上界进行分析。对ADC算法而言,距离的期望误差的上界只与量化误差有关,与输入的x无关,而对SDC算法而言,距离的期望误差的上界是ADC距离的期望误差的上界的两倍,所以作者建议在应用时倾向于用ADC算法。作者做的第二点分析是计算距离的平方的期望,并希望通过矫正拿到距离的无偏估计。作者虽然推导出校准项,但在实验中却发现加上校准项反倒使得距离的残差的方差加大了,所以作者建议在应用时倾向于不加校准项,也就是说还是用公式1或者公式2做计算。

4. Product Quantization算法的改进

第3节介绍了SDC和ADC算法,当n>kD时,计算瓶颈存在于公式1和公式2的计算上,它们的复杂度都是O(n×m)。实际中n可能是千万量级甚至更大,虽然相比暴力搜索算法,PQ算法已经减少了计算量,但计算量依旧很大,并不实用。所以作者提出了IVFADC算法,一种基于倒排索引的ADC算法。简而言之,该算法包含2层量化,第1层被称为coarse quantizer,粗粒度量化器,在原始的向量空间中,基于kmeans聚类出k个簇(文献[8]建议k=n)。第2层是上文讲的PQ量化器,不过这个PQ量化器不是直接在原始数据上做,而是经过第1层量化后,计算出每个数据与其量化中心的残差后,对这个残差数据集进行PQ量化。用PQ处理残差,而不是原始数据的原因是残差的方差或者能量比原始数据的方差或者能量要小。图5是该方法的索引和查询的流程图。

The energy of the residual vector is small compared to that of the vector itself.

 
图5 IVFADC算法的索引和查询的流程图 

对IVFADC的3点补充说明:

  1. 考虑到在coarse quantization中,x和它的近邻不一定落在同一个簇中,所以在查询coarse quantization时,会同时取出w个倒排链。
  2. 对取出的每个倒排链,还是用第3节介绍的PQ算法把近邻给找出。
  3. 考虑当n>kD时,朴素的ADC算法的复杂度是O(n×m),而IVFADC算法的复杂度会降低为O((n×w/k)×m)

参考文献

[1] Product quantization for nearest neighbor search

[2] Efficient matching and indexing

[3] 百度NLP | 神经网络模型压缩技术

[4] Faiss

[5] 图像检索:再叙ANN Search

[6] What are some fast similarity search algorithms and data structures for high-dimensional vectors?

[7] Locality-Sensitive Hashing: a Primer

[8] Billion-scale similarity search with GPUs

[9] 解读Product quantization for nearest neighbor search

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



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

相关文章

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

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

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

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例,告诉我们不懂推荐算法的产品,也能从产品侧出发, 设计出一款不错的推荐系统。 相信很多新手产品,看到算法二字,多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法(注:传统是指科班出身的产品都会接触过)。但对于推荐算法,多数产品对着网上搜到的资源,都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后,更是加大了理解的难度。 但,不了解推荐算法,就无法做推荐系

康拓展开(hash算法中会用到)

康拓展开是一个全排列到一个自然数的双射(也就是某个全排列与某个自然数一一对应) 公式: X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。(a[i]在不同应用中的含义不同); 典型应用: 计算当前排列在所有由小到大全排列中的顺序,也就是说求当前排列是第

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动,这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升:减少抖动,提高图像的清晰度和细节表现力,使得监控画面更加真实可信。 - 细节增强:在低光条件下,抖