检索Evaluation

Evaluation Criteria of Unranked Retrieval

-	Retrieved	Not-retrieved
relevante	TP(true positive)	FN(false negative)
Non-relevant	FP(false positive)	TN(true negative)

$precision = \frac{TP}{TP+FP}$ $recall = \frac{TP}{TP+FN}$

通常precision和recall是呈一种负相关的关系，recall越高，precision越低。precision-recall curve以recall为横坐标，以precision为纵坐标，表示precision-recall变化关系。

组合precision和recall的评价参数。

$F = \frac{1}{\alpha\frac 1P + (1-\alpha)\frac 1R} = \frac{(\beta^{2}+1)PR}{\beta^2P+R}$

通常我们取$\beta=1,2,3..=，1$，也就是$\alpha=0.5$，也就是harmonic mean，也写作$F_1$，当取$\beta=1,2,3..$，也就得到$F_1, F_2, F_3..$：

$F_1 = \frac{2}{\frac 1P + \frac 1R}=\frac{2PR}{R+P}$

用于表示在top k结果中的precision和Recall，如P@10，表示top 10结果的precision。

也就是Mean reciprocal rank，reciprocal rank表示对于一个query第一个正确结果排名位置的倒数值，也就是$RR=\frac {1}{rank}$。MRR表示多个query的RR的平均值：

$MRR=\frac{1}{|Q|}\sum^{|Q|}_{i=1}\frac {1}{rank_i}$

维基百科给出了一个很好的例子：

query	results	correct response	rank	reciprocal rank
cat	cattern,cati,cats	cats	3	1/3
torus	toril,tori,toruses	tori	2	1/2
virus	viruses,virii,viri	viruses	1	1

$MRR=\frac {(\frac 13 + \frac 12 + 1)}{3}=0.61$

Mean average precision，上面的MRR适合只考虑第一个正确结果检索性能使用，如果有多个正确结果且都要考虑，则应该使用MAP。

假设query q有m个correct document(or query suggestion etc.).

$AP(q)=\frac 1m \sum^{i=m}_{i=1}P(RankSet_i)$

$RankSet_i$表示document i排序所在的位置及以上的位置所有的document。假设docuement i=3，排在第7的位置，则$RankSet_3$为1-7的documents，$P(RankSet_i)$即是这个set的precision。

MAP为多个query的AP的mean：

$MAP=\frac{1}{|Q|}\sum^{|Q|}_{i=1}{AP(i)}$

DCG：Discounted cumulative gain
nDCG：Normalized Discounted cumulative gain

给每个文档指定一个得分，我们希望的得分越高的文档排在越前面。
假设一个排名是: $G=[5,2,3,0,10,3]$

cumulativfe gain可以计算如下：

$CG[k]=\sum^{k}_{i=1}G[i]$

加上一个惩罚系数，排名越后惩罚越多：

$DCG[k]=\sum^{k}_{i=1}\frac{G[i]}{log_2(1+i)}$

存在理想的排序$G^`=[10,5,3,3,2,0]$，使得DCG的得分最高。

使用这个最高得分normal实际的排序，得到就是nDCG得分。

$nDCG[k]=\frac{DCG[k]}{DCG^`[k]}$