一、什么是 BM25?
BM25(Best Matching 25)是一种基于概率信息检索框架的相关性评分算法,主要用于衡量查询(Query)与文档(Document)之间的相关程度。
它广泛应用于:
- 搜索引擎全文检索。
- 企业知识库搜索。
- 文档管理系统。
- 日志与技术文档检索。
- RAG 系统中的关键词召回。
- 向量检索与关键词检索的混合召回。
BM25 的核心思想是:
一个文档与查询越相关,其查询词在文档中出现得越合理、越具有区分度,文档就应该获得越高的相关性评分。
例如,用户搜索:
Java 线程池如何控制并发数量?
搜索系统可能找到以下文档:
| 文档 | 内容 |
|---|---|
| A | Java 线程池通过核心线程数和最大线程数控制并发 |
| B | Java 并发编程中的线程同步机制 |
| C | Python 线程池的使用方法 |
| D | Java 基础语法与面向对象编程 |
BM25 会综合考虑查询词在文档中的出现情况,以及这些词在整个文档集合中的区分能力,为文档计算相关性分数。
与简单的关键词匹配不同,BM25 不只是统计查询词出现了多少次,还会考虑词频饱和和文档长度。
1.1 BM25 的核心组成
BM25 主要涉及三个概念:
| 概念 | 英文 | 主要作用 |
|---|---|---|
| 词频 | Term Frequency,TF | 衡量查询词在文档中出现的频率 |
| 逆文档频率 | Inverse Document Frequency,IDF | 衡量词语在整个文档集合中的区分能力 |
| 文档长度归一化 | Document Length Normalization | 调整不同长度文档之间的评分偏差 |
这三个因素共同决定文档的相关性评分。
1.2 BM25 与简单关键词匹配的区别
简单关键词匹配通常只判断查询词是否出现在文档中。
例如:
查询:Java 线程池
文档 A:Java 线程池的核心参数
文档 B:Java 线程池的线程管理机制
文档 C:Java 的基本语法
如果只判断关键词是否存在,A、B、C 都可能获得一定的匹配结果。
BM25 则会进一步考虑:
- 查询词出现了多少次。
- 查询词在整个文档集合中是否常见。
- 文档本身有多长。
- 高频词是否已经达到收益饱和。
因此,BM25 能够对匹配结果进行更合理的排序。
二、BM25 的底层基础:倒排索引
BM25 负责计算相关性分数,但在大规模全文检索系统中,通常不会逐篇扫描所有文档。
搜索引擎一般使用倒排索引(Inverted Index)快速定位包含查询词的文档。
2.1 什么是倒排索引?
倒排索引是一种以词项为入口组织文档信息的数据结构。
传统文档存储通常按照文档组织:
文档 A:Java 线程池 并发控制
文档 B:Java 锁机制 线程同步
文档 C:Python 线程池 并发处理
倒排索引则反过来,以词项为索引入口:
Java:
文档 A
文档 B
线程池:
文档 A
文档 C
并发:
文档 A
文档 C
锁机制:
文档 B
这种结构可以快速找到包含指定词项的文档,而不需要扫描全部文档内容。
2.2 倒排索引的基本结构
倒排索引主要包含两个部分:
词典(Dictionary)
保存经过分析处理后的词项及其索引信息。
倒排列表(Posting List)
保存包含该词项的文档记录,以及相关统计信息。
例如:
{
"java": [
{
"doc_id": "A",
"term_frequency": 3,
"positions": [1, 5, 9]
},
{
"doc_id": "B",
"term_frequency": 2,
"positions": [2, 7]
}
],
"thread_pool": [
{
"doc_id": "A",
"term_frequency": 2,
"positions": [3, 8]
}
]
}
其中:
doc_id:文档标识。term_frequency:词项在文档中出现的次数。positions:词项在文档中的位置。
实际搜索引擎通常采用压缩、分块、跳表或其他优化结构存储倒排列表,并不一定直接使用上述 JSON 形式。
2.3 倒排索引如何建立?
建立倒排索引通常包含以下步骤:
- 获取原始文档。
- 对文档进行文本分析。
- 执行分词、规范化等处理。
- 统计词项出现频率。
- 记录词项所属文档。
- 构建倒排列表。
- 保存文档长度和集合统计信息。
flowchart TD
A["原始文档集合"] --> B["文本解析"]
B --> C["分词与文本规范化"]
C --> D["生成词项序列"]
D --> E["统计词频与词项位置"]
E --> F["按词项组织文档记录"]
F --> G["构建倒排列表"]
G --> H["保存文档长度与集合统计"]
H --> I["生成倒排索引"]
style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#EAF3EC,stroke:#83A995,color:#315D49
style D fill:#EAF3EC,stroke:#83A995,color:#315D49
style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style F fill:#EAF3EC,stroke:#83A995,color:#315D49
style G fill:#EAF3EC,stroke:#83A995,color:#315D49
style H fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style I fill:#E5F0E9,stroke:#83A995,color:#315D49
2.4 倒排索引与 BM25 的关系
需要区分两个概念:
- 倒排索引负责快速找到包含查询词的候选文档。
- BM25 负责计算候选文档与查询之间的相关性分数。
两者协同工作。
倒排索引解决的是检索效率问题,BM25 解决的是相关性排序问题。
三、BM25 的数学公式
BM25 的经典评分公式为:
其中:
| 符号 | 含义 |
|---|---|
| D | 当前待评分文档 |
| Q | 用户查询 |
| q_i | 查询中的第 i 个词项 |
| f(q_i,D) | 查询词在文档 D 中的词频 |
| ( | D |
| avgdl | 文档集合的平均长度 |
| k_1 | 控制词频饱和程度的参数 |
| b | 控制文档长度归一化程度的参数 |
| IDF(q_i) | 查询词的逆文档频率 |
公式可以拆成三个核心部分:
- IDF:判断查询词的重要程度。
- TF 饱和:判断词频对相关性评分的贡献。
- 长度归一化:调整文档长度造成的评分偏差。
理解这三个部分,就能理解 BM25 的主要工作机制。
四、第一部分:TF 词频与词频饱和
TF(Term Frequency)表示某个词项在文档中出现的次数。
例如:
文档 A:
Java 线程池可以管理线程。
线程池支持并发控制。
线程池可以复用线程。
文档 B:
Java 提供了多种并发编程机制。
如果查询词是“线程池”:
- 文档 A 中出现 3 次。
- 文档 B 中出现 0 次。
从词频角度看,文档 A 应该获得更高的匹配贡献。
但如果只根据词频进行评分,会产生一个问题:
词语出现次数越多,分数就会无限增长。
这并不合理。
4.1 为什么需要词频饱和?
假设查询词“Java”在一篇文档中出现:
| 出现次数 | 简单词频 |
|---|---|
| 1 | 1 |
| 5 | 5 |
| 10 | 10 |
| 20 | 20 |
| 100 | 100 |
如果直接使用词频,出现 100 次的文档会获得出现 1 次文档的 100 倍分数。
但对于搜索相关性而言:
- 从 0 次增加到 1 次,可能非常重要。
- 从 1 次增加到 2 次,通常仍然有价值。
- 从 20 次增加到 21 次,新增价值可能已经很小。
也就是说,词频对相关性的贡献应逐渐趋于饱和。
4.2 BM25 的词频饱和公式
先忽略文档长度归一化,BM25 的词频部分可以写成:
其中:
- f:查询词在文档中的词频。
- k_1:控制饱和速度的参数。
当词频增加时,TF 贡献会逐渐接近上限:
因此,BM25 不会因为某个词重复出现大量次数,就无限提高文档评分。
4.3 k1 参数的作用
k_1 控制词频饱和速度。
一般情况下:
- k_1 较小:词频更快达到饱和。
- k_1 较大:词频增加带来的贡献持续时间更长。
常见取值范围大致在 1.2 到 2.0 左右,但并不是固定标准,应结合具体检索任务进行评估。
4.4 词频饱和示例
假设:
词频贡献为:
不同词频对应的结果:
| 词频 f | TF 贡献 |
|---|---|
| 1 | 1.000 |
| 2 | 1.429 |
| 3 | 1.667 |
| 5 | 1.923 |
| 10 | 2.174 |
| 20 | 2.326 |
| 100 | 2.463 |
可以观察到:
词频从 1 增加到 5,评分贡献明显增长;但从 20 增加到 100,贡献增长已经很有限。
这就是词频饱和机制。
五、第二部分:IDF 逆文档频率
IDF(Inverse Document Frequency)用于衡量一个词在整个文档集合中的区分能力。
一个词在越多文档中出现,通常越难帮助系统区分不同文档。
反过来,一个词越少见,往往越具有区分价值。
5.1 为什么需要 IDF?
假设一个知识库中有 10000 篇文档。
查询:
Java 线程池参数配置
不同词项的分布可能如下:
| 词项 | 包含该词的文档数 |
|---|---|
| Java | 6000 |
| 线程池 | 800 |
| 参数 | 4000 |
| 配置 | 3000 |
| ThreadPoolExecutor | 50 |
其中:
- Java 出现在大量文档中。
- 参数和配置也比较常见。
- ThreadPoolExecutor 相对少见。
如果某个词出现在几乎所有文档中,它的区分能力就比较弱。
BM25 通过 IDF 对不同词项赋予不同权重。
5.2 IDF 的经典公式
BM25 常见的一种 IDF 形式为:
其中:
- N:文档集合中的文档总数。
- n(q_i):至少包含查询词 q_i 的文档数量。
- \ln:自然对数。
这里需要注意:
n(q_i) 统计的是包含该词的文档数量,而不是该词在所有文档中出现的总次数。
5.3 IDF 的计算示例
假设:
某个词出现在 100 篇文档中:
代入公式:
再假设另一个词出现在 8000 篇文档中:
则:
对比可知:
- 只出现在少量文档中的词,IDF 较高。
- 出现在大量文档中的词,IDF 较低。
因此,稀有词通常具有更高的区分权重。
5.4 为什么 IDF 公式中有 0.5?
公式中的 0.5 属于平滑处理的一部分。
它能够避免某些边界情况下出现除零等问题,并使 IDF 计算更加稳定。
例如:
当一个词出现在全部文档中时:
如果不进行适当平滑,IDF 的数值可能出现不合理的边界行为。
需要注意,BM25 在不同搜索系统中可能采用不同的 IDF 实现或变体。上面给出的是经典 Robertson 风格的 BM25 IDF 形式,不应假设所有搜索引擎的内部实现完全一致。
5.5 IDF 的工程意义
IDF 对搜索质量非常重要。
例如,查询:
ERR_CONNECTION_RESET 网络错误
其中:
- “网络”是较常见的词。
- “错误”也是较常见的词。
- “ERR_CONNECTION_RESET”通常具有较强的区分能力。
合理的 IDF 能够提升精确术语在相关性排序中的影响力。
六、第三部分:文档长度归一化
BM25 的第三个重要机制是文档长度归一化。
它用于解决不同长度文档之间的评分偏差。
6.1 为什么文档长度会影响评分?
假设有两个文档:
文档 A:
Java 线程池可以控制线程数量。
文档 B:
Java 线程池可以控制线程数量。
Java 线程池可以管理任务队列。
Java 线程池可以复用工作线程。
Java 线程池可以配置拒绝策略。
Java 线程池可以控制并发执行。
……
文档 B 比文档 A 长得多。
如果只考虑词频,长文档往往有更多机会出现查询词,因此可能获得更高的分数。
但长文档不一定比短文档更加相关。
BM25 通过文档长度归一化,对这种偏差进行调整。
6.2 文档长度归一化公式
BM25 中的长度调整项为:
其中:
- |D|:当前文档长度。
- avgdl:整个文档集合的平均长度。
- b:长度归一化参数。
当:
则:
此时文档长度不会额外改变词频部分的分母。
6.3 b 参数的作用
b 控制文档长度归一化程度。
通常:
不同取值的含义:
| b 值 | 作用 |
|---|---|
| 0 | 不进行文档长度归一化 |
| 0.5 | 进行部分长度归一化 |
| 0.75 | 常见默认取值之一 |
| 1 | 完全按照文档长度比例进行归一化 |
当 b=0:
文档长度不再参与调整。
当 b=1:
文档长度会完整参与归一化。
6.4 长文档与短文档的影响
假设:
对于长度为 50 的文档:
对于长度为 200 的文档:
在其他条件相同的情况下:
- 短文档的长度调整项较小。
- 长文档的长度调整项较大。
由于长度调整项位于 BM25 词频分式的分母中,因此长文档通常会受到更强的长度惩罚。
不过,实际分数仍然取决于词频、IDF 和其他参数,不能仅根据文档长度判断最终排序。
七、完整理解 BM25 的评分机制
现在将 TF、IDF 和文档长度归一化结合起来。
完整公式:
可以将其理解为:
每个查询词分别计算贡献,再将所有查询词的贡献累加,得到文档的最终评分。
7.1 评分过程拆解
假设查询为:
Java 线程池
文档为:
Java 线程池能够管理工作线程,并通过线程池参数控制并发数量。
系统需要分别计算:
- Java 对该文档的贡献。
- 线程池对该文档的贡献。
然后将两部分相加:
其中每个词项的评分都包含 IDF、词频和长度归一化。
7.2 完整评分流程
flowchart TD
A["用户提交查询"] --> B["查询文本分析与分词"]
B --> C["提取查询词项"]
C --> D["倒排索引查找候选文档"]
D --> E["读取词频与文档长度"]
E --> F["计算查询词 IDF"]
F --> G["计算词频饱和"]
G --> H["执行文档长度归一化"]
H --> I["累加各查询词评分"]
I --> J["得到 BM25 分数"]
J --> K["按分数降序排序"]
K --> L["返回 Top-K 文档"]
style A fill:#DCEFE5,stroke:#4F8B70,color:#24563F
style B fill:#EAF3EC,stroke:#83A995,color:#315D49
style C fill:#EAF3EC,stroke:#83A995,color:#315D49
style D fill:#EAF3EC,stroke:#83A995,color:#315D49
style E fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style F fill:#EAF3EC,stroke:#83A995,color:#315D49
style G fill:#EAF3EC,stroke:#83A995,color:#315D49
style H fill:#EAF3EC,stroke:#83A995,color:#315D49
style I fill:#EAF3EC,stroke:#83A995,color:#315D49
style J fill:#F5F8F4,stroke:#B5CBBB,color:#40594A
style K fill:#EAF3EC,stroke:#83A995,color:#315D49
style L fill:#E5F0E9,stroke:#83A995,color:#315D49
八、BM25 完整计算示例
通过一个具体例子理解 BM25 的计算过程。
假设文档集合中有 1000 篇文档,用户查询:
Java 线程池
当前需要计算文档 A 的相关性。
文档 A:
Java 线程池能够管理工作线程,线程池可以控制并发任务数量。
假设经过分词后,查询包含两个词项:
Java
线程池
已知统计数据:
| 参数 | Java | 线程池 |
|---|---|---|
| 文档集合总数 N | 1000 | 1000 |
| 包含该词的文档数 n | 600 | 100 |
| 当前文档中的词频 f | 1 | 2 |
另外:
8.1 计算长度归一化项
代入:
8.2 计算 Java 的 IDF
8.3 计算线程池的 IDF
可以看到,“线程池”出现的文档更少,因此 IDF 更高。
8.4 计算 Java 的词频贡献
因此:
8.5 计算线程池的词频贡献
因此:
8.6 计算最终 BM25 分数
这个结果说明,在给定统计数据和参数的条件下,文档 A 与查询具有一定的相关性。
需要注意,BM25 分数不是概率,也没有统一的最大值。它主要用于同一检索系统、相同评分配置下的候选文档排序。
九、BM25 的实际实现
理解公式之后,可以通过 Python 实现一个简化版本。
下面的实现假设输入已经完成分词,并且查询与文档都使用相同的词项规范化规则。