信息检索导论第七章－－一个完整搜索系统中的评分计算

#信息检索导论第七章–一个完整搜索系统中的评分计算

一、精确topK检索及其加速办法

目标：从文档集的所有文档中找出K 个离查询最近的文档
(一般)步骤：对每个文档评分(余弦相似度)，按照评分高低排序，选出前K个结果

优化加速思路：

• 思路一：加快每个余弦相似度的计算
• 思路二：不对所有文档的评分结果排序而直接选出Top K篇文档
• 思路三：能否不需要计算所有Ｎ篇文档的得分？

1、优化方法一：快速计算余弦

不考虑查询词项的权重，即查询词项无权重
相当于假设每个查询词项都出现1次

于是，不需要对查询向量进行归一化
于是可以对上一讲给出的余弦相似度计算算法进行轻微的简化

无权重计算余弦

2、优化方法二：堆法J中选K

检索时，通常只需要返回前K条结果，可以对所有的文档评分后排序，选出前K个结果，但是这个排序过程可以避免

令 J = 具有非零余弦相似度值的文档数目
利用小顶堆从J中选K个最大的

3、优化方法三：提前终止计算

到目前为止的倒排记录表都按照docID排序
接下来将采用与查询无关的另外一种反映结果好坏程度的指标(静态质量)

例如: 页面d的PageRank g(d), 就是度量有多少好页面指向d的一种指标 (参考第 21章)
于是可以将文档按照PageRank排序 g(d1) > g(d2) > g(d3) > . . .
将PageRank和余弦相似度线性组合得到文档的最后得分
net-score(q, d) = g(d) + cos(q, d)

假设：

• g → [0, 1];
• 检索算法按照d1,d2,…，依次计算(为文档为单位的计算，document-at-a-time)，当前处理的文档的 g(d) < 0.1；
• 而目前找到的top K 的得分中最小的都 > 1.2

由于后续文档的得分不可能超过1.1 ( cos(q,d) <1 )
所以，我们已经得到了top K结果，不需要再进行后续计算

4、精确topK检索的问题

• 仍然无法避免大量文档参与计算

• 一个自然而言的问题就是能否尽量减少参与计算文档数目，即使不能完全保证正确性也在所不惜。

即采用这种方法得到的top K虽然接近但是并非真正的top K—-因此引入非精确top K检索

二、非精确top K检索

1、非精确top K检索的可行性

• 检索是为了得到与查询匹配的结果，该结果要让用户满意
• 余弦相似度是刻画用户满意度的一种方法
• 非精确top K的结果如果和精确top K的结果相似度相差不大，应该也能让用户满意

2、快速评分及排序

目的：显著降低输出前 K 篇文档所需要的计算复杂度，同时并不让用户感觉到前 K 个结果的相关度有所降低。

一般思路：

1. 找到一个文档集合A，它包含了参与最后竞争的候选文档，其中K < |A| << N。A 不必包含前K 篇得分最高的文档，但是它应该包含很多和前K 篇文档得分相近的文档。
2. 返回A 中得分最高的K 篇文档

   上述思路不仅适用于余弦相似度得分，也适用于其他相似度计算方法

2.1、索引去除

一般检索方法中，通常只考虑至少包含一个查询词项的文档，可以进一步拓展这种思路
(1)只考虑那些包含高idf查询词项的文档

• 优点:低idf词项会对应很多文档，这些文档会排除在集合A之外

(2)只考虑那些包含多个查询词项的文档(比如达到一定比例，3个词项至少出现2个，4个中至少出现3个等等)

• 优点：这种方法很容易在倒排记录表合并算法中实现

  这相当于赋予了一种所谓软合取(soft conjunction)的语义 (早期Google使用了这种语义)

2.2、胜者表

对每个词项t，预先计算出其倒排记录表中权重最高的r篇文档，如果采用tfidf机制，即tf最高的r篇，这r篇文档称为t的胜者表，也称为优胜表(fancy list)或高分文档(top docs)。

注意：r 比如在索引建立时就已经设定，因此，有可能 r < K

检索时，仅计算某些词项的胜者表中包含的文档集合的并集，从这个集合中选出top K作为最终的top K

问题：

1. 胜者表方式和前面的索引去除方式有什么关联？如何融合它们？
2. 如何在一个倒排索引当中实现胜者表？（胜者表与docID大小无关）

2.3、静态质量得分排序方式

我们希望排名靠前的文档不仅相关度高(relevant) ，而且权威度也大(authoritative)

相关度常常采用余弦相似度得分来衡量，而权威度往往是一个与查询无关的量，是文档本身的属性

权威度计算
为每篇文档赋予一个与查询无关的(query-independent ) [0,1]之间的值，记为g(d)，最终文档排名基于g(d)和相关度的线性组合。
net-score(q,d) = g(d) + cosine(q,d)

可以采用等权重，也可以采用不同权重
可以采用任何形式的函数，而不只是线性函数

接下来我们的目标是找net-score最高的top K文档：

• 首先按照g(d)从高到低将倒排记录表进行排序，该排序对所有倒排记录表都是一致的(只与文档本身有关)
• 因此，可以并行遍历不同查询词项的倒排记录表来进行倒排记录表的合并及余弦相似度的计算

利用g(d)排序的优点：

• 这种排序下，高分文档更可能在倒排记录表遍历的前期出现
• 在时间受限的应用当中 (比如，任意搜索需要在50ms内返回结果), 上述方式可以提前结束倒排记录表的遍历

将g(d)排序和胜者表相结合

• 对每个词项，维护两个倒排记录表 ，分别成为高端表和低端表，比如可以将高端表看成胜者表
• 遍历倒排记录表时，仅仅先遍历高端表，如果返回结果数目超过K，那么直接选择前K篇文档返回，否则，继续遍历低端表，从中补足剩下的文档数目

上述思路可以直接基于词项权重，不需要全局量g(d)，实际上，相当于将整个索引分层

2.4、影响度排序

如果只想对$wf_{t,d}$足够高的文档进行计算，那么就可以将文档按照 $wf_{t,d}$排序，但是这种做法会导致倒排记录表的排序不一致。
那么此时有两种方法实现top K检索：

1. 提前结束法

遍历倒排记录表时，可以在如下情况之一发生时停止：

• 遍历了固定的文档数目r
• $wf_{t,d}$低于某个预定的阈值

将每个词项的结果集合合并，仅计算合并集合中文档的得分

2. 将词项按照idf排序

• 对于多词项组成的查询，按照idf从大到小扫描词项
• 在此过程中，会不断更新文档的得分(即本词项的贡献)，如果文档得分基本不变的话，停止

可以应用于余弦相似度或者其他组合得分

2.5、簇剪枝方法

随机选 $\sqrt{N}$ 篇文档作为先导者，对于其他文档，计算和它最近的先导者

• 这些文档依附在先导者上面，称为追随者(follower)
• 这样一个先导者平均大约有$\sqrt{N}$个追随者

查询处理过程：

1. 给定查询 Q, 找离它最近的先导者L
2. 从L及其追随者集合中找到前K个与Q最接近的文档返回

一般化变形：

• 每个追随者可以附着在b1 (比如3)个最近的先导者上
• 对于查询，可以寻找最近的b2 (比如4)个先导者及其追随者

问题：

• 随机选择先导者会造成什么问题？
• 为了找到最近的先导者，需要计算多少次余弦相似度？
• 为什么第一步中采用$\sqrt{N}$个先导者？
• 上一张讲义中的常数 b1, b2 会对结果有什么影响？

三、信息检索系统的组成

1、完整搜索系统示意图

2、层次索引

基本思路:

1. 建立多层索引，每层对应索引词项的重要性
2. 查询处理过程中，从最高层索引开始
3. 如果最高层索引已经返回至少k (比如, k = 100)个结果，那么停止处理并将结果返回给用户
4. 如果结果 < k 篇文档，那么从下一层继续处理，直至索引用完或者返回至少k 个结果为止

例子：两层的系统
第1层: 所有标题的索引
第2层: 文档剩余部分的索引

PS：标题中包含查询词的页面相对于正文包含查询词的页面而言，排名更应该靠前

3、向量空间模型对各种查询操作的支持

我们介绍了支持自由文本查询的向量空间模型，而前面介绍的几种查询操作，而实际上增加了查询的表达能力。下面考察能否在用向量空间模型的同时，支持这些查询操作，从而增加表达能力。在建立一个搜索引擎时，我们往往希望能够支持用户的多种查询操作符。

向量空间模型支持自由文本查询，这与前面的布尔查询、通配符查询和短语查询处理有所不同。下面看看向量空间模型怎么支持这些查询。

（1）向量空间模型显然能够处理布尔查询。

（2）对于通配符查询rom*，我们将所有可能的词项输入到查询向量中去，这样通配符查询也能支持。

（3）对于短语查询，如果短语被转换为向量，丢失了短语的位置信息。所以我们用向量空间模型来检索“german sherpherd”类型短语的时候，只能检索出两个词项权重较高的文档，不能保证2个词项连续出现。