在检索中，根据一个词查询相关文档，最简单的倒排索引和布尔检索。这两种方法只考虑查询词项在每个文档中出现与否，忽略了词项出现的次数。直觉上，一个词项在文档中出现次数越多，那么该词项和文档的相关性也应该越大。因此，可以将词项 t 在文档 d 中出现的次数，即词项频率 tf（term frequency）作为词项的权重。

然而，仅使用词项频率，是将所有词项视为“同等重要”又太简单粗暴。检索的目的是在给定文档集中找出匹配的文档，假设一个词项无法很好的区分一个文档与其他文档，那么这个词项的权重理应很小。比如一批跟手机相关的文档集中，几乎所有文档均包含“手机”，但有一小部分文档包含了“iPhone”，那么在检索时，“手机”意义并不大，但“iPhone”可以帮助筛掉很多文档。因此，一个直观的想法是，在计算权重时也要考虑包含词项的文档数量，即文档频率 DF（document frequency）。

DF 越大的词，区分作用越小，那么它的权重应该越小。也即是权重跟它的文档频率成反比，即跟文档的倒数成正比，文档的倒数即是逆文档频率（inverse document frequency，IDF）。

TF-IDF

综合起来，一个词项 $t$ 在文档 $d$ 中的权重 $w_{t,d}$ 可以定义为：

w_{t,d} = \text{TF}(t, d) \cdot \text{IDF}(t)

但上面的计算方式还存在两个问题：

如果一个词在文档中出现 $n$ 次，那么它的权重相当于只出现一次的词的权重的 $n$ 倍，这显然不太合理。
一般来说，长文档中的词项频率比短文档中的词项频率大，但这并不能直接说明文档的相关性增加。一个更合理的统计量是文档中“词的密度”，即单位长度中词的个数。

针对第一种情况，可以对 TF 进行约束，比如取开方，同样的思想也适用于 IDF。针对第二种情况，可以对文档长度进行归一化，比如除以文档长度，这样长文档和短文档的权重就可以比较了。那么，一个词项 $t$ 在文档 $d$ 中的权重 $w_{t,d}$ 可以定义为：

\begin{aligned} w_{t,d}&=\sqrt{\text{TF}(t,d)}\cdot\frac{1}{\text{DL}(d)}\cdot\text{IDF}(t) \\\ & =\sqrt{\text{TF}(t,d)}\cdot\frac{1}{\text{DL}(d)}\cdot\log\frac{N}{\text{DF}(t)}\\\ & \approx_{\text{smooth IDF}}\sqrt{\text{TF}(t,d)}\cdot\frac{1}{\text{DL}(d)}\cdot\log(\frac{N + 1}{\text{DF}(t)+1}) \end{aligned}

其中 $\text{DL}(d)$ 是文档 $d$ 的长度， $\text{DF}(t)$ 是包含词项 $t$ 的文档数量， $N$ 是文档集合的大小。

BM25

BM25 算法是对 TF-IDF 的改进，它在权重上进行了更多的约束，使得权重更加合理。

词频上的约束

首先考虑 TF 项，暂不考虑文档长度，TF-IDF 中 TF 项尽管作了开方，但增长仍然没有上限。从业务上讲，一个正相关的因素对业务可以有大的影响，但不能无限大。 BM25 算法将这点考虑在内，对 TF 这里的优化考虑到了三点：

$w_{t,d}$ 仍然与 TF 正相关，即是 TF 项的增函数。
$w_{t,d}$ 的值存在一个上界 $k$ ，即 $w_{t,d} \leq k$ 。
如果需要，这一项可以退化成原来的 TF 项。

综合上面三点，新的 TF 项可以定义为：

\text{TF}^{bm25}(t, d) = \frac{x \cdot k}{x + k}

其中 $x=\text{TF}(t, d)$ 是原来 TF-IDF 的 TF 项， $k$ 是上界。可以验证一下，这个函数同时满足以上三点。当然，也可以设计成其他的形式，就看最终谁的效果更好了。最后，再对分子作一下平滑，即 term 不存在时 (TF(t,d)=0)，也有一个非零的值，即得到：

\text{TF}^{bm25}(t, d) = \frac{x \cdot k + 1}{x + k}

这跟 BM25 中的设计还有点差距，BM25 考虑到当 $k=0$ 时，TF 项不再参与权重计算，即 $\text{TF}^{bm25}$ 变成一个常数，BM25 的设计是：

\text{TF}^{bm25}(t, d) = \frac{x \cdot (k+1)}{x + k}

但如果 $k$ 确定了，差异不是那么大。还是那句话，就看谁的效果好了。 BM25 与 TF-IDF 的权重关于词频增长的对比如下图所示：

文档长度上的约束

再考虑文档长度 DL 的问题，设计思想有两点：

可以通过超参（比如 $b$ ）调控 DL 对权重的影响， $b=0$ 时，DL 不影响权重， $b > 0$ 时，DL 影响权重；
权重跟”词的密度”成正比，当词频确定时，权重跟 DL 成反比，即是 DL 的减函数。

BM25 的设计是在把这个约束加到了分母 $k$ 的系数上，即 $k'=k(1 - b(1 - \frac{\text{DL}}{\text{AvgDL}}))$ ，其中 DL 是文档长度，AvgDL 是文档集合的平均长度。这样，当 $b=0$ 时， $k'=k$ ，即 DL 与权重不相关。当 $b=1$ 时， $k'= k \cdot \frac{\text{DL}}{\text{AvgDL}}$ ，即 DL 与权重负相关。

这个设计看起来有点复杂，但细究起来还是挺合理的，甚至说有点巧妙。

比如说，为什么不直接像 TF-IDF 那样把 DL 项单独拿出来呢？即 $\text{TF}^{bm25}(t, d) = \frac{xk + x}{x + k} \cdot \frac{1}{\Lambda(d)}, \text{where } \Lambda(d) = 1 - b(1 - \frac{\text{DL}}{\text{AvgDL}})$ 。这样做的话，当 $k,b$ 确定时，TF 项的上界就不再是 $k$ 了，这违背了第二项约束。
同理，这个约束 $\Lambda(d)$ 不能直接到加分母的 $x$ 上，因此这样上界就变成了 $\frac{k}{\Lambda(d)}$ 且具体值依赖于 $\text{DL}$ 。
再比如说，为什么分子上的的 $k$ 不加上同样的约束？第一，这同样违背了 TF 设计的第二项约束，上界不再是一个确定的值；第二，加了之后，TF 反而是 DL 的增函数，这违背了 DL 设计的第二项约束。

因此，要满足 DL 设计的第二项约束，DL 这一项得附加（乘）在分母上，且不能加到 $x$ 上，也不能两个（ $k,x$ ）都加，那只能落到 $k$ 头上。这样，最终的 BM25 的设计是：

\text{TF}^{bm25}(t, d) = \frac{x \cdot (k+1)}{x + k(1 - b(1 - \frac{\text{DL}}{\text{AvgDL}}))}

IDF 上的约束

这一项说是拓展了二元独立模型的得分函数，具体推理可以参考博客。

\begin{aligned} \text{IDF}^{bm25}(t) &= \log \frac{N - \text{DF}(t) + 0.5}{\text{DF}(t) + 0.5} \\\ &= \log (\frac{N+1}{\text{DF}(t)+0.5} - 1) \end{aligned}

同样， +0.5 是为了平滑，且“分子上凑个数”，满足：当 DF(t)=N 时，这一项为 0。整体上跟 TF-IDF 的差距不大。

神奇的数字 25

据说是指第 25 次迭代调参才获得最终的算法，参考 https://opensourceconnections.com/blog/2015/10/16/bm25-the-next-generation-of-lucene-relevation/

局限性

适用场景：

在文档包含查询词的情况下，或者说查询词精确命中文档的前提下，可能利用 BM25 计算相似度，内容进行排序。

不适用场景：

从上面的公式可以看出，如果一个词在文档中没有出现过，那么它与文档的相关度为 0。但实际上文档中存在语义上相关的词，但是没有出现在查询词中，这种情况下，BM25 无法计算出相关度。这也是基于传统检索模型的方法会存在一个固有缺陷，就是检索模型只能处理 Query 与 Document 有重合词的情况，传统检索模型无法处理词语的语义相关性。

DRP

从 20 年后，提取 BM25，就不得不提一下检索界的新秀 DRP（Dense Passage Retriver,《Dense Passage Retrieval for Open-Domain Question Answering》）了。DRP 的思想非常直观，将问题及段落都向量化，然后根据相似度进行排序。效果对比 BM25 有显著提升，但这也没什么稀奇的，毕竟

是基于 BERT 微调的，已经迁移了大量语义知识；
有监督学习。如果只结合已有文本，训练一个 encoder，再按上述思路去做，效果还真说不准。

$\text{sim}(p, q) = E_Q(q)^T E_P(p)$

其中， $E_Q(q)$ 是问题 $q$ 的向量表示， $E_P(p)$ 是段落 $p$ 的向量表示。 $p, q$ 的相似度即它们的内积。选择内积来计算相似度是因为，1. 内积简单，计算速度快；2. 通过消融实验对比，其他方式例如 L2 范数，在效果没有特别大的差异，且都比余弦相似度效果要好。

模型结构

Dual Encoder 结构（也称 biEncoder），每个 encoder 都是一个 BERT，这跟SBERT中的结构比较类似。不同之处在于 SBERT 中是 Siamese 结构（Siamese Dual Encoder,SDE，如下图左），即两个 encoder 共享参数，而 DRP 中是 Asymmetric Dual Encoder（ADE，如下图中），两个 encoder 的参数是独立的。关于 dual encoder 更多内容，可以阅读一个小论文《Exploring Dual Encoder Architectures for Question Answering》。

训练

DPR 训练的目的是要学习得到一个嵌入函数/映射，将相关的 query/answer 映射到向量空间中距离相似的向量，这本质上是一个度量学习的问题。那流程无怪乎选择 Siamese Networks 或者 Triplet Networks，通过最小优化损失函数，来学习得到这个嵌入函数。

DPR 使用了 N-pair 损失函数，N-pair loss 的一般形式是

\begin{aligned} \mathcal{L}_{\text{N-pair}}(x, x^+, \{x_i^-\}_{i=1}^{N-1}) &= \log(1 + \sum_{i=1}^{N-1} \exp(f(x)^T f(x_i^-) - f(x)^T f(x^+))) \\\ &= - \log \frac{\exp(f(x)^T f(x^+))}{\exp(f(x)^T f(x^+)) + \sum_{i=1}^{N-1} \exp(f(x)^T f(x_i^-))} \end{aligned}

因为是通过相似度来确定 query, passage 距离的，这里 $f=\text{sim}$ ：

$\mathcal{L}(a) = - \log \frac{e^{\text{sim}(q*i, p_i^+) / \tau}}{(\sum*{j=1}^{n} e^{\text{sim}(q_i, p_j^-) / \tau}) + e^{\text{sim}(q_i, p_i^+) / \tau}}$

其中 $a = \langle q_i, p_i^+, p_1^-, p_2^-, ..., p_n^- \rangle$ 表示一个完整的样本， $q_i$ 表示 query， $p_i^+$ 是正相关答案（e.g., QA 数据集中的 golden answer）， $p_i^-$ 表示若干个负相关答案。这个目标函数跟 SimCSE 有监督版本的目标函数有点像（参考之前的文章《Semtatic Similarity》）。不同点在于， SimCSE 一个样本只考虑一个负样本，而 DPR 可能考虑多个。不过，在实际实验中，DPR 最有效的模型也只考虑一个负样本，这个负样本是通过 BM25 召回的一个段落，这个段落不包含 query 的答案但跟 query 有最多的 token 重合。

题外话，DPR(20)、SimCSE(21) 及 RAG(20) 这三个工作，Danqi 大佬都有参与，Danqi 大佬在同年(20)还指导了另一篇类似思想的工作 DensePhrases，主要侧重于 phrase 的检索。

负样本采样

训练数据中，正样本由 (Query, Answer) 构成，但负样本的采集就需要人工构造了。DPR 考虑了三种方式：

从语料中随机采取段落；
BM25 返回的不包含回答的 Top K 个段落；
其它问题的回答。SimCSE 也是类似的思路，天下无新事。