Ranking Metrics: NDCG@k, MRR and MAP@k

MediumML Coding

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_k divided by the ideal DCG, the DCG of the same relevances sorted in descending order. Return 0.0 if the ideal is 0. Round to 4 decimals.

mrr(ranked_lists)

  • ranked_lists is a list of relevance lists, one per query. For each query take 1 / (position of the first relevant item) with positions starting at 1, or 0 if 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; 0 if $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