信息检索期末复习

MorphLing 1月 03, 2022

1. 绪论

*信息检索是什么？

给定用户需求返回满足该需求信息的一门学科。通常涉及信息的获取、存储、组织和访问。

从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的过程。

2. 词汇表和倒排记录表

倒排索引如何存储？

磁盘上顺序存储便于快速读取。内存中采用链表或者变长数组。需要在存储空间和插入代价之间平衡。

倒排索引如何排序，为什么要排序？

按词项排序，然后每个词项按DOCID排序。排序是为了在线性时间内对两个倒排记录表完成合并（排序后可以双指针扫描）。

倒排索引的组成？

词典
倒排记录表
词典指向倒排表的指针

倒排索引的构建过程？每个步骤的作用？

待索引文档转化为词条流（Tokenizer词条化工具，作用：分词）
词条流转化为修改后的词条（语言分析工具，作用：契合用户输入习惯）
生成倒排索引（加速查询）

词条和词项的区别？

词条经过归一化后的结果就是词项，词项是要被索引的对象。归一化的方法包括大小写转换、同义词词典、soundex、词形合并、词干还原等。

文档和查询的同义词需要归一化成同一形式。

为什么要归一化（不太确定）

减少词项个数和词典大小
合并类似的词项
契合用户输入形式和习惯

跳表的优势和局限性？

跳表指针可以加速合并和查询效率，考虑在链表上每隔$\sqrt N$加一个跳表指针之后的场景，可以跳过不可能的检索结果。

局限性在于如果倒排记录表不能放入内存（例如每次读跳表都要进行一次磁盘I/O），跳表的I/O开销可能远远超过其带来的优势。

3. 词典及容错式检索

*短语查询需要怎么转变，使得倒排索引支持短语查询？

双词索引

对每两个连续的词组成词对进行索引，将更长的短语查询分解为若干个双词。扩展方式：词性标注

缺点：会出现伪正例（需要二次验证文档是否满足），导致词典和词项数目剧增
带位置信息索引

在倒排记录表中，对每个词项在每篇文档中的每个位置进行存储

将输入的短语查询在文档的层次上进一步合并（即考虑位置是否匹配）

扩展：位置索引可以解决邻近式查询，所以是更常用的方法（实际检索系统的标配）

关于倒排索引的索引结构，对比一下哈希表和树

这取决于词项数目是固定还是持续增长、词项的相对访问频率和词项的数目。

哈希表优点：查询时间是常数，缺点：无法处理词项微小变形，不支持前缀（区间）搜索，如果词汇表持续增长，需要定期对所有词项重新哈希（否则由于哈希冲突，效率会越来越慢）。

树优点：可以支持前缀查询缺点：速度略低于哈希表，维护平衡的开销很大

*二级索引结构用什么数据结构？

二级索引指k-gram索引中，对每个k-gram再建一个倒排索引，该倒排索引词典部分是所有的k-gram，记录表部分是对应k-gram的所有词项。

那么可以知道这个词典大小比较小且有固定的上界（词项大小上界为$26^k$），词典大小不会持续增加，且词项的相对访问频率会比较高，显然比较适合使用哈希表构建二级索引。

如何进行通配符查询？

轮排索引。构建索引时，将每个词项末尾加入特殊符号$，然后将词项旋转多次，将每次旋转后的结果都加入词典，即B树中。

查询时，将通配符旋转至右部，在B树上进行前缀查询。

对于存在两个或以上通配符（除了*X*这种形式只需要查询X*），需要对查询结果二次验证。

比较词项纠正的两种方法

两种方法：词独立法和上下文敏感法。

词独立法只检查每个单词本身的拼写错误，如果某个单词拼错成另一个单词则无法检测。

上下文敏感法则考虑了周围的单词。

编辑距离怎么算？

常见的有Levenshtein距离，包括插入、删除、替换。

Damerau-Levenshtein距离还包括两个字符交换。

计算编辑距离可以利用权重（替换代价），因为键盘输入的错误率不同。

*Soundex怎么做？

保留首字母
按照一定规则将字母转化为数字
将连续出现的字符转为一个（这里说的字符应该是转化后的数字，即剔除连续的数字）
剔除0，尾部补0至3位，返回首字母+前三位数字

4. 索引构建

简单对比BSBI和SPIMI算法？

BSBI会在内存中维护一个全局词典，局部索引为TermID及其倒排记录表，按字典顺序排序。

SPIMII建立局部词典，不需要全局词典，将局部索引合并后再生成全局词典。

5. 索引压缩

有哪些关于词项、词频的经典定律？

Heaps定律：词项大小M是文档集T的一个函数，M与$\sqrt T$基本呈正比，$M\propto \sqrt T$

Zipf定律：第i常见的词频$cf_i$与$1/i$成正比，即$cf_i\propto\frac{1}{i}$（另一种解释：二八定律）

*词典压缩有哪些方法？

将所有词项压缩成一个字符串，用词项指针指向每个词项在字符串中的对应位置。

定长方式的缺陷：一是短词项也要分配足够空间，会造成浪费，二是不能处理长度大于分配空间的词项。
按块存储：减少词项指针数量，节约空间，但词项查找速度稍慢

同时需要在字符串中记录每个词项的长度，导致字符串稍长。
前端编码：将每个块的公共前缀进行压缩

倒排索引和词典压缩哪个重要性更高？

倒排索引。因为量级远远大于词典。

*倒排索引压缩有哪些压缩方法？

间隔编码：每个倒排记录表中的docID记录间隔（除了第一个）

问题：会导致罕见词和常见词的间隔大小差别太大。
变长编码：对于小间隔采用短编码，长间隔采用长编码。

方法：将原数字的二进制表示7位拆分，在最高位加一位表示延续位置，0表示未结束，1表示结束
$\gamma$编码：把每个数用长度和偏移表示，偏移为该数去掉最高位后的1剩下的部分，长度为偏移的长度一元编码后的结果

6. 文档评分、词项权重计算及向量空间模型

为什么需要对搜索结果排序？

因为用户通常只愿意浏览极少的搜索结果。

*布尔模型的优劣？

优点：对于需求和文档集性质非常了解的专家来说，布尔模型效果比较好。

缺点：需要大量训练才能撰写布尔查询，且往往搜索结果过少或过多，需要大量技巧才能得到合适规模结果的查询。

*词袋模型是什么？有什么典型的词袋检索模型？

词袋模型，指不考虑词在文档中出现顺序的模型。

典型词袋检索模型：tf-idf，one-hot

*为什么说idf只会影响至少包含两个词项的查询结果？

当只有一个词项时，该词项的idf值$idf_t=\log_{10}\frac{N}{df_t}$在每个文档中都一样，相当于每个文档的结果计算中乘了一个常数，不会对文档之间结果的大小关系产生任何影响。

词项频率tf、文档频率df、文档集频率cf的定义？

df和cf会一起增加。tf和cf会一起增加。tf和df没有直接关系。

为什么通常cf比df更适合权重计算？

某些特定词项会在特定文档中以非常高的频率出现，这导致该词项的cf值很高，但这不意味着应该减少该词项的权重。因为这种词反而对特定文档而言识别度很高，应该有更高的权重。

向量空间模型表达的物理意义？

可以将查询也做同样处理，转化为高维向量。
转化为向量后，可以定义文档之间的相似度，于是可以回答给定若干篇文档，哪两篇最相关的问题。

为什么文档相似性常用夹角而不是绝对距离？

假想实验：在文档D复制一份加在自身末尾得到D’，显然语义上D和D’有相同的内容。

两者的夹角为0，但绝对距离可能会很大。

7. 完整搜索系统中的评分计算

*文档的长短对于向量空间模型下有什么影响？通过什么方法消除这种差异？

由余弦相似度计算公式$cos\theta=\frac{a\cdot b}{|a|\cdot|b|}$，可知当$a\cdot b$值相等时，短文档的分母小于长文档，导致短文档的余弦相似度明显大于长文档。

为了消除这种差异，会选择一个平衡点(pivot)，对余弦归一化操作进行线性调整（回转长度归一化）。

为什么需要扩展倒排索引（如加入词频）？

需要在倒排索引中加入词项的文档频率df和在每个文档中的词项频率tf。

因为词项t在文档d中的tf-idf权重$w_{t,d}=(1+\log tf_{t,d})\log\frac{N}{df_t}$需要用到这两个属性，直接在倒排索引中记录可以加快计算速度。

加速topK检索的方法有哪些？

快速计算余弦

不考虑查询词项的权重$w_{t,d}$，假设每个查询词项的词频tf为1
不对所有结果排序，用堆维护topK
不计算所有文档的得分
- 仅考虑包含高idf查询词项的文档
- 仅考虑包含多个词项的文档
- 预计算每个词项tf最高的r篇作为胜者表
- 根据权威度（文档本身属性）
- 高端表和低端表
- 簇剪枝

8. 检索评价

检索指标有哪些？物理意义分别是什么？

效率：时间开销、空间开销、响应速度

效果：正确率（返回文档中相关文档个数）、召回率（所有相关文档返回了多少）、相关文档是否靠前

其他指标：覆盖率、访问量、数据更新速度

正确率，召回率的定义和计算？

正确率：RR/(RR+RN)

召回率：RR/(RR+NR)

*计算正确率，召回率分别有哪些不足或难点？

不足：都没有考虑排序的先后关系。

难点：召回率计算很困难，因为文档很大，无法对每个查询标记所有相关文档，需要用其他方法度量召回率，如pooling方法

pooling方法：对多个检索系统的TopN个结果组成的集合进行人工标注，标注出的相关文档作为整个相关文档集合。

调和平均F值有什么好处？

$F=\frac{2PR}{P+R}$

如果用算术平均值，那么一个返回全部文档的搜索结果F值就不低于50%，这过高了。

调和平均值使得，无论P或R过低都能表现在F值上，相较于最小值，F值更平滑，即可以把F值看成平滑的最小值函数

精确率(Accuracy)如何计算？为什么通常不使用精确率？

精确率$accuracy=(RR+NN)/(RR+NN+NR+RN)$

由于不相关文档数远大于相关文档数，一个什么都不返回（把所有文档标记为不相关）的搜索结果，可以达到非常高的精确率，这不合理。

引入序是什么？

检索结果按一定顺序排列，在用户观察过程中，召回率不断增加，因此可以求出在不同召回率上对应的正确率，然后描出图像

在上面的曲线对应的系统结果更好

*P-R曲线怎么画？

先按顺序求出结果中每个相关文档所在的P、R值，对10%,…100%的召回率点进行插值。

对于t%，如果不存在该召回率点，则定义t%的正确率为从t%到100%(>=t%)中最大的正确率值。

*平均正确率AP是什么？插值和未插值的区别是什么？

未插值AP

插值AP

Precision@N如何计算？为什么该指标有效？

在第N个位置上的正确率。

因为用户通常只关注前一/二页的结果。

*Macro Average和Micro Average分别如何计算？

*MAP是什么？

对所有查询的AP求宏平均。

覆盖率和出新率分别是什么？如何计算？

假定用户已知的相关文档集合为U，检索结果和U的交集为Ru，则可以定义覆盖率(Coverage) C=|Ru|/|U|，表示系统找到的用户已知的相关文档比例。

假定检索结果中返回一些用户以前未知的相关文档Rk，则可以定义出新率(Novelty Ratio) N=|Rk|/(|Ru|+|Rk|)，表示系统返回的新相关文档的比例。

NDCG是什么？如何计算？

每个文档有一个相关等级$rel_i$，计算$DCG=\sum\limits_irel_i/\log_2(i+1)$，理想情况下$IDCG$为$rel_i$从大到小排序后的计算结果

$NDCG=\frac{DCG}{IDCG}$

另一种计算方式是加大相关性的权重，由$rel_i$增加到$2^{rel_i}$

9. 相关反馈

*提高召回率有哪些方法？从局部方法和全局方法两个角度考虑。（填空题）

局部方法：对用户查询进行局部的即时分析，主要方法是相关反馈

全局方法：进行一次性的全局分析，生成同/近义词词典，主要方法是利用该词典进行查询扩展

*相关反馈分成哪三种？分别简述。（简答题）

显式相关反馈：用户显式参加交互过程

优点：准确度较高

缺点：用户通常不愿意提供显式相关反馈
隐式相关反馈：系统根据用户行为推测相关性

常见的用户行为包括：鼠标键盘操作（点击、停留、翻页）、用户眼珠动作（拉近、拉远、凝视、往某个方向转）等等

优点：省去了用户显式参与的过程

缺点：判定结果不一定准确，对行为分析有较高要求，且有时需要额外设备
伪相关反馈：系统直接假设返回文档前k篇为相关文档

优点：不用考虑用户因素，在实验中的平均效果不错

缺点：对某些查询效果很差，准确率难以保证，可能导致查询漂移。

*Rocchio相关反馈的原理是什么？如何画图表示？

分别找到相关文档和不相关文档的质心，对相关文档的质心进行偏移，偏移向量为相关向量与不相关向量之差。

Rocchio的物理意义

即将相关文档的质心移动一个量，该量为相关文档质心和不相关文档的差异量。

为什么向量要偏移？如果不偏移会怎么样？

偏移是为了使得新查询向相关文档靠拢并远离不相关文档。

如果不偏移，区分效果将变差。

为什么通常更看重正反馈而不是负反馈？

通常不相关文档的数目远远大于相关文档，很难对所有不相关文档进行标记，不相关的情况可能很复杂，但相关的情况比较简单。

换言之，相关文档数量较少，意义明确。不相关文档数量过多，意义不明确。

*搜索引擎是否使用相关反馈？

会使用，但需要分情况讨论。

由于用户通常不会显式参加交互过程，所以搜索引擎通常无法使用显式相关反馈。但搜索引擎可以使用隐式相关反馈，通过用户的点击，浏览行为，或者眼动轨迹之类的数据推断结果的相关性，基于这些相关性进行相关反馈。

搜索引擎也可以使用伪相关反馈。

10. 概率模型

贝叶斯公式和使用？

$P(A_j|B)=\frac{P(A_jB)}{P(B)}=\frac{P(A_j)P(B|A_j)}{\sum\limits_i P(A_i)P(B|A_i)}$

*概率检索模型定义是什么？

检索系统对用户查询的理解是非确定的 (uncertain)，对返回结果的猜测也是非确定的。

概率检索模型是通过概率的方法将查询和文档联系起来：

定义3个随机变量$R,Q,D$：

相关度$R=\{0,1\}$，查询 $Q=\{q1,q2,…\}$，文档$D=\{d1,d2,…\}$，则可以通过计算条件概率$P(R=1|Q=q,D=d)$来度量文档和查询的相关度。

概率模型包括一系列模型，如Logistic Regression(回归)模型及最经典的二值独立概率模型BIM、BM25模型等等(还有贝叶斯网络模型)。

*Logistic回归模型基本思想？

为了求$Q$和$D$相关的概率$P(R=1|Q,D)$，通过定义多个特征函数$f_i (Q,D)$，认为$P(R=1|Q,D)$是这些函数的组合。

*生成式模型是什么？

生成式模型对后验概率建模，从统计的角度表示数据的分布情况，能够反映同类数据本身的相似度。

优点：信息比判别模型丰富，研究单类问题比判别模型灵活，可以进行增量学习，能用于数据不完整的情况。

缺点：学习和计算过程比较复杂

常见模型：naive bayes、GMM、HMM、马尔可夫随机场

*二值独立模型BIM是什么？

BIM模型通过Bayes公式对所求条件概率$P(R=1|Q,D)$展开进行计算。BIM是一种生成式(generative)模型。

两个假设：

二元假设

一篇文章在由特征表示时，以特征“出现”和“不出现”两种情况表示。
词汇独立性假设

文档里出现的单词或词语之间没有任何关联。由于词汇之间没有关联，可以将文档概率转化为每个词汇概率的乘积。