极客时间已完结课程限时免费阅读

032 | 经典搜索核心算法：BM25及其变种（内附全年目录）

032 | 经典搜索核心算法：BM25及其变种（内附全年目录）-极客时间

032 | 经典搜索核心算法：BM25及其变种（内附全年目录）

2017-11-15 洪亮劼 来自北京
《AI技术内参》
课程介绍

讲述：初明明

时长09:45大小4.46M

周一我们讲了 TF-IDF 算法和它的四个变种，相对于 TF-IDF 而言，在信息检索和文本挖掘领域，BM25 算法则更具理论基础，而且是工程实践中当仁不让的重要基线（Baseline）算法 。BM25 在 20 世纪 70 年代到 80 年代被提出，到目前为止已经过去二三十年了，但是这个算法依然在很多信息检索的任务中表现优异，是很多工程师首选的算法之一。
今天我就来谈谈 BM25 算法的历史、算法本身的核心概念以及 BM25 的一些重要变种，帮助你快速掌握这个信息检索和文本挖掘的利器。

BM25 的历史

BM25，有时候全称是 Okapi BM25，是由英国一批信息检索领域的计算机科学家开发的排序算法。这里的“BM”是“最佳匹配”（Best Match）的简称。
BM25 背后有两位著名的英国计算机科学家。第一位叫斯蒂芬·罗伯逊（Stephen Robertson）。斯蒂芬最早从剑桥大学数学系本科毕业，然后从城市大学（City University）获得硕士学位，之后从伦敦大学学院（University College London）获得博士学位。斯蒂芬从 1978 年到 1998 年之间在城市大学任教。1998 年到 2013 年间在微软研究院剑桥实验室工作。我们之前提到过，美国计算机协会 ACM 现在每三年颁发一次“杰拉德·索尔顿奖”，用于表彰对信息检索技术有突出贡献的研究人员。2000 年这个奖项颁给斯蒂芬，奖励他在理论方面对信息检索的贡献。BM25 可谓斯蒂芬一生中最重要的成果。
另外一位重要的计算机科学家就是英国的卡伦·琼斯（Karen Spärck Jones）。周一我们在 TF-IDF 的文章中讲过。卡伦也是剑桥大学博士毕业，并且毕生致力于信息检索技术的研究。卡伦的最大贡献是发现 IDF 以及对 TF-IDF 的总结。卡伦在 1988 年获得了第二届“杰拉德·索尔顿奖”。

BM25 算法详解

现代 BM25 算法是用来计算某一个目标文档（Document）相对于一个查询关键字（Query）的“相关性”（Relevance）的流程。通常情况下，BM25 是“非监督学习”排序算法中的一个典型代表。
顾名思义，这里的“非监督”是指所有的文档相对于某一个查询关键字是否相关，这个信息是算法不知道的。也就是说，算法本身无法简单地从数据中学习到相关性，而是根据某种经验法则来“猜测”相关的文档都有什么特质。
那么 BM25 是怎么定义的呢？我们先来看传统的 BM25 的定义。一般来说，经典的 BM25 分为三个部分：
单词和目标文档的相关性
单词和查询关键词的相关性
单词的权重部分
这三个部分的乘积组成某一个单词的分数。然后，整个文档相对于某个查询关键字的分数，就是所有查询关键字里所有单词分数的总和。
我们先从第一部分说起，即单词和目标文档的相关性。这里相关性的基本思想依然是“词频”，也就是 TF-IDF 里面 TF 的部分。词频就是单词在目标文档中出现的次数。如果出现的次数比较多，一般就认为更相关。和 TF-IDF 不同，BM25 最大的贡献之一就是挖掘出了词频和相关性之间的关系是非线性的，这是一个初看有违常理但细想又很有道理的洞察。
具体来说，每一个词对于文档相关性的分数不会超过一个特定的阈值。这个阈值当然是动态的，根据文档本身会有调整。这个特征就把 BM25 里的词频计算和一般的 TF 区分开了。也就是说，词频本身需要“标准化”（Normalization），要达到的效果是，某一个单词对最后分数的贡献不会随着词频的增加而无限增加。
那 BM25 里词频的标准化是怎么做的呢？就是某一个词的词频，除以这个词的词频加上一个权重。这个权重包含两个超参数（Hyper-parameter），这些超参数后期是可以根据情况手动调整的。这个做法在非监督的排序算法中很普遍。同时，这个权重还包括两个重要信息：第一，当前文档的长度；第二，整个数据集所有文档的平均长度。
这几个因素混合在一起，我们就得到了一个新的词频公式，既保证单词相对于文档的相关度和这个单词的词频呈现某种正向关系，又根据文档的相对长度，也就是原始长度和所有文档长度的一个比值关系，外加一些超参数，对词频进行了限制。
有了单词相对于文档的相关度计算公式作为基础，单词相对于查询关键字的相关度可以说是异曲同工。首先，我们需要计算单词在查询关键字中的词频。然后，对这个词频进行类似的标准化过程。
和文档的标准化过程唯一的区别，这里没有采用文档的长度。当然，对于查询关键字来说，如果需要使用长度，也应该是使用查询关键字的长度和平均长度。但是，根据 BM25 经典公式来说，这一部分并没有使用长度信息进行重新标准化。
接着我来谈谈最后一个部分，单词权重的细节，通常有两种选择。
第一种选择就是直接采用某种变形的 IDF 来对单词加权。一般来说，IDF 就是利用对数函数（Log 函数）对“文档频率”，也就是有多少文档包含某个单词信息进行变换。这里回顾一下周一讲的内容，IDF 是“文档频率”的倒数，并且通过对数函数进行转换。如果在这里使用 IDF 的话，那么整个 BM25 就可以看作是一个某种意义下的 TF-IDF，只不过 TF 的部分是一个复杂的基于文档和查询关键字、有两个部分的词频函数。
第二种单词的权重选择叫作“罗伯逊 - 斯巴克 - 琼斯”权重（Robertson-Spärck-Jones），简称 RSJ 值，是由计算机科学家斯蒂芬·罗伯逊和卡伦·琼斯合作发现。我们刚才讲过，这两位都是重要的信息检索学术权威。这个权重其实就是一个更加复杂版本的 IDF。一个关键的区别是 RSJ 值需要一个监督信息，就是要看文档对于某个查询关键字是否相关，而 IDF 并不需要。
对比以上两种思路，在很多情况下，利用 IDF 来直接进行单词权重的版本更加普遍。如果在有监督信息的情况下，RSJ 值也不失为一个很好的选择。
通过这里简单的介绍，我们可以很容易地发现，BM25 其实是一个经验公式。这里面的每一个成分都是经过很多研究者的迭代而逐步发现的。很多研究在理论上对 BM25 进行了建模，从“概率相关模型”（Probabilistic Relevance Model）入手，推导出 BM25 其实是对某一类概率相关模型的逼近。对这一部分我在这里就不展开论述了。需要你记住的是，BM25 虽然是经验公式，但是在实际使用中经常表现出惊人的好效果。因此，很有必要对这一类文档检索算法有所了解。

BM25 算法变种

由于 BM25 的情况，一方面是经验公式，另一方面是某种理论模型的逼近，这样就出现了各式各样的 BM25 变种。这里我仅仅介绍一些有代表性的扩展。
一个重要的扩展是 BM25F，也就是在 BM25 的基础上再多个“域”（Field）文档上的计算。这里“域”的概念可以理解成一个文档的多个方面。比如，对于很多文档来说，文档包括标题、摘要和正文。这些组成部分都可以认为是不同的“域”。那么，如何结合不同的“域”，让文档的相关性能够统一到一个分数上就是 BM25F 的核心内容。
具体来说，BM25F 对于 BM25 的扩展很直观。那就是每一个单词对于文档的相关性是把各个域当做一个“小文档”的加权平均。也就是说，我们先把每个域当做单独的文档，计算词频，进行标准化。然后集合每个域的值，进行加权平均，再乘以词的权重（我们上面提到了，用 IDF 或者是 RSJ 值）。
另外一个重要的扩展就是把 BM25 和其他文档信息（非文字）结合起来。这个想法是在“学习排序”（Learning To Rank）这一思路出现以前的一种普遍的做法，往往就是用线性加权的形式直接把各种信息相结合。例如，在 21 世纪初期比较流行的做法是用 BM25 和 PageRank 的线性结合来确定网页的相关度。这里面，BM25 是和某个查询关键字有联系的信息，而 PageRank 则是一个网页的总体权重。

小结

今天我为你讲了文档检索领域或者说搜索领域里最基本的一个技术：BM25。我们可以看到，BM25 由三个核心的概念组成，包括词在文档中相关度、词在查询关键字中的相关度以及词的权重。BM25 是一个长期积累的经验公式，也有很深的理论支持，是一个强有力的非监督学习方法的文本排序算法。
一起来回顾下要点：第一，简要介绍了 BM25 的历史。第二，详细介绍了 BM25 算法的三个主要组成部分。第三，简要地介绍了 BM25 的一些变种 。
最后，给你留一个思考题，虽然 BM25 是非监督的排序方法，并且我们提到其中有一些超参数，那么是否可以通过机器学习的手段来学习到这些超参数的最佳取值呢？
欢迎你给我留言，和我一起讨论。
分享给需要的人，Ta购买本课程，你将得29元
生成海报并分享

赞 1

提建议

© 版权归极客邦科技所有，未经许可不得传播售卖。 页面已增加防盗追踪，如有侵权极客邦将依法追究其法律责任。
上一篇
031 | 经典搜索核心算法：TF-IDF及其变种
下一篇
033 | 经典搜索核心算法：语言模型及其变种
 写留言

精选留言(8)

  • 小田
    2020-01-14
    老师文字表达思路很清晰，但是一些量还是用公式表达更一目了然
    4
  • L
    2021-02-19
    BM25中的25指什么
    2
  • new
    2018-07-04
    这里的超参数是对词频进行缩放，那么不同的缩放效果会对结果产生什么影响呢？如果用机器学习调参，那么应该对文档相关性有个评估标准，这样就可以用grid search或者其它方法搜索。
    2
  • 鬼猫猫
    2017-12-14
    看了全年课表，简直太值了！

    作者回复: 谢谢。

    2
  • Geek_035cac
    2023-01-12 来自北京
    老师可以提供公式嘛，这样表述不太容易理解
  • 付雪林
    2022-12-28 来自北京
    看了全年的课程表，非常感兴趣，这是书还是课程啊？怎么持续看啊？
  • rookie
    2019-05-27
    可以用网格搜索
  • 庄小P
    2019-05-26
    写得太棒了，循序渐进了解每个算法是怎么一步步改进的，对自己开拓思维很有帮助