『IR 信息检索入门必看』#5 检索系统评价（简明）

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），这两种值是互相依存、互相影响的。