BM25算法以及变种算法简介

Okapi BM25，一般简称 BM25 算法，在 20 世纪 70 年代到 80 年代，由英国一批信息检索领域的计算机科学家发明。这里的 BM 是 “最佳匹配”（Best Match）的缩写，Okapi 是第一个使用这种方法的信息获取系统的名称。在信息检索领域，BM25 算法是工程实践中举足轻重的重要的 Baseline 算法。迄今为止距 BM25 的提出已经过去三十多年，但是这个算法依然在很多信息检索的任务中表现优异，是很多工程师首选的算法之一。

BM25（Best Match 25）是一种用于信息检索的统计算法，主要用于计算查询文本与文档的相关性评分。它考虑了文档中的词频（）和逆文档频率（）等因素。主要对对 Query 进行语素解析，生成语素 (词)；然后，对于每个搜索结果 ，计算每个语素  与  的相关性得分，最后，将 “一个 各个  相对于 的相关性得分” 加权求和，从而得到“ 与  的相关性得分”。

以下是 BM25 的一些重要的变种和衍化算法：

BM25 详解

首先，简单概括 BM25 究竟作何用途。BM25 算法实质上是一个用于信息检索中，对给定查询（query）和若干 “相关” 文档（document）进行相关性排序打分的排序函数。严格来讲，这不是一个打分函数，而是一个家族的一系列评分函数，因为它的提出并非一蹴而就的事情，它的发明经过了若干试验迭代演进。一般情况下，这个相关性打分是一个类似 TF-IDF 的基于统计计数的无监督学习过程。

BM25 算法其主要思想可简述如下：对 query 进行特征提取分解，生成若干特征项（词）；然后对于每个搜索结果 D，计算每个特征与 D 的相关性得分，最后，将 相对于 D 的相关性得分进行加权求和，从而得到与的相关性得分。

BM25 算法的一般表示可简写为如下形式：

其中， 表示 ,  表示  分解之后的一个特征项（对中文而言我们可以把对 query 的分词作为基本特征项）， 表示一个搜索结果文档； 表示特征 的权重；表示特征项  与文档  的相关性得分。

上面这个一般的式子里的 和 的具体计算，都是基于词袋方法的词频计数，它不考虑多个搜索词在文档里的关联性，只考虑它们各自的出现次数。 下面我们来考察以上得分函数的两个量 和  该如何设计和计算。 首先来看如何定义 ，考察一个特征词的权重，方法比较多，较常用的是 IDF，BM25 选择的是 Robertson-Sparck Jones IDF:

其中， 为文档集合中的全部文档数， 为包含  的文档数。 公式指出， 出现在越多的文档中，则  的权重则越低。这里个定义有个问题，那就是，如果一个词在超过半数的文档里出现，则  为负值，于是这个词对 BM25 分数的贡献是负的。一般不希望这样的特性，所以当  为负数时，可将其置为 0，或者一个比较小的正数，或者改用一种平滑过渡到 0 的函数形式。

我们再来考察特征项 与文档  的相关性得分 。 比较朴素的考虑可以用特征词的文档词频来简单表示 ，但这种直观的想法不可避免导致长文本中，词的频度普遍较高，最终相关性得分会过度倾向于长文本，显然不尽合理；另一方面，不难想象到，某个词对文档的贡献不应该无限度地随词频增长而线性增加，当该词的词频高于某个程度就应该趋于饱和，而不应该让其得分贡献无限度增大，从而在整个得分求和式子中占支配地位。 基于以上两方面的考虑，BM25 采取了以下方式来计算 ：

这里， 为 在  中的文档频率， 为文档长度， 为文档集合中的平均长度， 和  为可自由调节的超参数，一般取值范围是 ， 关于 的函数是一个 “饱和” 的递增函数，使得文档词频增长对相关性得分增长成为非线性的。

从 的定义中不难看出，超参数  起着调节特征词文本频率尺度的作用， 取  意味着算法退化为二元模型（不考虑词频），而取较大的值则近似于只用原始的特征词频。超参数  一般称作文本长度的规范化，作用是调整文档长度对相关性影响的大小。 越大，文档长度的对相关性得分的影响越大，而文档的相对长度越长， 值将越大，则相关性得分会越小。这可以理解为，当文档相对较长时，包含  的机会越大，因此，同等  的情况下，长文档与  的相关性应该比短文档与  的相关性弱。 至此，综合上述讨论，BM25 的一般形式可完整表示如下：

此外，若 query 比较长，且某些 term 在 query 中出现频率较高，我们理应考虑这些 term 的重要性也该相应提高，但同样应该有类似 term 相对文档的饱和增长设置来约束 query 中的 term 频率增长。这里我们将类似的权重策略用于 query 中的特征项，得到：

其中， 为特征项  在查询  中的频率，超参数  的作用依然是调节特征词在 query 文本频率尺度，此时对 query 进行长度规范化却是不必要的，因为对所有候选检索结果而言，query 是先有的固定好的。 从以上对 BM25 的完整讨论，我们知道了 BM25 其实是一个（准确说，是一系列）经验公式，这里面的每一个环节都是经过很多研究者的迭代而逐步发现的。很多研究在理论上对 BM25 进行了建模，从 “概率相关模型”（Probabilistic Relevance Model）入手，推导出 BM25 其实是对某一类概率相关模型的逼近，对此我还没有详尽研究，就无法进一步展开论述了。从结果上看，我们应该明了 BM25 权重计算公式，已经在众多的数据集和搜索任务上，被极其高频广泛和成功地使用。

由 K  的表达式可知，的作用是调整 对 “相关性的影响” 的大小，即越大，对 “相关性得分的影响” 越大；而 越长， 值越大，相关性得分越小。 可如下解释，当文档较长时，包含的机会越大，则同等的情况下，“长文档与的相关性” 应该比 “短文档与的相关性” 弱。

BM25 的变种和改进

BM25 算法公式，通过使用不同的特征项的分析方法、特征项权重判定方法，以及特征项与文档的相关度计算方法，都留有较强的灵活性，自然会促使后续的研究者在此基础上，提出更具个性化的不同的搜索相关性得分算法。

所有 BM25 后续改进中，Lv & Zhai 两位研究者的工作最为深入和全面。

BM25L

Lv & Zhai 观察到 BM25 公式中的文本长度规范化项（L_d/L_{avg}）使得模型得分过于偏好长度较短的文档。他们在 “When documents are very long, BM25 fails!” 一文中提出了 BM25L 算法，用来弥补 BM25 的这一不足。 首先，BM25L 对特征词的 IDF 权重项也做了小小改变，让这一项不会取到负值：

然而，BM25L 更感兴趣的是调节 BM25 中这一项，以避免算法对过长文本的惩罚。Lv & Zhai 通过对加上一个正值的常数来实现这一点，只需这一个小操作便可以起到让与之前比较，向偏好取更小的值转移（即较大的分母，较长的文本）。 因此，可将 BM25L 算法写作如下：

同 BM25 公式记号保持一致，这里

BM25+

Lv & Zhai 进一步发现对过长文本的惩罚不止出现在 BM25 算法中，还出现在许多其他的排序函数中，他们为此提出了一个一般性的解决方案，即为每一个 query 中出现于文本的特征项相关性得分设置一个下界。此时，不论文本多长，某个搜索特征项至少贡献了一个正的常数相关性得分。他们这个做法略不同于之前的 BM25L，而是在乘 IDF 之前对整个  加上一个常数 ：

BM25-adpt

之前的 BM25 算法和相关改进，都忽略了对超参数 的考察。Lv & Zhai 在不同的 BM25 相关研究工作中，发现对实际应用而言，全局的  参数不及特征项相关的（term-specific）参数使用起来高效。他们用随机理论中的信息增益和散度等概念，实现了去 “超参化” 的目标，即 跟随  不同而变化，可以直接计算获得，这个算法被称为 BM25-adpt。BM25-adpt 的具体推导比上面的 BM25 变种算法要稍微复杂一些，要讲清楚其中的想法和细节，需要另辟篇幅，只好以后得空的时候补缀上，这里就不能多加介绍了