检索技术核心20讲
陈东
奇虎360商业产品事业部资深总监
立即订阅
2377 人已学习
课程目录
已完结 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
登录|注册

12 | 非精准Top K检索:如何给检索结果的排序过程装上“加速器”?

陈东 2020-04-22
你好,我是陈东。
上一讲,我们详细讲解了 Top K 检索的打分排序过程,并且还提到可以使用堆排序代替全排序,来大幅降低排序的时间代价。然而,对于这整个检索过程来说,精准复杂的打分开销要比排序大得多。因此,如果我们想更大幅度地提升检索性能,优化打分过程是一个重要的研究方向。那打分过程具体该怎么优化呢?今天,我们就来聊聊这个问题。

什么是非精准的 Top K 检索?

想要优化打分过程,一个很自然的思路就是通过简化打分机制,来降低打分开销。但是简化之后,我们的排序结果就不精准了。这该怎么办呢?这个问题先不着急解决,我们先来看看不精准的排序结果对用户会有什么影响。
其实,在搜索引擎中,排在第一页的结果并不一定是分数最高的。但由于用户在搜索时,本来就没有明确的目标网页,所以只要第一页的网页内容能满足用户的需求,那这就是高质量的检索结果了。
不仅如此,在推荐引擎中也是一样。推荐系统会根据用户的历史行为进行推荐,可推荐的物品非常多。比如说,如果用户曾经购买过《C++ 程序设计》这本书,那接下来我们既可以推荐《C++ 编程实战》,也可以推荐《C++ 编程宝典》。无论我们推荐哪一本,可能对用户来说差别都不大。
我们发现,其实在很多实际的应用场景中,高质量的检索结果并不一定要非常精准,我们只需要保证质量足够高的结果,被包含在最终的 Top K 个结果中就够了。这就是非精准 Top K 检索的思路
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《检索技术核心20讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(8)

  • 一步
    看完这篇文章和上一篇文章:我的理解是
    静态质量得分的非精确打分和精确打分的打分对象是不同的
    静态质量得分非精确打分因为是离线打分,针对的是文档进行打分,该文档的所有关键词的分都一样
    精确打分:针对的某个关键词和文档的相关性进行打分

    作者回复: 是的。静态质量得分不考虑相关性,因此只需要对文档自身进行打分就好。写成函数形式就是f(d),d代表文档。
    而精确打分要考虑查询词和文档的相关性。如果文档是d,查询词是q,那么打分函数就是f(q,d)。由于查询词是动态的,因此只能在实时环节进行打分,无法在离线环节打分。(注意:查询词可能有多个词项,比如同时有“极客”和“时间”两个词项,因此只能实时计算相加。否则如果查询词只有一个词项,那么是可以用胜者表的方法离线计算相关性的)。

    2020-04-22
    4
  • 问题1 降序是必然的,毕竟升序没有意义,但根据静态分降序,然后根据静态分去做粗排,这样不会饿死静态分不高的文档吗,或者它活该饿死。。。。
    问题2,没想到什么场景,但思路就是比如可以用一些近似计算的方式算一遍,排除掉一些数据项,再做精确运算。

    作者回复: 1.你提了很好的一个问题,静态质量分不好的是否会被活活饿死?其实,不管是静态质量得分还是动态的相关性打分,既然是排序,肯定会有优胜劣汰,只是在大数据的场景下,所谓的劣汰不是完全封杀,而是降低出现的概率。
    首先,如果快速截断采取的是静态质量分,那么粗排的时候肯定就是换一种打分机制了,比如说采用bm25进行粗排,或者使用简化版的机器学习(为了保证效率,用在粗排阶段的机器学习模型会比较简单,而不是和用在精排阶段的机器学习模型完全一样)。
    另一方面,为了保证结果的多样性,我们应该加入exploit &explore机制,就是保证有小比例的流量可以采用随机的方式选择检索结果,而不是靠打分排序,从而给一些初始打分不高的检索结果证明自己的机会。但如果数据依然不好,那么接下来这些低质量的结果被选出来的概率就会越来越低。
    2.在搜索引擎和推荐引擎中,使用tf-idf,bm25,甚至是简化的逻辑回归模型来做非精准top k检索,都是常见的使用方案。此外,就像你说的一样,可以用一些简单算法算一遍,快速排除掉一些数据项。这方面其实也有许多研究和论文,比如说雅虎有一篇wand(weak and)算法的论文,就是讲如何根据相似度的上限来快速截断。
    其实,使用非精准检索思路的场景非常多,我文中的简历筛选的过程就是一个例子。下一篇你也会看到另一个例子。

    2020-04-22
    1
    3
  • 牛牛
    感觉计算机的世界和人类的世界是惊人的相似, 总是在做各种权衡(时间和空间, 资源消耗与效率提升、耗时与准确度...) 总是在追求较小成本的最大收益(也正因为如此、才推动社会的进步和发展、不断的创新、尝试), 而这种关系、总在趋于平缓(某种资源达到一定程度之后、对整体的提升就不再明显), 所以就需要不断的突破(计算机的发展和自我成长都是如此)~~~~

    ---------------
    尝试回答下今天的问题:
    1. 应该是为了在同层次索引中最快速的得到相关度最高的top N 结果
      至于是升序还是降序, 若[posting list]是链表的话、应该是降序; 但我有一个疑问, 就是 [posting list]是目前一般都这么实现的吗? 为什么不是使用小顶堆呢 ?这样topk的取值效率应该是 O(1) ?堆插入的效率会低于链表、就搜索来说、应该是插入频次远小于查询频次的

    2. a. 每次购物时、同类型的商品我们会加入多个(非精准topK)、然后再对比价格、评论等信息, 再决定买哪一个或哪些(精准筛选)
       b. 找相关文章时、一般会先打开多个链接、然后再从中挑选一下, 看哪个文章更适合自己(有时候top1、2、3的推荐不一定是适合的, eg. 理论性太强、全英文等)
      c. 在微信读书选书时、一般我会调同一题材的多本书籍、然后再根据感兴趣的程度继续挑选最喜欢的一到两个放到书架
    暂时能想到这几个场景、不知道算不算~~~

    作者回复: 从某种角度角度来说,计算机世界和我们的生活的确都是蛮相似的,其实都是在针对目标,做各种优化和平衡,我们的学习,其实也是应该触类旁通,不仅仅是学习技术本身,也在学习做事的方式。
    问题1: posting list的确是用链表或数组降序排序好的。而不是用堆。因为用堆的话,取出堆顶元素,就需要调整堆,代价是log n。但posting list只要是只读的就好,我们没必要要读第二大的元素的时候还要实时调整,这样效率反而会低。包括posting list如果插入新元素,其实我们可以使用第九讲索引更新的技术实现,而不是实时插入。因此,posting list目前的实现还是跳表或数组。
    2.你举的这些例子都很好,都是先初步筛选,再精确筛选的。如果我们要实现人工智能的话,其实也是可以按照这个思路来设计实现的。

    2020-05-09
    2
  • 那时刻
    1.分层索引采用静态质量得分是大概率只扫描第一层索引就可以得到topk。而采用词频相关性的话,为保证文档齐全大概率需要搜索多层索引。效率比较低。分层索引采用降序排序。

    作者回复: 就如你说的,分层索引大概率只扫描第一层就能得到top k。因此,在第一层索引候选集充足的情况下,采用静态质量分降序,能更快进行top k截断,而不需要完整检索完第一层索引,从而达到检索加速的目的。

    2020-04-22
    1
  • 流浪在寂寞古城
    分层索引有一些不明白,高质量的索引离线计算的方式得到分数,我理解这个离线计算应该是利用词频类似的方法吧(因为高质量内部排序用的静态分)。以“极客”和“时间”为例,这时候如果高质量的召回不够k,那么很可能“极客”的高质量索引与“时间”低质量索引有交集,反之毅然。这时候我们为例凑够k个,一般工业上是如何操作的呢?拿彼此的高质量和低质量进行匹配?因为高质量的索引一定文档不是很多,有可能还是不够k个。还是直接低质量和低质量召回呢?

    作者回复: 你思考了一些细节和案例,这个习惯很好。你也会发现:高质量索引的“极客”和低质量索引的“时间”求交集,这个方法感觉不太对是不是? 分层索引的确不是这么实现的。
    分层索引不是根据词频类似的打分方式来对文档进行分层,它更多的还是根据静态质量分来区分。
    比如说,来自门户网站的文章会被打上更高的质量分,而个人站点的类似文章会被打上较低的质量分。它们分别被划分到了高质量文档集合a,以及普通文档集合b中。
    我们在建立倒排索引时,会针对a建立一个倒排索引,针对b建立一个倒排索引。
    在检索时,先检索a索引,得到x个文档。如果不满足k个结果,那么再去索引b中,以“极客”和“时间”为key,单独在索引b中找到符合条件的y个文档,然后将x个文档和y个文档合并,再取top k。
    那为什么不是在索引a中用“极客”检索posting list,再在索引b中用“时间”检索出posting list然后合并呢?因为这两个posting list的文档集合是空。(索引a和索引b中的文档是无交集的)。

    2020-06-30
  • 一步
    第一步,我们取出这两个关键词的 posting list,但不直接截断;第二步,我们对这两个 posting list 归并排序。留下分数和文档 ID 都相同的条目作为结果集合,当结果集合中的条目达到 k 个时,
    --------------------------------------------------
    这里面为什么也要要求分数也相当呢?
    如果一个文档对于 关键词 A 的分是4,对于B的是5,那不就是把这个文档过滤掉了?
    归并的时候找到前 k 个文档 ID 相同的不就可以了吗?
    2020-04-22
    1
  • 那时刻
    老师,您在胜者表提到静态质量得分和词频两个维度综合考虑来计算文档权重,请问在实际操作中有这样的应用么?

    作者回复: 实际中是有的。其实就是一个加权的表达式:
    w1*tf + w2*静态质量分。
    具体w1和w2的权重,可以看你的应用诉求,手动调整。

    2020-04-22
  • pedro
    问题1,根据静态质量得分来排序可以有效的筛选出高质量的内容,排序应该是降序,将高质量文档放在前面从而更快的打分。
    问题2,没想到深度学习的降维打击,让传统经典的打分算法都沦为到非精准打分的环节了,哎,英雄迟暮。

    作者回复: 1.是的。还是为了快速截断。如果在高质量文档的索引中也有足够的候选集,那么其实我们也不需要检索完全部文档,因此对于高质量索引,依然采用根据静态质量降序,是能有加速效果的。
    2.的确是这样的,现在的召回环节中,就有用逻辑回归进行截断的,当然,这个环节也有人叫做“粗排”环节。不过历史是相似的,在机器学习出来之前,bm25就是精排;在机器学习出来后,bm25就变成粗排了;同理,在深度学习出来以后,机器学习就可以变成粗排了。说不定未来哪天,深度学习也会变成粗排。

    2020-04-22
收起评论
8
返回
顶部