8 Evaluation Metrics
A recommender is only as trustworthy as the number you grade it with, and the choice of metric encodes what you think “good” means. This chapter builds every metric you will meet from zero, each with the same promise: a one-line intuition, a tiny toy example you can check by hand, and, where the name explains the formula, why it carries that name. The ranking metrics of §4–§7 all run on one shared example, so you can see exactly how they differ on the same list. This chapter owns the metric definitions for the book: the later recommender chapters report its ranking metrics and point here.
What this chapter assumes: arithmetic and the base-2 logarithm (\(\log_2 x\) is the power you raise \(2\) to in order to get \(x\), so \(\log_2 8=3\) because \(2^3=8\); §7 repeats this where it is first used); the natural logarithm \(\ln\) is glossed where it first appears, in the LogLoss line below. §11 also leans on the chapter Probability & Statistics for Machine Learning: its paired \(t\)-test and confidence intervals (its §8) and its sigmoid (its §3), and each such use points back to it. Not assumed: any earlier knowledge of recommender systems, and any probability beyond those two borrowed tools.
1. The three questions a metric can answer
Bob has built a film recommender and tells Ann it is great. Great at what: guessing her star ratings, putting her favourites at the top of a short list, or not showing everyone the same blockbusters? Each question needs a different number, and this section sorts the numbers into three families.
The metrics fall into three families, one for each question:
- “How wrong are the predicted numbers?” — rating-error metrics such as the mean absolute error (MAE), the mean squared error (MSE) and the root mean squared error (RMSE), for when the model predicts a rating (★1–5). §2.
- “Is the ranked list any good?” — top-\(K\) ranking metrics such as Precision, Recall, Mean Reciprocal Rank (MRR) and Normalized Discounted Cumulative Gain (NDCG), for the real task: show a short ordered list — the top \(K\) items, for some list length \(K\) — and put the good items on top. §4–§9. This is what modern recommender-systems research actually reports (a claim from practice, not tested here; Datasets & Benchmarks §4 lists the protocols).
- “Is the list healthy beyond being accurate?” — beyond-accuracy metrics (coverage, diversity, novelty, serendipity), because a recommender that only shows blockbusters can look accurate and still be useless. §10.
Why “metric.” From Greek metron, “measure.” A metric measures how good the output is, and different metrics measure different goods, which is why you must pick the one that matches your goal (§13).
These three questions map onto recommendation’s fundamental tasks — and each task fixes not just a metric but a train/test split (which logged interactions the model may learn from — the training set — and which are hidden from it so they can grade it — the test set) and a full evaluation protocol (which has itself evolved; §11).
The whole picture is in the table below. On a first read, columns 1, 2 and 4 are enough (“metric@\(K\)” there, e.g. Recall@\(K\), means the metric computed on the top \(K\) items of the list only); the split and protocol columns use terms that §11 builds properly, and each is glossed in the lines below the table.
| Task | What it predicts | Train/test split | Headline metric(s) | Protocol shift |
|---|---|---|---|---|
| Rating prediction | a star value (1–5) | random split of the ratings, or \(k\)-fold | RMSE, MAE (§2) | stable |
| Top-\(K\) ranking | a ranked list of items | random split, leave-one-out (LOO) or global temporal split (varies — §11) | Recall@\(K\), NDCG@\(K\) (§4–§9), MRR | sampled \(\to\) full |
| Next-item / sequential | the next item in a session | leave-one-out (each user’s last item) | HR@10 (Hit Rate in the top 10, §4), NDCG@10, MRR | sampled \(\to\) full |
| Click-through rate (CTR) prediction (the ranking stage) | a click probability | random split of the impressions | area under the curve (AUC) (§8), LogLoss | stable |
The split mechanics (\(k\)-core filtering, which repeatedly drops users and items with fewer than \(k\) interactions; random versus time-based splits; a worked leave-one-out example) are owned by Datasets & Benchmarks §3, and the benchmark map there (§4) says which model is run on which dataset under which protocol. The protocol depth (ranking against the full catalog versus a sample, online A/B tests, which are live experiments that split real users between two systems, A and B, and significance) is §11, and the “protocol shift” column is the old-to-modern change spelled out there.
The table’s terms, one line each (§11 and the chapters named here build most of them properly; \(k\)-fold is built in Probability & Statistics for Machine Learning §8):
- Random split / leave-one-out (LOO) / global temporal split — hide a random fraction of the interactions / hide each user’s chronologically last interaction / hide everything logged after one cut-off date (§11a).
- \(k\)-fold — split the ratings into \(k\) equal parts, test on each part in turn while training on the other \(k-1\), and average the \(k\) scores.
- AUC — the “curve” is the receiver operating characteristic (ROC) curve; the area under it is the chance that the model scores a random relevant item above a random irrelevant one (§8).
- Sampled \(\to\) full — the held-out item used to be ranked against about \(100\) randomly sampled items; modern work ranks it against the full catalog (§11b).
- CTR — click-through rate, the chance that a shown item is clicked; an impression is one showing of an item to a user. CTR models do the ranking stage of a real system: after a cheap retrieval step has shortlisted a few hundred items from the whole catalog, a richer model orders that shortlist precisely (Training and Serving a Recommender §8).
- LogLoss — log loss, also called binary cross-entropy: the average of \(-\log\)(the probability the model gave to what actually happened), so a confident wrong guess costs the most (Loss Functions & Regularizers §2.2). Here \(\ln x\) is the natural logarithm (the ln key on a calculator); \(\ln\) of a number below \(1\) is negative, so the minus sign makes each cost positive. Toy: one clicked item scored \(0.9\) and one unclicked item scored \(0.2\) (so \(0.8\) given to “no click”) cost \(-(\ln 0.9+\ln 0.8)/2=0.164\) on average; had the clicked item been scored \(0.01\), that one item alone would cost \(-\ln 0.01=4.61\).
Two broader references on evaluating recommenders: Herlocker et al. (2004), the classic survey of how to evaluate collaborative filtering, and the handbook of Ricci et al. (2022).
In one line: three questions, three families (rating error, ranking quality, list health), and even within the ranking family one list scores anywhere from \(0.442\) to \(1.0\) (§9). The rest of the chapter scores one running list of five films (three hits) in the ranking family (§3–§9), and gives each other family a small toy of its own (§2 four films, §10 five small toys, §11–§12 their own toy numbers).
2. Rating-error metrics: MAE, MSE, RMSE
A film site predicts Ann’s star ratings for four films: it says 4, 2, 5 and 3, and she then rates them 5, 2, 3 and 3. How wrong was the site, as one number? This section gives three answers and shows where they disagree.
When a model predicts a number (a rating), grade it by how far the prediction is from the truth. For each of the \(n\) rated items \(i\), write \(\hat r_i\) for the predicted rating (the hat marks a prediction), \(r_i\) for the true one, and the error \(e_i=\hat r_i-r_i\) (predicted minus actual). Then \[ \text{MAE}=\frac{1}{n}\sum_{i=1}^{n}|e_i|,\qquad \text{MSE}=\frac{1}{n}\sum_{i=1}^{n}e_i^{2},\qquad \text{RMSE}=\sqrt{\text{MSE}}, \] where \(\sum_{i=1}^{n}\) adds up the terms for \(i=1,2,\dots,n\) and the bars in \(|e_i|\) drop the sign. Toy (\(n=4\)): predictions \([4,2,5,3]\) vs. actual \([5,2,3,3]\) → errors \([-1,0,2,0]\).
- MAE — Mean Absolute Error. Average of the absolute errors. “On average, how many stars off am I?” \[\text{MAE}=\tfrac{|{-1}|+|0|+|2|+|0|}{4}=\tfrac{3}{4}=0.75.\]
- MSE — Mean Squared Error. Average of squared errors (the regression loss, Loss Functions & Regularizers §2.1). \[\text{MSE}=\tfrac{1+0+4+0}{4}=1.25.\]
- RMSE — Root Mean Squared Error. Square-root of MSE, to put it back in the original units (stars, not stars²). \[\text{RMSE}=\sqrt{1.25}=1.118.\]
Why the names, and RMSE vs MAE. The names are literal recipes read inside-out: (Root) (Mean) (Squared) Error. Squaring punishes big misses harder, so \(\text{RMSE}\ (1.118) > \text{MAE}\ (0.75)\) here — the single error of \(2\) dominates RMSE. Use RMSE when large mistakes are especially bad; MAE when every star of error is equally bad (and you want robustness to outliers). Low, middle and high: errors \([1,1,1,1]\) give MAE \(1\) and RMSE \(1\); errors \([0,0,0,4]\) (the same total of \(4\) stars, all in one miss) give MAE \(1\) but RMSE \(\sqrt{16/4}=2\); and misses of \(1\), \(2\) and \(3\) stars cost \(1\), \(4\) and \(9\) once squared.
In one line: MAE is the plain average miss (\(0.75\) stars on the toy); RMSE squares each miss first, so the single \(2\)-star miss lifts it to \(1.118\).
3. The ranking setup — one running example
Ann’s page shows five films, labelled A to E, and four films exist that she would love (B, C, E and G). How good is that page? Before any score can answer, we must agree on which films count as success and how long the list is; this section fixes both on one list that §4 to §7 reuse.
Real recommenders output a ranked list, and we care whether relevant items (ones the user actually likes) sit near the top. The setup:
- Our user, Ann, whose truly-relevant items are \(\mathcal{R}=\{B,C,E,G\}\) — so \(|\mathcal{R}|=4\) (the bars \(|\cdot|\) count a set’s members). Where does \(\mathcal{R}\) come from? In practice it is the set of this user’s logged interactions that we deliberately hid from the model before training — the test set of §11a — so we can check whether the model would have found them.
- The recommender returns the top-\(K\) list (\(K=5\)): \(\;[\,A,\,B,\,C,\,D,\,E\,]\).
- Mark each position relevant (1) or not (0): \(\;[\,0,\,1,\,1,\,0,\,1\,]\) — hits at ranks 2, 3, 5; item \(G\) is relevant but missed (not in the top-5).
![The running example. The top-5 list [A,B,C,D,E] has relevant items (teal) at ranks 2, 3, 5; the fourth relevant item G falls outside the top-5 (missed).](../figs/recsys-metrics-1.svg)
Why “@K,” “relevant,” “hit.” “@\(K\)” = evaluated at the top \(K\) positions (users only see a short list, so only the top matters). A relevant item is one the user truly wants (the ground truth). A hit is a relevant item that made the list. Every metric in §4–§7 is computed from this one little list — that is the point: same list, different verdicts. (AUC in §8 needs item scores this list doesn’t carry, so it uses a small separate example.)
In one line: one running list (\(K=5\), hits at ranks \(2,3,5\), the fourth relevant item \(G\) missed) is scored by every metric of §4 to §7, so any difference between the scores is a difference in what each metric rewards.
4. Hit Rate, Precision@K, Recall@K, F1@K
Ann’s page of five films holds three of the four films she would love. Is that good? Two fair questions hide in it: how much of what was shown was good, and how much of the good stuff was shown? This section turns each into a number, and then into one number that balances them.
The four scores, each on the running list (each is one user’s score; the number a paper reports is its mean over the test users, as the mean reciprocal rank of §5 and the mean average precision of §6 are):
- Hit Rate (HR@K) — did we get at least one relevant item in the top-\(K\)? Here yes → \(\text{HR@5}=1\). (Averaged over users it becomes the fraction of users with \(\ge 1\) hit.) Blunt but useful when one good item is enough.
- Precision@K — of the \(K\) items I served, what fraction were relevant? \[\text{Precision@5}=\tfrac{\#\text{hits}}{K}=\tfrac{3}{5}=0.6.\]
- Recall@K — of all the relevant items, what fraction did I find in the top-\(K\)? \[\text{Recall@5}=\tfrac{\#\text{hits}}{|\mathcal{R}|}=\tfrac{3}{4}=0.75.\] (With more than \(K\) relevant items Recall@K cannot reach \(1\): its ceiling is \(K/|\mathcal{R}|\), so \(K=5\) and \(|\mathcal{R}|=8\) cap it at \(5/8=0.625\).)
- F1@K — one number balancing precision and recall: their harmonic mean, which is the reciprocal of the average of their reciprocals. (The reciprocal of a number \(x\) is \(1/x\): \(2\) becomes \(0.5\), and \(0.5\) becomes \(2\).) Writing \(P\) for Precision@5 and \(R\) for Recall@5 (not the relevant set \(\mathcal{R}\)): \[\text{F1@5}=\frac{1}{\tfrac12\left(\tfrac1P+\tfrac1R\right)}=\frac{2}{\tfrac1P+\tfrac1R} =\frac{2\,P\,R}{P+R}=\frac{2(0.6)(0.75)}{0.6+0.75}=0.667.\] (The third form comes from multiplying the top and bottom of the second by \(PR\).) Step by step on the reciprocals: \(\tfrac{1}{0.6}=1.667\) and \(\tfrac{1}{0.75}=1.333\) average to \(1.5\), and \(\tfrac{1}{1.5}=0.667\) — a little below the ordinary average \(0.675\) of \(0.6\) and \(0.75\).
![Precision@K and Recall@K as K grows from 1 to 5, on the running list [A,B,C,D,E] with R=B,C,E,G.](../figs/recsys-metrics-2.svg)
The intuition. Precision = “don’t waste the user’s attention” (everything I showed should be good); Recall = “don’t miss the good stuff” (find all of it). They trade off: show more items → recall can only stay or rise, while precision can go either way (in the figure above it runs \(0,0.5,0.667,0.5,0.6\)). F1 is a harmonic mean, so it stays low unless both are decent. (Concretely: if \(P=0.1,R=0.9\), the arithmetic mean flatters them at \(0.5\), but F1 \(=\frac{2(0.1)(0.9)}{0.1+0.9}=0.18\). It is low because the reciprocals are \(10\) and \(1.11\), the small \(P\)’s huge reciprocal dominates their average \(5.56\), and \(1/5.56=0.18\). The harmonic mean is not fooled by one strong half, which is why it is used.)
Why the names. Precision and recall come from information retrieval (IR), the field behind search engines (Manning et al., 2008, is the standard textbook): precision = exactness of what you returned, recall = how much of the relevant set you recalled (retrieved). F1 is one member of the F-measure family \(F_\beta=\dfrac{(1+\beta^2)\,P\,R}{\beta^2P+R}\), where the weight \(\beta\) says how many times more you care about recall than precision; \(\beta=1\) weighs them equally and gives back \(\dfrac{2PR}{P+R}\) — hence the “1” in F1.
They all ignore the order within the top-\(K\): a hit at rank 1 counts the same as a hit at rank 5. The next metrics fix that.
In one line: on the running list precision is \(3/5=0.6\), recall \(3/4=0.75\) and F1 \(0.667\), and all three stay the same wherever in the top \(5\) the three hits sit.
5. MRR — Mean Reciprocal Rank
Bob asks his phone for a song to play now. He listens to the first suggestion that is good and then stops. How far down the list did he have to go? This section turns that into one number per person and averages it over people.
MRR asks one thing: how high is the first relevant item? For one user, take the reciprocal \(1/\text{rank}\) of the first hit — that user’s reciprocal rank (RR) — then average RR over users.
In our list the first relevant item (\(B\)) is at rank 2, so for this user \[\text{RR}=\frac{1}{\text{rank of first hit}}=\frac{1}{2}=0.5.\]
(First hit at rank 1 → \(1.0\); rank 2 → \(0.5\); rank 3 → \(0.33\); rank 5 → \(0.2\); rank 10 → \(0.1\). It falls off fast near the top, which is the point, since moving the first hit from rank 1 to rank 2 costs \(0.5\) while moving it from rank 5 to rank 10 costs only \(0.1\).)
A user with no hit in the top-\(K\) gets \(\text{RR}=0\). Over a set \(U\) of test users (\(|U|\) of them, and \(\text{RR}_u\) the reciprocal rank of user \(u\)), \[\text{MRR}=\frac{1}{|U|}\sum_{u\in U}\text{RR}_u ,\] where \(\sum_{u\in U}\) adds one term for every user \(u\) in \(U\). For example, our user (\(\text{RR}=0.5\)), a second user whose first hit is at rank 4 (\(\text{RR}=0.25\)) and a third with no hit in the top-5 (\(\text{RR}=0\)) give \(\text{MRR}=\tfrac{0.5+0.25+0}{3}=0.25\).
Why “reciprocal rank,” and when to use it. Reciprocal = \(1/\text{rank}\) — so the earlier the first hit, the bigger the score. Use MRR when one good answer is enough and you want it fast: question-answering, “I’m feeling lucky” search, a single next-track suggestion. It ignores everything after the first hit.
In one line: MRR is the average over users of \(1/\text{rank of the first hit}\): \(0.5\) for our user, \(0.25\) for the three-user example, whatever sits below the first hit.
6. MAP — Mean Average Precision
Ann’s page finds three of her four favourites, at positions 2, 3 and 5. A rival page finds the same three at positions 1, 2 and 3. Which is better, and by how much? The score of the last section looks only at the first find; this section builds one that looks at every find.
(Not the MAP of Probability & Statistics for Machine Learning — maximum a posteriori estimation: same letters, an unrelated idea.)
Average Precision (AP) rewards getting every relevant item high, not just the first: compute Precision@\(k\) — the precision of the list cut off at rank \(k\) — at each rank \(k\) where a hit occurs, add them, and (by convention) divide by the number of relevant items. (Lower-case \(k\) is a position inside the list; capital \(K\) stays the list length.) MAP is AP averaged over the test users \(U\), exactly as MRR averages RR: \(\text{MAP}=\frac{1}{|U|}\sum_{u\in U}\text{AP}_u\), where a user with no hit in the top-\(K\) has \(\text{AP}_u=0\).
Our hits are at ranks 2, 3, 5 (writing P@\(k\) for Precision@\(k\)): \[ P@2=\tfrac{1}{2}=0.5,\quad P@3=\tfrac{2}{3}=0.667,\quad P@5=\tfrac{3}{5}=0.6, \] \[ \text{AP}=\frac{P@2+P@3+P@5}{|\mathcal{R}|}=\frac{0.5+0.667+0.6}{4}=0.442. \]
Now the rival page. Its hits sit at ranks 1, 2 and 3, so Precision@\(k\) is \(1\) at every one of them, and \[ \text{AP}_{\text{rival}}=\frac{1+1+1}{4}=0.75 . \] The rival is better, by \(0.75-0.442=0.308\): it finds the same three films but puts them all at the top, and it costs the same missed \(G\). MRR would see only the first find (\(0.5\) against \(1\)); AP also sees that the rival’s other two finds come early too.
Why “average precision,” and its character. It is literally the sum of Precision@\(k\) over the hit positions, divided by \(|\mathcal{R}|\). Because each hit is scored by the precision at that point, a relevant item buried low drags AP down — so MAP rewards pushing all relevant items up. (Convention note: dividing by \(|\mathcal{R}|=4\) charges you for the missed item \(G\); some implementations divide by the number of hits — always check which. Some divide by \(\min(K,|\mathcal{R}|)\) instead (a claim from practice, not tested here).)
In one line: AP adds the precision at each hit position and divides by the \(4\) relevant items: Ann’s page scores \(0.442\), the rival that finds the same three at positions 1 to 3 scores \(0.75\) (better by \(0.308\)), and dividing Ann’s by the \(3\) hits would give \(0.589\), so the missed \(G\) costs real score.
7. NDCG — Normalized Discounted Cumulative Gain (the gold standard)
Two pages find the same film Ann loves, one at the top of the page and one near the bottom, and she loves some films more than others. A fair score should pay more for a high position and more for a bigger favourite. This section builds such a score one idea at a time.
NDCG (introduced by Järvelin & Kekäläinen, 2002; the exponential gain \(2^{\text{rel}}-1\) used below is a common variant, and some papers use the raw grade) is the most-reported ranking metric (a claim from practice, not tested here), because it handles three things at once: graded relevance (not just 0/1), position (high ranks worth more), and comparability across users. (“Gold standard” in the heading means the default most papers report — not the best metric for every goal: §13 shows there is no single best one.) Build it up one word at a time:
Gain — the reward for the item shown at rank position \(i\) (here \(i\) counts positions down the list, \(i=1\) at the top — not items). Each position carries a relevance label \(\text{rel}_i\): binary \(0/1\) in our running example, or a grade such as \(0\)–\(3\) (below). The label becomes a gain through \(\text{gain}_i=2^{\text{rel}_i}-1\); for binary labels this is just the label itself (\(2^0-1=0\), \(2^1-1=1\)), so the binary example can use the \(0/1\) labels directly.
Cumulative Gain — sum the gains down the list (\(0+1+1+0+1=3\) on the running list).
Discounted — divide each gain by \(\log_2(i+1)\) so lower ranks count less. (\(\log_2 x\) is the power you raise \(2\) to in order to get \(x\), e.g. \(\log_2 4=2\); on a calculator, \(\log_2 x=\ln x/\ln 2\) with the natural-log key ln — or the same ratio with the base-10 log key — e.g. \(\log_2 3=1.585\).) A hit at rank 2 is worth more than one at rank 5; the \(+1\) makes rank 1’s divisor \(\log_2 2 = 1\) — no discount.
A logarithm falls off gently, gentler than \(1/i\): at ranks \(2\), \(4\) and \(8\) the discount is \(0.63\), \(0.43\) and \(0.32\), against \(0.5\), \(0.25\) and \(0.125\) for \(1/i\), so items deep in the list still differ slightly rather than being crushed. Summing the discounted gains gives the Discounted Cumulative Gain (DCG); for our list, with all five terms written out: \[ \begin{aligned} \text{DCG@5}&=\sum_{i=1}^{5}\frac{\text{gain}_i}{\log_2(i+1)} =\frac{0}{\log_2 2}+\frac{1}{\log_2 3}+\frac{1}{\log_2 4}+\frac{0}{\log_2 5}+\frac{1}{\log_2 6}\\[4pt] &=0+0.631+0.5+0+0.387=1.518. \end{aligned} \]
Normalized — divide by the Ideal DCG (IDCG), the DCG of the best possible ordering (all 4 relevant items at the top; a user with more than \(K\) relevant items fills all \(K\) places), so the score lands in \([0,1]\) and is comparable across users with different numbers of relevant items: \[ \text{IDCG@5}=\frac{1}{\log_2 2}+\frac{1}{\log_2 3}+\frac{1}{\log_2 4}+\frac{1}{\log_2 5} =1+0.631+0.5+0.431=2.562, \] \[ \boxed{\text{NDCG@5}=\frac{\text{DCG}}{\text{IDCG}}=\frac{1.518}{2.562}=0.593.} \]
The top-versus-bottom comparison of the opener: one relevant film at rank \(1\) adds \(1/\log_2 2=1\) to the DCG, the same film at rank \(6\) adds \(1/\log_2 7=0.356\). With that film the only relevant one, the IDCG is \(1\), so NDCG@10 (a list of \(10\) items) is \(1.0\) against \(0.356\).
Graded NDCG — a mini-example. NDCG is not limited to binary 0/1 relevance; it handles graded labels, e.g. \(0\) = irrelevant, \(1\) = fair, \(2\) = good, \(3\) = excellent (star ratings are mapped onto such a scale before scoring). Now the gain rule \(\text{gain}_i=2^{\text{rel}_i}-1\) really matters: rel \(0\!\to\!0\), \(1\!\to\!1\), \(2\!\to\!3\), \(3\!\to\!7\), so a grade-3 item is worth \(7\times\) a grade-1 item (not \(3\times\)), rewarding lists that put the very best items first. Suppose a list of five items has relevances \(\text{rel}=[3,0,1,0,2]\) (ranks 1–5), i.e. gains \([7,0,1,0,3]\). Then: \[
\begin{aligned}
\text{DCG}&=7(1.000)+0(0.631)+1(0.500)+0(0.431)+3(0.387)\\[4pt]
&=7.000+0.000+0.500+0.000+1.161=8.661.
\end{aligned}
\] The ideal ordering places the highest gains first: \([7,3,1,0,0]\), giving \[
\text{IDCG}=7(1.000)+3(0.631)+1(0.500)+0+0=7.000+1.893+0.500=9.393,
\] \[
\text{NDCG}=\frac{8.661}{9.393}=0.922.
\] (Each gain is multiplied by its discount \(1/\log_2(i+1)\) at rank \(i\); e.g.
\(1/\log_2(2)=1.000\), \(1/\log_2(3)\approx0.631\), \(1/\log_2(6)\approx0.387\).)
Some papers instead use the label itself, \(\text{rel}_i\), as the gain for graded data; on this list that gives \(0.897\) rather than \(0.922\), so a paper should say which gain it uses. This book always uses \(2^{\text{rel}_i}-1\).
Why each word earns its place. Gain (relevance is a reward), Cumulative (sum down the list), Discounted (a log-discount for low ranks — diminishing attention), Normalized (÷ ideal → a \(0\)–\(1\) score, \(1\) = perfect order). Use NDCG when position and graded relevance matter — that is, whenever the list has an order and the items can differ in value. It is the usual companion of Recall in the graph-recommender literature (the benchmark map of Datasets & Benchmarks §4 lists Recall@20 and NDCG@20 for that family); §9 says which of this book’s chapters quote which.
In one line: NDCG@5 is the DCG divided by the ideal DCG, \(1.518/2.562=0.593\) for the running list, and \(0.922\) on the graded example, where a grade-3 item earns a gain of \(7\) and a grade-1 item \(1\).
8. AUC — Area Under the ROC Curve
Bob’s film site scores every film in its catalog, not just a short list. Cara loves two films and does not care for three. Pick one loved and one unloved film at random: how often does the site score the loved one higher? This section counts that, then draws the curve it leads to.
The answer is the AUC, a global ranking metric over all items: pick a random relevant item and a random irrelevant item — what’s the probability the model scores the relevant one higher (a tie counts as half a correct pair)? That probability is the area under the receiver operating characteristic (ROC) curve, which we build below. Unlike §4–§7, it needs each item’s score (the number the model ranks items by), not just their order in a top-\(K\) list.
Toy: relevant scores \(\{0.9, 0.6\}\), irrelevant scores \(\{0.7, 0.4, 0.3\}\). There are \(2\times3=6\) (relevant, irrelevant) pairs; check each one (✓ = the relevant item is scored higher, \(\times\) = it is not):
| relevant item’s score | vs. \(0.7\) | vs. \(0.4\) | vs. \(0.3\) |
|---|---|---|---|
| \(0.9\) | ✓ | ✓ | ✓ |
| \(0.6\) | \(\times\) | ✓ | ✓ |
The model orders 5 of the 6 pairs correctly (only \(0.6<0.7\) fails): \[ \text{AUC}=\frac{\#\text{correctly-ordered pairs}}{\#\text{pairs}}=\frac{5}{6}=0.833. \] \(0.5\) = random guessing; \(1.0\) = every relevant item above every irrelevant one.
Building the ROC curve. Pick a cut-off score — a threshold — and call every item scoring at or above it “recommended”. Two rates describe the result:
- the true-positive rate (TPR) — the share of the relevant items that are recommended (here out of 2);
- the false-positive rate (FPR) — the share of the irrelevant items that are recommended (here out of 3).
Now lower the threshold one item at a time, from above the top score down to the lowest:
| threshold (recommend if score \(\ge\)) | item it lets in | TPR | FPR |
|---|---|---|---|
| above \(0.9\) | none | \(0\) | \(0\) |
| \(0.9\) | relevant | \(1/2\) | \(0\) |
| \(0.7\) | irrelevant | \(1/2\) | \(1/3\) |
| \(0.6\) | relevant | \(1\) | \(1/3\) |
| \(0.4\) | irrelevant | \(1\) | \(2/3\) |
| \(0.3\) | irrelevant | \(1\) | \(1\) |
Each row is one point (FPR, TPR); joining them gives the ROC curve of the figure below: every relevant item lifts it up by \(\tfrac12\), every irrelevant one pushes it right by \(\tfrac13\).
Why the area equals the pair count. The up-steps have height \(\tfrac12\) (one per relevant item) and the right-steps width \(\tfrac13\) (one per irrelevant item), so the unit square splits into \(2\times3=6\) cells — one per (relevant, irrelevant) pair, the six cells of the pair table above. A cell lies under the curve exactly when the curve climbed for that relevant item before it stepped right for that irrelevant one — that is, when the relevant item scored higher. The area is \(\tfrac13\times\tfrac12+\tfrac23\times1=\tfrac16+\tfrac46=\tfrac56\): five cells, the five ✓ pairs.
Why “AUC / ROC.” AUC = Area Under the Curve; the curve is the ROC = Receiver Operating Characteristic — a term from signal-detection theory (Green & Swets, 1966): how well a receiver told signal from noise. The pairwise probability above equals that area, as the grid shows (Fawcett, 2006, is the standard tutorial on ROC analysis).
AUC is closely tied to Bayesian Personalized Ranking (BPR) (Loss Functions & Regularizers §9), a training loss built on the same (relevant, irrelevant) pairs: it rewards scoring each relevant item above an irrelevant one through a smooth stand-in for the 0/1 “ordered correctly?” count — the count itself only jumps, giving training no gradual signal to follow — so BPR pushes AUC up rather than maximizing it exactly.
In one line: with \(2\) relevant and \(3\) irrelevant items there are \(6\) pairs and the model orders \(5\) of them correctly, so AUC \(=5/6=0.833\); \(0.5\) is a coin flip and \(1.0\) is perfect.
9. All ranking metrics on the same list
The same five-film page has now been scored seven ways, and the answers run from 0.442 to 1.0. Is one of them wrong? This section puts them side by side to show that each answers a different question about the same list.
Every number below except AUC comes from the one list of §3 (\(\mathcal{R}=\{B,C,E,G\}\), top-5 \([A,B,C,D,E]\), hits at ranks 2,3,5); AUC needs item scores, so its row repeats §8’s separate toy for comparison. (With a single user, MRR is just that user’s RR and MAP is just its AP.) Seeing them together is the fastest way to feel the differences:
| Metric | Value | What it rewarded |
|---|---|---|
| Hit Rate@5 | \(1.0\) | got \(\ge 1\) relevant item |
| Precision@5 | \(0.60\) | 3 of 5 shown were good |
| Recall@5 | \(0.75\) | found 3 of 4 relevant |
| F1@5 | \(0.667\) | balance of the two |
| MRR | \(0.50\) | first hit was at rank 2 |
| MAP | \(0.442\) | all hits’ positions (penalizes missed \(G\)) |
| NDCG@5 | \(0.593\) | positions, normalized to the ideal |
| AUC | \(0.833\) | global pair-ordering (from §8’s scores) |
One recommendation, seven different verdicts (eight with AUC’s, from its own toy) — because each metric encodes a different definition of “good.” That is why §13 (choosing) matters.
What do typical values look like? Small, and not comparable across datasets. The real-data values that the three graph chapters (10 to 12) print are under \(0.2\) for Recall@20 and under \(0.16\) for NDCG@20 (as printed there at the time of writing). One example: LightGCN (a graph neural network recommender; From Graphs to LightGCN §12) scores \(0.1755\) to \(0.1830\) Recall@20 on Gowalla (a public dataset of check-ins at places) with \(1\) to \(4\) layers.
These are values reported there, not tested here. The same model gets \(0.0411\) on one Amazon-Book file (The Spectral / Graph-Filter View §4) and \(0.1411\) on another (Self-Supervised & Contrastive Learning §7), because the files differ (Datasets & Benchmarks §4), and none of the three chapters restates the ranking protocol, which Datasets & Benchmarks §4 gives (a random per-user split, where each user’s interactions are divided at random, and full ranking, where every held-out item is ranked against the whole catalog).
In one line: the same list scores from \(0.442\) (MAP) to \(1.0\) (hit rate); a number means something only next to its metric’s definition and its \(K\).
10. Beyond-accuracy metrics — because accuracy isn’t enough
Bob’s film site shows every user the same ten blockbusters. Its accuracy numbers look fine, yet nobody ever finds a small film and every page looks like the last. Which number would warn him? This section builds five such health checks.
A recommender that only suggests the blockbusters can score high on Recall or NDCG and still be a bad product: boring, repetitive, and blind to the catalog. Two ideas from earlier chapters name the trap: the popularity bias and the long tail, the many rarely-seen items that together make up most of a catalog (Traditional Recommender Systems §6; worked numerically in From Graphs to LightGCN §13). These metrics guard the health of the list:
- Coverage — what fraction of the catalog ever gets recommended? Toy: only 4 distinct items recommended across all users out of 10 → \(\text{coverage}=4/10=0.4\). Low coverage = the long tail is invisible.
- Diversity (intra-list) — how dissimilar are the items within one user’s list? Average pairwise \((1-\text{similarity})\). The similarity is the cosine similarity of two items’ feature vectors, \(1\) for the same direction and \(0\) for nothing in common when the features are never negative (Linear Algebra for Machine Learning §4). Toy (3 items, pairwise cosines \(0.5,0.0,0.5\)): \(\text{diversity}=\tfrac{0.5+1.0+0.5}{3}=0.667\). Low = “you watched one sci-fi, here are 10 more sci-fi.”
- Novelty — how non-obvious are the items? Often \(-\log_2\) of an item’s popularity, its share of users who saw it. Toy: an item seen by \(1\%\) of users → \(-\log_2(0.01)=6.64\) bits of novelty (a blockbuster seen by 50% → only \(1\) bit). A bit is the information in one fair coin flip: an event with probability \(\tfrac12\) carries \(1\) bit, and rarer events carry more.
- Serendipity — relevant and surprising: a good recommendation the user would not have found themselves (relevant minus what a popularity baseline — a simple recommender that shows everyone the same most-popular items — would have shown). The “delightful surprise” metric; hardest to measure, said to be most valued by users (a claim from practice, not tested here). As a formula (one simple form; papers define it differently): \[\text{serendipity@}K=\frac{\#\text{hits the popularity baseline would not have shown}}{K}.\] Toy: of our top-5 list’s \(3\) relevant hits, suppose \(2\) are items a popularity baseline would not have shown (genuinely surprising) and \(1\) is a blockbuster the baseline picks anyway; then \(\text{serendipity@5}=\tfrac{2}{5}=0.4\). (Note Precision@5 was \(0.6\) — it credited all \(3\) hits; serendipity discards the obvious one, crediting only the \(2\) non-obvious finds.)
- Gini coefficient / popularity bias — how concentrated recommendations are on a few popular items. Gini \(0\) means perfectly even across the catalog; the maximum, all traffic to one item, is \((n-1)/n\) for a catalog of \(n\) items (\(0.8\) for the \(5\) items below, approaching \(1\) as the catalog grows). High Gini = the rich-get-richer blockbuster trap. Toy: a \(5\)-item catalog is recommended with counts \([8,2,0,0,0]\) (\(10\) recommendations, mean \(\mu=2\)). The next three paragraphs compute its Gini twice and then give the verdict.
Gini by pairs. With \(x_i\) the recommendation count of item \(i\), \(n=5\) the number of items and \(\mu\) the mean count, \[ G=\frac{\sum_i\sum_j |x_i-x_j|}{2\,n^2\,\mu}. \] (Here \(G\) is the Gini coefficient, not the missed item \(G\) of §3.)
The double sum visits every ordered pair \((i,j)\), so each gap is counted twice, and an item paired with itself adds \(0\). The table lists each pair once.
| pair of items (their counts) | gap | number of such pairs | gap total |
|---|---|---|---|
| \(8\) and \(2\) | \(6\) | \(1\) | \(6\) |
| \(8\) and a \(0\) | \(8\) | \(3\) | \(24\) |
| \(2\) and a \(0\) | \(2\) | \(3\) | \(6\) |
| two \(0\)s | \(0\) | \(3\) | \(0\) |
| all pairs, once each | \(10\) | \(36\) |
Counting both orders doubles the total to \(72\), so \(G=\dfrac{72}{2\cdot 25\cdot 2}=\dfrac{72}{100}=0.72\). In words, \(G\) is the average absolute gap between two items’ counts (over all \(n^2\) ordered pairs, here \(72/25=2.88\)) divided by twice the mean (\(4\)): \(0\) when every count is equal and never above \((n-1)/n\). All \(10\) recommendations on one item, \([10,0,0,0,0]\), give \(80/100=0.8\).
Gini by the Lorenz curve (figure below). Sort the items from fewest to most recommended; the Lorenz curve plots, for each fraction of the catalog, what share of all recommendations that fraction holds. Perfect equality would be the straight diagonal. Region \(A\) is the gap between the diagonal and the curve, region \(B\) the area under the curve, and together they fill a triangle of area \(\tfrac12\). Then \(G=\tfrac{A}{A+B}\). Here \(B\) is two trapezoids, \(\tfrac12(0{+}0.2)(0.2)+\tfrac12(0.2{+}1)(0.2)=0.14\), so \(A=\tfrac12-0.14=0.36\) and \(G=\tfrac{0.36}{0.5}=0.72\), the same answer.
Verdict. At \(0.72\), \(90\%\) of the way to the \(0.8\) maximum for five items, this is a near-monopoly catalog: a red flag that an accuracy number such as Recall@\(K\) would never reveal.
![The Lorenz curve for the Gini toy (counts [8,2,0,0,0], sorted fewest first): the bottom 3 items hold 0% of recommendations, and the last two carry the curve up to 0.2 and then 1.0.](../figs/recsys-metrics-5.svg)
Why the names. Coverage = how much of the catalog you cover; diversity = variety; novelty (Latin novus, “new”) = newness/non-obviousness; serendipity (from the fairy tale The Three Princes of Serendip, whose heroes made happy discoveries by accident) = a fortunate surprise; the Gini coefficient is named after the statistician Corrado Gini, borrowed from economics (income inequality), and the Lorenz curve it is read from after the economist Max Lorenz.
In one line: a list can be accurate and unhealthy: the toy catalog with counts \([8,2,0,0,0]\) has Gini \(0.72\), \(90\%\) of the \(0.8\) maximum for five items, and no accuracy number would show it.
11. Evaluating honestly — the protocol behind the number
Bob says his new model beats the old one by 0.002 in its ranking score. Should Ann believe him? (The significance part below answers this exact case.) That depends on how the test was run. Five questions decide it: which films were hidden; what the hidden film was ranked against; whether real users agree; whether the gap is bigger than luck; and whether a score of 0.8 really means an 80% chance. This section goes through them one by one.
Every number above assumed a test set and, for AUC, the model’s scores were already in hand. How you produce them decides whether the metric means anything at all — a state-of-the-art NDCG on a sloppy protocol is worth less than a modest one measured correctly. Five lenses on a trustworthy number, each with a classic trap.
Before the lenses, the big picture: recommendation’s evaluation protocol changed sharply around 2019–2020, after a reproducibility study (Ferrari Dacrema et al., 2019), which found that several recent neural recommenders were beaten by simple, well-tuned baselines, and the sampled-metrics critique (Krichene & Rendle, 2020), which showed that sampled rankings can reverse which model looks better. The first appeared at the ACM Conference on Recommender Systems (RecSys), the second at the ACM Conference on Knowledge Discovery and Data Mining (KDD). The shift, dimension by dimension:
| Protocol choice | Old / legacy (common before ~2020) | Modern (state of the art) | Why (the lens) |
|---|---|---|---|
| Train/test split | random split (can train on the future) | time-aware within each user: leave-one-out (each user’s last item) or, strictest, a global temporal split | (a) don’t train on the future |
| Ranking candidates | item vs. ~100 sampled negatives | the full catalog | (b) sampling can reverse rankings |
| Reporting | one run, a point estimate | mean \(\pm\) standard deviation over random seeds, + a significance test | (d) is the gain real? |
| Baselines (the models a new one is compared against) | often under-tuned | tuned classical baselines (\(k\)-nearest-neighbor, matrix factorization — Traditional Recommender Systems §4–§5) | Ferrari Dacrema et al.; Datasets & Benchmarks §5 |
| Verdict | offline metric alone | offline filter + online A/B test | (c) offline is a proxy |
In the Reporting row, the standard deviation (std) is how far the runs typically spread around their average, and a random seed is the starting number of one run (§11d). The benchmark map of Datasets & Benchmarks §4 draws this old-versus-modern fork as a decision tree and pins each research regime to it, and the baselines row follows the reproducibility critique (Datasets & Benchmarks §5). The left column is earlier practice, not a verdict on every paper: the graph chapters of this book (2019–2023) use a random per-user split with full ranking, as §9 and §11f note.
11a. The train/test split — and the leakage trap
Ann’s model scores well on the films it was tested on, but did it train on clicks that, in real life, had not happened yet? How the test films are hidden decides that.
You hide some interactions as the test set and train on the rest. Three schemes plus the validation rule, which applies to all of them:
- Random split — hide a random fraction of the interactions (of each user’s, or of the whole log — a paper should say which). Simple, but it can leak the future into the past: you might train on a click that happened after a test click — something the live system could never do.
- Leave-one-out (LOO) — for each user, hide the chronologically last interaction (unless a paper says otherwise), sometimes also the second-last as a validation item (below), and rank it against the rest. It is leak-free within a user but not across users: one user’s held-out item may be older than another user’s training data. LOO is not a legacy scheme: it is still the standard split for next-item models — the sequential recommenders SASRec and BERT4Rec (two neural models that read a user’s history as a sequence, the second borrowing a language-model design; Sequential & Session-Based Recommendation §4–§5) — and it was the split of the Neural Collaborative Filtering (NCF) line of neural recommenders. What changed around 2020 is what the held-out item is ranked against (lens b).
- Global temporal split — one cut-off timestamp for everybody: train on everything before it, test on everything after. The most honest, because it mirrors deployment (predict the future from the past). Prefer it whenever timestamps exist.
- Validation set — whichever split you use, carve a third slice out of the training data to choose settings: hyper-parameters (settings fixed by hand before training, such as how long to train or how big the model is), when to stop training, and calibration maps (rescalings that make a score a trustworthy probability; lens e). The test set is touched once, at the very end; choosing anything by looking at test scores is itself leakage. Hence train / validation / test: learn on the first, choose on the second, report the third.
Toy for the three schemes and the validation rule. Ann’s log holds five films, watched on days 1 to 5. A random split might hide day 2: the model then trains on days 1, 3, 4 and 5, three of which came after the film it must predict. Leave-one-out hides day 5 and trains on days 1 to 4; with a validation item it also sets day 4 aside, so training stops at day 3, the validation set is day 4 and the test is day 5. A global temporal split with the cut after day 3 trains every user on days 1 to 3 and tests on days 4 and 5.
The trap to avoid is data leakage — any information from the test period seeping into training can inflate the metrics above and then evaporate in production (a claim from practice, not tested here, but Ji et al., 2023, measure it on real data; Datasets & Benchmarks §3 explains the time-aware splits).
In one line: hide each user’s last interaction (or cut by one timestamp), never train a user on anything later than that user’s test click, and choose settings on a validation slice, not on the test set.
11b. Full vs. sampled ranking — how sampling distorts the score
Bob ranks Ann’s held-out film against only \(100\) other films and reports a high score. Would the same model score as high against the whole catalog?
To compute Recall@K / NDCG@K you must rank the held-out relevant item among candidates. Two choices:
- Full ranking — rank it against the entire catalog of unseen items (often millions). Expensive but correct.
- Sampled ranking — rank it against the true item plus a handful (say \(100\)) of randomly sampled negatives (items the user never interacted with, treated as irrelevant). Cheap, and the common default before about 2020, as the table above says.
Worked: why sampling flatters. Take a catalog of \(10\) items in which the held-out item’s full rank is \(4\): three items score higher, so it is a miss for HR@3 (the hit rate of §4 at \(K=3\)). Now sample \(3\) negatives from the other \(9\) — say the items the full ranking puts at positions \(2\), \(7\) and \(9\). Only one of them (position \(2\)) outranks the held-out item, so among the \(4\) candidates it ranks 2nd: a sampled HR@3 hit. Whatever three are drawn, its sampled rank can never be worse than its full rank \(4\) — sampling only removes competitors — and it reaches \(4\) only if the sample is exactly the three items above it (a \(1\)-in-\(84\) chance).
The \(84\) comes from a counting rule: to choose \(3\) items from \(9\) you can pick them in order in \(9\times8\times7=504\) ways, but each set of three is then counted \(3\times2\times1=6\) times (once per order), so there are \(504/6=84\) different sets, and only one of them is the three items above it.
At real scale the effect is enormous: an item at full rank \(5{,}000\) in a \(1{,}000{,}000\)-item catalog is a clear HR@10 miss, but each of \(100\) random negatives outranks it with probability \(4{,}999/999{,}999\approx0.5\%\), so on average only \(100\times0.005=0.5\) of them do. Its sampled rank averages \(1.5\) and exceeds \(10\) only about once in nine billion draws — a sampled HR@10 hit.
A second model that puts the same item at full rank \(20{,}000\), four times further down, is also a full-ranking miss; but sampled, it has \(100\times0.02=2\) outrankers on average, a sampled rank of \(3\), and a sampled HR@10 miss only about once in \(29{,}000\) draws.
A third model that puts the item at full rank \(100{,}000\) has \(100\times0.1=10\) outrankers on average, a sampled rank near \(11\), and a sampled HR@10 miss in about \(55\%\) of draws. Across the three models the sampled miss rate goes from one in nine billion to one in \(29{,}000\) to about one in two, although the full ranks (\(5{,}000\), \(20{,}000\), \(100{,}000\)) are all clear misses and the first two are four times apart. Three models are enough to show the shape because each step moves the miss rate by orders of magnitude (a sampled miss needs at least ten of the 100 sampled items to outrank it, and how likely that is depends on how many outrankers exist). Sampling rewards being merely better than random items, so the first two look identical (both almost always hits); only at full rank \(100{,}000\) does sampling begin to miss.
The catch is that sampled metrics are inconsistent. Krichene & Rendle (KDD 2020) showed that sampling can reverse which model looks better versus full ranking — @K over \(100\) items measures something genuinely different from @K over millions. Report full-ranking metrics, or at minimum disclose the sampling protocol; the graph-recommender papers (neural graph collaborative filtering, NGCF; LightGCN; self-supervised graph learning, SGL) rank against all items (Datasets & Benchmarks §4).
If compute truly forces sampling:
- sample the negatives by popularity (not uniformly), so the distractors resemble the hard, popular items a full ranking would surface, and use a large sample (\(\ge1000\), not \(100\)) while reporting its size (the claim that sampling was the common default and both pieces of advice here are claims from practice, not tested here);
- read the result as an optimistic stand-in for the full-ranking number. With one held-out item per user, as in leave-one-out, the item faces fewer competitors and can only rank higher, so every top-\(K\) metric (HR, Recall, MRR, NDCG) comes out at least as high as under full ranking for the same model;
- never compare it across papers that sampled differently.
In one line: sampling only removes competitors, so a sampled rank is never worse than the full rank (in the \(10\)-item toy the film moved from 4th to 2nd); read a sampled score as an optimistic stand-in.
11c. Offline metrics are proxies — the real judge is online (A/B)
Bob’s new model has the better NDCG on the logged films. Will Ann’s real viewers click more? The log holds only what the old system chose to show, so it cannot say.
Everything above is offline: computed on logged history. But logged data is itself biased, because you only ever observe what the old system chose to show. The decisive test is an online A/B test: split live users, serve model A to one half and B to the other, and compare a business metric (click-through, watch-time, revenue). The lift is the relative improvement of B over A in that live metric.
Toy: \(1{,}000\) users see A and \(1{,}000\) see B; A earns \(40\) clicks and B earns \(46\), a click-through rate of \(4.0\%\) against \(4.6\%\), so the lift is \((46-40)/40=15\%\) (one impression per user). Is that lift real? A two-proportion \(z\)-test on these counts gives \(z=0.66\) (the gap of \(0.6\) points over its standard error of about \(0.9\) points), \(p=0.51\), so \(40\) against \(46\) clicks on \(1{,}000\) users is not distinguishable from noise: a real test needs far more users, and §11d shows the same question for seeds and for resampled users. Offline NDCG and this online lift routinely disagree; offline is the cheap filter, online is the verdict. (That claim, and the other statements about online metrics in this subsection, are claims from practice, not tested here.)
Four online metrics recur, each with a small number:
- CTR (§1) \(=\text{clicks}/\text{impressions}\): the \(46\) clicks on \(1{,}000\) impressions above are \(4.6\%\);
- dwell / watch-time, how long the user stayed. Its distribution is usually heavy-tailed: a few extremely long sessions dominate the mean, so compare medians or a trimmed mean (the mean after dropping, say, the top and bottom \(10\%\) of values), not a raw mean. Toy: nine sessions of \(2\) minutes and one of \(120\) give a mean of \(13.8\) minutes but a median of \(2\); the \(10\%\) trimmed mean drops the \(120\) and one \(2\), and is \(2\);
- conversion rate, the fraction who took the target action (buy, subscribe): \(30\) of the \(1{,}000\) users who saw B subscribed, a conversion rate of \(3\%\);
- session length / return rate, for longer-horizon health: if \(300\) of the \(1{,}000\) users come back within a week, the return rate is \(30\%\).
No offline number predicts these perfectly: NDCG tracks CTR only loosely, so the A/B test, not the offline score, is the verdict.
In one line: offline NDCG is the cheap filter and the live A/B test is the verdict; in the toy, \(46\) clicks against \(40\) is a \(15\%\) lift.
11d. Is the gain real? — statistical significance
Bob’s model beats the baseline by \(0.002\) NDCG. Is it a better model, or did it get one lucky run? Run each model over several random seeds: a seed is the starting number of the random-number generator that sets a model’s random starting weights and the order in which it sees the data, so changing it gives a different, equally valid training run, and each seed is one independent run (the toy below uses \(5\) seeds). Report mean \(\pm\) standard deviation over the seeds.
Then use a paired \(t\)-test (the same machinery as the confidence intervals of Probability & Statistics for Machine Learning §8) to ask: is this gap bigger than the run-to-run wobble? Report its \(p\)-value — the chance of seeing a gap at least this large, in either direction, if the two models were truly equal (the toy below gets \(p=0.75\)); below \(0.05\) is the usual bar. A headline number with no significance test — or no stated \(K\) and ranking protocol — is not yet evidence.
Why paired. The test is paired because both models run on the same test users and the same seeds, so you compare them seed by seed and cancel what the seeds share. Over \(5\) seeds, say model A scores NDCG \(\{0.40,0.41,0.42,0.43,0.44\}\) and model B \(\{0.41,0.40,0.44,0.42,0.44\}\): the means are \(0.420\) and \(0.422\), and some seeds are lucky for both.
Treated as two independent groups (sample standard deviations, which divide the squared distances by \(n-1=4\) rather than by \(n\), as in Probability & Statistics for Machine Learning §8.3: \(s_A=0.0158\) and \(s_B=0.0179\)), the gap of \(0.002\) has a standard error (SE: the standard deviation of the values divided by \(\sqrt n\), how far a mean of \(n\) runs is itself likely to wander) of \(\sqrt{s_A^2/5+s_B^2/5}=0.0107\).
Paired, the per-seed gains are \(d=[+0.01,-0.01,+0.02,-0.01,0.00]\), with mean \(0.002\) and sample standard deviation \(s_d=0.0130\) (again with \(n-1\)), so \(\text{SE}=s_d/\sqrt5=0.0058\): the luck the seeds share cancels, and the noise nearly halves. The test statistic is \(t=\text{mean gain}/\text{SE}=0.002/0.0058=0.34\); the \(p\)-value is read from software at \(n-1=4\) degrees of freedom (the number of values still free to vary once their mean is fixed: with \(5\) seeds, \(4\)): \(p=0.75\) (two-sided; a \(t\) table only shows that \(|t|=0.34\) is far below the \(2.776\) cut-off, the \(95\%\) threshold for \(4\) degrees of freedom, Probability & Statistics for Machine Learning §8.3), far above the \(0.05\) bar, so no evidence.
| quantity | formula | value |
|---|---|---|
| unpaired SE | \(\sqrt{s_A^2/5+s_B^2/5}\) | \(0.0107\) |
| paired SE | \(s_d/\sqrt5\) | \(0.0058\) |
| \(t\) | mean gain / paired SE | \(0.34\) |
| \(p\) (4 degrees of freedom) | read from software | \(0.75\) |
Pairing helps only when the two models’ scores rise and fall together across seeds, as they do here (the correlation between the two columns is \(0.71\)); if they moved independently, pairing would gain nothing. The test also covers only the randomness of training. Which users happen to be in the test set is a separate source of luck, and the bootstrap below handles it.
A confidence interval, and what to do when the metric isn’t Gaussian (bell-shaped: most values near the middle, few far out). For model A alone: mean \(0.420\), sample standard deviation \(0.016\), \(\text{SE}=0.016/\sqrt5\approx0.0072\), so the \(95\%\) confidence interval (CI) is a Student-\(t\) interval with the same \(n{-}1{=}4\) degrees of freedom and \(t^{*}=2.776\) (Probability & Statistics for Machine Learning §8): \(0.420\pm2.776(0.0072)=0.420\pm0.020=[0.400,\,0.440]\).
But per-user scores are usually not Gaussian (most users score \(0\), a few score \(1\)), so the cleaner tool is the bootstrap (Efron, 1979): resample the test users with replacement a few thousand times, recompute the metric each time, and read the \(2.5\)th and \(97.5\)th percentiles (the value below which \(2.5\%\), respectively \(97.5\%\), of the resampled scores fall) as the interval. It assumes no distribution at all. Report the interval, not just the point estimate.
Bootstrap, with numbers. For the non-Gaussian per-user case above: say \(20\) test users give HR@10 \(=1\) for \(6\) of them (mean \(0.30\)). One resample-with-replacement repeats some users and drops others for \(7/20=0.35\); another gives \(5/20=0.25\). Over a few thousand resamples, the \(2.5\)/\(97.5\) percentiles land at \([0.10,\,0.50]\) — wide for just \(20\) users, and assuming no distribution at all.
The verdict, made concrete — and it is the gain’s interval that decides. Take the paired example above: B beats A by a headline \(+0.002\) NDCG@10, with the \(5\) per-seed gains \(d=[+0.01,-0.01,+0.02,-0.01,0.00]\): \(\bar d=+0.002\), but they swing in sign, so \(\text{SE}=0.0058\), the paired \(t=0.34\) (\(p=0.75\)), and the \(95\%\) CI of the gain is \([-0.014,\,+0.018]\) — it includes \(0\). So the \(+0.002\) is within run-to-run noise and you do not ship B on this evidence. The headline mean never told you that; its interval did. (Test mechanics and three more cases: Probability & Statistics for Machine Learning §8.7, where the per-seed gap is A’s score minus B’s, so the roles of A and B are swapped.)
In one line: a gain counts only if its interval clears \(0\); Bob’s \(+0.002\) had \(p=0.75\) and a \(95\%\) interval of \([-0.014,+0.018]\), so it is not shown to be better.
11e. Are the scores themselves meaningful? Calibration
Bob’s film site prints a percentage beside every film it shows Ann: “80% match”. Bob asks whether Ann really likes four of every five films marked 80%. Ranking metrics cannot answer, because they only look at the order of the films. This part checks the numbers themselves.
Many uses need the score to be a trustworthy probability: a “watch-probability” shown to the user, a threshold for whether to recommend at all, or blending scores across models. A model is calibrated if, among items it scores \(0.8\), about \(80\%\) are actually clicked.
Check it with a reliability diagram: group the predictions into bins of similar predicted value (say, all predictions near \(0.8\)) and plot each bin’s predicted vs observed click rate; points on the diagonal mean calibrated. The one-number summary is the Expected Calibration Error (ECE): the average absolute gap (its size, ignoring sign) between predicted and observed rates, each bin weighted by its share of the predictions.
Worked, two bins of \(5\) items. A high-confidence bin predicts \(0.80\) but only \(3/5=0.60\) click (gap \(0.20\)); a low bin predicts \(0.20\) and \(1/5=0.20\) click (gap \(0\)). So \[\text{ECE}=\tfrac12(0.20)+\tfrac12(0)=\boxed{0.10},\] and the model is over-confident (its scores promise more clicks than happen), as the figure below shows. With five items in a bin the arithmetic stays small; a real bin holds hundreds, so a gap of \(0.20\) on five items proves nothing by itself.
Why the names. Each bin is weighted by its share of the predictions, so ECE is the gap you would expect for a prediction picked at random; to calibrate is to adjust an instrument until its readings match reality; a reliability diagram shows whether the scores can be relied on as probabilities.
The plain idea. Think of a weather forecaster. On the days she says “80% chance of rain”, it should rain on about four days in five. If it rains on only three of five such days, her “80%” is not a probability: still fine for sorting days from wet to dry, but wrong for deciding whether to carry an umbrella. Our toy model is that forecaster. On its five films marked \(0.80\) the user liked only \(3\), so the correct label is \(0.60\). Calibration is relabelling: print \(0.60\) where the model said \(0.80\) and leave \(0.20\) alone. No film changes place, only the numbers beside them. The ECE of \(0.10\) says how far off the labels are on average.
The fixes are cheap post-hoc rescalings, applied afterwards to an already-trained model’s scores: Platt scaling (Platt, 2000: fit an S-shaped curve to the raw scores) or isotonic regression (fit a staircase that never goes down). Both recalibrate the numbers without ever reversing the ranking: Platt keeps the order exactly when the fitted slope \(a\) is positive (the normal case), and isotonic regression’s flat steps can merge neighboring scores into ties. The two boxes below show how each is fitted; skip them on a first reading.
Side issue: how Platt scaling is fitted. Platt scaling and isotonic regression both learn a map from a model’s raw score \(s\) to a calibrated probability. Here \(s\) is the number the model computes before any squashing into \([0,1]\), and it can be any real number; for a model whose last step is a sigmoid it is the logit of its probability, \(s=\ln\frac{p}{1-p}\) (Probability & Statistics for Machine Learning §3). So the model’s \(0.80\) comes from \(s=\ln\frac{0.8}{0.2}=\ln 4=1.386\), and its \(0.20\) from \(s=-1.386\). The map is fitted on the validation set of §11a, never on the test set.
Platt scaling fits a two-parameter S-curve: find two numbers \(a\) and \(b\) that minimize the cross-entropy (the log loss of §1) between the binary click labels and \[p_{\text{cal}} = \sigma(a\,s + b), \qquad \sigma(z)=\tfrac{1}{1+e^{-z}},\] where \(\sigma\) is the sigmoid, the S-shaped function that squashes any real number into \((0,1)\) (Probability & Statistics for Machine Learning §3). The curve always has this S shape; only its position (\(b\)) and slope (\(a\)) are fitted, which is cheap even on large validation sets.
Worked. Fitting the ten validation items of the ECE example (a computer does the minimizing) gives \(a\approx0.65\) and \(b\approx-0.49\). Check it by hand: the high bin’s \(s=1.386\) becomes \(\sigma(0.65\times1.386-0.49)=\sigma(0.41)=0.60\), exactly its observed rate, and the low bin’s \(s=-1.386\) becomes \(\sigma(-1.39)=0.20\), which was already right. With two bins and two numbers to fit, the best fit reproduces both observed rates. It is the pair \((a,b)\) acting together, not \(a\) alone, that moves \(0.80\) down to \(0.60\) while leaving \(0.20\) in place.
The second fix, isotonic regression, is fitted differently.
Side issue: how isotonic regression is fitted. It fits a free monotone (non-decreasing) step function, a staircase that never goes down as the score goes up (“isotonic” means order-preserving), with no fixed shape such as the sigmoid assumed. Its fitting rule, the pool-adjacent-violators (PAV) algorithm, is simple enough to run by hand. It is more flexible than Platt scaling, but needs more validation data to avoid over-fitting (copying the noise of a small sample into the steps).
Worked. Five validation items, sorted by raw score:
raw score \(s\) (sorted) \(-1.2\) \(-0.4\) \(0.3\) \(0.9\) \(1.6\) clicked? (\(1\) = yes) \(0\) \(1\) \(0\) \(1\) \(1\) calibrated \(g(s)\) after PAV \(0\) \(0.5\) \(0.5\) \(1\) \(1\) A calibrated map must never go down as the score rises, but the click row has a \(1\) followed by a \(0\), a violation. PAV pools such a pair of neighbors into their average, \(\tfrac{1+0}{2}=0.5\), giving the last row. No value now drops below the one before it, so this staircase is the calibrated map: among all non-decreasing rows it is the one closest to the clicks in squared error (the sum of squared differences, here \(0.5\)).
Had the pooled value still sat below its left neighbor, PAV would pool again; it needs only about one pass along the sorted list, so its work grows in step with the number of items \(n\), written \(O(n)\), “order \(n\)”. Note the tie it created: items 2 and 3 now share \(0.5\) although their raw scores differ, so break such ties with the raw score.
Both fixes are post-hoc: they are applied to a frozen model’s output scores without any retraining, and a non-decreasing map never swaps two items (only isotonic regression’s ties can merge neighbors). The key reference is Niculescu-Mizil & Caruana (2005, at the International Conference on Machine Learning, ICML), who benchmarked both methods across classifiers (models that sort inputs into classes). As they report it, Platt scaling works best when a model’s distortion is sigmoid-shaped, as for support vector machines (SVMs) and boosted trees, two classic families of classifiers, while isotonic regression can correct any monotone distortion but over-fits more easily and does worse than Platt scaling when data are scarce (reported there, not tested here).
In one line (calibration): a score of \(0.80\) should mean \(80\%\); in the toy the \(0.80\) bin was right \(60\%\) of the time, an ECE of \(0.10\), and a post-hoc rescaling repairs the numbers without changing the order.
11f. The five lenses as one checklist
You have now met five separate ways a number can mislead: a leaky split, a sampled ranking, an offline score that real users do not share, a gap that is only luck, and scores that do not mean what they say. Nobody keeps five sections in mind while reading a paper, so this subsection folds them into one list to run down before trusting any result.
The one-paragraph protocol checklist. Before trusting any Recall@K / NDCG@K: (1) split by time if you can, and never leak; (2) rank against the full catalog, or disclose the sampling; (3) treat offline as a proxy and confirm with an A/B test; (4) report mean \(\pm\) std over seeds with a significance test, and always state \(K\) and binary-vs-graded relevance; (5) if the raw scores are read as probabilities, check calibration and rescale them if needed (§11e). The fanciest metric on a leaky, sampled, single-seed protocol is worth less than Recall@20 measured correctly.
In practice. Start with the cheap, standard pair: Recall@\(K\) (or NDCG@\(K\)) plus one beyond-accuracy number — coverage or Gini is enough. Serendipity is aspirational: it needs a baseline and user labels, so it is rarely computed in published work (a claim from practice, not tested here). Rank against the full item catalog, not a sampled handful of negatives — Krichene & Rendle (2020) showed that sampled top-\(K\) metrics can reverse which model wins versus full ranking.
The three graph collaborative-filtering (CF) recommenders behind this book’s graph chapters — NGCF (neural graph collaborative filtering), LightGCN and SGL (self-supervised graph learning) — are evaluated that way in their papers, with full ranking; Datasets & Benchmarks §4 records the protocol, while the graph chapters quote the Recall@20 results and do not restate it. Finally, guard against leakage: if interactions are timestamped, use a global temporal split so nothing from the test period (or its future) leaks into training. On this point those same three models are not the ones to copy: they are evaluated on a random per-user split, which does not guard against it (Datasets & Benchmarks §4).
→ Which frameworks enforce this? The Implementation Choices appendix §5 lists the toolkits that bake in these protocols (RecBole, Cornac, Elliot — open-source software toolkits for running recommender experiments) and the papers behind each pitfall here — Krichene & Rendle on sampled metrics, Ferrari Dacrema et al. on under-tuned baselines, Ji et al. (2023) on data leakage.
In one line: a trustworthy number needs a leak-free split, full-catalog ranking, an online check, a gain whose interval clears zero and, when scores are read as probabilities, calibration (ECE \(0.10\) in the §11e toy): in the example above, a \(+0.002\) gain had a \(95\%\) interval of \([-0.014,+0.018]\) and was not worth shipping.
12. Bias, fairness, and the feedback loop
Cara never clicked on Vendetta. Did she dislike it, or did the site simply never show it to her? The log cannot tell. This section names the biases that this blindness creates, shows how they grow over time, and ends with the fix and with a second question: good for whom?
Every metric so far quietly assumed the test set was a fair sample of what the user would have liked. It is not. A recommender’s logged data is not a random sample: it is what the system itself chose to show and what the user then chose to click. The parts of this section: the biases that creates (§12.1–§12.2), the loop that makes them worse (§12.3), the standard tool to correct them, inverse propensity scoring (IPS) (§12.4), and the second question metrics usually skip: not just is the list good? but good for whom? (§12.5), and the practitioner takeaways (§12.6).
12.1 The core problem — the data is missing-not-at-random (MNAR)
Why not simply count the clicks? Because the clicks we have come only from the films the system chose to show.
Statisticians call data MNAR — Missing-Not-At-Random when whether a value is observed depends on the value itself (and on choices that correlate with it). Recommendation logs are the textbook case: you mostly observe interactions for items the system promoted, so the missing entries are missing for a reason, not by coin-flip. Computing a metric naively over this log therefore measures the old system’s habits as much as the new model’s quality — the estimate is biased.
Why “MNAR.” Read literally: the data that is Missing is missing Not At Random. The comfortable opposite is missing completely at random (MCAR): the gaps are pure coin-flips, unrelated to anything — the assumption that lets you ignore the problem, and one that recommender logs almost never satisfy (a claim from practice, not tested here). Statisticians also name a middle case, missing at random (MAR): whether a value is missing may depend on other things that were recorded — say, the list position an item was shown in — but not on the missing value itself.
In one line: a film shown to \(20\) of \(100\) users can only collect clicks from those \(20\); the other \(80\) are missing, not negative.
12.2 The bias taxonomy
A film is liked by \(80\%\) of users and still earns few clicks. Why? Three biases, defined once each. They are distinct but feed one another (§12.3).
- Selection / exposure bias — users can only interact with items they were shown. Un-shown items have no feedback, so their absence from the clicks says nothing about whether the user would have liked them. (“Selection” = the system selected what to expose; “exposure” = only exposed items can be judged.) Toy, the film of §12.1 shown to \(20\) of \(100\) users: its clicks can come only from those \(20\); the other \(80\) users have given no feedback at all, and their silence means “not shown”, not “disliked”.
- Position bias — within a shown list, items higher up get more clicks regardless of true relevance, simply because they are seen first (a claim from practice, not tested here; the toy assumes its rates). A rank-1 slot can out-click a more relevant rank-8 item — so a click is partly a vote for position, not only for quality. Toy, with assumed looking rates: users look at rank \(1\) with probability \(0.9\) and at rank \(8\) with probability \(0.2\), and click what they look at if they like it. A film \(V\) liked by \(50\%\) of users, shown at rank \(1\), earns \(0.9\times0.5=0.45\) clicks per page shown; a film \(Z\) liked by \(80\%\), shown at rank \(8\), earns \(0.2\times0.8=0.16\). \(V\) out-clicks \(Z\) about \(2.8\) times although \(Z\) is the better film.
- Popularity bias — already-popular items (the head of the popularity curve, as opposed to the long tail of §10) dominate exposure and feedback, crowding out the long tail (a claim from practice, not tested here). Toy, with assumed counts: in a catalog of \(10\) films the \(3\) most popular take \(70\) of every \(100\) clicks, about \(23\) clicks each, while each of the other \(7\) films gets about \(4\). The toy of §12.3 shows how that gap grows. This is the Gini / long-tail effect of §10, made dynamic — see From Graphs to LightGCN §13 for the numerical version.
| Bias | What the log over-counts | Tilted in favor of |
|---|---|---|
| Selection / exposure | only shown items get any feedback | whatever the old system showed |
| Position | clicks on high-ranked slots | items placed near the top |
| Popularity | clicks on already-popular items | the head of the catalog |
In one line: three biases tilt the log; in the toy a film liked by \(50\%\) at rank \(1\) earns \(0.45\) clicks against \(0.16\) for one liked by \(80\%\) at rank \(8\).
12.3 The feedback loop — why bias compounds
The three biases are tied together by a dynamic that makes them grow over time:
the model recommends popular / high-position items → users interact with those (because those are what they saw) → the new interactions are logged as training data → that data is even more skewed toward the popular / high-position items → the next model trained on it is more biased → it recommends those items even harder …
This is the “rich get richer” spiral: a small head-start in exposure becomes a self-reinforcing advantage. Bias is not a one-off measurement error you correct once; in practice it is reported to amplify with every retraining cycle if left alone (a claim from practice, not tested here; the toy below shows the mechanism under an assumed rule). It must be designed against continuously (§12.6), and audited over time, not just at a single snapshot. The figure draws the cycle; the toy after it puts numbers on it.
The loop, with numbers. Two films, \(X\) and \(Y\), are equally good: each is clicked by \(30\%\) of the users it is shown to. The first model gives \(X\) \(60\) of every \(100\) slots and \(Y\) \(40\). Clicks follow exposure, \(60\times0.3=18\) on \(X\) and \(40\times0.3=12\) on \(Y\), so \(X\) holds \(60\%\) of the clicks.
The next model is trained on those clicks and sharpens: its exposure share for each film is proportional to the square of that film’s share of the clicks. With \(s\) the share of slots \(X\) holds, \[s_{\text{next}}=\frac{s^2}{s^2+(1-s)^2},\qquad\text{round 1: }\ \frac{0.6^2}{0.6^2+0.4^2}=\frac{0.36}{0.52}=0.692 .\] Each round applies the rule to the previous round’s output, with its clicks again proportional to its exposure, so each row is the next. Four rows are enough to see it: by round 3 the tail film holds \(4\) slots in \(100\), and further rounds push it only closer to \(0\). Carrying the fractions exactly (round 2 is \(81/97=0.8351\); starting from the rounded \(0.69\) instead would print \(0.83\)):
| round | share of slots for \(X\) | share of slots for \(Y\) | slots for \(Y\) (of \(100\)) |
|---|---|---|---|
| \(0\) | \(0.6000\) | \(0.4000\) | \(40\) |
| \(1\) | \(0.6923\) | \(0.3077\) | \(31\) |
| \(2\) | \(0.8351\) | \(0.1649\) | \(16\) |
| \(3\) | \(0.9624\) | \(0.0376\) | \(4\) |
The films are equally good, yet \(Y\) falls from \(40\) slots to \(4\) in three rounds: the whole drift is made by the loop and none by quality. At \(50/50\) the rule changes nothing, but that balance is unstable: any tilt grows. The squaring is our assumption, a stand-in for a model that puts the apparent winner in the better positions (§12.2), so that it gains more than its share of the clicks; with the exponent \(1\) there would be no drift at all, and the exponent of a real system is unknown.
In one line: two equally good films, a \(60/40\) start and a rule that gives the leader slightly more than its share: the tail film falls from \(40\) slots to \(4\) in three retrainings.
12.4 IPS — inverse propensity scoring (the standard fix)
If the problem is that some items were shown far more than others, the fix is to re-weight each observed interaction by how unlikely it was to be observed in the first place. That is IPS — Inverse Propensity Scoring (for evaluating recommenders: Schnabel et al., 2016).
- Propensity = the probability that an item was shown / observed (its propensity to be seen). Call it \(p\) (not the \(p\)-value of §11d). In practice \(p\) is estimated from the logs — for instance as the fraction of sessions in which the item was displayed (an item shown in \(20\) of \(100\) sessions has \(p=0.2\)). It is measured most reliably on a small slice of traffic where items are shown in random order, so that exposure is known exactly (a claim from practice, not tested here).
- Weight each observed interaction by \(\boxed{1/p}\) — the inverse of its propensity (\(p=0.2\) gives weight \(5\)). An over-exposed item (high \(p\)) gets down-weighted; a rarely-shown item (low \(p\)) gets up-weighted, so its one hard-won click counts for more. When \(p\) is the true exposure probability and is never \(0\) for an item that matters, the re-weighted count is an unbiased estimate — right on average — of the metric you would have measured under uniform exposure (the worked example below shows exactly what that means); an estimated \(p\) is only approximately unbiased, and clipping or self-normalizing (below) trade the rest for less noise.
Worked example (check by hand). Take two new items, unrelated to §3’s list and to the films of §12.3: item \(X\) was shown with propensity \(p_X=0.8\), item \(Y\) with \(p_Y=0.2\). A click on each contributes its inverse propensity: \[ \text{click on }X \;\to\; \frac{1}{p_X}=\frac{1}{0.8}=\boxed{1.25}, \qquad \text{click on }Y \;\to\; \frac{1}{p_Y}=\frac{1}{0.2}=\boxed{5}. \] So a click on the rarely-shown \(Y\) is worth \(5/1.25=\boxed{4\times}\) a click on the heavily-shown \(X\) in the unbiased estimate. Intuition: \(Y\) “had to overcome” being shown only a quarter as often as \(X\) (\(0.2\) vs \(0.8\)), so each \(Y\)-click is far stronger evidence of genuine preference.
Now the whole estimate — why dividing by \(p\) removes the bias. Suppose \(X\) and \(Y\) are in truth equally good: each is clicked \(30\%\) of the times it is shown. Over \(100\) sessions the old system shows \(X\) in \(80\) of them (\(24\) clicks) and \(Y\) in \(20\) (\(6\) clicks), so the raw click counts make \(X\) look \(4\times\) better. IPS re-weights every click by \(1/p\): \(X\) gets \(24\times1.25=30\) and \(Y\) gets \(6\times5=30\) — equal, and exactly the \(30\) clicks each item would have earned had it been shown in all \(100\) sessions (uniform exposure). That is what unbiased means here: on average, the re-weighted count lands on the number you would have seen if every item had been shown equally, whatever the old system’s habits.
Applied to a metric: IPS-weighted recall. Back on §3’s list (relevant items \(\{B,C,E,G\}\), top-5 \([A,B,C,D,E]\), hits \(B,C,E\)), suppose the logs say that \(B\) and \(C\) were shown with propensity \(0.8\) and \(E\) and \(G\) with \(0.2\) (assumed values for the toy). The weights \(1/p\) are \(1.25\), \(1.25\), \(5\) and \(5\). Raw Recall@5 gives every relevant item one vote: \(3/4=0.75\). The IPS-weighted Recall@5 gives each relevant item its weight and divides the weight of the hits by the weight of all the relevant items: \[\text{Recall@5}_{\text{IPS}}=\frac{1.25+1.25+5}{1.25+1.25+5+5}=\frac{7.5}{12.5}=0.60 .\]
The score falls from \(0.75\) to \(0.60\) because the item the list missed, \(G\), was a rarely shown one: it is \(1\) of \(4\) items in the raw count (\(25\%\)) but \(5\) of the \(12.5\) weight (\(40\%\)). Dividing by the total weight (the self-normalized form) keeps the score between \(0\) and \(1\) at the price of a little bias. The same re-weighting works for other metrics. For a Hit Rate over users, a user whose hit came from an item with \(p=0.2\) counts \(5\) instead of \(1\) in the sum (before any normalizing). This weighted recall is this book’s self-normalized adaptation of the estimators in Schnabel et al. (2016), not their exact formula.
Why “inverse propensity.” You weight by the inverse (\(1/p\)) of the propensity (\(p\), the chance of being shown). This is exactly the \(1/Q\) importance-weighting behind the sampled-softmax log-\(Q\) correction in Loss Functions & Regularizers §10 — there you divide by an item’s sampling probability to undo a biased negative sampler; here you divide by its exposure probability to undo a biased logging policy (the rule by which the old system decided what to show). Same idea — un-bias an estimate by dividing out the probability that produced the sample — in a different place. (Caveat: tiny propensities give huge weights and noisy estimates, so in practice they are clipped.)
In one line: weight each click by \(1/p\): \(X\) and \(Y\) both come out at \(30\), and on the running list the IPS-weighted Recall@5 is \(0.60\) against the raw \(0.75\).
12.5 Fairness — “good for whom?”
Accuracy metrics ask is the list good? Fairness asks the sharper question: good for whom? (The survey of Ekstrand et al., 2022, is the standard reference.) Recommendation is inherently multi-stakeholder — at least users, providers (item creators / sellers), and the platform — and a list that is great on average can be systematically worse for some group. Two sides:
- Consumer / user-side fairness — is recommendation quality (Recall, NDCG, …) comparable across user groups (e.g. by age, gender, region)? Unfair if one group reliably gets worse lists.
- Provider / item-side fairness — is exposure comparable across item creators / groups? The long tail being starved of exposure (§10) is partly a provider-fairness problem: a few providers can capture most of the recommendation slots, as in the toy below.
Two standard group-fairness definitions, borrowed from classification, one line each:
- Demographic parity — equal selection / exposure rate across groups (each group is recommended / shown at the same rate, whatever share of each group would like the item).
- Equal opportunity — equal true-positive rate (TPR) across groups: the share of the truly relevant cases that get surfaced, the idea of §8 counted over users instead of items (among users who would like an item, each group is equally likely to actually have it surfaced).
Both, on tiny numbers. Demographic parity (provider exposure): a feed has \(100\) recommendation slots and two provider groups that each own half the catalog: the popular studios fill \(85\) slots, the long-tail creators \(15\). The exposure rates are \(0.85\) vs \(0.15\) — a parity gap of \(0.70\), where parity would require \(0.50/0.50\).
Equal opportunity (consumer TPR): among the users who genuinely would like a given item, what fraction get it in their top-\(K\)? Group 1: \(120\) of \(200\) → TPR \(0.60\); group 2: \(80\) of \(200\) → TPR \(0.40\) — an equal-opportunity gap of \(0.20\). The two ask different questions: parity wants equal exposure regardless of preference; equal opportunity wants an equal hit-rate among those who would actually like the item — a model can satisfy one and fail the other.
These can trade off against accuracy. Toy, with assumed click rates: a popular-studio slot is clicked \(10\%\) of the time and a long-tail slot \(6\%\). The unconstrained \(85/15\) split of \(100\) slots earns \(85\times0.10+15\times0.06=9.4\) clicks; forcing \(50/50\) earns \(50\times0.10+50\times0.06=8.0\), about \(15\%\) fewer. Whether real systems pay this price, and how much, varies (a claim from practice, not tested here). There is no free lunch: fairness is a deliberate choice about which good you are optimizing, the same lesson as §1’s “different metrics measure different goods.”
In one line: the parity gap (\(0.85\) against \(0.15\) is \(0.70\)) and the equal-opportunity gap (\(0.60\) against \(0.40\) is \(0.20\)) are different checks, and forcing parity in the toy costs about \(15\%\) of the clicks.
12.6 Practitioner takeaways
- Report by group, not just on average. Break out exposure / coverage (§10) per user and per provider group — an aggregate number hides who is being underserved.
- Prefer IPS-corrected offline metrics for click data (the worked recall of §12.4), since raw clicks carry position and exposure bias. Estimate the propensity \(p\) (the chance an item was shown, §12.4) from exposure logs — an item’s display-count share, a fitted position-bias curve (the chance of a click at each list position, estimated from the logs), or, most reliably in practice (a claim from practice, not tested here), a small randomized-exposure slice (traffic where items are shown in random order, so exposure is known exactly) — and clip extreme propensities (put a floor under \(p\), which caps the weight \(1/p\)) so one rarely-shown item can’t dominate the estimate.
- Stratify by popularity, not just the average. Report NDCG/Recall on head vs. tail items (head: the few most popular; tail: the many rarely seen, §10) separately: a model can lift top-line NDCG purely by serving the popular head better while the tail rots, and only a per-bucket split reveals it (the same lesson as the Gini coefficient, §10). Toy, with assumed scores: model M1 scores NDCG \(0.30\) on head items and \(0.05\) on tail items, model M2 \(0.34\) and \(0.02\). With \(80\%\) of the test cases on head items, the top-line NDCG rises from \(0.250\) to \(0.276\) while the tail score falls to \(0.4\) of its old value.
- Audit the feedback loop over time, not once. The “rich get richer” skew (§12.3) is a trajectory: track concentration (Gini, §10) and group exposure across successive retrainings, and confirm real gains with an A/B test (§11c), the only judge the loop cannot fool.
In one line: the log shows only what was shown; the loop turns a \(60/40\) tilt into \(96/4\) in three rounds, IPS re-weights by \(1/p\), and fairness asks for whom the list is good.
13. Which metric, when?
Bob has a dozen scores on his screen and one slot in the report. Which number should he put there? The answer depends on what Bob’s site is for, so this section maps each goal to a metric and ends with one rule that covers them all.
| Your goal | Reach for |
|---|---|
| Predict a rating accurately (★1–5) | RMSE (punish big misses) or MAE (robust) |
| Top-\(K\) list, “find all the good items” | Recall@K |
| Top-\(K\) list, “don’t waste slots” | Precision@K (or F1@K for balance) |
| Just need one good item, fast | MRR (or HR@K) |
| Position + graded relevance (the default) | NDCG@K |
| Binary relevance, every relevant item should rank high | MAP |
| Overall ranking quality (pairwise) | AUC (ties to BPR, Loss Functions & Regularizers §9) |
| Is the catalog used / list varied / fresh? | coverage, diversity, novelty, serendipity, Gini |
| Is the score a trustworthy probability? | ECE (§11e) and LogLoss (§1) |
| Is the list fair to each group? | per-group metrics: demographic parity, equal opportunity (§12.5) |
Golden rule: report at least one accuracy metric and at least one beyond-accuracy metric — a single number hides the popularity trap. Always state the \(K\) (Recall@10 \(\ne\) Recall@50) and whether relevance is binary or graded.
In one line: pick the metric that matches the goal in the table, report one accuracy number and one beyond-accuracy number, and always say \(K\): on the running list Recall@3 is \(0.50\) but Recall@5 is \(0.75\).
14. Exercises
Work these by hand — the numbers are kept tiny on purpose. Several use a second user, introduced in exercise 2, so that you compute fresh numbers instead of re-reading the chapter’s; the chapter’s running example (relevant set \(\mathcal{R}=\{B,C,E,G\}\), top-5 list \([A,B,C,D,E]\) with hits at ranks 2, 3, 5) returns as a comparison in exercise 5. Full worked solutions are in the Solutions appendix at the back of the book.
(compute) A rating model predicts \([3,5,2,4]\) for four movies whose true ratings are \([4,5,4,3]\). Compute the MAE and the RMSE (§2). Which of the two is larger here, and which single prediction is most responsible for that gap?
(compute) A second user has relevant set \(\{C,F,G\}\) and receives the top-5 list \([C,A,F,B,D]\). Compute this user’s Precision@5, Recall@5, and F1@5 (§4). State in one phrase what each of the three numbers is telling you.
(compute) Reciprocal rank and MRR (§5), for three users. The first is the second user of exercise 2. For the other two users the first relevant item sits at rank 5 and at rank 3 of their top-5 lists. Compute the three reciprocal ranks and the MRR averaged over the three users.
(compute) For the second user of exercise 2, compute the Average Precision (§6): find the ranks of the hits, the precision at each hit position, and divide their sum by the number of relevant items. Show the Precision@\(k\) values you used.
(compute) Compute the NDCG@5 (§7) of the second user’s list (exercise 2): its DCG@5, the ideal IDCG@5 (all three of their relevant items at the top), then the ratio. Is it higher or lower than the running list’s \(0.593\), and why, in one line? (Useful: \(\log_2 3\approx1.585\), \(\log_2 4=2\).)
(apply) AUC as a pairwise probability (§8). A model scores two relevant items \(\{0.8,\,0.5\}\) and two irrelevant items \(\{0.6,\,0.3\}\). List the \(2\times2=4\) (relevant, irrelevant) pairs, count how many the model orders correctly (relevant scored higher), and report the AUC. Is it above the \(0.5\) of random guessing?
(apply) IPS-weighted recall (§12.4). For the second user of exercise 2 (relevant films \(\{C,F,G\}\), top-5 list \([C,A,F,B,D]\)) the logs say the three relevant films were shown with propensities \(p_C=0.5\), \(p_F=0.25\) and \(p_G=0.1\). (a) Give the weight \(1/p\) of each film. (b) Compute the IPS-weighted Recall@5 (the weight of the hits divided by the weight of all the relevant films) and, for comparison, the raw Recall@5. (c) Which film accounts for most of the difference between the two numbers, and why?
(extend) Gini and serendipity (§10). (a) A 5-item catalog is recommended with counts \([6,3,1,0,0]\) (10 recommendations, mean \(\mu=2\)); compute the Gini coefficient \[G=\frac{\sum_i\sum_j|x_i-x_j|}{2n^2\mu}\] and say whether this catalog is more or less concentrated than the chapter’s \([8,2,0,0,0]\) (\(G=0.72\)). (b) Of the second user’s 2 relevant hits (exercise 2), suppose one — item \(C\) — is a blockbuster that a popularity baseline would have shown anyway; compute serendipity@5 and say how it compares with the Precision@5 you found in exercise 2, and why.
(apply) Two lists, four metrics (§4, §5, §7). A user has \(4\) relevant films. List P puts two of them at ranks \(1\) and \(2\) of its top \(5\); list Q puts two at ranks \(3\) and \(5\). (a) Compute Precision@5 and Recall@5 of each list. (b) Compute the reciprocal rank and the NDCG@5 of each (the ideal DCG@5 for four relevant films is \(2.562\), §7). (c) If only the first suggestion is ever used, which of the four metrics would you trust, and how many times larger is list P’s value than list Q’s on it? Answer in one sentence.
(apply) Full against sampled (§11b). A catalog has \(8\) items. For model P the held-out item has full rank \(5\) (four items score higher, three lower); for model Q it has full rank \(6\) (five higher, two lower). Each is re-ranked against \(3\) negatives drawn at random from the other \(7\) items and scored by HR@2. (a) Under full ranking, does either model score a hit? (b) There are \(35\) ways to choose \(3\) negatives from \(7\) (ordered picks divided by orderings, as in §11b). For P, in how many does the held-out item land in the top \(2\) of its four candidates? Answer the same for Q. (c) In one line, what do your two fractions say about comparing a sampled HR@2 with a full-ranking HR@2?
(apply) Looks better, but should you ship? Model B beats A by a headline \(+0.003\) NDCG@10. Over \(5\) shared seeds the per-seed gains are \[d=[+0.012,\,-0.006,\,+0.011,\,-0.004,\,+0.002].\] (a) Compute the mean gain \(\bar d\) and say whether it is positive. (b) Compute its \(95\%\) confidence interval (CI) from the five gains, using the \(t\) multiplier \(2.776\) for \(5\) runs (§11d): does it clear \(0\)? (c) Ship B or not, and give the one-sentence reason (§11d).
(apply) Calibration (§11e). A model’s predictions fall in three bins. Bin 1: predicted \(0.9\), \(10\) predictions, \(7\) clicked. Bin 2: predicted \(0.6\), \(20\) predictions, \(9\) clicked. Bin 3: predicted \(0.2\), \(10\) predictions, \(2\) clicked. (a) Compute the observed click rate and the gap (predicted minus observed) in each bin. (b) Compute the ECE from the absolute gaps, weighting each bin by its share of the \(40\) predictions. (c) Is the model over-confident or under-confident? Say in one line how the signs of the gaps show it.
(extend) Fairness (§12.5). A feed has \(60\) slots and two provider groups that each own half the catalog; the popular studios get \(45\) slots and the long-tail creators \(15\). (a) Compute the two exposure rates and the demographic-parity gap. (b) Among users who would like a given film, group 1 gets it in their top-\(K\) for \(38\) of \(50\) users and group 2 for \(21\) of \(60\). Compute the two true-positive rates and the equal-opportunity gap. (c) Suppose a slot given to a studio earns \(0.10\) clicks and one given to a creator \(0.06\) (assumed values). Compare the clicks earned by the \(45/15\) split with those of an equal \(30/30\) split.
15. Where this fits in the book
| Metric (here) | Where it shows up |
|---|---|
| Recall@K, NDCG@K | Recall@20 is the number quoted in From Graphs to LightGCN §12 and The Spectral / Graph-Filter View §4 (which also prints one NDCG@20 pair); Self-Supervised & Contrastive Learning §7 also reports Recall@10, Recall@20 and NDCG@20, for LightGCN and for RLMRec (a method that adds knowledge from a large language model to such a graph recommender) |
| RMSE/MAE | Traditional Recommender Systems §6 (rating prediction; the Netflix Prize, a famous rating-prediction competition) |
| AUC ↔︎ BPR | Loss Functions & Regularizers §9 — BPR trains on correctly ordered (relevant, irrelevant) pairs through a smooth stand-in for the 0/1 pair count, so it pushes AUC up without maximizing it exactly |
| Coverage / Gini / long-tail | From Graphs to LightGCN §13 (popularity bias, worked numerically) and the self-supervised fixes in Self-Supervised & Contrastive Learning |
| Evaluation protocol (§11) | full ranking, the split choice (random per-user in the graph chapters; leave-one-out or a temporal split where leakage matters) and per-seed significance: how the literature behind those chapters is measured and where it leaks (protocol recorded in Datasets & Benchmarks §4) |
Carry this forward: rating error (RMSE/MAE) grades numbers; ranking metrics (Precision / Recall / F1 / HR / MRR / MAP / NDCG / AUC) grade the ordered list — NDCG is the default; beyond-accuracy metrics (coverage/diversity/novelty/serendipity/Gini) grade the list’s health. Pick the metric that matches what you actually want, and never report accuracy alone.
16. Glossary
| Term | Plain meaning |
|---|---|
| Relevant item | A ground-truth item the user actually likes. |
| @K | Evaluated over the top \(K\) recommended positions only. |
| MAE / MSE / RMSE | Mean Absolute / Mean Squared / Root-Mean-Squared rating error. |
| Hit Rate (HR@K) | Fraction of users with \(\ge 1\) relevant item in the top-\(K\). |
| Precision@K | Of the \(K\) shown, the fraction relevant. |
| Recall@K | Of all relevant items, the fraction in the top-\(K\). |
| F1@K | Harmonic mean of precision and recall. |
| Harmonic mean | The reciprocal of the average of the reciprocals; for two numbers \(P,R\) it is \(2PR/(P+R)\), dragged down by the smaller one (\(0.6\) and \(0.75\) give \(0.667\)). |
| MRR | Mean Reciprocal Rank — each user’s reciprocal rank (RR), \(1/\)rank of the first relevant item (\(0\) if none in the top-\(K\)), averaged over users. |
| AP / MAP | Average Precision (Precision@\(k\) summed over hit positions, divided by \(|\mathcal{R}|\)) / its mean over users. |
| DCG / IDCG / NDCG | Discounted Cumulative Gain (gains \(2^{\text{rel}}-1\), each divided by \(\log_2(i+1)\) at rank \(i\)) / its ideal / the normalized ratio in \([0,1]\). |
| AUC / ROC | Area Under the Receiver Operating Characteristic (ROC) Curve = P(score of a random relevant > random irrelevant) = the fraction of correctly ordered (relevant, irrelevant) pairs. |
| LogLoss | Log loss, or binary cross-entropy: the average of \(-\ln\)(the probability given to what happened); \(0.9\) on a click and \(0.2\) on a non-click give \(0.164\). |
| TPR / FPR | True- / false-positive rate: the share of the relevant / irrelevant items scoring at or above a threshold (a cut-off score); lowering the threshold step by step traces the ROC curve. |
| Coverage | Fraction of the catalog ever recommended. |
| Diversity | Average dissimilarity within a recommended list. |
| Novelty | Non-obviousness, often \(-\log_2(\text{popularity})\). |
| Serendipity | Relevant and surprising: hits a popularity baseline would not have shown, divided by \(K\). |
| Popularity baseline | A simple recommender that shows everyone the same most-popular items. |
| Gini coefficient | Concentration of recommendations on few items: \(0\) = perfectly even; the maximum, all on one of \(n\) items, is \((n-1)/n\) — near \(1\) only for a large catalog. |
| Lorenz curve | The share of recommendations held by the least-recommended fraction of the catalog; Gini \(=A/(A+B)\), the gap below the diagonal over the whole triangle. |
| Train/test split | How held-out test data is chosen: a random split, leave-one-out (LOO: each user’s chronologically last interaction), or a global temporal split (one cut-off date for everyone). |
| Validation set | A third slice, carved from the training data, used to choose settings (hyper-parameters, when to stop, calibration maps); the test set is touched once, at the very end. |
| Data leakage | Test-period information seeping into training; silently inflates every metric. |
| Full vs. sampled ranking | Rank the true item against the whole catalog vs. a few sampled negatives; the latter is inconsistent across papers and optimistic (with one held-out item per user, as in leave-one-out, fewer competitors mean the item can only rank higher). |
| A/B test (online eval) | Serve two models to live user halves and compare a business metric — the real verdict. |
| CTR / impression | Click-through rate \(=\) clicks \(/\) impressions, where an impression is one showing of an item to a user. |
| Significance (paired \(t\)-test) | Is a gain bigger than run-to-run seed noise? Report mean \(\pm\) standard deviation over seeds and a \(p\)-value. |
| Standard error (SE) | The standard deviation of a mean: the sample standard deviation of the values (divided by \(n-1\), not \(n\)) divided by \(\sqrt n\); pairing the runs shrinks it when the runs share luck (\(0.0107\) unpaired against \(0.0058\) paired in §11d). |
| Degrees of freedom | The number of values still free to vary once their mean is fixed: \(n-1\) for \(n\) runs (\(4\) for \(5\) seeds). |
| Percentile | The \(q\)th percentile is the value below which \(q\%\) of the values fall; the bootstrap reads its interval from the \(2.5\)th and \(97.5\)th. |
| Cosine similarity | How alike two vectors point: \(1\) for the same direction, \(0\) for nothing in common when the features are never negative. |
| Bit | The information in one fair coin flip; an event of probability \(\tfrac12\) carries \(1\) bit, and \(-\log_2 p\) bits in general. |
| IPS-weighted recall | Recall with each relevant item weighted by \(1/p\) and divided by the total weight: \(0.60\) against the raw \(0.75\) on the running list (§12.4). |
| Random seed | The starting number of the random-number generator; each seed gives one independent training run. |
| Bootstrap | Resample the test users with replacement thousands of times and read the metric’s \(2.5\)th / \(97.5\)th percentiles as its interval — no distribution assumed. |
| Calibration / ECE | A model is calibrated if items it scores \(0.8\) are clicked about \(80\%\) of the time; the Expected Calibration Error averages the per-bin absolute gap between predicted and observed rates, weighting each bin by its share of predictions. |
| Reliability diagram | Predicted vs. observed rate, one point per bin; calibrated points lie on the diagonal. |
| Platt scaling | Calibrates a raw score \(s\) with a fitted S-curve \(\sigma(as+b)\); keeps the ranking exactly when the slope \(a>0\). |
| Isotonic regression (PAV) | Calibrates with a fitted non-decreasing staircase; the pool-adjacent-violators algorithm averages neighbors that break the order, which can create ties. |
| MNAR data | Missing-Not-At-Random: whether an interaction is observed depends on what the system chose to show — recommender logs are the textbook case (the opposite, missing completely at random, is pure coin-flip missingness). |
| Selection / exposure bias | Only items the system showed can get feedback; un-shown items look “disliked” by silence. |
| Position bias | Higher-ranked slots draw more clicks regardless of true relevance. |
| Feedback loop | Recommend → click → log → retrain on skewed data → more skew; the “rich get richer” spiral that compounds bias. |
| Propensity / IPS | Propensity = probability an item was shown; inverse propensity scoring (IPS) re-weights each interaction by \(1/\)propensity to undo exposure bias. |
| Demographic parity | Equal selection / exposure rate across groups. |
| Equal opportunity | Equal true-positive rate across groups (the truly-relevant are surfaced equally). |
| Provider vs. consumer fairness | Comparable exposure across item creators (provider) vs. comparable quality across user groups (consumer). |
17. References
- Efron, B. (1979). Bootstrap methods: another look at the jackknife. The Annals of Statistics, 7(1), 1–26. https://doi.org/10.1214/aos/1176344552
- Ekstrand, M. D., Das, A., Burke, R., & Diaz, F. (2022). Fairness in information access systems. Foundations and Trends in Information Retrieval, 16(1–2), 1–177. https://doi.org/10.1561/1500000079
- Fawcett, T. (2006). An introduction to ROC analysis. Pattern Recognition Letters, 27(8), 861–874. https://doi.org/10.1016/j.patrec.2005.10.010
- Ferrari Dacrema, M., Cremonesi, P., & Jannach, D. (2019). Are we really making much progress? A worrying analysis of recent neural recommendation approaches. In Proceedings of the 13th ACM Conference on Recommender Systems (RecSys) (pp. 101–109). https://doi.org/10.1145/3298689.3347058
- Green, D. M., & Swets, J. A. (1966). Signal detection theory and psychophysics. New York: Wiley.
- Herlocker, J. L., Konstan, J. A., Terveen, L. G., & Riedl, J. T. (2004). Evaluating collaborative filtering recommender systems. ACM Transactions on Information Systems, 22(1), 5–53. https://doi.org/10.1145/963770.963772
- Järvelin, K., & Kekäläinen, J. (2002). Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems, 20(4), 422–446. https://doi.org/10.1145/582415.582418
- Ji, Y., Sun, A., Zhang, J., & Li, C. (2023). A critical study on data leakage in recommender system offline evaluation. ACM Transactions on Information Systems, 41(3), 75:1–75:27. https://doi.org/10.1145/3569930
- Krichene, W., & Rendle, S. (2020). On sampled metrics for item recommendation. In Proceedings of the 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD). https://doi.org/10.1145/3394486.3403226
- Manning, C. D., Raghavan, P., & Schütze, H. (2008). Introduction to information retrieval. Cambridge University Press. https://nlp.stanford.edu/IR-book/
- Niculescu-Mizil, A., & Caruana, R. (2005). Predicting good probabilities with supervised learning. In Proceedings of the 22nd International Conference on Machine Learning (ICML) (pp. 625–632). https://doi.org/10.1145/1102351.1102430
- Platt, J. C. (2000). Probabilities for SV machines. In A. J. Smola, P. Bartlett, B. Schölkopf, & D. Schuurmans (Eds.), Advances in large-margin classifiers (pp. 61–74). MIT Press. https://doi.org/10.7551/mitpress/1113.003.0008 (This chapter circulated as a 1999 preprint under the longer title “Probabilistic outputs for support vector machines and comparisons to regularized likelihood methods”, which is the title most papers cite.)
- Ricci, F., Rokach, L., & Shapira, B. (Eds.). (2022). Recommender systems handbook (3rd ed.). Springer.
- Schnabel, T., Swaminathan, A., Singh, A., Chandak, N., & Joachims, T. (2016). Recommendations as treatments: Debiasing learning and evaluation. In Proceedings of the 33rd International Conference on Machine Learning (ICML) (pp. 1670–1679). https://proceedings.mlr.press/v48/schnabel16.html
Links and entries checked October 2026. The title of the 1999 preprint in the Platt entry is quoted from the usual citation, not from a source opened for this chapter.