UIUC《文本检索与搜索引擎》课程学习笔记(三)—— 模型评估

UIUC《文本检索与搜索引擎》课程学习笔记(三)—— 模型评估

引导问题(Guiding Questions)

Develop your answers to the following guiding questions while completing the readings and working on assignments throughout the week.

  • Why is evaluation so critical for research and application development in text retrieval?
  • How does the Cranfield evaluation methodology work?
  • How do we evaluate a set of retrieved documents?
  • How do you compute precision, recall, and F1?
  • How do we evaluate a ranked list of search results?
  • How do you compute average precision? How do you compute mean average precision (MAP) and geometric mean average precision (gMAP)?
  • What is mean reciprocal rank?
  • Why is MAP more appropriate than precision at k documents when comparing two retrieval methods?
  • Why is precision at k documents more meaningful than average precision from a user’s perspective?
  • How can we evaluate a ranked list of search results using multi-level relevance judgments?
  • How do you compute normalized discounted cumulative gain (nDCG)?
  • Why is normalization necessary in nDCG? Does MAP need a similar normalization? Why is it important to perform statistical significance tests when we compare the retrieval accuracies of two search engine systems?

额外阅读材料(Additional Readings and Resources)

  • Mark Sanderson. Test collection based evaluation of information retrieval systems. Foundations and Trends in Information Retrieval 4, 4 (2010), 247-375.
  • C. Zhai and S. Massung. Text Data Management and Analysis: A Practical Introduction to Information Retrieval and Text Mining, ACM Book Series, Morgan & Claypool Publishers, 2016. Chapter 9

关键概念(Key Phrases and Concepts)

Keep your eyes open for the following key terms or phrases as you complete the readings and interact with the lectures. These topics will help you better understand the content in this module.

  • Cranfield evaluation methodology
  • Precision and recall
  • Average precision, mean average precision (MAP), and geometric mean average precision (gMAP)
  • Reciprocal rank and mean reciprocal rank
  • F-measure
  • Normalized discounted cumulative Gain (nDCG)
  • Statistical significance test

一、引言(Evaluation of TR System)

正如对其他预测系统所做的一样,我们对文本搜索系统也要进行一个定量的评估。

1.用什么指标来评估(What to Measure)

  • 精度(Effectiveness/Accuracy): 搜索结果的精度有多高?
    -着眼于一个系统把相关文档排在无关文档前面的能力
  • 效率(Efficiency):用户多久才能得到结果?为了完成询问,需要多少的计算资源?
    -着眼于时间、空间复杂度
  • 适用性(Usability):这个系统对于实际需求而言有帮助吗?
    -进行用户调查

2.克兰菲尔德评估方法论(The Cranfield Evaluation Methodology)

  • 1960年代诞生的一种用来选取实验检测中的要素的方法论
  • 思想:构建一个可重用(reusable)的测试集&定义方法
    – 一个文档样本集(模拟实际文档集)
    – 一个关于主题/询问的样本集(模拟用户询问)
    – 相关度判断(对于用户而言的理想结果)- 理想状态下的排名名单
  • 一个能够重用的测试集,测试结果用来与其他系统对比

二、基本评估方法(Basic Measure)

1.准确率和召回率(Precision & Recall)

学过机器学习的同学对这两个指标肯定不陌生了,我们看看它们在NLP中的应用:

我们将某次询问的结果用向量表示,其中每个系统判断的相关文档数不同。这些文档中真正相关的文档标记为+号,不相关的标记为-号。

系统A返回的相关结果​\( R_A =[++-] \)​,

系统B返回的相关结果​\( R_B=[+–++] \)​。

如果文档集里面真正的相关文档数为10的话,那么对于系统A而言:

\[ Precision=2/3 \\ Recall = 2/10 \]

对于系统B而言:

\[ Precision=3/5 \\ Recall=3/10 \]

这和你的计算一不一样呢?它们的表达式是:

\[ Precision=\frac{结果中真正相关的文档数 }{返回的结果的文档总数}\space\space\space\space\space\space(2.1)\\Recall=\frac{结果中真正相关的文档数}{测试集中所有的相关文档数}\space\space\space\space\space\space(2.2) \]

2.连接准确度与召回率:F-Measure(Combine Precision and Recall : F-Measure)

同样,我们在机器学习中学过F1指数,它这里的F-Measure的特殊情况。

\[ F_\beta=\frac{1}{\frac{\beta^2}{\beta^2+1}\frac{1}{R}+\frac{1}{\beta^2+1}\frac{1}{P}}=\frac{(\beta^2+1)P*R}{\beta^2P+R}\space\space\space\space\space\space(2.3) \]

其中

P=准确率

R=召回率

β=参数(经常被设为1)

如果我们设β为1就得到了F1函数:

\[ F_1=\frac{2PR}{P+R} \]

为什么经常设β为1呢?

我们用特殊情况来理解:

  • 当β趋近于无穷大的时候,

    \[ \lim_{\beta\rightarrow\infty}F_\beta=\frac{\beta^2P*R}{\beta^2P}=R \]

    怎么理解呢?这个情况是说,β趋近于无穷大的时候,F-Measure退化成召回率R。

  • 当β趋近于0的时候:

    \[ \lim_{\beta\rightarrow0}F_\beta=\frac{P*R}{R}=P,when \space R \ne0 \]

    当β趋近于零的时候,F-Measure退化成准确度P。

综上,β是用来改变P和R的权重的,当β=1时两者得兼。β越大,越倾向于召回率。

3.总结

  • 准确率(Precision):所有的搜索结果都是相关的吗?
  • 召回率(Recall):所有的相关文档都被搜索到了吗?
  • F-Measure关联了精确率和选择率
  • 如何权衡精确率和召回率的关系,取决于用户的需求

三、评估排名名单(Evaluating Ranked Lists)

1.精确率-召回率曲线(Precision-Recall Curve)

确定了评估一个文本检索所需的观测量,那么我们现在用一个系统的搜索结果来实际分析一次:

对于一个用户来说,他可能并不会把所有的搜索结果都看一遍,而是看TOP-N。在不同阅读量的时候,P和R是有浮动的,这个时候,我们就能够画出一条关于P和R的曲线。(注意,这里的N也是变量,但在该方法中暂未考虑进去,不大严谨

我们看到,准确率与召回率似乎是负相关的,怎么理解呢?

一个系统可以用一个阈值选择在它有多大把握的时候把文档判断为相关文档,如果阈值太低,那么会返回更多搜索结果(尽管系统对于结果是否相关的把握不大),这样就更难有“漏网之鱼”。而反过来,如果阈值太高,那么只有当有很大把握的时候才会判定为相关,但这样也就导致了一些相关文档被放走。

理想情况下:一个系统对与每一个召回率的把握都是一样高的。(这里我还不是特别理解该怎么思考和表述,欢迎讨论)

此外,对于一个系统,其不同召回率的情况下准确度如果都很高,那么曲线的位置会在更上面。如果一个曲线完全在另一个的上面,那么毫无疑问这个算法更好。

但是,实际上很多系统的P-R曲线并不是这样的,它们会交叉。这时候就需要根据需求来选择搜索系统了。

2.如何总结一个排名名单(How to summarize a ranking)

上面我们通过PR曲线对于评估方法有了一个感性的认识,那么这个评估该如何量化呢?

我们之前提到过,用户可能并不会读完全部的搜索结果,而只读TOP-N。而不同的N下,精确率和召回率都是不同的。那么假如我们需要从这两个指标入手,该如何把它们归结为一个量化指标呢?

一种方法是简单相加,这显然不是特别妥当,因为读TOP-N的人数占比是不一样的。

这里提出了一个方法,Mean Average Precision(MAP):

\[ \frac{\sum_{N}{该top-N中实际相关文档数}}{测试集中相关文档的总数} \space\space\space\space\space\space ,while\space(top-N:后续还有相关文档)(3.1) \]

之所以例题中最后几项的P都取0,是因为,后面再也无法找到新的相关文档了(听起来很有道理,可是我对此还是有一些模糊)。

3. 平均值的选取

  • 平均准确率(Average Precision)
    – 在正确命中相关文档的截断处进行平均值计算
    – 标准化者(Normalizer)= 集合中相关文档的总号数
    – 对于排名名单中每一个相关文档都很敏感
  • Mean Average Precision
    – MAP = 一系列Query的平均准确率的算术平均值
    – gMap= 一些列Query的平均准确率的几何平均值
    – 哪一个更好?

4.特殊情况:平均排名倒数(Special Case:Mean Reciprocal Rank)

当集合中只有唯一一个相关文档的时候(例如,对于已知物品的搜索)

  • 平均准确率=平均排名倒数=1/r,其中r为该唯一相关文档的排名位置
  • Mean Average Precision -> Mean Reciprocal Rank
  • 为什么不简单地使用r?

5.总结

  • 准确率-召回率曲线抽取出了一个排名名单的总体特征
  • 一个排名名单的实际用途取决于一个用户到底会检查名单的前几位
  • 平均准确率是比较两种排名方法的常规方法
    – 联系了准确率和召回率
    – 对于排名名单中每一个实际相关文档都敏感

四、多级评估(Multi-Level Judgements)

之前我们讨论了布尔预测(只判断是否相关)下的评估方法。假如我们需求更加精确的预测,比如[不相关,可能相关,非常相关],该怎么办呢?

这里有两种选择方法:

  1. 累积增益(Cumulative Gain) 这种方法下,直接将子集合中的预测等级相加。通过之前的讨论我们知道,这种算法并没有考虑到用户浏览不同TOP-N的可能性存在的不同。
  2. 折扣累积增益(Discounted Cumulative Gain) 这种方法相对于第一种方法,考虑到了用户浏览不同TOP-N的可能性,引入了权重项logN。
Tags:


Leave a Reply

Your email address will not be published.

*
*
*

Insert math as
Block
Inline
Additional settings
Formula color
Text color
#333333
Type math using LaTeX
Preview
\({}\)
Nothing to preview
Insert