MAP@k计算
MAP@k computation
在 k 处计算的平均平均精度（对于答案中的前 k 个元素），根据 wiki, ml metrics at kaggle, and this answer: 应计算为 k 处的平均精度平均值，其中 k 处的平均精度计算为：
其中：P(i)是列表中截断点i处的精度； rel(i) 是一个指标函数，如果排名 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[=119不相同=].
我是不是看错代码了？
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 不一致？
更新
我发现了这个已关闭的问题，指的是同样的问题：https://github.com/thuml/HashNet/issues/2
以下说法正确吗？
AP is a ranking metric. If the top 2 retrievals in the ranked list are relevant (and only the top 2), AP is 100%. You're talking about Recall, which in this case is indeed 0.2%.
根据我的理解，如果我们将 AP 视为 PR 曲线下的面积，则上述说法是不正确的。
P.S。我怀疑这是否应该转到 Cross Validated 或 Whosebug。如果您认为将它放在交叉验证中更好，我不介意。我的推理是，这不是理论问题，而是参考实际代码实现的问题。
你找到这个是完全正确的，做得很好。鉴于代码的相似性，我的猜测是存在一个源错误，然后一篇又一篇论文在没有仔细检查的情况下复制了错误的实现。
"akturtle" 问题提出者也完全正确，我将举同样的例子。我不确定 "kunhe" 是否理解这个论点，当然在计算平均精度时召回很重要。
是的，错误应该会使数字膨胀。只希望排行榜够长，方法够合理，能在排行榜中达到100%的召回率，这样bug就不会影响结果了。
不幸的是，审稿人很难发现这一点，因为通常审稿人不会审阅论文代码。值得联系作者，让他们更新代码，用正确的编号更新他们的论文，或者至少不要不要在他们以后的作品中继续犯错误。如果您打算写一篇比较不同方法的论文，您可以指出问题并报告正确的数字（以及可能有错误的数字，只是为了比较不同的方法）。
回答你的附带问题：
Is MAP@k always less than MAP computed for all ranked list?
不一定，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%，因为您不能比检索 1 1 1 做得更好。
但这与您发现的错误无关，因为他们的错误保证 MAP@k 至少与真实 MAP@k 一样大。
在 k 处计算的平均平均精度（对于答案中的前 k 个元素），根据 wiki, ml metrics at kaggle, and this answer:
其中：P(i)是列表中截断点i处的精度； rel(i) 是一个指标函数，如果排名 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[=119不相同=].
我是不是看错代码了？
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 不一致？
更新
我发现了这个已关闭的问题，指的是同样的问题：https://github.com/thuml/HashNet/issues/2
以下说法正确吗？
AP is a ranking metric. If the top 2 retrievals in the ranked list are relevant (and only the top 2), AP is 100%. You're talking about Recall, which in this case is indeed 0.2%.
根据我的理解，如果我们将 AP 视为 PR 曲线下的面积，则上述说法是不正确的。
P.S。我怀疑这是否应该转到 Cross Validated 或 Whosebug。如果您认为将它放在交叉验证中更好，我不介意。我的推理是，这不是理论问题，而是参考实际代码实现的问题。
你找到这个是完全正确的，做得很好。鉴于代码的相似性，我的猜测是存在一个源错误，然后一篇又一篇论文在没有仔细检查的情况下复制了错误的实现。
"akturtle" 问题提出者也完全正确，我将举同样的例子。我不确定 "kunhe" 是否理解这个论点，当然在计算平均精度时召回很重要。
是的，错误应该会使数字膨胀。只希望排行榜够长，方法够合理，能在排行榜中达到100%的召回率，这样bug就不会影响结果了。
不幸的是，审稿人很难发现这一点，因为通常审稿人不会审阅论文代码。值得联系作者，让他们更新代码，用正确的编号更新他们的论文，或者至少不要不要在他们以后的作品中继续犯错误。如果您打算写一篇比较不同方法的论文，您可以指出问题并报告正确的数字（以及可能有错误的数字，只是为了比较不同的方法）。
回答你的附带问题：
Is MAP@k always less than MAP computed for all ranked list?
不一定，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%，因为您不能比检索 1 1 1 做得更好。 但这与您发现的错误无关，因为他们的错误保证 MAP@k 至少与真实 MAP@k 一样大。