Ranking metrics

Definitions#

For user $u$ with relevance labels $\mathrm{rel}(u, i) \ge 0$ and a ranked list $\pi_u$ where $\pi_u(j)$ is the item at position $j$:

Precision and recall at $k$:

$$ P@k = \frac{1}{k}\sum_{j=1}^{k} \mathbb{1}[\mathrm{rel}(u, \pi_u(j)) > 0], \qquad R@k = \frac{\sum_{j=1}^{k} \mathbb{1}[\mathrm{rel}(u,\pi_u(j)) > 0]}{|{i : \mathrm{rel}(u,i) > 0}|} $$

Average precision, with $R_u$ the relevant set:

$$ AP@k = \frac{1}{|R_u|}\sum_{j=1}^{k} P@j \cdot \mathbb{1}[\pi_u(j) \in R_u] $$

MAP is $AP$ averaged over users. It approximates the area under the precision-recall curve.

Discounted cumulative gain, in the exponential-gain form standard since Burges et al. (2005):

$$ DCG@k = \sum_{j=1}^{k} \frac{2^{\mathrm{rel}(u, \pi_u(j))} - 1}{\log_2(j + 1)}, \qquad nDCG@k = \frac{DCG@k}{IDCG@k} $$

$IDCG@k$ is $DCG@k$ evaluated on the relevance-sorted ideal permutation. With binary relevance, $2^1 - 1 = 1$ and the exponential form collapses to the linear one used in the code above.

The $1/\log_2(j+1)$ discount is a modelling choice, not a derivation. Järvelin and Kekäläinen (2002) introduced it as a smooth, slowly decaying weight. Rank-biased precision (Moffat and Zobel, 2008) replaces it with a geometric discount $p^{j-1}$ derived from an explicit user model — the probability the user continues to the next item — which makes the assumption inspectable and tunable.

The metric is a user model#

Every ranking metric encodes an assumption about how the list is consumed.

Choosing a metric is choosing a user model. Report the one whose assumption matches your interface, and say which one you chose. A ranked feed with infinite scroll and a single-answer search box should not be evaluated the same way.

Sampled metrics are not order-preserving#

Evaluating against the full catalogue costs $O(|I|)$ per user. The widespread shortcut ranks each held-out positive against $m$ sampled negatives, usually $m = 100$.

Krichene and Rendle (2020), On Sampled Metrics for Item Recommendation, show this is not a benign approximation. The sampled metric is a non-linear, non-monotone function of the true metric, so two models can swap order between the sampled and exact evaluation. They demonstrate the inversion on real benchmarks and give corrected estimators that recover consistency.

The practical rule: compute exact metrics whenever the catalogue permits it, and when it does not, use their correction rather than the raw sampled value.

Offline bias, restated precisely#

Held-out interactions were generated under the logging policy $\pi_0$. The observed relevance label for $(u,i)$ exists only if $o_{ui} = 1$, and $P(o_{ui}=1)$ depends on $\pi_0$. The naive estimate of any of the metrics above is therefore an estimate of performance on the distribution the old system induced.

The inverse-propensity-weighted form for a position-dependent examination model $P(o = 1 \mid \text{rank } j) = \theta_j$:

$$ \widehat{\Delta}{\text{IPS}}(\pi) = \frac{1}{|D|}\sum{(u,i) \in D} \frac{\lambda!\left(\mathrm{rank}(i \mid \pi, u)\right)}{\theta_{\mathrm{rank}(i \mid \pi_0, u)}} $$

Where $\lambda(\cdot)$ is the metric's rank weight (for DCG, $\lambda(j) = 1/\log_2(j+1)$) and $\theta_j$ is the examination propensity at the position where the interaction was logged. Joachims, Swaminathan and Schnabel (2017) give the estimator and the propensity-estimation procedure via result randomisation.

Two conditions are unavoidable: propensities must be bounded away from zero, so the logging policy needs stochasticity; and impressions must have been logged, which is a decision made in the data pipeline long before evaluation.

Beyond accuracy#

Report at least one of each, or the accuracy number will flatter a degenerate system:

• Catalogue coverage: $|\bigcup_u \mathrm{top}_N(u)| / |I|$.
• Intra-list diversity: mean pairwise distance within a slate.
• Gini coefficient over item exposure counts — inequality of attention.
• Novelty: mean self-information $-\log_2 p(i)$ of recommended items, with $p(i)$ the item's popularity share.
• Serendipity: relevance conditioned on the item being unexpected relative to a popularity baseline.

Details and code are in diversity and filter bubbles.

Papers#

• Järvelin and Kekäläinen (2002), Cumulated Gain-Based Evaluation of IR Techniques, ACM TOIS — the DCG paper.
• Burges et al. (2005), Learning to Rank Using Gradient Descent, ICML — the exponential gain formulation.
• Moffat and Zobel (2008), Rank-Biased Precision for Measurement of Retrieval Effectiveness, ACM TOIS.
• Joachims, Swaminathan and Schnabel (2017), Unbiased Learning-to-Rank with Biased Feedback, WSDM — arxiv.org/abs/1608.04468
• Krichene and Rendle (2020), On Sampled Metrics for Item Recommendation, KDD.
• Cañamares and Castells (2020), On Target Item Sampling in Offline Recommender System Evaluation, RecSys.

What to learn next#

• A/B testing a recommender — the online estimator these offline ones approximate.
• Diversity and filter bubbles — beyond-accuracy measurement in detail.
• Two-tower retrieval models — where recall@k is the metric that governs the whole pipeline.