BM25算法以及变种算法简介

深入理解TF-IDF、BM25算法与BM25变种：揭秘信息检索的核心原理与应用
原文链接： https://xie.infoq.cn/article/8b7232877d0d4327a6943e8ac

BM25算法以及变种算法简介

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

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

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

• BM25L（BM25 with Length Normalization）：BM25L 算法是在 BM25 算法的基础上，考虑了文档长度对得分的影响，通过引入文档长度规范化项来平衡不同长度的文档，目的是降低文档长度对相关性评分的影响，它可以通过对 BM25 公式中的长度归一化因子进行调整来实现，优化点改进在于更全面地考虑文档特征，以更准确地衡量文档与查询之间的相似度。
• BM25+：BM25+是一种改进的 BM25 算法，加入了查询项权重的计算，以更好地处理查询中的重要词项，这个惩罚项用于调整较长的文档的相关性评分，以避免较长的文档在评分中占据过大的比重。优化点改进在于对查询项的权重进行动态调整，以提高信息检索的准确性和性能。
• BM25T（BM25 with Term Weights）：BM25T 是一种将词权重引入 BM25 的方法，通过考虑词频、逆文档频率以及文档长度等特征，以确定每个词项在文本中的重要性，它允许用户为查询中的每个词分配不同的权重，以更好地反映查询的重要性。优化点改进在于更精细地衡量词项的重要性，以提高信息检索的准确性。
• $T{F}_{1\circ \delta \circ p}\times IDF$：是一种将词频和词位置信息综合考虑的改进算法。其中，TF表示词频，δ函数表示词位置的影响，p表示词位置权重，IDF表示逆文档频率,通过p和δ来调整词频和逆文档频率的权重，以提高对稀有词项的重视程度。这种算法可以根据词在文档中的位置给予
• BM25F：BM25F 是一种将多个字段考虑在内的改进算法。在信息检索中，通常会有多个字段（如标题、正文、标签等）的相关性需要评分。BM25F 通过对多个字段的评分进行加权求和，可以更好地考虑文档的不同部分对匹配得分的影响，从而得出最终的相关性评分。优化点改进在于更灵活地处理文档的不同部分，以提高信息检索的准确性。

BM25 详解

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

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

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

$$score(q,d)=\sum _i{W}_i\cdot R(q_i,d)$$

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

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

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

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

这里，$f(q_i,d)$ 为$ q_i$ 在 $d$ 中的文档频率，$L_d$ 为文档长度，$L_{avg}$ 为文档集合中的平均长度，$k_1$ 和 $b$ 为可自由调节的超参数，一般取值范围是 $k_1\in [1.2,;2.0]$，$b=0.75,R(q_i,d)$ 关于$ \tilde{tf}(q_i, d)$ 的函数是一个 “饱和” 的递增函数，使得文档词频增长对相关性得分增长成为非线性的。

从$ \tilde{tf}(q_i, d)$ 的定义中不难看出，超参数 $k_1$ 起着调节特征词文本频率尺度的作用，$k_1$ 取 $0$ 意味着算法退化为二元模型（不考虑词频），而取较大的值则近似于只用原始的特征词频。超参数 $b$ 一般称作文本长度的规范化，作用是调整文档长度对相关性影响的大小。$b$ 越大，文档长度的对相关性得分的影响越大，而文档的相对长度越长，$\widetilde{tf}(q_i,d)$ 值将越大，则相关性得分会越小。这可以理解为，当文档相对较长时，包含 $q_i$ 的机会越大，因此，同等 $tf(q_i,d)$ 的情况下，长文档与 $q_i$ 的相关性应该比短文档与 $q_i$ 的相关性弱。
至此，综合上述讨论，BM25 的一般形式可完整表示如下：
$$score(q,d)=\sum _i\log \frac{N-n(q_i)+0.5}{n(q_i)+0.5}\cdot \frac{(k_1+1)\cdot tf(q_i,d)}{k_1(1-b+b\cdot \frac{L_d}{L_{avg}})+tf(q_i,d)}$$

此外，若 query 比较长，且某些 term 在 query 中出现频率较高，我们理应考虑这些 term 的重要性也该相应提高，但同样应该有类似 term 相对文档的饱和增长设置来约束 query 中的 term 频率增长。这里我们将类似的权重策略用于 query 中的特征项，得到：
$$score(q,d)=\sum _i\log \frac{N-n(q_i)+0.5}{n(q_i)+0.5}\cdot \frac{(k_1+1)\cdot tf(q_i,d)}{k_1(1-b+b\cdot \frac{L_d}{L_{avg}})+tf(q_i,d)}\cdot \frac{(k_3+1)\cdot tf(q_i,q)}{k_3+tf(q_i,q)}$$

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

BM25算法简易

一条 Query 与搜索结果的任意 doc 之间相关性分数:
$$Score(Q,d)=\sum _i^n{W}_{i}R(q_i,d)$$

上式， $Q$ 表示$Query$， $q_i$ 表示根据 $Q$ 解析获得的语素， $d$ 表示搜索结果的一条文档， $W_i$ 表示语素 q_i的权重， R(q_i, d)表示q_i和d的相关性得分。
（1） W_i的定义
定义一个语素与一个文档的相关性权重，较常用的是
$IDF(q_i)=log\frac{N-n(q_i)+0.5}{n(q_i)+0.5}$
上式，$N$ 是索引中的全部文档数，$n(q_i)$是包含 $q_i$的文档数。
很显然， $n(q_i)$与$IDF(q_i)$成反相关，即当给定的文档集合里，很多文档都包含 $q_i$时， $q_i$的区分度就不高，则使用$q_i$来判断相关性的重要度就较低。
（2） $R(q_i,d)$ 的定义
定义一个语素与一个文档的相关性得分，一般形式如下
$R(q_i,d)=\frac{f_i(k_1+1)}{f_i+K}\frac{q{f}_i(k_2+1)}{q{f}_i+k_2}$
$K=k_1(1-b+b\frac{dl}{avgdl})$
上式$k_1$ ，$k_2$ ，$b$ 是可根据经验设置的调节因子，一般 $k_1\in [1.2,2]$ ， $b=0.75$ ； $f_i$ 是 $q_i$ 在 $d$ 中出现的频率， $q{f}_i$ 为 $q_i$ 在 $Q$ 中的出现频率。 $dl$ 为 $d$ 的长度， $avgdl$ 为文档集中所有 $d$ 的平均长度。在多数情况下， $q_i$ 在$Q$中只会出现一次，即 $q{f}_i=1$，公式可简化为：

$$R(q_i,d)=\frac{f_i(k_1+1)}{f_i+K}$$

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

BM25 的变种和改进

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

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

BM25L

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

$$\text{IDF}(q_i)=\log \frac{N+1}{n(q_i)+0.5}$$

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

$$score(q,d)=\sum _i\log \frac{N+1}{n(q_i)+0.5}\cdot \frac{(k_1+1)\cdot (\widetilde{tf}(q_i,d)+\delta )}{k_1+\widetilde{tf}(q_i,d)+\delta }$$

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

$$\widetilde{tf}(q_i,d)=\frac{tf(q_i,d)}{1+b(\frac{L_d}{L_{avg}}-1)}$$

BM25+

Lv & Zhai 进一步发现对过长文本的惩罚不止出现在 BM25 算法中，还出现在许多其他的排序函数中，他们为此提出了一个一般性的解决方案，即为每一个 query 中出现于文本的特征项相关性得分设置一个下界。此时，不论文本多长，某个搜索特征项至少贡献了一个正的常数相关性得分。他们这个做法略不同于之前的 BM25L，而是在乘 IDF 之前对整个 $R(q_i,d)$ 加上一个常数 $\delta$：
$$score(q,d)=\sum _i\log \frac{N+1}{n(q_i)+0.5}\cdot \left(\frac{(k_1+1)\cdot \widetilde{tf}(q_i,d)}{k_1+\widetilde{tf}(q_i,d)}+\delta \right)$$

BM25-adpt

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

小结

除了以上探讨的几种 BM25 的衍化算法，其他重要的变种还有 BM25T、TF1∘δ∘p×IDF\text{TF}_{1\circ\delta\circ p}\times \text{IDF}、BM25F 等等，在许多不同的场景都表现除了优于原始 BM25 算法的效果。当然，这些表现的优越性因具体数据集和相应 search 任务场景而异。
更多优质内容请关注公号：汀丶人工智能；会提供一些相关的资源和优质文章，免费获取阅读。
参考链接：
bm25 算法：https://blog.csdn.net/cymy001/article/details/91972337.
Okapi BM25 算法：https://www.cnblogs.com/geeks-reign/p/Okapi_BM25.html
TF-IDF 算法 https://www.cnblogs.com/geeks-reign/p/TF-IDF.html
[1]. wikipedia: Okapi_BM25, https://en.wikipedia.org/wiki/Okapi_BM25.
[2]. Okapi BM25: a non-binary model, https://nlp.stanford.edu/IR-book/html/htmledition/okapi-bm25-a-non-binary-model-1.html.
[3]. Trotman, A., Puurula, A. Burgess, B., Improvements to BM25 and Language Models Examined.
[4]. Lv, Y., C. Zhai, When documents are very long, BM25 fails! SIGIR 2011, p. 1103-1104.
[5]. Lv, Y., C. Zhai, Lower-bounding term frequency normalization, CIKM 2011, p. 7-16.
[6]. Lv, Y., C. Zhai, Adaptive term frequency normalization for BM25, CIKM 2011, p. 1985-1988.