AI论文解读 | 基于熵的BM25语义相似增强搜索 BMX

AI论文解读 | 基于熵的BM25语义相似增强搜索 BMX

1 前置知识

好的，为了更好地理解论文《BMX : Entropy-weighted Similarity and Semantic-enhanced Lexical Search》，你需要掌握以下基础知识：

1. 信息检索 (Information Retrieval, IR)

• 定义: 信息检索是指从大量非结构化文本数据（通常是文档）中找到与用户需求相关的文档的过程。简单来说，就是“搜索”。
• 例子: 你在Google上搜索“如何做红烧肉”，Google会返回一系列与红烧肉做法相关的网页，这就是信息检索。

2. 词汇搜索 (Lexical Search)

• 定义: 词汇搜索是一种基于关键词匹配的搜索方法。它主要关注查询 (Query) 和文档 (Document) 之间字面上的匹配程度，而不考虑语义信息。
• 原理: 词汇搜索会将查询分解成一个个关键词，然后在文档中查找这些关键词。如果文档中包含的关键词越多，或者关键词的权重越高，那么该文档与查询的相关性就越高。
• 例子: 如果你搜索 "best cat food"，词汇搜索会查找包含 "best", "cat", "food" 这三个词的文档。

3. BM25 算法

• 定义: BM25 是一种经典的词汇搜索算法，也是论文中 BM X 的基础。它在 TF-IDF 的基础上进行了改进，考虑了文档长度等因素，使得搜索结果更加准确。

• 公式:

  score(D, Q) = ∑ IDF(qi) *  F(qi, D) * (k1 + 1) / (F(qi, D) + k1 * (1 - b + b * |D| / avgdl))  
  

• D: 文档 (Document)
• Q: 查询 (Query)
• qi: 查询中的第 i 个词 (Term)
• IDF(qi): 逆文档频率 (Inverse Document Frequency)，衡量词 qi 的重要性。如果一个词在很多文档中都出现，那么它的 IDF 值就低，反之则高。
• F(qi, D): 词频 (Term Frequency)，表示词 qi 在文档 D 中出现的次数。
• |D|: 文档 D 的长度 (Document Length)，即文档包含的词的数量。
• avgdl: 平均文档长度 (Average Document Length)，表示所有文档的平均长度。
• k1, b:  BM25 的两个可调参数，用于控制词频和文档长度对评分的影响。

• 理解:

• IDF: 常见的词（如“的”、“是”）IDF低，不常见的词（如“量子”、“区块链”）IDF高。
• TF: 某个词在文档中出现的次数越多，文档和查询的相关性越高。
• 文档长度归一化: 长文档更容易包含查询词，因此BM25会根据文档长度进行惩罚，避免长文档获得过高的分数。

4. TF-IDF (Term Frequency - Inverse Document Frequency)

• 定义: TF-IDF 是一种用于信息检索和文本挖掘的常用加权技术。它用于评估一个词对于一个文档集合或语料库中的其中一份文档的重要程度。

• 原理: TF-IDF 的核心思想是：一个词在文档中出现的频率越高，同时在整个文档集合中出现的频率越低，那么这个词就越能代表该文档的主题。

• 公式:

  TF-IDF = TF * IDF  
  

• TF: 词频 (Term Frequency)
• IDF: 逆文档频率 (Inverse Document Frequency)

• 例子: 假设我们有一个文档集合，其中一篇文档的内容是 "猫喜欢吃鱼，猫很可爱"。

• "猫" 在这篇文档中出现了 2 次，所以 TF 较高。
• 如果 "猫" 在整个文档集合中出现的频率很低，那么 IDF 也较高。
• 因此，"猫" 这个词的 TF-IDF 值会比较高，说明 "猫" 这个词对于这篇文档来说比较重要。

5. 熵 (Entropy)

• 定义: 在信息论中，熵用于衡量一个随机变量的不确定性。熵越大，不确定性越高；熵越小，不确定性越低。

• 公式:

  H(X) = - ∑ p(xi) * log(p(xi))  
  

• X: 随机变量
• xi: 随机变量 X 的可能取值
• p(xi): 随机变量 X 取值为 xi 的概率

• 理解:

• 事件 A：明天一定会下雨 (概率为 1)
• 事件 B：明天有 50% 的概率下雨，50% 的概率不下雨
• 事件 A 的熵为 0，因为确定性很高。
• 事件 B 的熵较高，因为不确定性较高。
• 例子: 假设有两个事件：

• 在论文中的应用: 论文使用熵来衡量查询词的信息量。如果一个查询词在很多文档中都出现，那么它的熵就高，信息量就低；反之，如果一个查询词只在少数文档中出现，那么它的熵就低，信息量就高。

6. 语义搜索 (Semantic Search)

• 定义: 语义搜索是一种基于语义理解的搜索方法。它不仅关注查询和文档之间字面上的匹配程度，还关注它们之间的语义关系。
• 原理: 语义搜索会利用自然语言处理 (NLP) 技术，例如词嵌入 (Word Embedding) 和知识图谱 (Knowledge Graph)，来理解查询和文档的含义，从而找到与用户需求真正相关的文档。
• 例子: 如果你搜索 "世界上最大的猫科动物"，语义搜索不仅会查找包含 "最大"、"猫科动物" 等关键词的文档，还会理解 "最大" 的含义，从而返回与 "老虎"、"狮子" 等相关的文档。

7. 词嵌入 (Word Embedding)

• 定义: 词嵌入是一种将词语映射到低维向量空间的技术。通过词嵌入，可以将词语之间的语义关系转化为向量之间的距离关系。
• 例子: "猫" 和 "狗" 在语义上比较接近，因此它们的词向量在向量空间中的距离也会比较近。
• 常见的词嵌入模型: Word2Vec, GloVe, FastText, BERT 等。

8. 大语言模型 (Large Language Model, LLM)

• 定义: 大语言模型是一种基于深度学习的自然语言处理模型。它通过在大规模文本数据上进行训练，学习语言的规律，从而能够生成自然流畅的文本，并完成各种自然语言处理任务。
• 例子: GPT-3, GPT-4, LLaMA, PaLM 等。
• 在论文中的应用: 论文使用 LLM 进行查询扩展 (Query Augmentation)，即根据原始查询生成一些语义相关的查询，从而提高搜索的准确性。

9. 查询扩展 (Query Augmentation)

• 定义: 查询扩展是一种通过向原始查询添加相关词语来改进搜索结果的技术。
• 目的: 提高搜索的召回率 (Recall)，即找到更多与用户需求相关的文档。
• 方法:
• 基于词典的查询扩展: 使用同义词词典 (例如 WordNet) 或知识图谱来查找与原始查询词相关的词语。
• 基于机器学习的查询扩展: 使用机器学习模型 (例如 LLM) 来生成与原始查询语义相关的查询。

10. NDCG (Normalized Discounted Cumulative Gain)

• 定义: NDCG 是一种用于评估排序结果的指标。它考虑了文档的相关性和排序位置。
• 原理: NDCG 的核心思想是：相关性高的文档应该排在前面，并且排名越靠前，对 NDCG 的贡献越大。
• 理解: NDCG 的值越高，说明排序结果越好。

总结

理解了以上基础知识，你就能更好地理解论文《BMX : Entropy-weighted Similarity and Semantic-enhanced Lexical Search》了。简单来说，这篇论文提出了一种新的词汇搜索算法 BM X，它在 BM25 的基础上，引入了熵加权相似度和语义增强技术，从而提高了搜索的准确性。

希望这些解释对你有所帮助！

2 解读论文

好的，我们来深入解读一下这篇论文《BMX : Entropy-weighted Similarity and Semantic-enhanced Lexical Search》。

论文核心思想

这篇论文的核心是改进传统的词汇搜索算法 BM25，使其在效率不降低太多的前提下，能够更好地理解查询和文档的语义信息，从而提高搜索的准确性。作者提出了 BM X 算法，它在 BM25 的基础上，主要做了以下两点改进：

1. 熵加权相似度 (Entropy-weighted Similarity): 考虑查询和文档之间的相似度，并根据查询词的信息量（熵）来调整相似度的权重。
2. 加权查询扩展 (Weighted Query Augmentation, WQA): 利用大语言模型 (LLM) 生成与原始查询相关的扩展查询，并将这些扩展查询与原始查询一起用于搜索，从而引入语义信息。

1. 熵加权相似度 (Entropy-weighted Similarity)

• 问题: BM25 只关注查询词在文档中出现的频率，忽略了查询和文档的整体相似度。此外，BM25 对所有查询词都一视同仁，没有区分哪些词更重要。

• 解决方案: BM X 引入了熵加权相似度，具体步骤如下：

1. 计算查询词的熵: 熵用于衡量一个查询词的信息量。如果一个词在很多文档中都出现，那么它的熵就高，信息量就低；反之，如果一个词只在少数文档中出现，那么它的熵就低，信息量就高。
2. 计算查询和文档的相似度: 使用简单的词 overlap 来计算查询和文档的相似度。
3. 将相似度与熵加权: 将查询和文档的相似度乘以查询词的熵，从而使得信息量高的查询词对最终的搜索结果产生更大的影响。

score(D, Q) = ∑ IDF(qi) * F(qi, D) * (α + 1.0) / (F(qi, D) + α * |D| / avgdl + α * E) + β * E(qi) * S(Q, D)  

• E(qi): 查询词 qi 的归一化熵。
• S(Q, D): 查询 Q 和文档 D 之间的相似度。
• β: 用于控制相似度项的权重。

• "cat" 和 "food" 的熵可能较低，因为它们是比较常见的词。
• "best" 的熵可能较高，因为它更具有区分性。
• BM X 会给文档 1 更高的分数，因为它不仅包含查询词，而且与查询的整体语义更相似。

2. 加权查询扩展 (Weighted Query Augmentation, WQA)

• 问题: 词汇搜索无法理解同义词、近义词等语义信息。例如，如果用户搜索 "big car"，但文档中只包含 "large automobile"，那么词汇搜索可能无法找到该文档。

• 解决方案: BM X 使用 LLM 进行查询扩展，具体步骤如下：

1. 使用 LLM 生成扩展查询: 将原始查询输入到 LLM 中，让 LLM 生成一些与原始查询语义相关的扩展查询。
2. 对扩展查询进行加权: 为每个扩展查询分配一个权重，表示该扩展查询与原始查询的相关程度。
3. 将扩展查询与原始查询一起用于搜索: 将原始查询和扩展查询一起输入到 BM X 算法中，从而提高搜索的召回率。

score(D, Q, QA) = score(D, Q) + ∑ wi * score(D, QA_i)  

• QA: 扩展查询的集合。
• QA_i: 第 i 个扩展查询。
• wi: 第 i 个扩展查询的权重。

• "top rated feline diet" (权重 0.8)
• "good quality kitten nutrition" (权重 0.7)
• BM X 会将这些扩展查询与原始查询一起用于搜索，从而找到更多与猫粮相关的文档。

3. 实验结果

论文通过大量的实验证明了 BM X 的有效性。实验结果表明：

• BM X 在多个信息检索 benchmark 上都优于传统的 BM25 算法。
• BM X 在长文本检索任务上表现出色，甚至超过了一些基于 LLM 的文本嵌入模型。
• 加权查询扩展 (WQA) 能够显著提高 BM X 的性能。

4. 总结

BM X 是一种有效的词汇搜索算法，它通过引入熵加权相似度和加权查询扩展，提高了搜索的准确性和召回率。BM X 的主要优点包括：

• 高效: BM X 仍然是一种词汇搜索算法，因此具有较高的搜索效率。
• 可解释性强: BM X 的搜索结果可以很容易地解释，因为它主要基于关键词匹配。
• 通用性强: BM X 可以应用于各种信息检索任务，不需要针对特定领域进行训练。

5. 论文的贡献

• 提出了 BM X 算法，它在 BM25 的基础上，引入了熵加权相似度和加权查询扩展。
• 设计了一种有效的加权查询扩展方法，可以利用 LLM 提高搜索的准确性。
• 通过大量的实验证明了 BM X 的有效性。
• 开源了 Baguetter 搜索引擎库，方便研究人员使用 BM X 算法。

希望这个更深入的解读能够帮助你更好地理解这篇论文！

3 术语

好的，我们来提取并详细解释《BMX : Entropy-weighted Similarity and Semantic-enhanced Lexical Search》论文中的一些重要术语，并使用 Markdown 图形进行辅助说明。

1. BM25 (Best Matching 25)

• 定义: 一种广泛使用的词汇搜索算法，是信息检索领域的基础算法之一。它基于词频 (Term Frequency, TF) 和逆文档频率 (Inverse Document Frequency, IDF) 来评估文档与查询的相关性。

• 核心思想: 某个词在文档中出现的频率越高，且在整个文档集合中出现的文档数越少，则该词对文档的重要性越高。

• 公式 (论文中的公式 1):

  score(D, Q) = ∑ IDF(qi) * F(qi, D) * (k1 + 1) / (F(qi, D) + k1 * (1 - b + b * |D| / avgdl))  
  

• D: 文档
• Q: 查询
• qi: 查询中的第 i 个词
• IDF(qi): 词 qi 的逆文档频率
• F(qi, D): 词 qi 在文档 D 中的词频
• |D|: 文档 D 的长度
• avgdl: 文档集合的平均文档长度
• k1, b: 调节参数

• 图示:

• 局限性:

• 忽略查询和文档的整体相似度。
• 缺乏语义理解，无法处理同义词、近义词等。

2. 熵 (Entropy)

• 定义: 在信息论中，熵用于衡量一个随机变量的不确定性。在本论文中，熵被用来衡量一个查询词的信息量。

• 核心思想: 如果一个词在很多文档中都出现，那么它的熵就高，信息量就低；反之，如果一个词只在少数文档中出现，那么它的熵就低，信息量就高。

• 公式 (论文中的公式 5):

  E(qi) = ˜E(qi) / max(˜E(q1), ..., ˜E(qm))  
  ˜E(qi) = - ∑ pj log pj  
  pj = sigmoid(F(qi, Dsj)) = 1 / (1 + exp(-F(qi, Dsj)))  
  

• E(qi): 查询词 qi 的归一化熵。
• ˜E(qi): 查询词 qi 的原始熵。
• pj: 查询词 qi 在包含该词的文档 Dsj 中的频率的 sigmoid 函数值。
• F(qi, Dsj): 查询词 qi 在文档 Dsj 中的词频。

• 图示:

  

• 作用: 用于在 BM X 中对查询词的相似度进行加权，使得信息量高的查询词对最终的搜索结果产生更大的影响。

3. 熵加权相似度 (Entropy-weighted Similarity)

• 定义: BM X 算法的核心组成部分之一，它将查询和文档之间的相似度与查询词的熵相结合，从而更好地评估文档与查询的相关性。

• 核心思想: 考虑查询和文档的整体相似度，并根据查询词的信息量（熵）来调整相似度的权重。

• 公式 (论文中的公式 2):

  score(D, Q) = ∑ IDF(qi) * F(qi, D) * (α + 1.0) / (F(qi, D) + α * |D| / avgdl + α * E) + β * E(qi) * S(Q, D)  
  

• E(qi): 查询词 qi 的归一化熵。
• S(Q, D): 查询 Q 和文档 D 之间的相似度。
• β: 用于控制相似度项的权重。

• 图示:

  

• 作用: 弥补了 BM25 忽略查询和文档整体相似度的缺陷，提高了搜索的准确性。

4. 加权查询扩展 (Weighted Query Augmentation, WQA)

• 定义: BM X 算法的另一个核心组成部分，它利用大语言模型 (LLM) 生成与原始查询相关的扩展查询，并将这些扩展查询与原始查询一起用于搜索，从而引入语义信息。

• 核心思想: 通过 LLM 扩展查询，引入同义词、近义词等语义信息，从而提高搜索的召回率。

• 公式 (论文中的公式 9):

  score(D, Q, QA) = score(D, Q) + ∑ wi * score(D, QA_i)  
  

• QA: 扩展查询的集合。
• QA_i: 第 i 个扩展查询。
• wi: 第 i 个扩展查询的权重。

• 图示:

  

• 作用: 弥补了词汇搜索缺乏语义理解的缺陷，提高了搜索的召回率。

5. Baguetter

• 定义: 一个开源的 Python 搜索引擎库，由论文作者开发，用于实现和评估 BM X 算法。
• 特点:
• 灵活、高效、可定制。
• 支持稀疏、稠密和混合检索方法。
• 提供统一的搜索接口。

总结

这些术语是理解 BM X 论文的关键。BM X 通过熵加权相似度和加权查询扩展，在 BM25 的基础上，提高了搜索的准确性和召回率，并在多个信息检索 benchmark 上取得了优异的成绩。

参考

https://arxiv.org/pdf/2408.06643

https://github.com/paradedb/paradedb/tree/dev/pg_search

https://docs.paradedb.com/documentation/concepts/bm25

https://github.com/jirutka/smlar

《PostgreSQL pg_bm25(open source by paradedb)：Postgres 内部的弹性质量全文搜索 性能优于tsvector tsrank 20x》

《PostgreSQL+pg_bestmatch+pgvector 打造适合自己文档库的TF-IDF加权, 库内将文本转换为向量, 提升文本搜索精确度和性能》

《PostgreSQL结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 1 文本(关键词)分析理论基础 - TF(Term Frequency 词频)/IDF(Inverse Document Frequency 逆向文本频率)》

《使用 PolarDB 开源版 smlar 插件进行高效率相似文本搜索、自助选药、相似人群圈选等业务》

《PostgreSQL 在资源搜索中的设计 - pase, smlar, pg_trgm - 标签+权重相似排序 - 标签的命中率排序》

《社交、电商、游戏等 推荐系统 (相似推荐) - 阿里云pase smlar索引方案对比》

《PostgreSQL 相似搜索插件介绍大汇总 (cube,rum,pg_trgm,smlar,imgsmlr,pg_similarity) (rum,gin,gist)》

《海量数据,海明(simhash)距离高效检索(smlar) - 阿里云RDS PosgreSQL最佳实践 - bit string 比特字符串 相似度搜索》

《PostgreSQL结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 3 rum, smlar应用场景分析》

《PostgreSQL结合余弦、线性相关算法 在文本、图片、数组相似 等领域的应用 - 2 smlar插件详解》

https://www.geeksforgeeks.org/understanding-tf-idf-term-frequency-inverse-document-frequency/

 以上内容基于DeepSeek、QwQ及诸多AI生成, 轻微人工调整, 感谢杭州深度求索人工智能、阿里云等公司. 

 AI 生成的内容请自行辨别正确性, 当然也多了些许踩坑的乐趣, 毕竟冒险是每个男人的天性.