信息检索导论第七章.ppt

第七章 一个完整搜索系统中的评分计算 前情回顾 7.1 快速评分及排序 精确Top K检索 加速办法 1、加快每个余弦相似度的计算 检索排序就是找查询的K近邻，一般而言，在高维空间下，计算余弦相似度没有很高效的方法，但是如果查询很短，是有一定办法加速计算的，而且普通的索引能够支持这种快速计算。 查询词项无权重，相当于假设每个查询词项都出现1次，于是，不需要对查询向量进行归一化，进而可以对上一讲给出的余弦相似度计算算法进行轻微的简化。 2、不对所有文档的评分结果排序而直接选出TOP K 篇文档 检索时，通常只需要返回前K条结果，可以对所有的文档评分后排序，选出前K个结果，但是这个排序过程可以避免，令 J = 具有非零余弦相似度值的文档数目 从J中选K个最大的。（堆法N中选K） 3、能否不需要计算N篇文档的得分 提前终止计算 到目前为止的倒排记录表都按照docID排序，接下来将采用与查询无关的另外一种反映结果好坏程度的指标(静态质量)。例如: 页面d的PageRank g(d), 就是度量有多少好页面指向d的一种指标 (参考第 21章)于是可以将文档按照PageRank排序 g(d1) g(d2) g(d3) . . . 将PageRank和余弦相似度线性组合得到文档的最后得分 net-score(q, d) = g(d) + cos(q, d) 假设: (i) g → [0, 1]; (ii) 检索算法按照d1,d2,…，依次计算(为文档为单位的计算，document-at-a-time)，当前处理的文档的 g(d) 0.1； (iii) 而目前找到的top K 的得分中最小的都 1.2 由于后续文档的得分不可能超过1.1 ( cos(q,d) 1 ) 所以，我们已经得到了top K结果，不需要再进行后续计算 精确TOP K检索仍然无法避免大量文档参与计算 一个自然而言的问题就是能否尽量减少参与计算文档数目，即使不能完全保证正确性也在所不惜。即采用这种方法得到的top K虽然接近但是并非真正的top K非精确top K检索。 检索是为了得到与查询匹配的结果，该结果要让用户满意，余弦相似度是刻画用户满意度的一种方法，非精确top K的结果如果和精确top K的结果相似度相差不大，应该也能让用户满意。 减少参与计算的文档数目的一些方法，包括下面两个步骤： 找一个文档集合A，它包含了参与最后竞争的候选文档，其中K|A|N，A不必包含前K篇得分最高的文档，但它要包括很多和前K篇文档得分相近的文档。 返回A中得分最高的K篇文档 小结 方法一：索引去除 一般检索方法中，通常只考虑至少包含一个查询词项的文档，可以进一步拓展这种思路。 一、只考虑那些包含高idf查询词项的文档 对于查询 catcher in the rye，仅考虑包含catcher和rye的文档的得分。 文档当中的in 和 the不会显著改变得分,因此也不会改变得分顺序 优点:低idf词项会对应很多文档，这些文档会排除在集合A之外 二、只考虑那些包含多个查询词项的文档(比如达到一定比例，3个词项至少出现2个，4个中至少出现3个等等) 对于多词项查询而言，只需要计算包含其中大部分词项的文档 比如，至少4中含3 这相当于赋予了一种所谓软合取(soft conjunction)的语义 (早期Google使用了这种语义) 指的是在对一个包含多个词项的查询进行检索时，检索中的文档中只要出现大部分查询词项即可，并不要求出现全部查询词项 方法二：胜者表 对每个词项t，预先计算出其倒排记录表中权重最高的r篇文档，如果采用tf-idf机制，即tf最高的r篇 注意：r 比如在索引建立时就已经设定，词项t所对应的tf值最高的r篇文档构成t的胜者表。 因此，有可能 r K 检索时，仅计算某些词项的胜者表中包含的文档集合的并集 从这个集合中选出top K作为最终的top K 方法三：静态质量得分排序方式 我们希望排名靠前的文档不仅相关度高(relevant) ，而且权威度也大(authoritative) 相关度常常采用余弦相似度得分来衡量 而权威度往往是一个与查询无关的量，是文档本身的属性 权威度示例：Wikipedia在所有网站上的重要性、某些权威报纸上的文章、论文的引用量、被 diggs, Y!buzzes或del.icio.us等网站的标注量、Pagerank 权威度计算 为每篇文档赋予一个与查询无关的(query-independent ) [0,1]之间的值，记为g(d) 同前面一样，最终文档排名基于g(d)和相关度的线性组合。 net-score(q,d) = g(d) + cosine(