Text Retrieval and Search Engines学习笔记(三)

这篇文章是继上一篇Text Retrieval and Search Engines学习笔记(二) 的后续部分，这一篇我们重点介如何绍改进Vector Space Model

Vector Space Model

在上一篇我们介绍了由BOW模型和Dot Product相似度计算方法组成的Simplest Vector Model ,在某种成都上说，这个方法确实解决了一些我们对文档排序的一些需求，但是从上面的例子中我们也可以简单的发现两个问题:

文档中出现关键字presidential越多，分数应该越高

针对这个问题，我们可以使用关键字出现的次数替换BOW模型中的{0,1}表示方法，即如果文章中出现了关键词，那么将原来的1替换成在该文章中出现某关键词的次数，而如果没有出现，那么还是0保持不变,也就是说我们的similarity计算公式变为: Sim(q,d)=x’₁y’₁+…+x’_iy’_i=$\sum_{i=1}^N$x’_iy’_i(这里的x’_i=Count(W_i,q)表示关键词W_i在query中出现的次数,y’_i=Count(W_i,d)表示关键词W_i在文档出现的次数，一般来说x_i的值都是1)

我们将改进过的similarity计算方式重新计算Simplest Vector Space Model中的例子:

我们可以看到Sim(q,d₄的分数从原来的3变成了4)，确实这样的改动能够达到我们的诉求。

关键字presidential要比关键词about的权重更高

当我们仔细的去分析/理解querynews about presidential campaign,的时候我们会自然而然的认为关键词presidential应该比about总要-> 为什么？，我们为什么会得出这样的结论，这几乎是所有正常人都会得出的结论—> 因为我们看到的太多了，这就好比我们每天都看到/遇到各种个样的人,这时候你在路上遇到个人你会觉得这是一件非常正常的事情,但是如果哪天你在路上看见一头大象你一定非常的在意这头大象，因为它太少见了.同样的道理，因为关键词about几乎出现在所有的文章中，那么关键字about也就没有关键字presidential那么”值钱”了，为了解决这种常见词的问题，我们这里可以使用IDF(逆文档频率来解决这个问题),IDF(W)=log[(M+1)/k],k表示有多少文档中出现了关键词W (和出现次数没有关系)

那么改进之后的Sim计算方法为:Sim(q,d)=x’₁y’’₁+…+x’_iy’’_i=$\sum_{i=1}^N$x’_iy’’_i(这里的x’_i=Count(W_i,q)表示关键词W_i在query中出现的次数,y’’_i=Count(W_i,d)*IDF(W_i)表示关键词W_i在文档出现的次数乘以关键词W_i的逆文档频率，我们没有将IDF应用到query中的关键词的权重计算中，个人理解是因为用户的query中的关键字一定是重要的词，不然为啥要当成检索式的组成要素，但是文本中的关键词因为表达的意义比较多会有主次之分),我们将改进之后的公式应用到同样的例子中(我们现对比下d2,d3,因为d2,d3的得分是一样的))

我们可以看到在引入idf之后d3文档的得分按照我们的想法得到的更多的提升，从而使用f(q,d2)=5.6 < f(q,d3)=7.1 ,这样两个文档之间因为得分不一样从而产生了区分度，我们也可以将文档d3排在文档d2的前面。

至此，我们通过使用TF, IDF分别解决了上述两个问题，我们来计算下所有的文档和query的相关度,看看这种计算方法是不是在所有情况下都能反应文档和query的真实相关度，

我们在上一篇文章中说过，一种idea的排序应该是(d4+, d3+ ,d1- ,d2- d5- ),貌似d4,d3,d1,d3的顺序和分数已经达到了我们想要的效果，但是d5的得分却是13.9，这和我们的期望相差的有点大。。。。

TF Transformation,解决词频轰炸

首先我们得明白为什么d5的相似度为13.9,这里我们可以分析下我们的rank方法f(q,d)=$\sum_{i=1}^N$x_iy_i=$\sum_{w \in q \cap w}$c(w,q)c(w,d)log$\frac{M+1}{df(w)}$, 不难发现f(q,d5)=13.9的原始是c(campaign,d5)=4, 这里idf(campaign)对于所有包含关键词campaign的文档来说都是一样的，为了解决这种高tf所带来的问题，我们需要对t这一指标进行改写，这里我们介绍BM25模型对tf的改写规则: TF(w,d) = $\frac{(k+1)x}{x+k}$,不难发现该函数有个特性就是上界为k+1,这里我们解释下，为什么不使用log函数对tf进行平滑？我们可以现看下这几个函数的走势图:

从图中我们可以看出，log函数是没有上界的，当k非常大的时候经过log函数的变化，结果依然会很大，假设我在网上发了一篇关于某主题的文章，文章的内容就是重复某个关键字几万甚至几十万次，那么如果我检索改关键词，那么这篇文章按照我们目前定义的函数来计算相似度的话，一定是排第一的，但是显然这又是非常不合理的(文章没有实质性的内容),所以为了不出现上述这种词频轰炸的问题，我们必须设置一个词频对分数影响的上届，当词频超过一定数量之后，它的影响不会随着tf的增加而发生缓慢的变化，并且这种变化有一个理论上的尽头。

经过上述对两个问题的分析和提出的解决方案，我们可以得到:
f(q,d) = $\sum_{i=1}^{N}$x_iy_i=$\sum_{w \in q \cap w}C(w,q)\frac{(k+1)C(w,d)}{C(w,d)+k}log\frac{M+1}{df}(w)$,其中

符号名称	符号含义
C(w,q)	表示关键词w_i在query中出现的次数，一般都是1词
M	表示文档的总数
df(W)	表示关键词w_i在文档d中出现的次数

文档长度也需要考虑在其中

除了词频和低频词的问题，正常来说大家都会发现文档有长有短，一般来说都是文章越长，命中某个query关键字的概率也就越大(不绝对，但是有一定的可信度),所以类似tf的处理规则一样，我们得对文档长度进行处理。我们使用Pivoted Length Normalization规则对文档的长度进行处理具体的公式为

normalizer = 1 -b + b$\frac{|d|}{avdl}$ (其中avdl是所有文档的平均长度,并且b$ \in [0,1]$)
如果b=0,那么normalizer=1 ,也就是说这个时候文档长度不参与最终的打分，当b>0时，如果某个文档的长度超过平均文档长度，那么随着b增加，normalizer的取值也就越大(这里注意最终的分数是越小的，因为我们要对这种长文档进行降分处理),当文档长度小于平均长度的时候，normalizer的取值也就越小(但是一定是大于0的),最终的分数应该是越大的，因为我们要对短文档的分数进行一定的补偿，也就是说b的值越大，对文档长度的打分的降低或者补偿的力度越大。从下面的图中，大家可以有个直观的理解。

最终的打分公式

到这里，加上我们对文档长度的处理，我们可以得到最终的BM25打分公式为:
f(q,d) = $\sum_{w \in q \cap d}$ [C(w,q) $\frac{(k+1)C(w,d)}{C(w,d)+k(1-b+b \frac {d}{avdl})}$log$\frac{M+1}{df(w)}$)]
其中:
C(w,q)= 关键词w在query中出现的次数，一般为1
C(w,q)= 关键词w在文档中出现的次数
k为正实数 k>0
b的取值范围为 b $\in [0,1] $
M 表示文档总数
df(w) 所有关键词w出现的文档的总数。
当然BM25只是vector space model的一种实现，而实验证明还有另外一种实现也和BM25一样高效, 即 Pivoted Length Normalization VSM,这里我们直接给出它的打分公式:

总结

到这里我们简单介绍了Simplest Vector Space Model所面临的问题，以及我们相应的改进方案，从0～1的介绍了BM25算法公式的由来和实现，在一篇中我们将介绍如何高效的计算BM25打分公式，毕竟真实场景中我们遇到的文档数量可能是千万甚至几十亿的级别，我们要以高效的计算方式实现BM25,否则一个检索式输入到系统中，我们到等几分钟或者几个小时才能得到答案，这肯定是不现实的。