526互联

深入理解TF-IDF、BM25算法与BM25变种：揭秘信息检索的核心原理与应用

发布时间 2024-01-08 11:49:32作者: 汀、人工智能

深入理解TF-IDF、BM25算法与BM25变种：揭秘信息检索的核心原理与应用

1.文本特征表示方法: TF-IDF

在信息检索, 文本挖掘和自然语言处理领域, IF-IDF 这个名字, 从它在 20 世纪 70 年代初被发明, 已名震江湖近半个世纪而不曾衰歇. 它表示的简单性, 应用的有效性, 使得它成为不同文本处理任务文本特征权重表示的首选方案. 如果要评选一个 NLP 领域最难以被忘记的公式, 我想, TF-IDF 应该是无可争议的第一和唯一. 虽然在以上领域，目前出现了不少以深度学习为基础的新的文本表达和权重（Weighting）表示方法，但是 TF-IDF 作为一个古董方法，依然在很多应用中发挥着不可替代的作用.
TF-IDF 一般是文本处理领域初学者入门阶段就会了解到的概念, 了解和掌握 TF-IDF 算法, 能够帮助初学者更快地理解其它更加深入复杂的文本挖掘算法和模型.
以下我会从 TF-IDF 的应用背景, TF-IDF 的发现历史, 算法公式及其变种, TF-IDF 的应用几个方面来介绍和展开讨论.

1.1 向量空间 (VSM) 模型

一个自然语言的文本一般表现为由文字, 数字和标点符号和少数特殊符号组成的字符串. 文字或字符等最基本的文本元素自底向上, 组成词, 进而形成短语, 句子, 段落和篇章. 要让计算机能高效地处理自然文本, 就需要找到一种合理的形式化的文本表示方法, 这种表示方法一方面能尽可能完整真实地反应文档的内容 (主题, 领域或结构信息), 另一方面还需要对不同的文档具有区分能力. 比较理想的形式化表示, 不难想到能否用 "向量" 来表示文档, 并尝试用现代数学工具(方法) 来解决信息检索或其他文本处理相关问题.
TF-IDF 正是源于一个最经典也是最古老的信息检索模型, 即 "向量空间模型" (Vector Space Model, VSM). VSM 是 20 世纪 60 年代末期由 G. Salton 等人提出的, 最早用在 SMART 信息检索系统中, 目前已经成为自然语言处理中的常用模型.
定义 (向量空间模型 (VSM)) 给定一个文档 $D(t_1, w_1; t_2, w_2;\cdots; t_n, w_n)(t_k, w_k)$分别为一个特征项及其对应的权重), $D$符合以下两条约定:
  (1). 各个特征项 $t_k(1\leq k \leq n)$互异;
  (2). 各个特征项 $t_k$无先后顺序关系 (即不考虑文档内部结构).

在以上两个约定下, 可以把特征项 $t_1, t_2, \cdots, t_n$看成一个 $n$维坐标系, 而权重 $w_1, w_2, \cdots, w_n$为相应的坐标值, 因此, 一个文本就表示为一个 $n$维空间中的一个向量. 我们称 $D=D(w_1, w_2, \cdots, w_n)$为文本 $D$的向量表示或向量空间模型.
采用向量空间模型进行文本表示时, 需要经由以下两个主要步骤:
  (1). 为特定任务生成文本表示所需要的特征项序列 $D=(t_1, t_2, \cdots, t_d)$;
  (2). 一举文本特征项序列, 对各个文档进行权重计算, 赋值, 规范化等处理, 将其转化为机器学习算法所需要的特征向量.

有了向量的表达, 文档相关度往往可以用向量在某种意义上的 “相似度” 来进行近似, 比如余弦相似性 (Cosine Similarity) 或者是点积 (Dot Product). 这样, 相关度就可以用一个值来进行表达. 不管是余弦相似度还是点积都能够从线性代数或者几何的角度来解释计算的合理性.

1.2 TF-IDF

文本向量化的尝试从 20 世纪 70 年代就已经开始, 1971 年, 美国康奈尔大学教授 Gerard Salton 发表了 "The SMART Retrieval System—Experiments in Automatic Document Processing" 一文, 文中首次提到了把查询关键字和文档都转换成 "向量", 并且给这些向量中的元素赋予不同的值. 这篇论文中描述的 SMART 检索系统, 特别是其中对 TF-IDF 及其变种的描述成了后续很多工业级系统的重要参考.
1972 年, 英国的计算机科学家 Karen Spärck Jones 在 "A Statistical Interpretation of Term Specificity and Its Application in Retrieval" 一文中第一次详细地阐述了 IDF 的应用. 其后 Jones 又在 "Index Term Weighting" 一文中对 TF 和 IDF 的结合进行了论述. 可以说, Jones 是第一位从理论上对 TF-IDF 进行完整论证的科学家, 因此后世也有很多人把 TF-IDF 的发明归结于 Jones.

回顾上面的向量空间模型, 可知关于文档的向量表示, 其实就是对预先定义 (设计) 好的特征项, 赋予其 "适当" 的权重. 特征权重用于衡量某个特征项在文档表示中的重要程度或区分能力的强弱. 权重计算的一般方法是利用文本的统计信息, 主要是词频, 给特征项赋予一定的权重.

最朴素的想法, 把文档向量设为 V 维度。这里的 V 是整个词汇表 (Vocabulary) 的总长度. 对于这个向量中的每一个维度, 都表示英文中的一个单词, 没有重复. 可以看到, 在这样的情况下, 如果当前的词出现在这个向量所对应的文档或者关键字里, 就用 1$1$ 来表达; 如果这个词没出现, 就用 $0$ 来表达. 这就是给每个维度赋值 (Weighting) 的最简单的方法. 形式化的表示如下:

$$w_{i,j} = \begin{cases} 1, & \text{if $tf_{i,j} > 0$} \ 0, & \text{else} \end{cases}$$

这里 $w_{i,j}$表示特征项 ti$t_i$在文本 Dj$D_j$中的权重. 这种表示方法被称为布尔权重 (Boolean weighting), 布尔权重把文本中的每个特征等同对待, 无法体现特征项在文本中的作用程度, 因而在实际中 $0, 1$值逐渐被更精确的特征项的频率所代替.
更进一步不难想到, 如果一个特征词在文本中出现的频数高, 它的重要性也应该相应拔高, 此使特征权重可以用

$$w_{i,j}=tf_{i,j}$$

表示, 这里 tfi,j$tf_{i,j}$表示特征项 ti$t_i$在文本 Dj$D_j$中的频数. 这种绝对词频 (term frequency, TF) 方法中, 无法体现低频特征的区分能力, 因为有些特征词出现次数很多, 但并不能很好地代表文本特征 (比如很多 generic 的常用词), 而有些特征项虽然频率较低, 但表征能力却很强.
倒排文档频度 (inverse document frequency, IDF) 方法是 1972 年 Karen Spärck Jones 提出的计算词与文本相关权重的经典计算方法, 其在信息检索具有重要重要地位.

$$w_{i,j}=\log\frac{N}{n_i}$$

$n_i$ 是全部文档集中出现特征项 $t_i$ 的文档数. 该方法指出稀有特征比常用特征有更重要的信息. 在实际使用中, 常用公式 $L + \log((N-n_i)/n_i)$替代, 其中, 常数 L$L$ 为经验值, 一般取 $1$. IDF 方法的权重随着包含某个特征的文档数量 $n_i$ 呈反向变化, 在极端情形下, 只在一篇文档中出现的特征含有最高的 IDF 值.
本文下面要介绍的 TF-IDF 就是在向量空间模型的假设下的一种更加复杂的, 将绝对词频 (TF) 和逆文档频率 (IDF) 二者结合起来的权重计算方法:

$$w_{i,j}=tf_{i,j} \cdot \log \frac{N}{n_i}$$

这个式子表面特征权重与特征项在文档里出现的频率成正比, 与在整个语料中含有该特征项的文档数成反比. 这个综合考虑了高频词与稀有词的公式, 现在看来只是一个略显朴素经验公式, 但它至今仍然在众多文档特征权重计算方法中暂居着难以被取替的地位.

1.3 TF-IDF 的变种和改进

经典的 TF-IDF 算法想法简明而自然, 在过去的很长一段时间里, 研究人员和工程师开发出了很多种 TF-IDF 的变种. 以下是几种常见的变形形式:

  1. 文本长度归一化.

$$w_{i,j}=\frac{tf_{i,j} \cdot \log (N/n_i)}{\sqrt {\sum_{t_i \in D_j} \left[tf_{i,j} \cdot \log(N/n_i) \right] ^ 2}}$$

或者

$$w_{i,j}=\frac{tf_{i,j} \cdot \log (N/n_i + 0.01)}{\sqrt {\sum_{t_i \in D_j} \left[tf_{i,j} \cdot \log(N/n_i + 0.01) \right] ^ 2}}$$

文档向量进行标准化，使得这些向量能够不受向量里有效元素多少的影响，也就是不同的文档可能有不同的长度, 当向量都标准化为一个单位向量的长度时, 进行点积运算就相当于在原来的向量上进行余弦相似度的运算. 所以, 另外一个角度利用这个规则就是直接在多数时候进行余弦相似度运算, 以代替点积运算.

  1. 文档频率的对数代替原始 TF

$$w_{i,j}=\frac{\log (tf_{i,j} + 1.0) \cdot \log (N/n_i)}{\sqrt {\sum_{t_i \in D_j} \left[\log (tf_{i,j} + 1.0) \cdot \log(N/n_i) \right] ^ 2}}$$

或者

$$w_{i,j}=\frac{(1.0 + \log tf_{i,j}) \cdot \log (N/n_i)}{\sqrt {\sum_{t_i \in D_j} \left[(1.0 + \log tf_{i,j}) \cdot \log(N/n_i) \right] ^ 2}}$$

对 TF 进行变换, 是为了一个不让 TF 线性增长. 举例而言, 人们常常用以上两种变化形式来代替原来的 TF 取值. 在这样新的计算下, 假如 "soccer" 一词出现一次，新的值是 $1$, 出现 $100$ 次, 新的值是 $5.6$, 而出现 $200$ 次, 新的值是 $6.3$. 很明显, 这样的计算保持了一个平衡, 既有区分度, 但也不至于完全线性增长.

  1. 特征频率的倒数的对数值代替 IDF

$$w_{i,j} = tf_{i,j} \cdot \left(\log \left(\frac{\sum_{i=1}^M nt_i}{nt_i}\right)\right) ^ 2$$

这里, $M$ 为特征项的个数, $nt_i$ 为特征项 $t_i$ 为特征项在预料中出现的次数. TF-IDF 的这种变形被称为 TF-IWF (inverse word frequency), 由 R. Basili et al.(1999) 提出来, 除了用特征频率倒数 IWF 替代 IDF, 算法还采用了 IWF 的平方, 而不是 IDF 的一次方. Basili 等认为 IDF 的一次方给了特征频率太多的倚重, 所以用 IWF 的平方来平衡权重值对于特征频率的倚重.

除了上面介绍的这些常用的方法以外, 还有很多其他的权重计算方法, 例如: Dagan et al. (1997) 提出的基于错误驱动的 (mistake-driven) 特征权重计算方法, 这种方法不是通过一个公式直接计算得到, 而是通过下游任务的目标, 为每个特征指定一个初始权重, 然后根据训练预料不断调整特征权重向量的取值, 直到权重向量大致不再改变. 还有 Okapi 权重函数企图进一步降低特征项 $t_i$ 在文本 $D_j$ 中出现的次数影响. Xue and Sun (2003) 将上面的某些方法进行叠加, 提出了 TF-IDF-IG 和 TF-EXP-IG 权重算法. Chen and Zong (2003) 则考虑特征词的频率分布不均衡性, 引入不均衡变量 (DBV) 并且用$\sqrt[m]{tf_{i,j}} (m=1, 2, \cdots)$ 替代 $tf_{i,j}$, 提出了 TF-IDF-DBV 权重算法, 等等. 还有很多特征权重算法, 在此难以一一列举.

最后需要指出的是, 这些不同的权重计算方法, 实质上都是考虑特征项在整个特征集中的分布问题, 这些经验公式从不同的角度定义公式, 往往缺少理论上的推导和验证, 因而表现出来的非一般性结果无法得到合理的解释.

1.4 TF-IDF 的应用

TF-IDF 作为向量空间模型中的基础文本特征表示方法, 一旦文本被表示为 TF-IDF 值的向量, 便可或直接或融合其他特征表示方法, 用于各种下游任务, 如文本语义相似性匹配, 文本聚类, 文本分类, 信息检索中 query-doc 文本相关性计算等等. 此外, TF-IDF 也可以作为一种无监督方法对文本进行关键词提取.

2.BM25算法以及变种算法简介

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

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

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

  • BM25L（BM25 with Length Normalization）：BM25L算法是在BM25算法的基础上，考虑了文档长度对得分的影响，通过引入文档长度规范化项来平衡不同长度的文档，目的是降低文档长度对相关性评分的影响，它可以通过对BM25公式中的长度归一化因子进行调整来实现，优化点改进在于更全面地考虑文档特征，以更准确地衡量文档与查询之间的相似度。

  • BM25+：BM25+是一种改进的BM25算法，加入了查询项权重的计算，以更好地处理查询中的重要词项，这个惩罚项用于调整较长的文档的相关性评分，以避免较长的文档在评分中占据过大的比重。优化点改进在于对查询项的权重进行动态调整，以提高信息检索的准确性和性能。

  • BM25T（BM25 with Term Weights）：BM25T是一种将词权重引入BM25的方法，通过考虑词频、逆文档频率以及文档长度等特征，以确定每个词项在文本中的重要性，它允许用户为查询中的每个词分配不同的权重，以更好地反映查询的重要性。优化点改进在于更精细地衡量词项的重要性，以提高信息检索的准确性。

  • $TF_{1∘δ∘p}×IDF$：是一种将词频和词位置信息综合考虑的改进算法。其中，$TF$表示词频，$δ$函数表示词位置的影响，$p$表示词位置权重，$IDF$表示逆文档频率,通过$p$和$δ$来调整词频和逆文档频率的权重，以提高对稀有词项的重视程度。这种算法可以根据词在文档中的位置给予不同的权重，进一步提高相关性评分的准确性.优化点改进在于更好地处理稀有词项，以适应大规模数据集的场景。

  • BM25F：BM25F是一种将多个字段考虑在内的改进算法。在信息检索中，通常会有多个字段（如标题、正文、标签等）的相关性需要评分。BM25F通过对多个字段的评分进行加权求和，可以更好地考虑文档的不同部分对匹配得分的影响，从而得出最终的相关性评分。优化点改进在于更灵活地处理文档的不同部分，以提高信息检索的准确性。

2.1 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 \tilde{tf}(q_i, d)}{k_1 + \tilde{tf}(q_i, d)}$$

$$\tilde{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$ 越大，文档长度的对相关性得分的影响越大，而文档的相对长度越长，$\tilde{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 权重计算公式，已经在众多的数据集和搜索任务上，被极其高频广泛和成功地使用。

2.2 BM25算法简易

一条 Query 与搜索结果的任意 doc 之间相关性分数:

$$Score(Q,d)=\sum\limits_{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{qf_i (k_2 +1)}{qf_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$ 中出现的频率， $ qf_i$ 为 $ q_i$ 在 $ Q$ 中的出现频率。$ dl$ 为 $ d$ 的长度， $ avgdl$ 为文档集中所有 $ d $ 的平均长度。在多数情况下， $ q_i $ 在 $ Q $ 中只会出现一次，即 $ qf_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$的相关性” 弱。

2.3 BM25 的变种和改进

BM25 算法公式，通过使用不同的特征项的分析方法、特征项权重判定方法，以及特征项与文档的相关度计算方法，都留有较强的灵活性，自然会促使后续的研究者在此基础上，提出更具个性化的不同的搜索相关性得分算法。
所有 BM25 后续改进中，Lv & Zhai 两位研究者的工作最为深入和全面。

2.3.1 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 中$\tilde{tf}(q_i, d)$ 这一项，以避免算法对过长文本的惩罚。Lv & Zhai 通过对 $\tilde{tf}(q_i, d)$ 加上一个正值的常数 $\delta$ 来实现这一点，只需这一个小操作便可以起到让 $\tilde{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 (\tilde{tf}(q_i, d) + \delta )}{k_1 + \tilde{tf}(q_i, d) + \delta}$$

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

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

2.3.2 BM25+

Lv & Zhai 进一步发现对过长文本的惩罚不止出现在 BM25 算法中，还出现在许多其他的排序函数中，他们为此提出了一个一般性的解决方案，即为每一个 query 中出现于文本的特征项相关性得分设置一个下界。此时，不论文本多长，某个搜索特征项至少贡献了一个正的常数相关性得分。他们这个做法略不同于之前的 BM25L，而是在乘 IDF 之前对整个 R(qi,d)$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 \tilde{tf}(q_i, d)}{k_1 + \tilde{tf}(q_i, d)} + \delta \right)$$

2.3.3 BM25-adpt

之前的 BM25 算法和相关改进，都忽略了对超参数 k1$k_1$ 的考察。Lv & Zhai 在不同的 BM25 相关研究工作中，发现对实际应用而言，全局的 k1$k_1$ 参数不及特征项相关的（term-specific）k1$k_1$ 参数使用起来高效。他们用随机理论中的信息增益和散度等概念，实现了 k1$k_1$ 去 “超参化” 的目标，即 k1$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.