平均精度的正确版本是什么？

Question

我正在尝试计算 Average Precision (and Mean Average Precision) on the Oxford Building image dataset。

下面是他们提供的用于计算平均精度的代码。请注意，pos_set 是来自地面集的 "optimal" 和 "good" 图像的并集，而 junk_set 是一组不相关的图像。

void OxfordTest::computeAp(std::vector<std::string> &ranked_list){
      float old_recall = 0.0;
      float old_precision = 1.0;
      float ap = 0.0;

      size_t intersect_size = 0;
      size_t i = 0;
      size_t j = 0;
      for ( ; i<ranked_list.size(); ++i) {
              if(!pos_set.count(ranked_list[i]))
                  std::cin.get();
        }
        if (junk_set.count(ranked_list[i])) continue; 
        if (pos_set.count(ranked_list[i])) intersect_size++;

        float recall = intersect_size / (float)pos_set.size();
        float precision = intersect_size / (j + 1.0);

        ap += (recall - old_recall)*((old_precision + precision)/2.0);

        old_recall = recall;
        old_precision = precision;
        j++;
      }
}

这与链接的维基百科页面上给出的概念完全不同。 这些概念之间有什么关联？

我非常确定维基百科的观点是正确的，因为它与这篇 and this 文章中给出的观点一致。

不明白为什么上面的代码会报错：

召回率，而维基百科的概念仅包括最后一个公式中的精度。
即使考虑到带有 delta recall 的公式，也没有人谈论 `(old_precision + precision) /2

This is the C++ original code.

Answer 1

召回率与平均精度绝对相关，因为您实际上是在每个可能的召回点计算精度。正如您自己注意到的那样，您可以在第一个维基百科定义中看到这一点。

还可以在这里找到对 AP 进行清晰解释的很好的概述： https://sanchom.wordpress.com/tag/average-precision/

我将从假设此代码片段正确计算 AP 开始，让我们看看它会将我们引向何方。（这不一定是真的，但考虑到该论文自 2007 年以来已被引用 1.8K 次，大概如果有错误现在有人会发现它。）

构成 AP 总和的每个元素被维基百科定义为：

P(k) * delta_r(k)

where k is the rank in the sequence of retrieved documents, n is the number of retrieved documents, P(k) is the precision at cut-off k in the list, and delta_r(k) is the change in recall from items k-1 to k.

换句话说，这一行...

ap += (recall - old_recall)*((old_precision + precision)/2.0);

...大概是添加求和元素的原因。

很明显delta_r(k)==(recall - old_recall)，所以那部分被覆盖了。

那么 ((old_precision + precision)/2.0) 呢？这也是你所关心的。

好的。所以。这一段确实很奇怪。它不是使用 P(k)（截止点 k 处的精度），而是显然对 P(k) 和 P(k -1)。我运行这是我的实验室伙伴（我在国家认可的 IR 实验室工作），我们无法弄清楚为什么代码会这样做。我的直觉是，这是作者选择做的某种形式的平滑，但我不明白为什么。另一种选择是总和以某种方式伸缩并且这些项目相互抵消。它确实看起来很 st运行ge。

编辑：这个 "weird" 规则显然借鉴了使用 trapeziodal rule instead of the rectangle rule 来估计曲线下的面积，正如 Relja A运行djelović 在接受的答案中所解释的那样。在这里添加是为了完整性。 <\编辑>

与此同时，您可以将此运行king 函数的结果与 trec_eval 进行交叉引用，看看是否获得相同或不同的结果。

Answer 2

垃圾集

原始论文指出：

(3) Junk – less than 25% of the object
is visible, or there is a very high level of occlusion or distortion.
(4) Absent – the object is not present

即垃圾图像 不是底片 。有正面 (OK+Good)、忽略 (Junk) 和负面 (Absent)。请注意，所有这些都是 per-query，即有些图像对于查询 1 是垃圾，但对于查询 15 不是。如果您查看 'junk' 的图像，您会看到模棱两可的例子，例如有些情况下有极度缩放或模糊，这会让你认为这张图片是否包含查询的地标，以及只有一小部分物体可见的情况，所以图像太硬了。

In computing the average precision, we use the Good and
Ok images as positive examples of the landmark in question,
Absent images as negative examples and Junk images
as null examples. These null examples are treated as though
they are not present in the database – our score is unaffected
whether they are returned or not.

所以作者将垃圾集定义为既不是正片也不是负片——这些图像最有可能描述了查询对象，但对于其中一些我们不确定，或者将它们视为正片会过于苛刻，并且要求系统检索这些示例（因此如果不检索则进行处罚）。同时，将它们视为负面的也很苛刻，就好像系统确实检索了它们一样，不应该受到惩罚。因此，所有需要做的就是（在每个查询的基础上）忽略垃圾并将它们视为不存在。因此，您获取检索到的列表，过滤掉此查询的所有垃圾图像，然后运行在这个过滤后的列表上进行正常的 AP 计算。这就是代码有效地做的事情——当示例在 amb(=junk) 中时，它只是被跳过。然后，如果示例不在 amb 中，如果它在 pos(itives) 中，则 intersect_size（直到位置 i 的当前正数）递增。数量 j（好吧，j-1）是列表中未跳过的元素的数量（仅当当前元素不是垃圾时才会递增）。

AP计算

正如 shiri 在上一个答案中所解释的那样，您当然需要在 AP 计算中进行召回，并且如您的文章所述，p(r) 是特定召回的精度。考虑 AP 的最佳方式不是检查随机公式，而是了解直觉是什么，然后查看公式如何捕捉它，即维基百科开头所说的内容：您可以将精度绘制为召回率的函数，而 AP就是曲线下的面积。您希望所有召回的精确度都很高，因此理想曲线是 p(r)=1，这将使 AP 最大化。

那么代码在做什么？它使用梯形规则计算精确召回曲线下的面积，请参阅 this equation on Wikipedia and you'll see it's identical to the code. The AP computation for the discrete case from your Wikipedia article is a (commonly used) worse approximation to the area under the precision-recall curve, the rectangle method。

平均精度的正确版本是什么？

What is the correct version of Average precision?

information-retrieval

precision-recall

垃圾集

AP计算