您的位置:

python实现bm25算法的简单介绍

本文目录一览:

求解python语句

format是一种格式化输出,你可以查一下,这句话的作用就是把tmp中4个元素按顺序填到前面的4个{}中,前面的 代表右对齐,后面的数字表示一个占几个字符,:表示规定空白位置补什么

BM25算法

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

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

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

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

假设一:二元假设

所谓二元假设,类似于布尔模型的表示方法,一篇文章在由特征表示的时候,以特征“出现”和“不出现”两种情况来表示,也可以理解为相关不相关。

假设二:词汇独立性假设

所谓独立性假设,是指文档里出现的单词之间没有任何关联,任一个单词在文章中的分布率不依赖于另一个单词是否出现,这个假设明显与事实不符,但是为了简化计算,很多地方需要做出独立性假设,这种假设是普遍的。

在以上两个假设的前提下,二元独立模型即可以对两个因子P(D|R)和P(D|NR)进行估算(条件概率),举个简单的例子,文档D中五个单词的出现情况如下:{1,0,1,0,1} 0表示不出现,1表示出现。用Pi表示第i个单词在相关文档中出现的概率,在已知相关文档集合的情况下,观察到文档D的概率为:

对于因子P(D|NR),我们假设用Si表示第i个单词在在不相关文档集合中出现的概率,于是在已知不相关文档集合的情况下,观察到文档D的概率为:

于是我们可以得到下面的估算

可以将各个因子规划为两个部分,一部分是在文档D中出现的各个单词的概率乘积,另一部分是没在文档D中出现的各个单词的概率乘积,于是公式可以理解为下面的形式

对公式进行一下等价的变换,可得:

为了方便计算,对上述公式两边取log,得到:

那么如何估算概率Si和Pi呢,如果给定用户查询,我们能确定哪些文档集合构成了相关文档集合,哪些文档构成了不相关文档集合,那么就可以用如下的数据对概率进行估算:

根据上表可以计算出Pi和Si的概率估值,为了避免log(0),对估值公式进行平滑操作,分子+0.5,分母+1.0

代入估值公式得到:

这个公式代表的含义就是,对于同时出现在查询Q和文档D中的单词,累加每个单词的估值结果就是文档D和查询Q的相关性度量,在预先不知道哪些文档相关哪些文档不相关的情况下,可以使用固定值代替,这种情况下该公式等价于向量空间模型(VSM)中的IDF因子,实际证明该模型的实际使用结果不好,但是它是BM25模型的基础。

后来人们发现应该讲BIM中没有考虑到的词频和文档长度等因素都考虑进来,就有了后面的BM25算法。

BIM(二元假设模型)对于 单词特征 ,只考虑单词是否在 doc中出现过 ,并没有考虑 单词本身的相关特征 ,BM25在BIM的基础上引入单词在查询中的权值,单词在doc中的权值,以及一些经验参数,所以BM25在实际应用中效果要远远好于BIM模型。

BM25由3部分组成:

在第二部分中K因子代表了文档长度的考虑,dl是文档的长度,avdl是文档的平均长度,k1和b是调整参数,b为0时即不考虑文档长度的影响,经验表明b=0.75左右效果比较好。但是也要根据相应的场景进行调整。b越大对文档长度的惩罚越大,k1因子用于调整词频,极限情况下k1=0,则第二部分退化成1,及词频特征失效,可以证明k1越大词频的作用越大。

在我们不知道哪些文档相关,哪些文档不相关的情况下,将相关文档数R及包含查询词相关文档数r设为0,那么第一部分的BIM公式退化成:

就是IDF因子的定义,N是总文档数,n是查询词的tf信息,0.5是平滑因子。

文本相似度算法

TF是指归一化后的词频,IDF是指逆文档频率。给定一个文档集合D,有d1,d2,d3,......,dn∈D。文档集合总共包含m个词(注:一般在计算TF−IDF时会去除如“的”这一类的停用词),有w1,w2,w3,......,wm∈W。我们现在以计算词wi在文档dj中的TF−IDF指为例。

TF的计算公式为:

TF=freq(i,j) / maxlen(j)

在这里freq(i,j) 为wi在dj中出现的频率,maxlen(j)为dj长度。

TF只能时描述词在文档中的频率,但假设现在有个词为”我们“,这个词可能在文档集D中每篇文档中都会出现,并且有较高的频率。那么这一类词就不具有很好的区分文档的能力,为了降低这种通用词的作用,引入了IDF。

IDF的表达式如下:

IDF=log(len(D) / n(i))

在这里len(D)表示文档集合D中文档的总数,n(i)表示含有wi这个词的文档的数量。

得到TF和IDF之后,我们将这两个值相乘得到TF−IDF的值:

TF−IDF=TF∗IDF

TF可以计算在一篇文档中词出现的频率,而IDF可以降低一些通用词的作用。因此对于一篇文档我们可以用文档中每个词的TF−IDF组成的向量来表示该文档,再根据余弦相似度这类的方法来计算文档之间的相关性。

BM25算法通常用来做搜索相关性评分的,也是ES中的搜索算法,通常用来计算query和文本集合D中每篇文本之间的相关性。我们用Q表示query,在这里Q一般是一个句子。在这里我们要对Q进行语素解析(一般是分词),在这里以分词为例,我们对Q进行分词,得到q1,q2,......,qt这样一个词序列。给定文本d∈D,现在以计算Q和d之间的分数(相关性),其表达式如下:

Score(Q,d)=∑ti=1wi∗R(qi,d)

  上面式子中wi表示qi的权重,R(qi,d)为qi和d的相关性,Score(Q,d)就是每个语素qi和d的相关性的加权和。

wi的计算方法有很多,一般是用IDF来表示的,但这里的IDF计算和上面的有所不同,具体的表达式如下:

wi=IDF(qi)=logN−n(qi)+0.5n(qi)+0.5

上面式子中N表示文本集合中文本的总数量,n(qi)表示包含qi这个词的文本的数量,0.5主要是做平滑处理。

R(qi,d)的计算公式如下:

R(qi,d)=fi∗(k1+1)fi+K∗qfi∗(k2+1)qfi+k2

其中

K=k1∗(1−b+b∗dlavgdl)

上面式子中fi为qi在文本d中出现的频率,qfi为qi在Q中出现的频率,k1,k2,b都是可调节的参数,dl,avgdl分别为文本d的长度和文本集D中所有文本的平均长度。

一般qfi=1,取k2=0,则可以去除后一项,将上面式子改写成:

R(qi,d)=fi∗(k1+1)fi+K

通常设置k1=2,b=0.75。参数b的作用主要是调节文本长度对相关性的影响。

文本抽取式摘要

关键词:抽取式,BM25算法,行业知识后处理。

背景

笔者所在的公司原来已经有一个自动摘要的模块,我只是在原来的基础上,做了些针对特定领域的优化。

首先自动文本摘要大概分为 抽取式和生成式两类。抽取式摘要主要是直接抽取输入文本的几句话来概括整段的内容,这个实现相对简单(常用算法 TextRank、TF-IDF 等,本文使用的是 BM25 算法)。另一种是生成式,生成式的构成比较复杂,实现难度也很大,效果在实际落地过程中也并不理想。所以下文主要是针对抽取式自动摘要来讨论的。

问题的算法抽象

首先抽取式摘要,问题可以归结为从文章中选取和其他句子最相关的那句话。也就是将每句话当成“搜索框”里输入的句子,然后计算其他句子和他的相关度得分,然后选取和其他句子相关性得分最高的那句话作为摘要。

BM25算法:

首先BM25算法在搜索引擎领域是很有用的。这里关于BM25解析,讲的很好的文章:  BM25 - ywl925 - 博客园  。这里就不展开介绍了。

BM25算法得分的归一化

经过BM25算法计算的得分,范围相差会很大,笔者为了实现后面的静态加分,先对BM25算的score进行了一个归一化。归一化一般最常见的两种: Min-Max和Z score,是相对常见的概念。可以参考博客: 数据归一化和两种常用的归一化方法 - ChaoSimple - 博客园

特定领域知识的积累

这里明确一下,这里所说的领域知识,主要是某些很有区分度的词和短语。这里涉及的底层模块也比较多。

首先是特定领域的语料库的积累。

以中文为例,除了一些公开的语料库,我们还需要一些扩充一些专门领域的语料。并对他们进行标注。

然后相应的,分词模块也要增强。

特别是针对那些领域专有的名词。由于现在中文分词的技术已经比较成熟,所以这块相对来说挑战不是很大。而且这面即使是基于HMM或者CRF做的分词,都已经有很可观的实用表现,和相当的泛化。不过如果能把底层的分词的模块性能和准确率提升一点,也会有很大的帮助,毕竟在中文文本处理中,分词是第一步要做的基础操作。

行业知识静态加分

这里的实现目前还是比较粗糙的。首先总结每个行业有区分度的词。这个词的获取会上面提到的特定的行业语料库,以及针对这个领域的分词。

在句子计算BM25得分,并归一化后,这里判断句子里面是否有领域关键词,如果有领域关键词,则静态的给归一化后的BM25 分数加一个静值。 之后对各个句子,按照这个新的分数排序。抽取得分最高的那句话。

这里还有一个问题可以深挖,就是笔者目前实现的领域知识加分,是在已经预先分好了分类的前提下,也就是说传入的参数,除了原文还会有属于哪个领域的具体信息。如果这个领域分类信息没有提前获得,那么就需要对整段文字做一个大概的分类,这样的难度就会大增。我们后续可以继续讨论这种情况。

经典检索算法:BM25原理

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

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

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

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

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相关性建模:

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

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

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

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

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

3个部分来介绍bm25算法。

,也就是有多少文档包含某个单词信息进行变换。如果在这里使用 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 频率进行缩放控制。

于是最后的公式是:

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

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

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

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

BM25 算法浅析

搜索之 BM25 和 BM25F 模型

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

信息检索导论

【转】相关性打分

原文: ;wd=eqid=c38628d80000913b000000055f5c827a

BM25算法是一种常见用来做相关度打分的公式,思路比较简单,主要就是计算一个query里面所有term和文档的相关度,然后在把分数做累加操作,而每个词的相关度分数主要还是受到tf/idf的影响。公式如下:

其中: 是每个词和文档的相关度值; 代表query中的term; 代表相关的文档; 是词 的权重。

可由外部设置,默认是 值,idf公式的基本思想是:词的重要程度和其出现在总文档集合里的频率成反比。其公式如下:

其中: 是文档总数; 是包含该词的文档数;0.5是调教系数,避免 为0的情况。取个log是为了让idf的值受N和 的影响更加平滑。

从这个公式可以看出当 越大, 越小时 值越大,

下面是 的公式,

其中: , , 都是调节因子,一般 , , ; 是词 在文档中的次数, 代表词在查询句里的次数; 是文档长度, 是文档平均长度;

可以看出如果其他因素一样 越大,相关度越低;至于除以一个 ,我想是拿本篇文档长度和整体文档长度水平做比较 ,以免单独取 值时过大。

乘积的左边因数代表词在文档中的次数关系,乘积的右边因数代表词在查询语句中的次数关系。绝大多数情况下,查询词在查询语句里面出现一次,所以 可以看成是1,又因为 为1,所以右边因数其实就等于1,所以公式可化简为下面这样:

公式化简后可得:

影响BM25公式的因数有

1 : 越高分数越高

2 : 越高分数越高

3 : 如果该文档长度在文档水平中越高则分数越低。

4 为分数的调节因子

一般情况下,一篇文章是分为多个部分的,如 title,content,description,anchor 等,在BM25F算分公式中,这些部分被称为域(field)。有两篇文章,一篇文章的title部分与query 的BM25相关性得分为 a, 另一篇文章的content部分与query 的BM25相关性得分也为 a。假设不考虑这两篇文章其他部分与query的相关性情况,根据经验,一般第一篇文章应该应该比第一篇文章更相关。BM25F 引入了文章d的每个域的信息,它将每个term在文章d中的每个域中的相关性进行了处理。公式如下:

BM25 被也称为 Okapi BM25 , OkaTP是BM25与 term proximity 融合的相关性计算公式。

query中第 个term的权重定义为:

可以发现 的定义在形式上比较像BM25中 query部分与IDF 的乘积。 区别是常量参数的设置。在论文中设置 .

term proximity 定义如下

is the distance expressed in number of words between search term and .

下式体现了BM25与 term proximity 的融合, 该算法将BM25中的tf 替换成了

的定义和BM25相同。

OkaTP 最终定义为

其中 S是 query中所有term 两两组合的集合。

该算法与 OkaTP 非常相似。

其中TP即 term proximity,在该算法中引入了proximity 信息来优化相关性计算效果。

假设一个query q中包含n个term , 表示一篇文章,任意两个不同term 在文章 中所处位置的距离表示为 。这两个term的

note: query中的第 个term可能在 document 可能出现多次, 每一次出现用 表示。

原始论文见 Term proximity scoring for ad-hoc retrieval on very large text collections

可以结合文章 Selective Term Proximity Scoring Via BP-ANN 理解上面第2,3两个公式。

文章认为OkaTP存在两个方面的问题 1. OkaTP 算分公式的后面部分(可以看做对于prase的算分)和前面的BM25部分是有重叠的,即一个term会同时出现在前后两个部分; 2.Linear combination of scores of unigrams and those of loose phrases may break the non-linear property of term frequency。

基于这两点提出了 newTP算法。 newTP中引入了 span的概念。 span 是根据query term在一个docment中的命中位置,将整个命中列表分割为多个片段,每个片段称为一个 expanded span。 span 的确定规则如下。

其中 MAX_DIS 是认为设定的。

根据span的中 query term的密度和数量来确定一个term对于相关性的贡献。从而取代OkaTP 中的 tpi 和 tf部分。

一个 中的term t的 对于相关性的贡献表示为:

其中:

一个term t 在整个document 中对相关性的贡献为:

可以看出 rc 中包含了 proximity的信息 和 tf的信息。

直接用 rc 替换 BM25 中的 tf, 得到新的相关性计算公式:

其中TOP即 term order proximity. 该算法是在BM25TP的基础上进行的优化。在该算法中引入了 term oder信息, 如果两个term在 query中出现的顺序 与 其在document中的顺序相反则进行惩罚, 如果顺序相同则 reward。

在BM25TP算法中 使用的 来计算proximity, 但是这个公式对于term oder是不敏感的。就会认为 John is faster than Mary 和 Mary is faster than John 两个句子是相同的。

为了说明 BM25TOP算法,先引入如下两个定义。

: The position of in query Q

: The position of in document d

在BM25TOP 中使用了一个新的公式对 进行了替换。这个公式应该符合如下三个条件。

满足前两条是BM25TP算法中dist 函数也能满足的,第三条是增加考虑 term order 的一项。

满足以上三个条件的公式挺多,论文中选择了如下公式。

其中

的大小表示 和 在文档 d 中 的相对距离,符号说明了这两个term在query和document中的顺序是否相同,正号(+) 表示顺序相同,符号(-) 表示这两个term在query和document中的顺序相反。

随 的函数变化图像如下:

[图片上传中...(image-8d6891-1599898211594-0)]

note: proximity 是 的倒数, 值越大 proximity 越小。

从上图可以看出,两个term距离越远, 越大, proximity 越小;

当对于两对term的 的大小相等,但符号相反时,符号为负(-) 的一对 term 的proximity会更小。

下面将BM25TOP的计算公正整理如下:

其中: