ReID任务中的CMC和mAP
转自https://rayhy.com/blog/20190223-reid%E4%BB%BB%E5%8A%A1%E4%B8%AD%E7%9A%84cmc%E5%92%8Cmap/
ReID指Re-identification，常翻译为重识别。ReID任务本身分类很多，本文只讨论基于图片的ReID任务中single-gallery-shot这一最简单的情况。
重识别任务可以描述如下：
给定一个Gallery集合G，包含有N张图片，分属M个ID(identity)。给定一张未知ID的图片做query(或者叫probe), 计算出下式的结果：
得到i之后，图片gi对应的ID就是query的ID。大部分ReID相关的研究，都是在研究Similarity()这个函数，使得这个函数在同ID时返回值高，不同ID时返回值低。
上图是一次典型的重识别任务
为了更好地理解，我在这篇文中介绍一个新的重识别任务：水果emoji重识别。
我们现有一个水果emoji的数据集GG：[????????????????????????????????????????????????????????????]，假定这个数据集中，即使是相同的emoji，图片也有细小的差别。 数据集一共包含N=15N=15张图片，共有M=3M=3种ID。任意给定一组query: [????,????]，从数据集GG中找到和每个query最相近的5张图片(为了保证准确率，我们都是返回一组最相近的图片，而不是如前文所述的单独一张图片)。
我们现在有两个评价emoji之间相似程度的函数Similarity1()和Similarity2()。 对于query????，Similarity1()得到[????????????????????]，Similarity2()得到[????????????????????]。 对于query????，Similarity1()得到[????????????????????]，Similarity2()得到[????????????????????]。 得到的结果都按与query的相似度从左至右排列。那么Similarity1()和Similarity2()哪个得到的结果更好呢？
或者说：我们应该怎么度量Similarity()函数的性能？答案就是CMC和mAP。
ＣＭＣ
CMC是Cumulative Matching Characteristics的缩写，我个人把它翻译为累计匹配特性。ReID模型的好坏可以通过CMC曲线来评价。 为了计算CMC曲线，首先要把每次查询的结果按相似程度排序。接着，引入一个概念: topKtopK准确度: AccKAccK，其计算公式如下：
这里的K是一个从1开始增加的变量。显然，AccK形同单位阶跃函数。假设在查询得到的结果中，与query同ID的结果第一次出现时的排名为F，那么显然，AccK在K=F时，值由0变为1。 CMC曲线的计算方法就是，把每个query的AccK曲线相加，再除以query的总数，即平均AccK曲线。
回到我们的水果emoji重识别任务。 分别计算两个query的AccK曲线如下：
再平均各个query的AccK曲线，由此我们得到这两种相似度函数的CMC曲线都是[0.5 1 1 1 1] 由于query只有两个，所以得到的CMC的值有些简单。当query数足够大时，CMC曲线就会变成下图这样：
由于AccK曲线是一个单位阶跃函数，CMC曲线必定是一个单调递增的曲线。曲线上某个点如(R5, 0.96)就表示正确结果在前返回所有结果中排名前5的准确率能达到5%。 实际论文中，常取CMC曲线上的某几个点之间对比，比如常出现的Rank1，Rank5，就分别是CMC曲线上，K=1，5时的值。
mAP
mAP是mean Average Precision的缩写。mAP涉及到的前置概念比较多：mAP是每个query的AP(Average Precision)的平均值，而AP又指Precision(准确率，又称查准率)的平均值。我们从头开始讲起。
对于ReID任务，我们经常关心两个问题：
- 查询得到的结果中，有多少比例是同一ID的 ?
- 同一ID的图片中，有多少比例被检索出来了?
这两个问题分别对应查准率(precision)和查全率(recall)，亦称作准确率和召回率。因为准确率这个称呼在别的领域有其它意义，为了防止误解，我还是喜欢用查准率和查全率的说法。
查准率和查全率
查准率就是和query同一ID的图片在查询结果中的占比。计算公式如下:
查准率可以同时考虑所有的获取到的结果，也可以单独给定一个特定的值K，只考虑返回结果中排名前K的查询结果，在这种情况下，查准率又可以称为前K查准率，记作[email protected]。
查全率就是和query同一ID的图片出现在查询结果中的数量占总数的比例。计算公式如下：
查准率和查全率看上去都很有意义，但我们能直接用它俩来评判ReID模型的性能了吗？当然不行，由于查准率和查全率都是通过比例来计算，完全忽略了返回的结果是有排序的！当查询????时返回结果????????????????????和????????????????????当然是不一样的，但其查准率和查全率却是一样的。返回结果的顺序被忽略了。
值得注意的是，查准率和查全率是一个相互矛盾的度量，比如为了增加查全率，我们可以通过增加查询结果的数量来实现，当查询结果数量等于数据集大小时，查全率一定等于1，因为这时所有图片都被查询得到了。但此时查准率就成了最小值。所以比较模型的性能不是那么简单的事情。
P-R曲线图
那怎么比呢？肉眼比对时，我们常从结果的第一个开始，一个一个比对。借鉴这种思路，我们可以逐渐增加查询结果的数量，从第一个开始，一直到系统给出的查询结果的最后一个，把中间每个点对应的查准率和查全率绘制到图上，得到类似下面的结果：
P-R图直观地显示出了ReID模型的查全率和查准率，显而易见，如果一个模型的P-R曲线包住了另一个模型的P-R曲线，这个模型的性能就好于另一个模型。
Average Precision
显然，PR曲线与坐标轴围起来图形的面积一定程度上反应了ReID模型的性能，我们把这个面积叫做Average Precision。这个面积怎么求？由积分知识可得:
可惜，我们得到的是曲线上一个个点，得不到p(r)的准确公式，没法用上面的公式计算。 但是，这个积分可以视作多个长方形条的面积之和，离散化后得到如下公式：
公式中的P(k)特指我们上文提到过的前K查准率，Δr(k)= r(k)-r(k-1)。需要注意的是，前k-1个查询结果和前k个查询结果中的同ID结果数量可能一样，所以Δr(k)可能为0。用公式写出来就是：假设数据集中有N个同ID查询结果，则有
所以如果令集合Ω为和query同ID的第k个查询结果的集合，那么上式可以接着改写为
即只考虑查询结果中同ID结果的查准率和查全率。网上搜mAP相关教程时经常出现的图片(来自yongyuan.name)用的就是这个公式。
为了使计算的AP更精确，我们可以用梯形面积公式替换矩形面积：
这里的P(0)=P(1)是什么意思呢？P(1)指的是第1个结果的查准率，P(0)即第0个结果的查准率本来是无意义的，但是，为了预防RESULT1与查询同ID时，公式中出现无意义的P(0)，我们补一个P(0)=P(1)的定义。
注意：i-1∈Ω不一定成立，所以这里的P(i−1)不是Ω集合中的上一个点的查准率，而是第i-1个查询结果对应的点的查准率。
详细分析附在了文章最后。
这两个公式都可以计算AP，后一个公式精确度更高一些。
最后，平均一下每个query的AP值就得到了mAP。
再回到我提出的水果emoji重识别任务，我们来计算下两种方法的mAP：
我们现在有两个评价emoji之间相似程度的函数Similarity1()和Similarity2()。 对于query????，Similarity1()得到[????????????????????]，Similarity2()得到[????????????????????]。 对于query????，Similarity1()得到[????????????????????]，Similarity2()得到[????????????????????]。
拿计算Similarity1()在query为????举例：
所以:
query为????时，AP=0.766666；所以mAP＝( 0.597 + 0.767 ) / 2= 0.682。
同理可以计算Similarity2()的mAP为0.722，所以我们最终得到，Similarity2()优于Similarity1()。