研究生课程：现代信息检索-第9讲 完整搜索系统中的评分计算
《现代信息检索》课程笔记：第9讲 完整搜索系统中的评分计算
第9讲 完整搜索系统中的评分计算
不排序的问题严重性
- 用户只希望看到一些而不是成千上万的结果
- 很难构造只产生一些结果的查询
- 即使是专家也很难
- 排序能够将成千上万条结果缩减至几条结果，因此非常重要
排序的重要性：
- 摘要阅读(Viewing abstracts)：用户更可能阅读第一页的结果的摘要
- 点击(Clicking)：点击的分布甚至更有偏向性
- 一半情况下，用户点击排名最高的页面
- 即使排名最高的页面不如排名第二的页面相关，仍然有接近30%的用户会点击它。
- 正确排序相当重要
- 排对最高的页面非常重要
结果排序的实现
倒排索引中的词项频率存储
- 每条倒排记录中，除了docIDd 还要存储tft,d
- 通常存储的是原始的整数词频，而不是对数词频对应的实数值
- 这是因为实数值不易压缩
- 对tf采用一元码编码效率很高
- 总体而言，额外存储tf所需要的开销不是很大：采用位编码压缩方式，每条倒排记录增加不到一个字节的存储量
- 或者在可变字节码方式下每条倒排记录额外需要一个字节即可
两种常见的评分累加算法：
以词项为单位(term-at-a-time, TAAT)，首先获得词项t的posting list，然后累加得分
以文档为单位的计算，首先获得包含查询词的所有文档，将这些文档按照静态评分排序，然后依次累加得分
精确top K检索及其加速办法：
目标：从文档集的所有文档中找出K个离查询最近的文档
步骤：对每个文档评分(余弦相似度)，按照评分高低排序，选出前K个结果
加速方法：
快速计算余弦：不考虑查询词项的权重
堆法N中选K：不对所有文档进行排序，只需要挑出最高的K个结果
提前终止计算：得到了top K结果，不需要再进行后续计算
精确topK检索的问题：仍然无法避免大量文档参与计算
非精确topK检索：非精确topK的结果如果和精确topK的结果相似度相差不大，应该也能让用户满意
找一个文档集合A，K<|A|<<N，利用A中的top K结果代替整个文档集的top K结果
方法一：索引去除
从查询词的角度：只考虑那些包含高idf查询词项的文档
从文档的角度：只考虑那些包含多个查询词项的文档
仅考虑高idf词项、仅考虑包含多个词项的文档
方法二：胜者表
对每个词项t，预先计算出其倒排记录表中权重最高的r篇文档，如果采用tfidf机制，即tf最高的r篇
方法三：静态质量得分排序方式
为每篇文档赋予一个与查询无关的[0,1]之间的值，记为g(d)，例如Pagerank
最终文档排名基于g(d)和相关度的线性组合
目标是找net-score最高的top K文档
方法四：影响度(Impact)排序
提前结束法：
遍历倒排记录表时，可以在如下情况之一发生时停止：
- 遍历了固定的文档数目r
- wft,d 低于某个预定的阈值
- 将每个词项的结果集合合并
- 仅计算合并集合中文档的得分
将词项按照idf排序：
- 对于多词项组成的查询，按照idf从大到小扫描词项
- 在此过程中，会不断更新文档的得分(即本词项的贡献)，如果文档得分基本不变的话，停止
- 可以应用于余弦相似度或者其他组合得分
方法五： 簇剪枝
随机选 
非docID的倒排记录表排序方法
与查询无关的一种反映结果好坏程度的指标
以文档为单位(Document-at-a-time)的处理、以词项为单位(Term-at-a-time)的处理方式
WAND（Weak AND） 评分算法
- 实验表明, WAND 可以降低 90% 以上的评分计算开支
- WAND并非仅仅适用于cosine评分排序
- WAND 及其不同的改进版能够满足安全排序（Safe Ranking, 即精确排序）
完整的搜索系统
多层次索引基本思路:
- 建立多层索引，每层对应索引词项的重要性
- 查询处理过程中，从最高层索引开始
- 如果最高层索引已经返回至少k (比如, k = 100)个结果，那么停止处理并将结果返回给用户
- 如果结果 < k 篇文档，那么从下一层继续处理，直至索引用完或者返回至少k 个结果为止