检索技术核心20讲
陈东
奇虎360商业产品事业部资深总监
立即订阅
2355 人已学习
课程目录
已完结 29 讲
0/4登录后,你可以任选4讲全文学习。
课前必学 (2讲)
开篇词 | 学会检索,快人一步!
免费
导读 | 三步走策略,轻松搞定检索!
基础技术篇 (8讲)
01 | 线性结构检索:从数组和链表的原理初窥检索本质
02 | 非线性结构检索:数据频繁变化的情况下,如何高效检索?
03 | 哈希检索:如何根据用户ID快速查询用户信息?
04 | 状态检索:如何快速判断一个用户是否存在?
05 | 倒排索引:如何从海量数据中查询同时带有“极”和“客”的唐诗?
测一测 | 检索算法基础,你掌握了多少?
特别加餐 | 倒排检索加速(一):工业界如何利用跳表、哈希表、位图进行加速?
特别加餐 | 倒排检索加速(二):如何对联合查询进行加速?
进阶实战篇 (13讲)
06 | 数据库检索:如何使用B+树对海量磁盘数据建立索引?
07 | NoSQL检索:为什么日志系统主要用LSM树而非B+树?
08 | 索引构建:搜索引擎如何为万亿级别网站生成索引?
09 | 索引更新:刚发布的文章就能被搜到,这是怎么做到的?
10 | 索引拆分:大规模检索系统如何使用分布式技术加速检索?
11|精准Top K检索:搜索结果是怎么进行打分排序的?
12 | 非精准Top K检索:如何给检索结果的排序过程装上“加速器”?
13 | 空间检索(上):如何用Geohash实现“查找附近的人”功能?
14 | 空间检索(下):“查找最近的加油站”和“查找附近的人”有何不同?
15 | 最近邻检索(上):如何用局部敏感哈希快速过滤相似文章?
16 | 最近邻检索(下):如何用乘积量化实现“拍照识花”功能?
特别加餐 | 高性能检索系统中的设计漫谈
测一测 | 高性能检索系统的实战知识,你掌握了多少?
系统案例篇 (4讲)
17 | 存储系统:从检索技术角度剖析LevelDB的架构设计思想
18 | 搜索引擎:输入搜索词以后,搜索引擎是怎么工作的?
19 | 广告系统:广告引擎如何做到在0.1s内返回广告信息?
20 | 推荐引擎:没有搜索词,“头条”怎么找到你感兴趣的文章?
结束语 (2讲)
结束语 | 成长和进化,技术如此,我们亦如此
免费
结课测试 | 这些检索知识,你都掌握了吗?
检索技术核心20讲
15
15
1.0x
00:00/00:00
登录|注册

16 | 最近邻检索(下):如何用乘积量化实现“拍照识花”功能?

陈东 2020-05-01
你好,我是陈东。
随着 AI 技术的快速发展,以图搜图、拍图识物已经是许多平台上的常见功能了。比如说,在搜索引擎中,我们可以直接上传图片进行反向搜索。在购物平台中,我们可以直接拍照进行商品搜索。包括在一些其他的应用中,我们还能拍照识别植物品种等等。这些功能都依赖于高效的图片检索技术,那它究竟是怎么实现的呢?今天,我们就来聊一聊这个问题。

聚类算法和局部敏感哈希的区别?

检索图片和检索文章一样,我们首先需要用向量空间模型将图片表示出来,也就是将一个图片对象转化为高维空间中的一个点。这样图片检索问题就又变成了我们熟悉的高维空间的相似检索问题。
如果我们把每个图片中的像素点看作一个维度,把像素点的 RGB 值作为该维度上的值,那一张图片的维度会是百万级别的。这么高的维度,检索起来会非常复杂,我们该怎么处理呢?我们可以像提取文章关键词一样,对图片进行特征提取来压缩维度。
要想实现图片特征提取,我们有很多种深度学习的方法可以选择。比如,使用卷积神经网络(CNN)提取图片特征。这样,用一个 512 到 1024 维度的向量空间模型,我们就可以很好地描述图像了,但这依然是一个非常高的维度空间。因此,我们仍然需要使用一些近似最邻近检索技术来加速检索过程。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《检索技术核心20讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(13)

  • 王创峰
    对于乘积法省空间的说法有点疑问.老师在文章里的说法确实能看出节省了空间,但是这里面临的问题是:给定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-03
    4
  • 每天晒白牙
    老师讲的是真好,只是学生我底子差,越到后面的文章越看不太懂了,很吃力

    也许这就是因为门槛高了,才使得做算法和 AI 的同学工资高

    想想从小学开始一直到大学(甚至有些读到了研究生和博士),也都是从简单开始学起,最开始的 1+1=2,看不出学生有多大差别,但后面四则混合运算,再到各种三角函数,大学的微积分等等吧

    越到后面学习门槛越高,大家的差距也逐渐拉开

    作者回复: 实话实说,这一讲的内容的确很难。即使是我自己当年学这些内容的时候,也琢磨了好久。而且这一部分的内容和AI结合较紧密,也是随着这几年AI的大面积铺开才开始变得重要起来的,之前大部分工程师可能并不熟悉。因此,多看几遍,有不懂的地方一起讨论分析,相信你会有收获的。
    为什么进阶篇最后一篇讲了这样一个内容呢,你会发现,我们的应用场景都在进化,现在搜索引擎已经支持图片搜索了,电商平台也支持拍照购物,还有人脸识别等应用,对应起来,我们的检索技术,已经需要从文本关键词检索,升级到图片检索,视频检索等更复杂的空间中了。
    包括现在的广告系统,其实各种智能匹配,都可以看着是向量匹配,而不仅仅是传统的关键词倒排检索。
    我希望我们都能跟着时代的潮流,提升自己的认知和竞争力。
    由于专栏篇幅有限,因此多少会有一些知识没有展开介绍。不过,你可以把这个专栏的内容当做一个索引,然后对于自己感兴趣的部分去深入学习了解。有不清楚的地方,也欢迎讨论和交流。

    2020-05-01
    3
  • 范闲
    今天上午刚刚看了乘积量化的论文。乘积量化实际上是建立在一个D维向量由M个子向量组成的假设上。子向量的维度就是K=D/M. 而M代表着码本的数量,码本实际上就是对子向量进行kmeans运算得到的聚类中心。另外在乘积量化过程中,还有个PQcode,实际上存储的子向量属于哪一个码本。

    在向量搜索过程中,向量直接和码本运算得到距离表,然后再同PQcode求和就能得到距离了。

    但是如果你的向量的数据集的数目N是亿级别的,就会导致你的向量搜索的速度下降。

    而倒排向量实际是为了解决这个问题而产生的。先对N个向量聚类,产生1024(这部分可以改变的)个中心,然后会得到N个向量和聚类中心的残差,再对残差进行乘积量化的步骤即可。

    作者回复: 你去看了乘积量化的论文,这一点非常好。原始的论文肯定会描述得更详细,有更多的内容,当然,也会更难懂。不过从你的描述来看,你很好地提炼出了乘积量化算法的核心,相信你对它已经理解得很清楚了。

    2020-05-01
    2
  • 那时刻
    非常感谢老师这一节内容,收获不少。对于高维度的向量进行乘积量化,颇类似于数据库里对于数据分表操作,分散存储和提高查询速度。

    尝试回答一下讨论问题
    1. 使用聚类中心向量来代替聚类中的样本向量,其一,这样不需要存储每个聚类里样本向量,只需要存储他们和中心向量的差值,乘积量化后减少存储,其二,查询时候,只需要比较这个中心向量,减少比较次数,提高查询效率。
    2.二维空间的点,可以按照x,y轴两个维度分别进行聚类,然后乘积量化来压缩存储。查询过程可以按照老师文章讲述的过程来查询。

    作者回复: 今天的内容的确会比较难,知识点也比较多,所以总结部分有一个思维导图,希望能帮你更好地吸收。
    关于思考题:
    1. 压缩的根源,是在于我们可以用1个类的中心向量来代替类内所有的n个样本向量。用你熟悉的数据库分表来做例子,分析如下:
    原来的向量存储是这样的:
    样本向量表结构:[样本向量ID | 向量数据]
    每个向量数据都是一个高维向量,会很占空间。
    但用聚类中心向量代替样本向量以后,我们会有两张表:
    聚类中心表结构:[聚类ID | 聚类中心向量数据]
    样本向量表结构:[样本向量ID | 聚类ID]
    你会发现,和原先的相比,我们加了一个聚类中心表,由于聚类不多,因此这个表不会太大。而原来的样本向量表,它存的数据从“向量数据”变成了“聚类ID”,从而不用存储具体的向量(可以用聚类ID关联到聚类中心表),因此表空间得到压缩。
    2.是的,这题是希望你能更好地理解乘积量化的思想,并不一定要求要严格按照每个流程做。我们可以分为xy轴两个维度(这样就是乘积了)。不过由于数据太少,所以也不需要用聚类,比如你把x轴等分2段也可以。然后每段编上号(这样就是量化了)。
    然后查询时,你分别和x轴和y轴比,找到对应的区域就好。

    2020-05-01
    1
  • 范闲
    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
  • paulhaoyi
    那么分组切分的数目有什么通用规则么?就是为什么1024通常分四组,每组256聚类,如果我多分,多聚类,或者少,会有那些影响?感觉应该是一个效果和成本的权衡?

    作者回复: 你说得很对,可以多分,也可以少分,取决于你的应用需求,以及对成本和效果的权衡。
    其实上一讲的simhash检索就是一个例子,如果我们将海明距离从3调为4,那么切分就需要从4段改为五段以上。可见,我们最主要还是要理解原理,这样在需要优化的时候,才会有思路和方向。

    2020-05-06
  • paulhaoyi
    关于向量乘积的例子,请教下老师,两个纬度各四个分区,共8个中心。如果我把2纬空间就分成8个聚类中心(不用16个),保持总分类数一样。也就是占用存储空间一样,那么两种方式的精度损失应该是不一样的吧?这个损失差别怎么理解?感觉不管怎么分,都是把整个空间或者说样本分成了8组或16组?那么直接二维分8组,为什么比两个一纬各分4组的效果差?这个地方感觉没理解清楚。

    作者回复: 如果是把二维空间分成8个聚类中心的话,那么划分粒度自然是比划分成16个聚类中心更粗,因此会损失精度。(你可以参考Geohash那一课的区域划分,你会看到,肯定是划分得越细粒度越精准)。
    并且,如果整个二维空间被划分为8个聚类中心的话,那我也可以将它看做是2*4两个子空间的乘积。因此我可以仅记录2+4个一维的聚类中心,这样还是比记录8个二维的聚类中心更省空间。
    你可以尝试拿一张纸,试着根据上面的例子,在纸上画一下区域划分的例子,这样应该会有所帮助。

    2020-05-06
  • 一步
    我们就可以用 1 个比特位的 0 或 1 编码,来代替任意一个点的二维空间坐标 <x,y> 了 。假设 x 和 y 是两个浮点数,各 4 个字节,那它们一共是 8 个字节。如果我们将 8 个字节的坐标用 1 个比特位来表示
    ------------------------------
    像文章说的二维空间量化,一个具体的坐标<x,y> 转换为一个 0 和 1,只知道大致的方向了,这样的话信息不是丢的很严重,这样的量化有意义吗?

    作者回复: 如果只将一个空间分为两部分,那的确可能太粗糙了,这个例子更多是让你直观感受一下量化的压缩原理。如果觉得太粗糙,你可以多划分几次,比如说用2个比特位,就可以将空间划分为4份,这样精度就提高。
    后面的例子中,你会看到,我们对于一段子空间,将它生成256个聚类,这样是一个常用的方案。当然,你也可以根据自己的需求去调整粒度,比如生成512个聚类,或者128个聚类都可以。

    2020-05-05
  • 一步
    K-means 算法的第三步:
    计算每个类内节点的向量均值,作为每个类的新的中心向量。

    有个问题是:如果计算出来的新的中心向量的值 不在 所有的节点中会怎么进行处理的? 还有这一步要不要判断 新的中心向量的值 在不在所有的节点中?

    作者回复: 不需要的。中心向量并不是已有节点。
    第一步之所以随机选择已有节点作为中心向量,只是一个初始化步骤而已。你也可以随机生成k个中心向量作为第一步的代替方案。

    2020-05-05
  • 那时刻
    请问在聚类算法进行相似检索中,对于聚类中的候选集不足 Top K 个,我们还可以再去查询次邻近的聚类,这个临近聚类怎么来寻找呢?是重新计算当前聚类中心点和其它中心点距离么?还是需要额外存储聚类中心点之间的距离?

    作者回复: 是这样的,在k-means算法中,我们会生成k个聚类,每个聚类都有自己的聚类中心向量。这些中心向量会存储好。
    然后,当查询向量到来的时候,我们会和这k个聚类中心向量比较,这样就能得到查询向量到每个聚类的距离。最近的那个聚类,就是目标聚类。如果这个目标聚类中的候选集不足,那么距离第二近的聚类,就是次临近的聚类。同理,如果次邻近的这个聚类中候选集还是不足,那么我们可以再去找距离第三近的聚类。依此类推。

    2020-05-01
收起评论
13
返回
顶部