MAP @ k计算

Question

根据wiki，ml metrics at kaggle和k答案得出的平均精度为k（对于答案中的前k个元素）计算的平均精度：Confusion about (Mean) Average Precision应计算为k处的平均精度的平均值，其中k处的平均精度计算如下：

其中：P（i）是列表中的截止精度i;如果等级i的项目是相关文档，则rel（i）是等于1的指示符函数，否则为零。

分隔符min(k, number of relevant documents)具有答案中最大可能相关条目数的含义。

这种理解是否正确？

MAP @ k是否总是小于为所有排名列表计算的MAP？

我担心的是，这不是MAP @ k在许多工作中的计算方式。

通常情况下，分隔符不是min(k, number of relevant documents)，而是top-k中相对文档的数量。这种方法将提供更高的MAP @ k值。

---

HashNet: Deep Learning to Hash by Continuation" (ICCV 2017)

代码：https://github.com/thuml/HashNet/blob/master/pytorch/src/test.py#L42-L51

    for i in range(query_num):
        label = validation_labels[i, :]
        label[label == 0] = -1
        idx = ids[:, i]
        imatch = np.sum(database_labels[idx[0:R], :] == label, axis=1) > 0
        relevant_num = np.sum(imatch)
        Lx = np.cumsum(imatch)
        Px = Lx.astype(float) / np.arange(1, R+1, 1)
        if relevant_num != 0:
            APx.append(np.sum(Px * imatch) / relevant_num)

其中relevant_num不是min(k, number of relevant documents)，而是结果中相关文件的数量，这与相关文件或k的总数不同。

我读错了代码吗？

---

Deep Visual-Semantic Quantization of Efficient Image Retrieval CVPR 2017

代码：https://github.com/caoyue10/cvpr17-dvsq/blob/master/util.py#L155-L178

def get_mAPs_by_feature(self, database, query):
    ips = np.dot(query.output, database.output.T)
    #norms = np.sqrt(np.dot(np.reshape(np.sum(query.output ** 2, 1), [query.n_samples, 1]), np.reshape(np.sum(database.output ** 2, 1), [1, database.n_samples])))
    #self.all_rel = ips / norms
    self.all_rel = ips
    ids = np.argsort(-self.all_rel, 1)
    APx = []
    query_labels = query.label
    database_labels = database.label
    print "#calc mAPs# calculating mAPs"
    bar = ProgressBar(total=self.all_rel.shape[0])
    for i in xrange(self.all_rel.shape[0]):
        label = query_labels[i, :]
        label[label == 0] = -1
        idx = ids[i, :]
        imatch = np.sum(database_labels[idx[0: self.R], :] == label, 1) > 0
        rel = np.sum(imatch)
        Lx = np.cumsum(imatch)
        Px = Lx.astype(float) / np.arange(1, self.R+1, 1)
        if rel != 0:
            APx.append(np.sum(Px * imatch) / rel)
        bar.move()
    print "mAPs: ", np.mean(np.array(APx))
    return np.mean(np.array(APx))

其中分隔符是rel，其计算为np.sum(imatch)，其中imatch是一个二进制向量，指示条目是否相关。问题是它只需要第一个R：imatch = np.sum(database_labels[idx[0: self.R], :] == label, 1) > 0。因此，np.sum(imatch)将在返回的大小R列表中提供相关条目的数量，但不是min(R, number of relevant entries)。请注意，论文中使用的R值小于DB中的条目数。

---

Deep Learning of Binary Hash Codes for Fast Image Retrieval (CVPR 2015)

代码：https://github.com/kevinlin311tw/caffe-cvprw15/blob/master/analysis/precision.m#L30-L55

    buffer_yes = zeros(K,1);
    buffer_total = zeros(K,1);
    total_relevant = 0;

    for j = 1:K
        retrieval_label = trn_label(y2(j));

        if (query_label==retrieval_label)
            buffer_yes(j,1) = 1;
            total_relevant = total_relevant + 1;
        end
        buffer_total(j,1) = 1;
    end

    % compute precision
    P = cumsum(buffer_yes) ./ Ns';

    if (sum(buffer_yes) == 0)
        AP(i) = 0;
    else
        AP(i) = sum(P.*buffer_yes) / sum(buffer_yes);
    end

这里的分隔符是sum(buffer_yes)，它是返回的大小为k的列表中的相对文档的编号，而不是min(k, number of relevant documents)。

---

"Supervised Learning of Semantics-Preserving Deep Hashing" (TPAMI 2017)

代码：https://github.com/kevinlin311tw/Caffe-DeepBinaryCode/blob/master/analysis/precision.m

代码与前一篇文章中的相同。

---

Learning Compact Binary Descriptors with Unsupervised Deep Neural Networks (CVPR 2016)

相同的代码：https://github.com/kevinlin311tw/cvpr16-deepbit/blob/master/analysis/precision.m#L32-L55

---

---

我错过了什么吗？以上论文中的代码是否正确？为什么它与https://github.com/benhamner/Metrics/blob/master/Python/ml_metrics/average_precision.py#L25-L39不一致？

---

Update

我发现这个封闭的问题，引用了同样的问题：https://github.com/thuml/HashNet/issues/2

声称以下声明是否正确？

AP是排名指标。如果排名列表中的前2个检索是相关的（并且只有前2个），则AP是100％。你在谈论Recall，在这种情况下确实是0.2％。

根据我的理解，如果我们将AP视为PR曲线下的区域，则上述声明是不正确的。

---

附：我怀疑这应该是Cross Validated还是StackOverflow。如果您认为最好将其置于Cross Validated我不介意。我的理由是它不是一个理论问题，而是参考实际代码实现一个。

Answer 1

找到这个你是完全正确的。鉴于代码的相似性，我的猜测是有一个源bug，然后论文复制了糟糕的实现而没有仔细检查。

“akturtle”问题提升者也是完全正确的，我打算给出相同的例子。我不确定“kunhe”是否理解这个论点，当然回想起计算平均精度时的问题。

是的，这个bug会使数字膨胀。我只希望排名列表足够长，并且方法足够合理，以便在排名列表中实现100％的召回，在这种情况下，错误不会影响结果。

不幸的是，审稿人很难抓住这一点，因为通常不会审查论文代码。值得联系作者试图让他们更新代码，用正确的数字更新他们的论文，或者至少不要继续犯错误在他们未来的作品中。如果您打算撰写一篇比较不同方法的论文，您可以指出问题并报告正确的数字（以及可能带有错误的那些只是为苹果比较制作苹果）。

回答你的问题：

MAP @ k是否总是小于为所有排名列表计算的MAP？

不一定，MAP @ k本质上是计算MAP，同时针对潜在的情况进行标准化，在这种情况下，只有k次检索才能做得更好。例如。考虑具有相关性的返回排序列表：1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1并假设总共有6个相关文档。这里的MAP应该略高于50％，而MAP @ 3 = 100％，因为你无法做到比检索11 1更好。但这与你发现的错误无关，因为他们的错误MAP @ k得到保证至少与真正的MAP @ k一样大。