16 | 最近邻检索(下):如何用乘积量化实现“拍照识花”功能?
该思维导图由 AI 生成,仅供参考
聚类算法和局部敏感哈希的区别?
- 深入了解
- 翻译
- 解释
- 总结
乘积量化技术在实现“拍照识花”功能中发挥着关键作用。文章介绍了图片检索的基本原理,包括将图片表示为高维空间中的点,并使用特征提取和近似最邻近检索技术来加速检索过程。重点阐述了如何使用聚类算法进行相似检索,通过将数据划分到不同的类中,并建立倒排索引,可以快速找到邻近的点。乘积量化技术通过将高维空间分解成多个子空间的乘积,并使用聚类技术分成多个区域,为向量的相似检索提供了一种高效的压缩表示方法。文章还提到了优化策略,如层次聚类和补全Top K个点,以提升检索效率和结果精准度。乘积量化技术不仅能够有效压缩存储空间,还能在相似性计算中显著减少时间代价,为大规模数据的快速检索提供了重要的技术支持。结合聚类、乘积量化和倒排索引技术,能在压缩向量节省存储空间的同时,通过快速减少检索空间的方式,提高了检索效率。文章深入浅出地介绍了乘积量化技术在图片检索中的应用,为读者提供了清晰的技术概览。
《检索技术核心 20 讲》,新⼈⾸单¥59
全部留言(20)
- 最新
- 精选
- wcf对于乘积法省空间的说法有点疑问.老师在文章里的说法确实能看出节省了空间,但是这里面临的问题是:给定16个二维空间的点,使用(x,y)的存储方法,会比分别存储x和y的方法更省空间吗?假如这16个点的x值分布在16个值上,y值也分布在16个值上,那两种方法都需要32个浮点数表示啊?怎么就能省空间呢?
作者回复: 首先,你举的这个例子不叫“乘积”,而只是将16个(x,y)分别存成16个(x)和16个(y),这样的确是没有省空间的。 然后,我文中的点,其实代表的是“聚类中心向量”,而不是“样本向量”。接下来我来和你一起分析一下。 如果二维空间按格子划分区域,一共有16个区域,那么我们就需要16个编号(相当于生成16个聚类,每个聚类要记录自己的中心向量,有16个二维的中心向量)。但如果我们把二维空间分解为x轴和y轴,那么x轴只需要4个编号,y轴只需要4个编号。这样我们只需要4+4个编号既可以表示完整的二维空间了(相当于将向量分为两个子空间,每个子空间生成4个聚类,每个聚类需要记录自己的中心向量,这样就有8个一维的中心向量) 那么,记录8个一维的中心向量比记录16个二维的中心向量省空间。空间是省在了这里,而不是省在样本向量上。 对于每个样本向量,之前的二维空间编号是1-16,需要4个比特位,分解后的两个一维空间编号是(1-4)*(1-4),也是需要4个比特位。因此,样本向量的存储,无论是个数,还是压缩后需要用到比特位,都是无法节省的。 总结一下,乘积的好处,其实是可以降低我们要存储的中心向量的个数和维度,而不是降低样本向量的个数。如果样本向量原来有n个,那么乘积量化后依然有n个。我文中举的“点”的例子,结合后面的内容看,你就会发现它代表的是聚类中心向量,而不是样本向量。我想这可能就是让你觉得疑惑的地方,希望这个分析可以解答你的疑惑。
2020-05-038 - 每天晒白牙老师讲的是真好,只是学生我底子差,越到后面的文章越看不太懂了,很吃力 也许这就是因为门槛高了,才使得做算法和 AI 的同学工资高 想想从小学开始一直到大学(甚至有些读到了研究生和博士),也都是从简单开始学起,最开始的 1+1=2,看不出学生有多大差别,但后面四则混合运算,再到各种三角函数,大学的微积分等等吧 越到后面学习门槛越高,大家的差距也逐渐拉开
作者回复: 实话实说,这一讲的内容的确很难。即使是我自己当年学这些内容的时候,也琢磨了好久。而且这一部分的内容和AI结合较紧密,也是随着这几年AI的大面积铺开才开始变得重要起来的,之前大部分工程师可能并不熟悉。因此,多看几遍,有不懂的地方一起讨论分析,相信你会有收获的。 为什么进阶篇最后一篇讲了这样一个内容呢,你会发现,我们的应用场景都在进化,现在搜索引擎已经支持图片搜索了,电商平台也支持拍照购物,还有人脸识别等应用,对应起来,我们的检索技术,已经需要从文本关键词检索,升级到图片检索,视频检索等更复杂的空间中了。 包括现在的广告系统,其实各种智能匹配,都可以看着是向量匹配,而不仅仅是传统的关键词倒排检索。 我希望我们都能跟着时代的潮流,提升自己的认知和竞争力。 由于专栏篇幅有限,因此多少会有一些知识没有展开介绍。不过,你可以把这个专栏的内容当做一个索引,然后对于自己感兴趣的部分去深入学习了解。有不清楚的地方,也欢迎讨论和交流。
2020-05-015 - 范闲今天上午刚刚看了乘积量化的论文。乘积量化实际上是建立在一个D维向量由M个子向量组成的假设上。子向量的维度就是K=D/M. 而M代表着码本的数量,码本实际上就是对子向量进行kmeans运算得到的聚类中心。另外在乘积量化过程中,还有个PQcode,实际上存储的子向量属于哪一个码本。 在向量搜索过程中,向量直接和码本运算得到距离表,然后再同PQcode求和就能得到距离了。 但是如果你的向量的数据集的数目N是亿级别的,就会导致你的向量搜索的速度下降。 而倒排向量实际是为了解决这个问题而产生的。先对N个向量聚类,产生1024(这部分可以改变的)个中心,然后会得到N个向量和聚类中心的残差,再对残差进行乘积量化的步骤即可。
作者回复: 你去看了乘积量化的论文,这一点非常好。原始的论文肯定会描述得更详细,有更多的内容,当然,也会更难懂。不过从你的描述来看,你很好地提炼出了乘积量化算法的核心,相信你对它已经理解得很清楚了。
2020-05-0164 - piboye好难啊
作者回复: 这可以说是最难的一章了。但是如果理解好了,你就能吃透向量检索的核心。而向量检索是近期结合深度学习浪潮的热门检索技术,在许多大公司中都开始采用了。建议可以耐心点慢慢多看几遍,相信会理解越来越深刻的。
2020-09-231 - 那时刻非常感谢老师这一节内容,收获不少。对于高维度的向量进行乘积量化,颇类似于数据库里对于数据分表操作,分散存储和提高查询速度。 尝试回答一下讨论问题 1. 使用聚类中心向量来代替聚类中的样本向量,其一,这样不需要存储每个聚类里样本向量,只需要存储他们和中心向量的差值,乘积量化后减少存储,其二,查询时候,只需要比较这个中心向量,减少比较次数,提高查询效率。 2.二维空间的点,可以按照x,y轴两个维度分别进行聚类,然后乘积量化来压缩存储。查询过程可以按照老师文章讲述的过程来查询。
作者回复: 今天的内容的确会比较难,知识点也比较多,所以总结部分有一个思维导图,希望能帮你更好地吸收。 关于思考题: 1. 压缩的根源,是在于我们可以用1个类的中心向量来代替类内所有的n个样本向量。用你熟悉的数据库分表来做例子,分析如下: 原来的向量存储是这样的: 样本向量表结构:[样本向量ID | 向量数据] 每个向量数据都是一个高维向量,会很占空间。 但用聚类中心向量代替样本向量以后,我们会有两张表: 聚类中心表结构:[聚类ID | 聚类中心向量数据] 样本向量表结构:[样本向量ID | 聚类ID] 你会发现,和原先的相比,我们加了一个聚类中心表,由于聚类不多,因此这个表不会太大。而原来的样本向量表,它存的数据从“向量数据”变成了“聚类ID”,从而不用存储具体的向量(可以用聚类ID关联到聚类中心表),因此表空间得到压缩。 2.是的,这题是希望你能更好地理解乘积量化的思想,并不一定要求要严格按照每个流程做。我们可以分为xy轴两个维度(这样就是乘积了)。不过由于数据太少,所以也不需要用聚类,比如你把x轴等分2段也可以。然后每段编上号(这样就是量化了)。 然后查询时,你分别和x轴和y轴比,找到对应的区域就好。
2020-05-011 - 易企秀-郭彦超老师 倒排乘机量化中,使用k-means将样本向量分为1024个聚类 ,这里的样本向量指的是图片向量吗,意思是将高维图片向量压缩为1024维图片向量吗,还是每张图片被划分到1024个聚类中的某一个
作者回复: 在本文的例子中,样本向量指的就是图片向量,分为1024个聚类,指的是将每个图片分到1024个聚类中的某一个。(图片向量维度可以很高,大于1024)
2021-01-27 - 范闲CheckSum的值还需要多个节点同步一下,来确认节点内的数据最终是一致的对吧。
作者回复: 对的。你可以将checksum的值汇总到zookeeper,或者Redis中,进行所有节点的数据一致性判断。当然,如果进行scp的数据源机器只有一台的话,汇总到这台机器进行判断和处理也是OK的。
2020-06-05 - 范闲最近遇到一个问题想请教下老师。 情况是这样的 我有一个在线召回模块和离线数据模块。 利用词向量生成句向量,然后利用Annoy搜索。 主线程负责在线召回的搜索,副线程负责监控有没有新的词向量模型和索引模型。 离线数据模块主要是从数据库和接口拉取用户问句,训练词向量模型,生成句向量和构建索引。当向量模型和索引构建完毕后,利用scp分别拷贝到多台在线召回的机器上,来完成数据同步。 1.当请求量上去以后,在线召回词向量模型的查性能不行而且随着数据量增大,词向量的内存占用也越来越大。 2.利用scp拷贝到多机的时候,没法确认是不是真的拷贝过去了,真的数据同步了,然后这就会导致不同在线模块的结果可能不一致。 针对问题1的话,我想在离线数据生成词向量的时候。直接写入redis集群,在线召回去redis读取即可。 针对问题2的话,目前没有考虑到太好的办法,只能还是按照scp的方式把索引文件同步过去。 关于问题2您有什么好的想法么?
作者回复: 关于使用scp拷贝数据的问题,如果你需要保证数据的一致性,可以做一下checksum的检查,要checksum一致才算是传输成功,否则就是同步失败。
2020-06-04 - 鲁滨逊老师,对于向量搜索我有两个实际问题。1.对于特征向量携带多个属性的情境下,属性过滤该怎么做呢?比如我们现在在给公安做的交通路口,人脸卡扣抓拍搜索,时间范围和地点这两个基本属性是一定会进行过滤的。我的考虑是,如果放在距离计算之前进行过滤,确实能减少搜索范围,但向量存储一定依照一定的组织方式,这种组织方式该怎样设计,或者其他数据库能解决?如果全量搜索完之后再做过滤,那可能得不到topk个结果,极端情形甚至一个都没有(都被过滤掉了)2.对于数据量不断增多,一段时间后倒排索引是不是得重新建立,聚类中心数量还如何选择呢?麻烦老师解惑。
作者回复: 对于第一个问题,属性过滤如何做?你可以参考一下后面广告系统,以及进阶篇的测试题“如何寻找附近的相同兴趣的人”。 你会看到,我们可以先用有明确过滤条件的属性(比如地点),将所有数据进行分片,然后在分片里进行向量检索,然后最后可以再进行属性过滤。 第二个问题,索引肯定是需要定期重建的,至于聚类的数量是否需要修改,主要还是看业务形态是否有变化和聚类结果是否依然理想。只要能保证类的边界清晰,类内元素紧密,那么聚类数量多一些少一些都可以的。
2020-06-04 - 峰问题1, 假设只有一个子空间就是本身,这就当于用聚类中心ID表示原始的数据点,当然还需要记录下聚类中心的原始特征向量,而多个就是扩展的问题,对每个子空间都采用这种方式对数据进行编码,但是如何选择有效的子空间无疑是这个算法的问题所在。 问题2,我理解17,17 是一个异常点,作为一个聚类中心,单独考虑记录好了。 额看了下评论,原来理解错了意思。。。。。 这节课真的是厉害了,思想其实都明白,串在一起还真是得好好看看看看看看。。。。。。
作者回复: 哈哈,的确是这样的,聚类,乘积,量化,倒排索引,其实每个词单独看都不算很复杂,但这些技术组合起来以后,却能发挥很好的效果。 包括为什么它们可以组合在一起串起来,怎么起到互补的作用,的确可以好好消化一下。 至于问题2,可能例子不算很好,不过大家看了评论以后,能理解怎么使用乘积量化,那么我觉得目的就达到了。
2020-05-10