Understanding the BM25 full text search algorithm理解 BM25 全文搜索算法

Nov 20, 2024 2024年11月20日

BM25, or Best Match 25, is a widely used algorithm for full text search. It is the default in Lucene/Elasticsearch and SQLite, among others. Recently, it has become common to combine full text search and vector similarity search into "hybrid search". I wanted to understand how full text search works, and specifically BM25, so here is my attempt at understanding by re-explaining.BM25（Best Match 25）是一种广泛使用的全文搜索算法。它是 Lucene/Elasticsearch 和 SQLite 等系统的默认算法。最近，全文搜索与向量相似度搜索的结合——“混合搜索”——变得很常见。我想了解全文搜索是如何工作的，尤其是 BM25，于是尝试通过重新解释来加深理解。

Motivation: can BM25 scores be compared across queries?动机：BM25 分数能在不同查询之间进行比较吗？
Ranking documents probabilistically概率性文档排序
Components of BM25BM25 的组成部分
Behold, Math!
1. Query terms查询词
2. Inverse Document Frequency (IDF)逆文档频率（IDF）
3. Term frequency in the document文档中的词频
4. Document length normalization文档长度归一化
5. Putting it all together把所有部分组合起来
Cleverness of BM25 and its precursors
1. Ranking by probability without calculating probability不计算概率的概率排序
2. Assuming most documents are irrelevant假设大多数文档都是不相关的
Conclusion: BM25 scores can be compared within the same collection结论：BM25 分数可以在同一集合内进行比较
Further reading进一步阅读

Motivation: can BM25 scores be compared across queries?

For a quick bit of context on why I'm thinking about search algorithms, I'm building a personalized content feed that scours noisy sources for content related to your interests. I started off using vector similarity search and wanted to also include full-text search to improve the handling of exact keywords (for example, a friend has "Solid.js" as an interest and using vector similarity search alone, that turns up more content related to React than Solid).为了说明我为何关注搜索算法，我正在构建一个个性化内容流，它会在嘈杂的来源中搜寻与你兴趣相关的内容。我最初使用向量相似度搜索，但想加入全文搜索以更好地处理精确关键词（例如，有位朋友的兴趣是 “Solid.js”，单纯使用向量相似度搜索会返回更多与 React 相关的内容，而不是 Solid）。

The question that motivated this deep dive into BM25 was: can I compare the BM25 scores of documents across multiple queries to determine which query the document best matches?促使我深入研究 BM25 的问题是：我能否比较同一文档在多个查询下的 BM25 分数，以判断该文档最匹配哪个查询？

Initially, both ChatGPT and Claude told me no — though annoyingly, after doing this deep dive and formulating a more precise question, they both said yes 🤦‍♂️. Anyway, let's get into the details of BM25 and then I'll share my conclusions about this question.最初，ChatGPT 和 Claude 都说不行——但在我深入研究并提出更精确的问题后，它们又都说可以 🤦‍♂️。好了，下面进入 BM25 的细节，随后我会分享对这个问题的结论。

Ranking documents probabilistically

At the most basic level, the goal of a full text search algorithm is to take a query and find the most relevant documents from a set of possibilities.在最基本的层面，全文搜索算法的目标是接受一个查询，并从可能的文档集合中找出最相关的文档。

However, we don't really know which documents are "relevant", so the best we can do is guess. Specifically, we can rank documents based on the probability that they are relevant to the query. (This is called The Probability Ranking Principle.)然而，我们并不知道哪些文档是“相关”的，所以我们只能猜测。具体来说，我们可以根据文档对查询相关的概率来对文档进行排序。（这被称为概率排序原则。）

How do we calculate the probability that a document is relevant?我们如何计算文档相关的概率？

For full text or lexical search, we are only going to use qualities of the search query and each of the documents in our collection. (In contrast, vector similarity search might use an embedding model trained on an external corpus of text to represent the meaning or semantics of the query and document.)对于全文或词汇搜索，我们只会使用查询本身以及我们集合中每个文档的特征。（相比之下，向量相似度搜索可能会使用在外部文本语料上训练的嵌入模型来表示查询和文档的意义或语义。）

Components of BM25

BM25 uses a couple of different components of the query and the set of documents:BM25 使用了查询和文档集合的若干不同组成部分：

Query terms: if a search query is made up of multiple terms, BM25 will calculate a separate score for each term and then sum them up.查询词：如果查询由多个词组成，BM25 会为每个词单独计算分数，然后将它们相加。
Inverse Document Frequency (IDF): how rare is a given search term across the entire document collection? We assume that common words (such as "the" or "and") are less informative than rare words. Therefore, we want to boost the importance of rare words.逆文档频率（IDF）：给定搜索词在整个文档集合中有多稀有？我们假设常见词（如 “the” 或 “and”）的信息量较低。因此，我们希望提升稀有词的重要性。
Term frequency in the document: how many times does a search term appear in a given document? We assume that more repetition of a query term in a given document increases the likelihood that that document is related to the term. However, BM25 also adjusts this so that there are diminishing returns each time a term is repeated.文档中的词频：给定搜索词在某篇文档中出现了多少次？我们假设查询词在文档中出现得越多，文档与该词的关联度越高。不过，BM25 也会对这种关系进行递减处理，使得每次重复的收益逐渐降低。
Document length: how long is the given document compared to others? Long documents might repeat the search term more, just by virtue of being longer. We don't want to unfairly boost long documents, so BM25 applies some normalization based on how the document's length compares to the average.文档长度：相对于其他文档，这篇文档有多长？长文档可能仅因为篇幅更大而出现更多搜索词。我们不想不公平地提升长文档的分数，所以 BM25 会根据文档长度相对于平均长度进行归一化。

These four components are what make up BM25. Now, let's look at exactly how they're used.这四个组成部分构成了 BM25。接下来，让我们看看它们到底是如何使用的。

Behold, math!看哪，数学！

The BM25 algorithm might look scary to non-mathematicians (my eyes glazed over the first time I saw it), but I promise, it's not too hard to understand!BM25 算法对非数学专业的人可能看起来很吓人（我第一次看到时眼睛都花了），但我保证，它并不难理解！

Here is the full equation:下面是完整的公式：

score (D, Q) = \sum_{i = 1}^{n} \ln (\frac{N - n (q_{i}) + 0.5}{n (q_{i}) + 0.5} + 1) \cdot \frac{f (q_{i}, D) \cdot (k_{1} + 1)}{f (q_{i}, D) + k_{1} \cdot (1 - b + b \cdot \frac{| D |}{avgdl})}

Now, let's go through it piece-by-piece.现在，让我们逐块拆解。

Query terms

score (D, Q) = \sum_{i = 1}^{n} . . .

$D$ is a given documentD 代表某个文档
$Q$ is the full query, potentially composed of multiple query termsQ 代表完整查询，可能由多个查询词组成
$n$ is the number of query termsn 是查询词的数量
$q_{i}$ is each of the query termsqi 是每个查询词

This part of the equation says: given a document and a query, sum up the scores for each of the query terms.公式的这部分表示：给定文档和查询，对每个查询词的分数求和。

Now, let's dig into how we calculate the score for each of the query terms.接下来，看看我们如何为每个查询词计算分数。

Inverse Document Frequency (IDF)

The first component of the score calculates how rare the query term is within the whole collection of documents using the Inverse Document Frequency (IDF).分数的第一部分使用逆文档频率（IDF）来衡量查询词在整个文档集合中的稀有程度。

\ln (\frac{N - n (q_{i}) + 0.5}{n (q_{i}) + 0.5} + 1)

The key elements to focus on in this equation are:该公式中需要关注的关键要素有：

$N$ is the total number of documents in our collectionN 是我们集合中文档的总数
$n (q_{i})$ is the number of documents that contain the query termn(qi) 是包含该查询词的文档数量
$N - n (q_{i})$ therefore is the number of documents that do not contain the query termN−n(qi) 因此是未包含该查询词的文档数量

In simple language, this part boils down to the following: common terms will appear in many documents. If the term appears in many documents, we will have a small number ( $N - n (q_{i})$ , or the number of documents that do not have the term) divided by $N$ . As a result, common terms will have a small effect on the score.通俗来说，这部分可以归结为：常见词会出现在很多文档中。如果词出现在很多文档里，我们会得到一个很小的数（N−n(qi) 除以 N），于是常见词对分数的影响很小。

In contrast, rare terms will appear in few documents so $n (q_{i})$ will be small and $N - n (q_{i})$ will be large. Therefore, rare terms will have a greater impact on the score.相反，稀有词只会出现在少数文档中，n(qi) 很小而 N−n(qi) 很大。因此，稀有词对分数的影响更大。

The constants $0.5$ and $1$ are there to smooth out the equation and ensure that we don't end up with wildly varying results if the term is either very rare or very common.常数 0.5 和 1 用来平滑公式，确保当词极其稀有或极其常见时不会得到异常的结果。

Term frequency in the document

In the previous step, we looked at how rare the term is across the whole set of documents. Now, let's look at how frequent the given query is in the given document.在上一步我们看到了词在整个文档集合中的稀有程度。现在，让我们看看该词在给定文档中的出现频率。

\frac{f (q_{i}, D)}{f (q_{i}, D) + k_{1}}

The terms in this equation are:公式中的各项为：

$q_{i}$ is a given queryqi 为给定查询词
$D$ is a given document
$f (q_{i}, D)$ is the frequency of the given query in the given documentf(qi,D) 为该查询词在文档 D 中的出现次数
$k_{1}$ is a tuning parameter that is generally set between $1.2$ and $2$ k1 为调节参数，通常取值在 1.2 到 2 之间

This equation takes the term frequency within the document into effect, but ensures that term repetition has diminishing returns. The intuition here is that, at some point, the document is probably related to the query term and we don't want an infinite amount of repetition to be weighted too heavily in the score.该公式考虑了文档内部的词频，但确保词的重复会产生递减收益。直观上讲，到了某个点，文档已经足够与查询词相关，我们不希望无限重复的词对分数产生过大权重。

The $k_{1}$ parameter controls how quickly the returns to term repetition diminish. You can see how the slope changes based on this setting:k1 参数控制词频递减的速度。你可以看到不同设置下斜率的变化：

Effect of the k parameter

From The Probabilistic Relevance Framework: BM25 and Beyond摘自《概率相关框架：BM25 及其后续》

Document length normalization

The last thing we need is to compare the length of the given document to the lengths of the other documents in the collection.最后一步是将文档长度与集合中其他文档的长度进行比较。

(1 - b + b \cdot \frac{| D |}{avgdl})

From right to left this time, the parameters are:这次从右到左的参数为：

$| D |$ is the length of the given document|D| 为给定文档的长度
$a v g d l$ is the average document length in our collectionavgdl 为集合中文档的平均长度
$b$ is another tuning parameter that controls how much we normalize by the document lengthb 为另一个调节参数，控制我们对文档长度的归一化程度

Long documents are likely to contain the search term more frequently, just by virtue of being longer. Since we don't want to unfairly boost long documents, this whole term is going to go in the denominator of our final equation. That is, a document that is longer than average ( $\frac{| D |}{a v g d l} > 1$ ) will be penalized by this adjustment.长文档因为篇幅更大，往往会更频繁地出现搜索词。由于我们不想不公平地提升长文档的分数，这整项会出现在最终公式的分母中。也就是说，长度超过平均值的文档（|D|/avgdl>1）会因该调整而被惩罚。

$b$ can be adjusted by the user. Setting $b = 0$ turns off document length normalization, while setting $b = 1$ applies it fully. It is normally set to $0.75$ .b 参数可以由用户自行调节。设 b=0 可关闭文档长度归一化，设 b=1 则完全启用。通常取值为 0.75。

Putting it all together

If we take all of the components we've just discussed and put them together, we arrive back at the full BM25 equation:如果把前面讨论的所有组成部分组合起来，就得到完整的 BM25 公式：

\underset{Summing each query term's score}{\underset{⏟}{score (D, Q) = \sum_{i = 1}^{n}}} \underset{Inverse Document Frequency}{\underset{⏟}{\ln (\frac{N - n (q_{i}) + 0.5}{n (q_{i}) + 0.5} + 1)}} \cdot \overset{Term frequency in the document}{\overset{⏞}{\frac{f (q_{i}, D) \cdot (k_{1} + 1)}{f (q_{i}, D) + k_{1} \cdot \underset{Document length normalization}{\underset{⏟}{(1 - b + b \cdot \frac{| D |}{avgdl})}}}}}

Reading from left to right, you can see that we are summing up the scores for each query term. For each, we are taking the Inverse Document Frequency, multiplying it by the term frequency in the document (with diminishing returns), and then normalizing by the document length.从左到右阅读，你会看到我们对每个查询词的分数进行求和。对每个词，我们先取逆文档频率，再乘以文档中的词频（带递减收益），最后再除以文档长度的归一化因子。

Cleverness of BM25 and its precursorsBM25 及其前身的巧妙之处

We've just gone through the components of the BM25 equation, but I think it's worth pausing to emphasize two of its most ingenious aspects.我们已经逐项讲解了 BM25 公式的组成，但我认为值得停下来强调其中两个最巧妙的方面。

Ranking by probability without calculating probability

As mentioned earlier, BM25 is based on an idea called the Probability Ranking Principle. In short, it says:正如前面提到的，BM25 基于一种叫做概率排序原则的思想。简而言之，它的核心论断是：

If retrieved documents are ordered by decreasing probability of relevance on the data available, then the system’s effectiveness is the best that can be obtained for the data.如果检索到的文档按照可用数据上相关概率的递减顺序排列，那么系统的有效性就是在该数据条件下能够达到的最佳水平。

The Probabilistic Relevance Framework: BM25 and Beyond摘自《概率相关框架：BM25 及其后续》

Unfortunately, calculating the "true" probability that a document is relevant to a query is nearly impossible.不幸的是，计算文档对查询的“真实”相关概率几乎是不可能的。

However, we really care about the order of the documents more than we care about the exact probability. Because of this, researchers realized that you could simplify the equations and make it practicable. Specifically, you could drop terms from the equation that would be required to calculate the full probability but where leaving them out would not affect the order.然而，我们更关心文档的排序而非精确概率。正因为如此，研究者发现可以简化公式，使其在实际中可用。具体来说，可以去掉那些计算完整概率所必需但对排序没有影响的项。

Even though we are using the Probability Ranking Principle, we are actually calculating a "weight" instead of a probability.即使我们使用了概率排序原则，实际计算的也不是概率，而是一个“权重”。

W (d) = \sum_{\begin{matrix} t \in q, \\ f_{t, d} > 0 \end{matrix}} \log \frac{P (F = f_{t, d} | R = 1) P (F = 0 | R = 0)}{P (F = f_{t, d} | R = 0) P (F = 0 | R = 1)}

This equation calculates the weight using term frequencies. Specifically:该公式使用词频来计算权重。具体如下：

$W (d)$ is the weight for a given documentW(d) 为给定文档的权重
$P (F = f_{t, d} | R = 1)$ is the probability that the query term would appear in the document with a given frequency ( $f_{t, d}$ ) if the document is relevant ( $R = 1$ )P(F=ft,d|R=1) 为在文档相关（R=1）的前提下，查询词在文档中出现频率为 ft,d 的概率

The various terms boil down to the probability that we would see a certain query term frequency within the document if the document is relevant or not relevant, and the probabilities that the term would not appear at all if the document is relevant or not.各种项归结为：如果文档相关或不相关，我们会看到某个查询词在文档中出现特定频率的概率，以及如果文档相关或不相关时该词根本不出现的概率。

The Robertson/Sparck Jones Weight is a way of estimating these probabilities but only using the counts of different sets of documents:Robertson/Sparck Jones 权重是一种仅使用不同文档集合计数就能估计这些概率的方法：

w^{R S J} = \log \frac{(r + 0.5) (N - R - n + r + 0.5)}{(n - r + 0.5) (R - r + 0.5)}

The terms here are:这里的各项为：

$r$ is the number of relevant documents that contain the query termr 为包含查询词的相关文档数量
$N$ is the total number of documents in the collectionN 为集合中文档的总数
$R$ is the number of relevant documents in the collectionR 为集合中相关文档的数量
$n$ is the number of documents that contain the query termn 为包含查询词的文档数量

The big, glaring problem with this equation is that you first need to know which documents are relevant to the query. How are we going to get those?这个公式的最大难题在于，你必须先知道哪些文档对查询是相关的。我们怎么得到这些信息？

Assuming most documents are irrelevant

The question about how to make use of the Robertson/Sparck Joes weight apparently stumped the entire research field for about 15 years. The equation was built up from a solid theoretical foundation, but relying on already having relevance information made it nearly impossible to put to use.关于如何利用 Robertson/Sparck Jones 权重的问题，曾让整个研究领域困惑约 15 年。该公式基于坚实的理论基础，但依赖已有的相关性信息，使其几乎无法实际使用。

The BM25 developers made a very clever assumption to get to the next step.BM25 的开发者做了一个非常聪明的假设，以继续推进。

For any given query, we can assume that most documents are not going to be relevant. If we assume that the number of relevant documents is so small as to be negligible, we can just set those numbers to zero!对于任意查询，我们可以假设大多数文档并不相关。如果我们认为相关文档的数量微乎其微，可以直接把这些计数设为零！

R = r = 0

If we substitute this into the Robertson/Sparck Jones Weight equation, we get nearly the IDF term used in BM25:把这个假设代入 Robertson/Sparck Jones 权重公式，就几乎得到 BM25 中使用的 IDF 项：

\log \frac{(0 + 0.5) (N - 0 - n + 0 + 0.5)}{(n - 0 + 0.5) (0 - 0 + 0.5)} = \log \frac{0.5 (N - n + 0.5)}{(n + 0.5) 0.5} = \log \frac{(N - n + 0.5)}{(n + 0.5)}

Not relying on relevance information made BM25 much more useful, while keeping the same theoretical underpinnings. Victor Lavrenko described this as a "very impressive leap of faith", and I think this is quite a neat bit of BM25's backstory.不依赖相关性信息让 BM25 更加实用，同时保留了相同的理论基础。Victor Lavrenko 将其称为“一次非常令人印象深刻的信念飞跃”，我觉得这也是 BM25 背后一个相当有趣的故事。

Conclusion: BM25 scores can be compared within the same collection

As I mentioned at the start, my motivating question was whether I could compare BM25 scores for a document across queries to understand which query the document best matches.正如我在开头提到的，我的动机问题是：我能否比较同一文档在不同查询下的 BM25 分数，以判断该文档最匹配哪个查询。

In general, BM25 scores cannot be directly compared (and this is what ChatGPT and Claude stressed to me in response to my initial inquiries 🙂‍↔️). The algorithm does not produce a score from 0 to 1 that is easy to compare across systems, and it doesn't even try to estimate the probability that a document is relevant. It only focuses on ranking documents within a certain collection in an order that approximates the probability of their relevance to the query. A higher BM25 score means the document is likely to be more relevant, but it isn't the actual probability that it is relevant.总体而言，BM25 分数不能直接进行跨查询比较（这正是 ChatGPT 和 Claude 最初对我强调的点 🙂‍↔️）。该算法并不产生 0 到 1 之间的分数，也不试图估计文档相关的概率。它只关注在特定集合内对文档进行排序，使排序顺序近似于文档对查询的相关概率。更高的 BM25 分数意味着文档更可能相关，但这并不是文档实际相关的概率。

As far as I understand now, it is possible to compare the BM25 scores across queries for the same document within the same collection of documents.据我现在的理解，在同一文档集合内，同一文档的 BM25 分数可以在不同查询之间进行比较。

My hint that this was the case was the fact that BM25 sums the scores of each query term. There should not be a semantic difference between comparing the scores for two query term and two whole queries.我之所以认为可以比较，是因为 BM25 对每个查询词的分数进行求和。比较两个查询词的分数与比较两个完整查询的分数在语义上没有区别。

The important caveat to stress, however, is the same document within the same collection. BM25 uses the IDF or rarity of terms as well as the average document length within the collection. Therefore, you cannot necessarily compare scores across time because any modifications to the overall collection could change the scores.需要强调的重要前提是：必须是同一文档、同一集合。BM25 使用了词的 IDF（稀有度）以及集合内的平均文档长度。因此，随时间对集合进行的任何修改都可能改变分数，从而导致跨时间的比较失效。

For my purposes, though, this is useful enough. It means that I can do a full text search for each of a user's interests in my collection of content and compare the BM25 scores to help determine which pieces best match their interests.对我而言，这已经足够实用了。这意味着我可以对用户的每个兴趣在我的内容集合中进行全文搜索，并比较 BM25 分数，以帮助判断哪些内容最符合他们的兴趣。

I'll write more about ranking algorithms and how I'm using the relevance scores in future posts, but in the meantime I hope you've found this background on BM25 useful or interesting!我将在后续文章中进一步讨论排序算法以及我如何使用相关分数，但与此同时，希望你已经觉得这段 BM25 背景信息有用或有趣！

Thanks to Alex Kesling and Natan Last for feedback on drafts of this post.感谢 Alex Kesling 和 Natan Last 对本文草稿的反馈。