# Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved
import numpy as np
# AP routine of the Holidays and INSTRE package
# Credits: Matthijs Douze
[docs]def score_ap_from_ranks_1(ranks, nres):
"""
Compute the average precision of one search.
Args:
ranks: ordered list of ranks of true positives
nres: total number of positives in dataset
Returns:
ap (float): the average precision following the Holidays and the INSTRE package
"""
# accumulate trapezoids in PR-plot
ap = 0.0
# All have an x-size of:
recall_step = 1.0 / nres
for ntp, rank in enumerate(ranks):
# y-size on left side of trapezoid:
# ntp = nb of true positives so far, rank = nb of retrieved items so far
if rank == 0:
precision_0 = 1.0
else:
precision_0 = ntp / float(rank)
# y-size on right side of trapezoid: ntp and rank are increased by one
precision_1 = (ntp + 1) / float(rank + 1)
ap += (precision_1 + precision_0) * recall_step / 2.0
return ap
# Credits: https://github.com/filipradenovic/revisitop/blob/master/python/evaluate.py
[docs]def compute_ap(ranks, nres):
"""
Computes average precision for given ranked indexes.
Args:
ranks: zero-based ranks of positive images
nres: number of positive images
Returns:
ap (float): average precision
"""
# number of images ranked by the system
nimgranks = len(ranks)
# accumulate trapezoids in PR-plot
ap = 0
recall_step = 1.0 / nres
for j in np.arange(nimgranks):
rank = ranks[j]
if rank == 0:
precision_0 = 1.0
else:
precision_0 = float(j) / rank
precision_1 = float(j + 1) / (rank + 1)
ap += (precision_0 + precision_1) * recall_step / 2.0
return ap
# Credits: https://github.com/filipradenovic/revisitop/blob/master/python/evaluate.py
[docs]def compute_map(ranks, gnd, kappas):
"""
Computes the mAP for a given set of returned results.
Credits:
https://github.com/filipradenovic/revisitop/blob/master/python/evaluate.py
Usage:
map = compute_map (ranks, gnd)
computes mean average precsion (map) only
map, aps, pr, prs = compute_map (ranks, gnd, kappas)
-> computes mean average precision (map), average precision (aps) for
each query
-> computes mean precision at kappas (pr), precision at kappas (prs) for
each query
Notes:
1) ranks starts from 0, ranks.shape = db_size X #queries
2) The junk results (e.g., the query itself) should be declared in the gnd
stuct array
3) If there are no positive images for some query, that query is excluded
from the evaluation
"""
map = 0.0
nq = len(gnd) # number of queries
aps = np.zeros(nq)
pr = np.zeros(len(kappas))
prs = np.zeros((nq, len(kappas)))
nempty = 0
for i in np.arange(nq):
qgnd = np.array(gnd[i]["ok"])
# no positive images, skip from the average
if qgnd.shape[0] == 0:
aps[i] = float("nan")
prs[i, :] = float("nan")
nempty += 1
continue
try:
qgndj = np.array(gnd[i]["junk"])
except Exception:
qgndj = np.empty(0)
# sorted positions of positive and junk images (0 based)
pos = np.arange(ranks.shape[0])[np.in1d(ranks[:, i], qgnd)]
junk = np.arange(ranks.shape[0])[np.in1d(ranks[:, i], qgndj)]
k = 0
ij = 0
if len(junk):
# decrease positions of positives based on the number of
# junk images appearing before them
ip = 0
while ip < len(pos):
while ij < len(junk) and pos[ip] > junk[ij]:
k += 1
ij += 1
pos[ip] = pos[ip] - k
ip += 1
# compute ap
ap = compute_ap(pos, len(qgnd))
map = map + ap
aps[i] = ap
# compute precision @ k
pos += 1 # get it to 1-based
for j in np.arange(len(kappas)):
kq = min(max(pos), kappas[j])
prs[i, j] = (pos <= kq).sum() / kq
pr = pr + prs[i, :]
map = map / (nq - nempty)
pr = pr / (nq - nempty)
return map, aps, pr, prs