1. 『IR 信息检索入门必看』#5 检索系统评价(简明)
前述文章介绍了几种基本信息检索模型,本文将介绍如何评价一个现有的文档检索系统。
一个检索系统的好坏,通常取决于其检索结果与用户查询的相关性,此外还有检索用时、检索范围等等。这里仅针对评价相关性展开讨论。
如何度量相关性?考虑如下三个待实现的要素:
当然,这个「打分标准」可能会随每个人的 信息需求 而变化(the information need is translated into a query),因此这个指标不是确定的(more than binary)。
有了以上三个基本要素,我们就可以构造出一个合理的 测试集 :包含文档集、查询集和有关评价机制。
在制定测试集的时候,往往要先标注好相关的「查询-文档」对。对于小的测试,可以采用人工标注(遍历文档集和查询集)。
但对于较大的测试集则不行(如 TREC 测试集)。此时,可以采用如下方法:
直接用已有的几个检索系统在「总的基准文档集」中检索,取出每个检索的前 n 个结果,取 并集 ,用这个「新的集合」作为「模拟基准文档集」进行标注,这样就可以大大减少范围。
可以通过随机抽样估计真实相关集的大小。
与其阅读所有的文档,不如人工用较宽泛的 Query 先得到一些检索结果,再在这些结果中标记。
有了合理的测试集,只需要用待测试 IR 查询「基准查询集」的内容,对查询结果与「查询-文档」对比较,即可得到有效性度量。
以下介绍两个在度量有效性过程中常用的变量。
在检索结果的 Top n 中,我们定义如下变量:
Precision (精度): Proportion of a retrieved set that is relevant.
Recall (召回率): Proportion of all relevant documents in the collection included in the retrieved set.
与这两个概念相关的还有 Miss (漏识率) 和 Fallout (误报率)。
对应的混淆矩阵(Confusion Matrix)如下表:
这样的计算过程没有考虑到检索结果的顺序,事实上相关文档排在前列的搜索引擎才是我们最需要的。
考虑搜索引擎返回的结果是有序的,取 Top n,则计算 P/R 的方法可以加以修正:
对检索到的文档按照 ranking 排列,顺次计算 P/R,每次计算时考虑前 k 个文档。最后会得到一组 n 个 P/R 值,再对 Top n 中的「相关文档」对应的 Precision 取平均。
上图中,我们对搜索引擎 A 和搜索引擎 B 查询了同一关键词,并取了 Top 10 的查询结果,其中各有 5 篇相关文档,经过计算可发现,A 的检索结果更优。
但是,如果我们要对同一个搜索引擎 A 用不同的关键词来查询呢?
对于不同的 query 可能 Top n 中有数量不同的相关文档,此时的 Recall 就会不一致。如果我们要计算同一 Recall 值处的精度,则需要用到插值方法。
仅用个别的 query 难以在数据巨大的文档集中得到准确的 P/R 值。因此需要考虑更多的 query,并对结果再次平均。
由此,引出两种平均的思想:
做宏平均的过程中,最重要的是将所有 query 视作平等的点。因为在微平均的过程中,我们往往只关注一些大样本、常见样本,而这些样本并不能完全体现搜索引擎的性能。而宏平均关注其他小样本、偏僻样本,这些样本的检索结果体现了搜索引擎内部的类别分布是否均匀。
这种方法也称作 MAP ( Mean Average Precision ),平均之上的平均。
如果只关注平均精度,则会隐藏检索结果的一些有效信息。如果用图表的形式呈现,则更能观察到趋势。
如果直接把 ranked retrieval 的结果画在图中,会得到一条「 锯齿状 」的曲线。因为在同一个召回率下,随着结果数的增长,精度是垂直向下的。
此时,如果我们想要关注曲线中的:
由于各个 query 对应的相关文档总数不同,观测到的召回率点也不同。此时就需要对离散的点用 interpolate (插值),做出连续的曲线,才能确定这些点的精度。接下来讨论如何选取适合的插值方法。
基本原则 :从 平均 来看,随着召回率的增加,精度应该是单调递减的。
基于这个原则,可以得到 即:选取「当前区间」最大的精度点,再以「召回率大于该点的区间」为「新区间」,选取最大的精度点,迭代至 100%。
最后用「 阶梯状 」曲线连接以上各点,可以得到单调递减的曲线。
综合考虑 P/R 值,可以计算出如下 单值评价指标 。
用于强调精度或召回率中的某一个指标,同时兼顾另一个指标。
根据 的取值,增大 代表强调精度的重要性,反之强调召回率。
令 ,可以得到 当 时可得到二者相同重要性的效果,此时的 具有的 物理意义 是所有相关文档 和所有检索到文档 的集合的 对称差 的基数除以两个集合的基数。
将 取补,可以得到
其中 分数则是 P/R 值的调和平均,较为平均的兼顾了二者。这是分类与信息检索中最常用的指标之一。
之所以使用 调和平均 而不是算术平均,是因为在 算术平均 中,任何一方对数值增长的贡献相当,任何一方对数值下降的责任也相当;而 调和平均 在增长的时候会偏袒较小值,也会惩罚精确率和召回率相差巨大的极端情况,很好地兼顾了精确率和召回率。
类似 和 这样的单值评价指标之所以重要,是因为这样能够更好的优化度量。此外,在文档评价中,我们还有如下指标:
定义在弱顺序文档,量化的用户查找 K 个相关文档所需工作量。这项指标计算预期用户在找到第 K 个相关文档之前,按顺序浏览搜索结果列表将要看到的非相关文档的数量。
寻找 Precision 等于 Recall 的点,通常在分类任务中用到。
对于某些 IR 系统(如问答系统或主页发现系统),只关心第一个标准答案返回的 rank,越前越好,这个位置的倒数称为 Reciprocal Rank (RR) ,对问题集合求平均,则得到 MRR。即,把标准答案在被评价系统给出结果中的排序取倒数作为它的准确度,再对所有的问题取平均。
2. 『IR 信息检索入门必看』#9 网页排序(简明)
当我们在一个小的文档库中查询时,即使 query 很模糊,我们只要返回所有相关文档即可,甚至不需要 猜测 用户的查询需求。
但如果在一个大的文档集中查询时(比如谷歌),往往可以返回大量的相关文档。如果基于相关度的 ranking,往往无法区分哪些文档该呈现在最前面,甚至可能时一些低质量的网页对于某些词的词频很高,从而排在了前面。
此时我们就不能只聚焦与「相关度」,PageRank 算法通过计算一个页面的「 重要度 」,从而判别网页质量,得到排序。
如何衡量「重要度」?用点击率、权威性?然而,这些数据都是爬虫无法爬取到的,同时也难以正确衡量。
科学家们从 Bibliometrics (文献计量学) 中借鉴了如下观点:
例如,最权威的 SCI 往往只收录其认为重要的期刊,也只记录其中的期刊相互引用的次数。当一篇文章被 SCI 收录的文章引用时,通常也可以说明其有一定的影响力——即重要度的「 传递 」。
对于文献引用的可视化,我们通常称为 Citation Graph,通常是一个 Directed Acyclic Graph (有向无环图,DAG),因为较早的文章无法修改而引用后来的文章。
在网页中,我们可以 Hyperlinks (超链接) 来类比引用,从而形成一个 Hyperlink Graph,区别是这类图中可以有环路。
从而引出网页排序的基本假设:
基于上述假设,我们很容易可以得到当前页面的链入、链出数。但是,要怎么知道链入当前页面的 前序页面 ,其重要度是多少呢?
在一个封闭的 Hyperlink Graph 中,随机选取一个页面作为访问起点,随机选取其链出的页面进行访问,再对下一个页面重复上述操作。
大量重复后,统计每个结点被访问的频率,用频率近似概率后,我们可以发现访问概率较大者通常有着较多的链入,或者其链入页面也有着较大的访问概率。用公式表示就是: 其中 表示从编号为 1 的网页跳转到编号为 i 的网页的概率,其计算方式为:
令 ,则 ,再令 ,则有:
特别地,当 i 取遍 1 到 N 的所有值后, 得到矩阵形式: 其中 B 称作 标准化链接矩阵 ,矩阵中的每个元素代表列号对应的 Page 链入行号对应的 Page 的概率,每列之和为 1。当一个页面没有链出时,这一列全为 0。
于是我们可以用 迭代 方法求解这个方程的稳定解 ——即我们想求的访问概率向量,也就是 重要度 向量。只需要将 设为全 1 向量(因为一开始随机访问到每个页面的概率都相同),不断代入即可。
然而,现在存在的问题是,上面的所有推导都是建立在理想状态下的,即假设所有网页组成的这个有向图是 强连通 的。
当 Hyperlink Graph 存在 link loops ( 循环陷阱 ),即存在一个小的子图,只有链入没有链出,所有随机游走的用户到了这几个网页后,就如同进了黑洞一般,一直在里面“打转”,出不来了。
这样就使得当游走次数趋于无穷时,最终陷阱中结点的访问次数远大于其他结点。这样会使得计算出的 向量中,陷阱外的结点访问概率都为 0。
PageRank 算法最终采用了 阻尼因子 (damping factor)的修正,使得进入陷阱后仍有机会跳出循环。 其中 为全 1 向量, d 是实验确定的常数,通常取 0.15。
有了重要度向量后,当有查询时,我们只需要先确定 命中文档 (至少有一个 term 与 query 相同的文档),再将其用重要度排序即可。
然而,这样做的缺点是,没有考虑到查询和文档的相关性——即,有可能一篇文档虽然有相同的 term,但主题却相去甚远。
于是,有人提出了结合 Term Weighting 和 PageRank 的方法,在确定命中文档后,利用传统的权重计算方法,计算出 query 和每个 doc 的相似度 。再和重要度 线性加权算出排序指标: 其中 为实验确定的常数。
在实际的网络中,PageRank 算法还存在「 主题漂移 」问题,特别对于大量随意交互外链的站点,会导致搜索引擎返回主题无关结果。
同时,前面的讨论提到,PageRank 忽略了 query 的主题相关性,也导致了结果的相关性降低。同一查询词在 不同语境 下,语义上指向的可能是不同的主题,但 PageRank 无论如何都是返回「重要度」最高的页面。
理想情况下,应为每个用户的偏好维护一套专用的「主题重要度」向量,但面对海量用户这种方法显然不可行。所以搜索引擎一般会选择一种称为主题敏感的折中方案。
基本假设 :在 PageRank 的随机游走模型中,用户倾向于选择具有 同一个主题 的链出网页。
基于这个假设,可以预定义几个话题类别,例如体育、娱乐、科技等等,对于某个网页来说,对应某个主题类型都有相应的 PageRank 分值,然后想办法关联用户的话题倾向,根据用户的话题倾向排序结果。
与原始的 PageRank 不同,新的算法对出度为 0 的网站加以处理以保证 收敛性 。引入了向量 来指示某一个网页是否出度为 0,若为 0 则对应项为 1。
向量 来表示访问各个网页的概率均等,代替 的写法:
两个矩阵的乘积所得的矩阵 D 表示出度为 0 的网页将以均等概率访问其他网页。与前述提到的矩阵 具有互补的特性,补充了在随机游走模型中,一个网页出度为 0 时的访问页面的情况。这样做使得最终矩阵的每一列之和都为 1。 则最终排名的计算方法为:
主题的预定义参考了 ODP (Open Directory Project) 网站,利用 ODP 中 16 个顶级分类下的 URLs 生成了 16 组偏置 PageRank 向量 (biased PageRank vectors)。
为了实现这一点,算法中采用了新的向量 ,针对每个主题有: 其中 表示在契合第 j 个主题的网页集合。包含在这些网页中的页面被赋予较大的跳转概率值,而其他网站则相对减少。
此外,还需要在给定一个查询 q 的时候,估算出该查询落在某个主题 的概率。文章使用了 朴素贝叶斯分类器 (naive-Bayes classifier),将查询 q 中的每个 term 分词记作 ,利用贝叶斯公式: 而 则容易用统计的方法估计出来,对于 则采用 先验概率 的方法,根据用户的查询历史(上下文)进行动态调整。
计算出了查询落在各个主题的概率后,再用这个概率对各个主题下的 Rank 向量进行线性加权,即可得到最终排序用的评分:
这里再介绍一种基础的网页排序算法——基于超链接追敏的主题排序,对于一个查询,不再返回单一的网页排名,而是同时返回两个列表:
那么,如何排序这两个列表呢?
基本假设 :
基于这两个假设,我们可以提出两个指标来衡量每个页面:枢纽值(Hub Scores)和权威值(Authority Scores),这两种值是互相依存、互相影响的。