检索技术核心 20 讲
陈东
前数禾科技 CTO,前奇虎 360 商业化资深总监
21492 人已学习
新⼈⾸单¥59
登录后,你可以任选4讲全文学习
课程目录
已完结/共 29 讲
检索技术核心 20 讲
15
15
1.0x
00:00/00:00
登录|注册

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

高质量索引和低质量索引
离线计算打分
使用胜者表
词频在索引构建时计算
posting list按静态质量得分排序
离线环节计算静态质量得分
非精准Top K检索和精准Top K共同完成
在线环节引入“非精准打分”环节
使用分层索引
根据词频得分排序截断
根据静态质量得分排序截断
检索排序过程分为两个阶段
非精准Top K检索结合精准Top K检索
高质量的检索结果
用户需求满足即可
降低打分开销
非精准Top K检索的方法和应用场景
分层索引中的文档排序
完整的Top K检索
非精准Top K检索的拓展
非精准Top K检索的实现
工业界中的应用
非精准的排序结果
优化打分过程
课堂讨论
非精准Top K检索

该思维导图由 AI 生成,仅供参考

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

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

想要优化打分过程,一个很自然的思路就是通过简化打分机制,来降低打分开销。但是简化之后,我们的排序结果就不精准了。这该怎么办呢?这个问题先不着急解决,我们先来看看不精准的排序结果对用户会有什么影响。
其实,在搜索引擎中,排在第一页的结果并不一定是分数最高的。但由于用户在搜索时,本来就没有明确的目标网页,所以只要第一页的网页内容能满足用户的需求,那这就是高质量的检索结果了。
不仅如此,在推荐引擎中也是一样。推荐系统会根据用户的历史行为进行推荐,可推荐的物品非常多。比如说,如果用户曾经购买过《C++ 程序设计》这本书,那接下来我们既可以推荐《C++ 编程实战》,也可以推荐《C++ 编程宝典》。无论我们推荐哪一本,可能对用户来说差别都不大。
我们发现,其实在很多实际的应用场景中,高质量的检索结果并不一定要非常精准,我们只需要保证质量足够高的结果,被包含在最终的 Top K 个结果中就够了。这就是非精准 Top K 检索的思路
确认放弃笔记?
放弃后所记笔记将不保留。
新功能上线,你的历史笔记已初始化为私密笔记,是否一键批量公开?
批量公开的笔记不会为你同步至部落
公开
同步至部落
取消
完成
0/2000
荧光笔
直线
曲线
笔记
复制
AI
  • 深入了解
  • 翻译
    • 英语
    • 中文简体
    • 中文繁体
    • 法语
    • 德语
    • 日语
    • 韩语
    • 俄语
    • 西班牙语
    • 阿拉伯语
  • 解释
  • 总结

非精准Top K检索是搜索引擎中常用的一种优化方法,通过在离线环节对文档进行排序截断,以降低在线环节的计算复杂度,从而提升检索性能。本文介绍了三种实现方法:根据静态质量得分排序截断、使用胜者表和分层索引。这些方法的核心思路是尽可能将计算从在线环节转移到离线环节,以在在线环节中快速截断Top K个结果,提升检索引擎的效率。此外,文章还探讨了将非精准Top K检索拓展到线上环节的可能性,通过引入“非精准打分”的环节,进一步减少参与“精准打分”的检索结果数量。最后,强调了完整的Top K检索是由非精准Top K检索和精准Top K共同完成的,以提升整体在线检索的效率。文章内容涵盖了搜索引擎优化的关键技术,对于搜索引擎开发人员和相关领域的研究人员具有重要参考价值。

仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《检索技术核心 20 讲》
新⼈⾸单¥59
立即购买
登录 后留言

全部留言(15)

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

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

    2020-04-22
    15
  • 牛牛
    感觉计算机的世界和人类的世界是惊人的相似, 总是在做各种权衡(时间和空间, 资源消耗与效率提升、耗时与准确度...) 总是在追求较小成本的最大收益(也正因为如此、才推动社会的进步和发展、不断的创新、尝试), 而这种关系、总在趋于平缓(某种资源达到一定程度之后、对整体的提升就不再明显), 所以就需要不断的突破(计算机的发展和自我成长都是如此)~~~~ --------------- 尝试回答下今天的问题: 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
    7
  • 问题1 降序是必然的,毕竟升序没有意义,但根据静态分降序,然后根据静态分去做粗排,这样不会饿死静态分不高的文档吗,或者它活该饿死。。。。 问题2,没想到什么场景,但思路就是比如可以用一些近似计算的方式算一遍,排除掉一些数据项,再做精确运算。

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

    2020-04-22
    2
    4
  • 流浪在寂寞古城
    分层索引有一些不明白,高质量的索引离线计算的方式得到分数,我理解这个离线计算应该是利用词频类似的方法吧(因为高质量内部排序用的静态分)。以“极客”和“时间”为例,这时候如果高质量的召回不够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
    3
  • zj
    第一种静态质量分 和 第三种分层索引方法,如果第三种分层索引也采用静态分层索引,那我觉得跟第一种静态质量分的效率是差不多的

    作者回复: 你说的没错,如果分层索引不考虑相关性,仅采用静态质量分,那么和第一种方法差不多(仅是在高质量层查不到的时候才有区别)

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

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

    2020-04-22
    1
  • 那时刻
    老师,您在胜者表提到静态质量得分和词频两个维度综合考虑来计算文档权重,请问在实际操作中有这样的应用么?

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

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

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

    2020-04-22
  • 庄墨寒
    很好的课程,回答了我对搜索引擎诸多忙点。点赞。
    2024-02-01归属地:浙江
  • 知错正在改
    给老师跪下了,讲得太好了😭,我终于学懂了,不会再犯低级错误😭,喜极而泣
    2023-12-06归属地:广东
收起评论
显示
设置
留言
15
收藏
沉浸
阅读
分享
手机端
快捷键
回顶部