Mean Average Precision (MAP)

Background

MAP (Mean Average Precision) averages AP across queries - a standard reranker / detection eval. Where AP measures precision over recall thresholds within one query, MAP just takes the mean of AP across many queries.

Problem statement

Implement mean_average_precision(retrieved_per_query, gold_per_query). Both inputs are lists with one entry per query: retrieved is a ranked ID list, gold is the set of relevant IDs.

$$\text{MAP} \;=\; \frac{1}{Q}\sum_{q=1}^{Q} \text{AP}(q),\qquad \text{AP}(q) \;=\; \frac{1}{|G_q|}\sum_{k:\,r_k \in G_q} \text{precision}@k$$

Input

• retrieved_per_query - list of ranked ID sequences.
• gold_per_query - list of iterables of relevant IDs (treated as sets).

Output

• float in $[0, 1]$. Queries with empty gold are skipped (no contribution to the average).

Examples

Input:  retrieved=[["a","b","c"], ["x","y","z"]], gold=[{"a","c"}, {"y"}]
Output: AP(0) = (1/1 + 2/3) / 2 = 0.8333; AP(1) = 1/2; MAP = (0.8333 + 0.5)/2 ~ 0.6667

Constraints

• Lengths of the two lists must match. ValueError otherwise.
• Queries with empty gold are skipped; if all queries have empty gold, return $0.0$.

Notes

• vs MRR / NDCG. MRR cares only about the first hit; NDCG weights with positional discounts; MAP averages precision at every relevant-hit position.