Ranking Metrics: NDCG@k, MRR and MAP@k
Problem statement
A recommender or search system returns an ordered list, and its quality depends on where the relevant items land. Implement the three metrics every ranking design discussion turns on. Relevance lists give the relevance of the item at each rank, top first; an item is relevant when its relevance is greater than 0.
dcg_at_k(rels, k)
- Discounted cumulative gain with linear gain: $\sum_{i=0}^{\min(k, n) - 1} \dfrac{\text{rels}[i]}{\log_2(i + 2)}$. Return a float.
ndcg_at_k(rels, k)
dcg_at_kdivided by the ideal DCG, the DCG of the same relevances sorted in descending order. Return0.0if the ideal is0. Round to 4 decimals.
mrr(ranked_lists)
ranked_listsis a list of relevance lists, one per query. For each query take1 / (position of the first relevant item)with positions starting at 1, or0if nothing is relevant; return the mean rounded to 4 decimals.
map_at_k(ranked_lists, k)
- For each query, average precision at
k: $\dfrac{1}{\min(k, R)} \sum_{i=1}^{\min(k, n)} P@i \cdot \mathbb{1}[\text{rel}_i > 0]$ where $P@i$ is the fraction of relevant items among the first $i$, and $R$ is the number of relevant items in the whole list;0if $R = 0$. Return the mean rounded to 4 decimals.
Example
Input:
rels = [0, 3, 1], k = 3
Output:
dcg_at_k = 2.3928, ideal DCG = 3.6309, ndcg_at_k = 0.659
Reasoning: the gains are $0/1 + 3/\log_2 3 + 1/\log_2 4 = 2.3928$. The ideal order [3, 1, 0] scores $3 + 1/\log_2 3 = 3.6309$, and $2.3928 / 3.6309 = 0.659$.
Show hint
For each metric, ask what it rewards: graded gains with a gentle position discount, the position of the first hit, or precision at every hit.
Relevant roles: ML Engineer, Data Scientist, Applied Scientist and Research Scientist.
Related free problems
- Choosing the Offline Metric for Candidate GenerationML System DesignMedium
- Multi-Head AttentionMedium
- Masked Self-AttentionMedium