信息检索-笔记

读书笔记 信息检索

---

第一章 布尔检索

• 信息检索定义
• 线性扫描 grepping 来自于grep命令 支持正则
• 非线性扫描 ->建立索引
• 对检索系统的效果评价 正确率Precision 召回率Recall
• 光采用词项-文档矩阵 文档量过大时会有极高的稀疏性
• 什么是归一化
• 在ad hoc文本检索中，倒排索引是其他结构无法抗衡的高效索引结构
• 倒排记录存储数据结构的选择
• 排序检索模型和有序检索模型
• 近邻操作符
• 布尔搜索的普遍问题就是采用and操作符产生的结果正确率高召回率低 or操作与之相反
• 增强型的索引结构

---

第二章 词项词典及倒排记录表

• 构建倒排索引的主要步骤 4点
• 转化字符序列时注意编码方式
• 索引粒度的选择 考虑正确率和召回率之间的权衡
• 词条化 与待处理语言本身有关
• 各国不同语言的特殊处理
• 中文分词 基于词典的最大匹配法 基于机器学习序列模型的方法
• 关于停用词的取舍
• 词条归一化就是将看起来不完全一致的多个词条归纳成一个等价类
• 两种建立等价类的方法
• 英语中的词干还原和词性归并 词干还原能够提高召回率但是会降低正确率
• 基于调表的快速合并算法
• 位置信息索引

---

第三章 词典及容错式检索

• 用来存储dictionary的数据结构 哈希表达方式和搜索树方式
• 平衡二叉树 B树 反向B树
• 通配符查询方法 轮排索引、k-gram索引
• k-gram索引：会导致非预期的结果 后过滤
• 拼写校正的两个步骤：基于编辑距离 基于k-gram overlap
• 计算两个字符串的编辑距离 动态规划
• 在字符串集合V中查找最小编辑距离的字符串 启发式算法
• 如何使用Jaccard系数来简化计算
• 上下文敏感的拼写纠正 根据高频双词
• 基于发音的校正技术 soundex算法

---

第四章 索引构建

• 索引器：构建索引的程序
• 与IR系统相关的硬件：高速缓存、寻道时间、内存
• 提高构建效率，将词项映射成ID
• BSBI算法 blocked sort-basedindexing algorithm 基于块的排序索引算法
  
  1. 将文档分割成大小相等的部分
  2. 将每个部分的词项ID-文档ID对排序
  3. 将中间产生的临时排序结果放入磁盘
  4. 将所有的中间文件合并成最终的索引
• BSBI算法劣势：不适用于大规模的文档集
• SPIMI算法 single-pass in-memory indexing 内存式单遍扫描索引算法 使用压缩技术提高效率 时间复杂度
• 分布式构建索引 distributed indexing 保证构建过程的鲁棒性
• MapReduce技术
  
  1. 维护高频词，低频词使用本身
  2. map阶段将输入的数据片映射成键值对
  3. reduce阶段，将同一词项ID的文档ID集中存储
• 动态索引构建方法
• 保持两个索引：一个大的主索引，一个是小的用于存储行文档信息的辅助索引
• 通过ACL access control list来实现用户授权 访问控制表

---

第五章 索引压缩

• 索引压缩的优点：增加高速缓存、加快数据从磁盘到内存的传输速度
• 无损压缩 lossless compression 压缩之后所有的原始信息都被保留
• 有损压缩 lossy compression 压缩后会丢掉一些信息，但有较高的压缩率
• Heaps定律，它将词项的数目估计成文档集大小的一个函数$M=kT^b$，其中T是文档集合中的词条个数；文档集大小和词汇量的关系是它们在对数空间中存才线性关系
• 不同文档集下参数k的取值差异会比较大，因为词汇量的大小依赖于文档集本身以及对它进行处理的方法
• Heaps定律的两个假设：
  
  1. 随着文档数目的增加，词汇量会持续增长而不会稳定到一个最大值
  2. 大规模文档集的词汇量也非常大
• Zipf定律 对词项的分布建模
• 如果t1是文档集中的出现最多的词项，t2是文档集中出现第二多的词项，以此类推，那么排名第i多的词项的文档集频率$cf_i$与1/i成正比
• 磁盘的访问次数决定了信息检索系统的响应时间，压缩词典后把大部分词典都放入内存，能提高查询吞吐率
• 将词典看成单一字符串来压缩，整个词典采用定长数组来存储且所有词项按照词典序排序，其缺点是空间浪费
• 按块存储：将长字符串中的词项进行分组变成大小为k的块，然后对每个块只保留第一个词项的指针；k越大，压缩率越高
• 前端编码技术 front coding：公共前缀被识别出来之后，后续的词项便可以使用一个特殊的字符来表示这段前缀* 如果不得不把词典划分成不同页存储在磁盘上，则可以采用B树对每页的第一个词项进行索引
• 倒排记录的压缩：按字节压缩 & 按位压缩
• VB Variable byte，可变字节，编码利用整数个字节来对间距编码。字节的后7位是间距的有效编码区，而第一位是延续位。
• γ编码，将间距G表示成长度和偏移两个部分进行变长编码。前缀无关，参数无关，解压的消耗会高

---

第六章 文档评分、词项权重计算及向量空间建模

• 元数据：和文档有关的一些特定形式的数据，比如文档的作者、标题、作者等等
• 参数化索引 parametric index 对每个字段都存在一个与之对应的参数化索引
• 域 zone 通常可以把文档的标题、摘要看作域
• 域加权评分：给定一个布尔查询q和一篇文档d，域加权评分方法给每个（q，d）对计算出一个[0,1]之间的得分，该得分由每个域上的得分线性组合而成。如果给定一系列文档，则满足$\sum_{i=0}^lg_i=1$,再乘以每篇文档自身的权重，因此域加权评分可以定义为 $$\sum_{i=1}^lg_is_i$$ 该方法又称为排序式布尔检索 ranked boolean retrieval
• 算法：如果两个词项都出现在文档同一域中，那么文档得分为1，否则为0
• 给定一批训练样本 training example 每个样本可以表示成一个三元组<查询q,文档d,q和d的相关性判断>
• 如果文档或者域中词项出现的频率越高，那么该文档或者域的得分也越高
• 词项频率 term frequency 词项在文档中出现的次数记为$tf_{t,d}$
• 原始的词项频率在进行相关度计算时，所有的词项都被认为是同等重要的；给文档集频率较高的词项赋予较低的权重
• 将文档频率映射到一个较小的取值范围，引入逆文档频率 $idf_t=\log{\frac{N}{df_t}}$,罕见词的idf很高，高频词的idf可能很低
• tf-idf权重 $tf-idf_{t,d}=tf_{t,d}*idf_t$
• 一系列文档在同一向量空间中的表示被称为向量空间模型 vector space model
• 余弦相似度 $sim(d_1,d_2) = \frac{\vec{V}\left(d_1\right) \cdot\vec{V}\left(d_2\right)}{|\vec{V}\left(d_1\right)||\vec{V}\left(d_2\right)|}$,两个向量的内积定义为$\sum_{i=1}^{M}x_iy_i$
• 计算查询向量和文档集中每个文档向量的余弦相似度，对结果排序，并选择得分最高的K篇文档

CosineScore(q)
    float Scores[0]=0
    Initialize Length[N]
    for each query term t
    do calculate w_tq and fetch posting list for t
        for each pair(d,tf_td) in postings list
        do Scores[d] += wf_td*w_tq
    Read the array Length[d]
    for each d
    do Scores[d] = Scores[d]/Length[d]
    return Top K components of Scores[]

• tf的亚线性尺度变换方法
• 基于最大值的tf归一化，采用文档中最大的词项频率对所有词项的频率进行归一化，为了减轻词项出现次数过高而带来较大词项频率的劣势

---

第七章 一个完整搜索系统中的评分计算

• 新的评分算法：在倒排索引中，遍历q中所有查询词项对应的倒排记录表，并将每篇文档上的得分进行累加
• 利用某种堆结构返回得分在前K篇文档
• 计算前K篇得分最高文档的主要开销在于大量文档都参与了余弦相似度的计算，非精确返回前K篇文档的方法：
  
  1. 找到一个文档集合A，包含了参与最后竞争的候选文档，其中K<|A|<
  2. 返回A中得分最高的K篇文档
• 启发式方法：
  
  1. 只考虑那些词项的idf值超过一定阈值的文档
  2. 只考虑包含多个查询词项的文档，其风险是计算结果往往可能少于K个
• 胜者表 champion list：对于词典中的每个词项t，预先计算出r个最高权重的文档，r的值需要事先给定；给定查询q，对查询q中所有词项的胜者表求并集，生成集合A，只有集合A中的文档才能参加到最后的余弦相似度计算
• 静态质量得分 static quality score：每篇文档d都有一个与查询无关的静态得分个g(d)，其可以基于用户的正面评价次数；如此后一篇文档的得分可以定义为g(d)和某个查询相关得分的组合
• 影响度排序，将词项t对应的所有文档d按照$tf_{t,d}$值降序排列，可以通过设定阈值的方法来减少扫描的文档数目;以查询词项为单位进行处理，然后对所有文档计算累计加分
• 簇剪枝方法 cluster pruning 只考虑利用少数几个簇中的文档进行余弦相似度计算，预处理步骤：
  
  1. 从N篇文档组成的文档集中选出$\sqrt{N}$篇文档，称为先导者集合 leader，其余称为追随者 follower
  2. 对于每篇不属于先导者集合的文档，计算离之最近的先导者
     查询处理过程如下：
  3. 给定查询q，通过与$\sqrt{N}$个先导者计算余弦相似度，找出和它最近的先导者L
  4. 候选集合A包括L及其追随者，然后对A中的所有的文档计算余弦相似度
• 层次型索引 tiered index 用来解决启发式方法得到的A集合个数比K小的情况
• 查询词项的邻近性：令文档d中包含所有查询词项的最小窗口大小为$w$，其取值为窗口内词的个数;$w$越小，文档d和查询匹配程度越高
• 查询分析器 query parser 将用户输入的关键词转换成带操作符的查询，该查询能够基于底层的索引结构进行处理
• 搜索系统的组成 针对自由文本查询的数据传递路径
  

---

第八章 信息检索的评价

• 用测试集来度量IR系统的效果，3个部分组成：文档集，用于测试的信息需求集合，信息需求可以表示成查询；一组相关性判定结果，二值判断结果
• 相关性判定是基于信息需求而不是基于查询来进行的
• 需要准备多个开发测试集，用来调试参数直至最佳的性能
• 正确率：返回结果中相关文档的数目/返回结果的数目；召回率：返回结果中相关文档中的数目/所有相关文档的数目

分类	相关(relevant)	不相关(nonrelevant)
返回	真正例(true positives,tp)	伪正例(false positives,fp)
未返回	伪反例(false negatives,fp)	真反例(true negatives,tn)

$P=tp/(tp+fp)$
$R=tp/(tp+fn)$
精确率：文档集中所有判断正确的文档所占的比例,计算公式为： $(tp+tn)/(tp+fp+fn+tn)$
一个融合了正确率和召回率的指标是F值：

$$F_{\beta=1}=\frac{2PR}{P+R}$$
当$\beta=1$时，表示正确率和召回率的权重相等，$\beta<1$表示强调正确率，$\beta>1$表示强调召回率

• 将正确率和召回率分别作为纵坐标横坐标，可得到正确率-召回率曲线 precision-recall curve
• 插值正确率 interpolated precision 定义为对于任意不小于r的召回率水平r'所对应的最大正确率 $$P_{interp}(r)=max_{r'\ge{r}}p(r')$$
• 平均正确率均值 mean average precision，对单个信息需求，返回结果中再每篇相关文档位置上的正确率的平均值，然后对所有信息需求求平均值，有很好的区别性和稳定性 ，可以粗略的认为是某个查询集合对应的多条正确率-召回率曲线下面积的平均值
• 用于测试的信息需求必须足够大，需求之间的差异也要足够大，这样的话系统在不同查询上体现出的效果才具有代表性
• R正确性，先知道相关的文档集|Rel|，然后计算前|Rel|结果集的正确率，R正确性是正确率-召回率线上的一个点，而不是对整条曲线求概括值
• 缓冲池法：即将一系列检索系统中每个系统所返回的前k篇文档合成一个文档子集，并对这个子集做相关性判定
• kappa统计量 用于类别型判断结果，是对随机一致性的一个简单校正
• 边缘相关性：关注的是在看了一些文档之后是否仍然具有显著的价值；即使一篇文档高度相关，其信息也可能是冗余的，因为已存在于一篇已经看过的文档当中
• 系统的构建者可以对系统做些许改动，得到系统的多个改变版本，然后将其中一个版本和其他版本运行进行对比，通过记录表示用户满意度的指标来对改动进行评价。最常用的方法是A/B测试，一小部分流量被随机导向测试系统，而大部分用户仍然使用现有系统，然后计算某个恰当的指标
• 可用的计算评价指标的方法 点击日志分析 clickthrough log analysis 点击流挖掘 clickstram minining
• 结果片段包括文档的标题以及一段自动抽取的摘要
  
  1. 静态摘要 永远保持不变，并不随查询变化而变化
  2. 动态摘要或基于查询的摘要 根据查询锁推导出的信息需求来进行个性化生成，并试图解释在给定查询下返回当前文档的原因

---

第九章 相关反馈及查询扩展

• RF（relevance feedback相关反馈） 在信息检索的过程中通过用户交互来提高最终的检索效果，其基本的过程如下：
  
  1. 用户提交一个简短的查询
  2. 系统返回初次检索结果
  3. 用户对部分记过进行标注，将它们标注为相关或不相关
  4. 系统基于用户的反馈计算出一个更好的查询来表示信息需求
  5. 利用新查询系统返回新的检索效果
• Rocchio相关反馈算法：假定我们要找一个最优查询向量$\vec{q}$，它与相关文档之间的相似度最大且同时又与不相关文档之间的相似度最小。若$C_r$表示相关文档集，$C_{nr}$表示不相关文档集，那么我们希望找到最优的$\vec{q}$是 $$\vec{q_{opt}}=arg\;max_{\vec{q}}[sim(\vec{q},C_r)-sim(\vec{q},C_{nr})]$$ 其中，sim函数为相似度计算方法，最优的查询向量等于相关文档的质心向量和不相关文档的质心向量的差
• 一种实现分类器的方法是采用朴素贝叶斯概率模型 $$\hat{P}(x_t=1|R=1)=|VR_t|/|VR|$$ $$\hat{P}(x_t=0|R=0)=(df_t-|VR_t|)/(N-|VR|)$$
  其中，N是文档的总数，$df_t$是包含t的文档数目，VR是已知的相关文档集，$VR_t$是VR中包含t的文档子集
• 相关反馈的成功依赖于某些假设：
  
  1. 用户必须要有足够的知识来建立一个不错的初始查询，该查询至少要在某种程度上接近需求文档
  2. 相关反馈方法要求相关文档之间非常相似
• 相关反馈策略的评价
  
  1. 比较一轮相关反馈前后的正确率-召回率曲线
  2. 利用剩余文档集对反馈后的结果进行评价，其性能的度量结果往往低于原始查询的结构
  3. 给出两个文档集，一个用于初始查询，一个用于比较和评价
• 伪相关反馈，盲相关反馈，该方法首先进行正常的检索过程，返回最相关的文档构成初始集，然后假设排名靠前的k篇文档是相关的，最后在此假设上像以往一样进行相关反馈
• 隐式相关反馈 利用间接的资源而不是显示的反馈结果作为反馈的基础
• 查询扩展 最普遍的查询扩展方法是通过某种形式的同义词词典进行全局分析，其构建方法如下：
  
  1. 使用人工编辑的一部受控词汇表
  2. 使用人工编纂的同义词词典
  3. 使用自动构建的同义词词典
  4. 基于日志挖掘进行查询重构