经典检索算法:BM25原理

image.png

本文cmd地址:经典检索算法:BM25原理

bm25 是什么?

bm25 是一种用来评价搜索词和文档之间相关性的算法,它是一种基于概率检索模型提出的算法,再用简单的话来描述下bm25算法:我们有一个query和一批文档Ds,现在要计算query和每篇文档D之间的相关性分数,我们的做法是,先对query进行切分,得到单词$q_i$,然后单词的分数由3部分组成:

  • 单词$q_i$和D之间的相关性
  • 单词$q_i$和D之间的相关性
  • 每个单词的权重

最后对于每个单词的分数我们做一个求和,就得到了query和文档之间的分数。

bm25 解释

讲bm25之前,我们要先介绍一些概念。

二值独立模型 BIM

BIM(binary independence model)是为了对文档和query相关性评价而提出的算法,BIM为了计算$P(R|d,q)$,引入了两个基本假设:

假设1 一篇文章在由特征表示的时候,只考虑词出现或者不出现,具体来说就是文档d在表示为向量$\vec x=(x_1,x_2,...,x_n)$,其中当词$t$出现在文档d时,$x_t=1$,否在$x_t=0$。 假设2 文档中词的出现与否是彼此独立的,数学上描述就是$P(D)=\sum_{i=0}^n P(x_i)$ 有了这两个假设,我们来对文档和query相关性建模:

其中

分别表示当返回一篇相关或不相关文档时文档表示为x的概率。

接着因为我们最终得到的是一个排序,所以,我们通过计算文档和query相关和不相关的比率,也可得文档的排序,有下面的公式:

其中

是常数,我们可以不考虑,再根据之前的假设2:一个词的出现 与否与任意一个其他词的出现与否是互相独立的,我们可以化简上面的式子:

由于每个 xt 的取值要么为 0 要么为 1,所以,我们可得到:

我们接着引入一些记号:

:词出现在相关文档的概率

:词出现在不相关文档的概率

于是我们就可得到:

我们接着做下面的等价变换:

此时,公式中

根据出现在文档中的词计算,

则是所有词做计算,不需要考虑,此时我们定义RSV (retrieval status value),检索状态值:

定义单个词的ct

下一步我们要解决的就是怎么去估计pt和ut,看下表:

其中dft是包含词t的文档总数,于是

, 此时词t的ct值是:

为了做平滑处理,我们都加上1/2,得到:

在实际中,我们很难知道t的相关文档有多少,所以假设S=s=0,所以:

其中N是总的文档数,dft是包含t的文档数。

以上就是BIM的主要思想,后来人们发现应该讲BIM中没有考虑到的词频和文档长度等因素都考虑进来,就有了后面的BM25算法,下面按照

  • 单词t和D之间的相关性
  • 单词t和D之间的相关性
  • 每个单词的权重

3个部分来介绍bm25算法。

单词权重

单词的权重最简单的就是用idf值,即

,也就是有多少文档包含某个单词信息进行变换。如果在这里使用 IDF 的话,那么整个 BM25 就可以看作是一个某种意义下的 TF-IDF,只不过 TF 的部分是一个复杂的基于文档和查询关键字、有两个部分的词频函数,还有一个就是用上面得到的ct值。

单词和文档的相关性

tf-idf中,这个信息直接就用“词频”,如果出现的次数比较多,一般就认为更相关。但是BM25洞察到:词频和相关性之间的关系是非线性的,具体来说,每一个词对于文档相关性的分数不会超过一个特定的阈值,当词出现的次数达到一个阈值后,其影响不再线性增长,而这个阈值会跟文档本身有关。

在具体操作上,我们对于词频做了”标准化处理“,具体公式如下:

其中,tftd 是词项 t 在文档 d 中的权重,Ld 和 Lave 分别是文档 d 的长度及整个文档集中文档的平均长度。k1是一个取正值的调优参数,用于对文档中的词项频率进行缩放控制。如果 k 1 取 0,则相当于不考虑词频,如果 k 1取较大的值,那么对应于使用原始词项频率。b 是另外一个调节参数 (0≤ b≤ 1),决定文档长度的缩放程度:b = 1 表示基于文档长度对词项权重进行完全的缩放,b = 0 表示归一化时不考虑文档长度因素。

单词和查询的相关性

如果查询很长,那么对于查询词项也可以采用类似的权重计算方法。

其中,tftq是词项t在查询q中的权重。这里k3 是另一个取正值的调优参数,用于对查询中的词项tq 频率进行缩放控制。

于是最后的公式是:

bm25 gensim中的实现

gensim在实现bm25的时候idf值是通过BIM公式计算得到的:

然后也没有考虑单词和query的相关性。

其中几个关键参数取值:

PARAM_K1 = 1.5
PARAM_B = 0.75
EPSILON = 0.25

此处EPSILON是用来表示出现负值的时候怎么获取idf值的。

总结下本文的内容:BM25是检索领域里最基本的一个技术,BM25 由三个核心的概念组成,包括词在文档中相关度、词在查询关键字中的相关度以及词的权重。BM25里的一些参数是经验总结得到的,后面我会继续介绍BM25的变种以及和其他文档信息(非文字)结合起来的应用。

参考

BM25 算法浅析

搜索之 BM25 和 BM25F 模型

经典搜索核心算法:BM25 及其变种

信息检索导论

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI科技大本营的专栏

900万张标注图像,谷歌发布Open Images最新V3版

翻译 | Shawn 过去几年机器学习的发展使得计算机视觉有了快速的进步,系统能够自动描述图片,对共享的图片创造自然语言回应。其中大部分的进展都可归因于 Ima...

4187
来自专栏机器学习、深度学习

人群密度估计--CrowdNet: A Deep Convolutional Network for Dense Crowd Counting

CrowdNet: A Deep Convolutional Network for Dense Crowd Counting published in ...

3138
来自专栏腾讯移动品质中心TMQ的专栏

机器学习之一:聚类实战

可预见的未来数据分析和机器学习将成为工作中必备技能,也许已经在某个项目中讨论怎么调参优化,就像过去讨论如何优雅的写python、如何避免C++内存泄露一样常见。

2546
来自专栏AI研习社

手把手教你用 Python 实现针对时间序列预测的特征选择

AI 研习社按:本文源自美国机器学习专家 Jason Brownlee 的博客,AI 研习社编译。 要将机器学习算法应用于时间序列数据,需要特征工程的帮助。 例...

6658
来自专栏数据派THU

三步教你搭建给黑白照片上色的神经网络 !(附代码)

来源:量子位 本文长度为7970字,建议阅读8分钟 本文为你介绍通过搭建神经网络,来给黑白照片上色的教程。 深度学习云平台FloydHub最近在官方博客上发了一...

5429
来自专栏人工智能头条

GAN学习指南:从原理入门到制作生成Demo

2607
来自专栏小小挖掘机

windows下使用word2vec训练维基百科中文语料全攻略!(三)

训练一个聊天机器人的很重要的一步是词向量训练,无论是生成式聊天机器人还是检索式聊天机器人,都需要将文字转化为词向量,时下最火的词向量训练模型是word2vec,...

3695
来自专栏算法channel

深度学习|循环神经网络之LSTM(后篇)

01 — 回顾 昨天推送了循环神经网络LSTM的前半部分,说到构成其网络模型:输入层包含一系列时序:x0, x1, ..., xt,隐含层是实现 Long-te...

4348
来自专栏AI研习社

GAN 学习指南:从原理入门到制作生成 Demo,总共分几步?

生成式对抗网络(GAN)是近年来大热的深度学习模型。最近正好有空看了这方面的一些论文,跑了一个 GAN 的代码,于是写了这篇文章来介绍一下 GAN。 本文主要分...

3456
来自专栏AI科技大本营的专栏

如何通过机器学习还原图像色彩

作者 | Klevis Ramo 译者 | Teixeira10 在本文中,作者提出了使用k-means算法来对图像进行色彩还原,介绍算法的步骤,同时应用在图...

35312

扫码关注云+社区

领取腾讯云代金券