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

11|精准Top K检索:搜索结果是怎么进行打分排序的?

陈东 2020-04-20
你好,我是陈东。
在搜索引擎的检索结果中,排在前面几页的检索结果往往质量更好,更符合我们的要求。一般来说,这些高质量检索结果的排名越靠前,这个搜索引擎的用户体验也就越好。可以说,检索结果的排序是否合理,往往决定了一个检索系统的质量。
所以,在搜索引擎这样的大规模检索系统中,排序是非常核心的一个环节。简单来说,排序就是搜索引擎对符合用户要求的检索结果进行打分,选出得分最高的 K 个检索结果的过程。这个过程也叫作 Top K 检索。
今天,我就和你仔细来聊一聊,搜索引擎在 Top K 检索中,是如何进行打分排序的。

经典的 TF-IDF 算法是什么?

在搜索引擎的应用场景中,检索结果文档和用户输入的查询词之间的相关性越强,网页排名就越靠前。所以,在搜索引擎对检索结果的打分中,查询词和结果文档的相关性是一个非常重要的判断因子。
那要计算相关性,就必须要提到经典的 TF-IDF 算法了,它能很好地表示一个词在一个文档中的权重。TF-IDF 算法的公式是:相关性 = TF*IDF。其中,TF 是词频(Term Frequency),IDF 是逆文档频率(Inverse Document Frequency)。
在利用 TF-IDF 算法计算相关性之前,我们还要理解几个重要概念,分别是词频、文档频率和逆文档频率。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《检索技术核心20讲》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(11)

  • INFRA_1
    老师是否typo,使用堆排序的最终时间复杂度应该是nlogk吧

    编辑回复: 作者回复:并不是typo,你其实提了一个好问题,使用堆来完成Top K检索,时间代价是什么呢?其实有两种不同的方法,对应了两个时间代价!
    一种方法,是先对前k个元素建一个堆,这时候时间代价是O(k)。然后接下来,对于每个新加入元素,判断要将堆里的哪个元素替换掉,判断和处理的时间代价是O(logk)。这样这个堆就一直是保持有k个元素。处理完了n个元素以后,时间代价就是O(n logk)。
    而另一种方法,是先对n个元素建一个堆,这时候时间代价是O(n),然后接下来,我们在这个堆中,进行k次操作,将堆顶的最大值取出。每次取出堆顶元素,调整的时间代价是O(log n)。因此,处理完k个元素,时间代价就是O(k log n)
    你会看到,我在文章中说的O(n) + O(k log n)的方法,其实就是第二种方法,我其实也简单做了描述。至于它和第一种方法相比,哪个更快,你会发现,当n很大的时候,第二种方法,其实时间代价是接近O(n)的,会比第一种方法O(n log k)快上接近log k倍。
    此外,如果不使用堆的话,我们还可以使用快速选择排序(注意,不是快排,但是使用了快排的partition思想),也是可以在O(n)的时间代价完成top K的检索的。

    2020-04-23
    1
    5
  • 我怎么感觉是构建训练集标注数据最耗时呢😂😂😂。
    正经点,我觉得打分不应该是在查询的时候实时算,每个词项的分数应该以一定的频率更新,毕竟只要文档基数上来了,加些文档,词项的分数影响不大。还有就是老师这里说的是查询项包含多个词项,然后用多个词项的分数代表文档分数,但这前提条件是词项是and且同比重,如果是or啥的,好了我不想了我头大。感觉老师这块打分排序整体上的逻辑没有和之前的搜索串连上,让我有种脱节的感觉。

    作者回复: 如果是or的话,那么其实也可以加权再相加。你会发现,由人工来制定规则的确会头大,因此不如交给机器学习打分,直接预估每个文档的点击率就好。

    至于为什么写这一篇,我也补充几点:
    1.对于一个完整的检索系统,检索结果的排序是无法回避的问题,包括在前面的课程中,留言已经有人提问,说如果检索出来的结果很多该怎么办?因此,这一篇文章能补全这个知识点,让我们知道搜索引擎,广告引擎和推荐系统是如何处理检索结果的。
    2.索引构建和打分机制其实是有关系的。如果你在使用elastic search,并且使用了基于文档的索引拆分,然后又选择了系统自带的tf-idf或者bm25进行相关性打分,那么如果处理不当,相关性计算会变差。(因为idf没有在全局被更新)。
    3.在下一篇讲如何加速检索的方案,你会发现好些内容会和这篇文章有关。敬请期待。

    2020-04-20
    4
  • 黄海峰
    太难了,跟不上了,每次看到一堆公式里面的各种符号都是很排斥然后就放弃了阅读。。。数学果然是分水岭

    作者回复: 我当初在写这一篇的时候也很纠结,不确定是否应该保留还是删除。不过最后出于知识体系的完整性,我还是保留了这一篇,并尽可能用通俗的语言来描述。
    不过不用担心,这是唯一一篇有公式的文章,如果公式不好理解也没关系,你只要知道,打分排序的代价很大就好了。下一篇就会恢复熟悉的味道。
    还有,对于不清楚的地方,其实你可以找些时间,重新多读几次,也许哪天你就能取得意想不到的突破。

    2020-04-20
    1
    4
  • 一野(wx:abley1874)
    老师你好,我有一个问题想请教,log(10)为什么等于1呢?不应该是lg(10)才等于1吗?仅仅log(10)并未标明底数呀?其实在前面的表示时间复杂度上就有此疑问,但后面想想时间复杂度仅仅是表示的变化趋势并不是具体的值也就能说通了。但这儿确实有些不解

    作者回复: 你看得很细致也很严谨。的确严格来说,log是要标明底数的。但是你也会发现,许多场合都会直接写log n,因为在时间代价分析中,我们更看重的是量级,而不是常数级的倍数差异。因此以2为底还是以10为底,不会影响结论。另一方面,其实log不写底数时,大家约定俗成有默认底数(10或2都有,看具体上下文场景)。但的确写上会更清晰。谢谢你的细心指出,我看看后续优化一下。

    2020-05-10
    1
    2
  • 王坤祥
    使用堆排序替换全排后,打分应该是最耗时的。个人感觉是打分的计算过程复杂,涉及到较多的特殊运算。现代一般的CPU面向的不是纯“算数”了,在当前大数据环境下,大量的纯数据计算需要使用对“算数”优化过的GPU来提高计算速度,还有就是把大量单一的数据运算变为矩阵运算(并行),也会显著提高数据的运算速度。

    之前读过一些资料,机器学习不同于以往的编程,它是一种逆向思维--使用数据来编程;看到不少资料都把深度学习称为「用数据编程」,这是一种更高级的编程,也是未来新一代程序员需要掌握的方法。

    在深度学习中,理论上我们不需要关注从A->B的推理逻辑,只要有标签化的数据,通过深度学习就能找到从A->B的计算模型。也就是说,机器学习适用性会更好,代价就是训练数据需要花费很多的时间。

    一点点感悟,不知道自己理解的对不对。

    作者回复: 打分的确是非常耗时的过程,因此,我们需要有更多的手段来加速打分过程。GPU的发展,还有矩阵运算等都是可用的手段。

    还有,你提到了不少资料都把深度学习称为“用数据编程”。不过,我更愿意称为“用数据推导规则”。实际上,无论是机器学习还是深度学习,目前其实离我们真正期待的智能还有一段距离,从文中的简单例子你可以看到,机器学习更多是基于巨大的算力,用数据去拟合出一个有限的规则表达式,这个学习出来的规则其实还有许多可完善的地方,比如说人脸识别,有人就做过实验,给一个五官完整,但是比例和位置一看就不对的人脸图像给模型识别,结果模型识别为“真人”。因此,在人工智能方向上,我们还需要再往前走。

    2020-04-20
    1
  • 那时刻
    有两个疑惑的地方,请教下老师。
    1.文档频率df,随着文档数量的增多,df应该会重新计算么?如果是需要重新计算,也需要批量更新所有文档的分数吧?
    2.机器学习计算分数,随着数量量增大,模型会越来越准确。此时是否需要对于之前已经算过分数的文档重新计算分数呢?

    作者回复: 你的问题很好!
    1.对于df,的确会随着文档的增加而变化。因此是需要更新的。在倒排索引中,由于idf是和key存在一起的,因此,我们可以在文档变化时,对增量倒排索引的key中的idf值进行更新就可以了。不过要注意:如果使用了基于文档的水平拆分,那么增量索引只会在一个分片中生效。这样如果持续久了,idf值会不准,相关性计算精度会下降。因此,需要周期性地重构全量索引。
    2.机器学习的模型也是需要频繁更新的。一般来说是每天都会更新,还有系统为了更新及时,还会使用在线学习进行更实时的模型更新。不过,我前面说的“机器学习模型更新”,指的是因子和对应权重的更新,并不是你问题中说的“重新计算分数”。因为对一个文档和当前查询词的相关性打分过程,本来就是在查询发生时实时进行的,而不是离线算好的。因此不存在“重复计算分数”这个问题。

    2020-04-20
    1
  • mickey
    我觉得Top K 检索的过程的打分和排序,需要考虑数据量的大小和打分的规则综合考虑。

    作者回复: 其实就是要在业务需求和性能开销之间做权衡。因此我们需要掌握多种方法,以便在合适的场合使用合适的技术。

    2020-07-01
  • paulhaoyi
    关于问题2,机器学习打分,不只是可以考虑内容和检索词本身吧?还可以考虑用户,甚至环境,上下问,这里,是不是可以近似一个推荐逻辑了?感觉检索和推荐有点像EE问题的两端,一个倾向于精确些,一个倾向于扩展些?

    作者回复: 你说得很对。其实我在文中也提到了,机器学习打分,会考虑更多的维度了,包括“用户的历史点击行为”,这其实就是你说的“考虑用户”了。
    而关于搜索和推荐,它们的许多底层技术是相通的,区别在于两者的约束条件和目标不同。搜索引擎由于有着明确的用户输入和意图,因此对于query相关性的要求很高。而推荐引擎由于没有明确的用户输入信号,因此自由度会更大,可以从更多的维度去考虑检索和排序问题。

    2020-05-03
    1
  • pedro
    问题1,耗时的是打分,尤其是引入了深度学习的计算量大大超过了排序。
    问题2,个人觉得机器学习打分的一个不可忽视的优点,那就是它会根据用户行为不断进行学习,不断优化自己,从而获得更好的用户体验。暂时没有使用过,老师可以后面举一个机器学习打分的具体算法和例子吗,机器学习毕竟有些笼统。

    作者回复: 1.的确,最耗时的步骤其实是打分,因此,我们如果想加快检索效率的话,如何优化打分过程就是一个很重要的方向。
    2.机器学习打分的例子,的确文中没有说得太详细。其实机器学习的关键就是寻找因子(也就是特征),以及学习权重的过程。对于机器学习和特征工程方向,这其实是另一个领域,也许有机会可以在其他地方再具体描述一下。

    2020-04-20
  • 黄海峰
    第一个tfidf怎么算的?文档一不是10*10+10*1=110,文档二不是1*10+100*1=110吗?

    作者回复: 这一部分我写得有些简略。文中有一句:“我们在使用TF和IDF时,都会使用对数函数进行平滑处理”,在示意图中有具体的处理方法。因此,“极客”的出现次数是10,但是TF值是1+log(10) =2。
    同理,“时间”的出现次数是10,故TF值也是2。
    故文档1的分数是2*10+2*1=22

    2020-04-20
  • 范闲
    1.tf-idf和BM25现在可以用来做召回
    2.在利用机器学习排序的时代,tdidf和BM25可以作为一个排序因子

    作者回复: 1.你说到了很有意思的一点,tf-idf和bm25现在可以用来做召回。下一讲我就会和大家介绍。
    2.的确是,机器学习的用法会很灵活,因子可以有很多,tfidf和bm25都可以当做排序因子来使用。

    2020-04-20
收起评论
11
返回
顶部