Warmup Guide — Learning to Rank

Zero-to-expert primer for Phase 05: ranking as its own ML discipline — NDCG derived from first principles, the pointwise/pairwise/listwise ladder, LambdaRank's central trick, click bias, and the evaluation discipline ranking demands.

Table of Contents

Chapter 1: Why Ranking Is Not Classification

A classifier predicts a property of one item; a ranker produces an ordering of a list, and the differences cascade:

  • Only relative order matters: a scorer that outputs 0.9/0.8 ranks identically to one outputting 5.2/1.1 — calibrated probabilities are not the goal (until ads, where price × pCTR makes calibration matter again — know both regimes).
  • Position is everything: users see the top; an error at rank 1 costs orders of magnitude more than at rank 50. Metrics must discount by position (Ch. 3) and objectives should concentrate effort at the top (Ch. 5).
  • The query is the unit: items are only comparable within a query's candidate list. This reshapes the loss (pairs within groups), the split (by query — Ch. 8), and the metric (per-query, then averaged).

The economic stakes explain the interview weight: search, recommendations, ads, and feeds are ranking systems, and at list-product companies a 1% NDCG-correlated gain is a revenue line.

Chapter 2: The LTR Data Model

The canonical dataset row: (query_id, doc_id, feature_vector, relevance_label) — grouped by query_id into lists.

  • Graded relevance: 0 (bad) … 4 (perfect) by convention (binary is the degenerate case). Sources: editorial judgment (expensive, clean) or behavioral signals (clicks/conversions — abundant, biased: Ch. 7).
  • Query groups are sacred: every operation — pair generation, batching, splits, metric computation — respects group boundaries. The single most common LTR bug is leaking across them (a random row-level split puts the same query's docs in train and test: the model memorizes query-specific feature quirks and the offline number lies — the CV track's group-leakage taxonomy, ranking edition).
  • Candidate lists come from Phase 04's retrieval — typically 100–1000 candidates per query, of which the ranker orders the top tens. The label distribution is wildly skewed (most candidates irrelevant) — pair-based objectives handle this naturally (only cross-label pairs train).

Chapter 3: NDCG, Derived

Build it from requirements, not memory:

  1. Graded gains: more-relevant documents should contribute more. Convention: $\text{gain} = 2^{rel} - 1$ — exponential, so a perfect (4 → 15) is worth ~5× a fair (2 → 3); this encodes "one great answer beats several mediocre ones."
  2. Position discount: contribution decays with rank. Convention: $1/\log_2(\text{rank}+1)$ — gentle (heavy tails of attention), normalized so rank 1 has discount 1.

$$\text{DCG@k} = \sum_{i=1}^{k} \frac{2^{rel_i} - 1}{\log_2(i + 1)}$$

  1. Comparability across queries: a query with three perfect docs has higher attainable DCG than one with none — raw DCG can't be averaged. Normalize by the ideal DCG (the DCG of the relevance-sorted ordering):

$$\text{NDCG@k} = \frac{\text{DCG@k}}{\text{IDCG@k}} \in [0, 1]$$

The properties your lab's tests pin: perfect ordering → 1.0; swapping a relevant doc downward strictly decreases it; it's invariant to what happens below k; all-zero relevance is defined as 0 (a convention — state it). Cousins for the toolbox: MRR (first-relevant only — navigational queries), MAP (binary labels, averaged precision — older IR). Knowing when NDCG is wrong (e.g., diversity isn't rewarded — ten near-duplicates of one perfect answer score brilliantly) is the senior layer.

Chapter 4: The Objective Ladder — Pointwise, Pairwise, Listwise

How do you train for a list metric with gradient methods? Three generations:

  • Pointwise: regress/classify each (query, doc) label independently. Simple, reuses everything you know — and ignores list structure entirely: it spends capacity getting absolute label values right when only within-query order matters, and weights every doc equally regardless of position impact.
  • Pairwise (RankNet): for documents $i \succ j$ within a query, model $P(i \succ j) = \sigma(s_i - s_j)$ and minimize the logistic loss; the gradient on each score is the elegantly simple $\lambda_{ij} = -\sigma(-(s_i - s_j))$ pushing $s_i$ up and $s_j$ down. Now the model optimizes order — but all pairs are equal: fixing a rank-49/50 inversion earns as much as fixing rank-1/2. The metric says otherwise.
  • Listwise in effect (LambdaRank): Chapter 5's move — keep the pairwise gradient, scale it by how much the metric cares about that pair.

Chapter 5: LambdaRank — Optimizing the Unoptimizable

The obstruction: NDCG depends on ranks, ranks come from sorting, and sorting is piecewise-constant in the scores — the gradient is zero almost everywhere. You cannot backprop through a sort (usefully).

LambdaRank's insight: you don't need the loss — you only need its gradients. Define them directly: for a pair $(i \succ j)$,

$$\lambda_{ij} = -\sigma\big({-(s_i - s_j)}\big) \cdot \big|\Delta \text{NDCG}_{ij}\big|$$

where $|\Delta \text{NDCG}_{ij}|$ is the NDCG change if you swapped $i$ and $j$ in the current ranking. Pairs straddling the top of the list get large weights; deep-list inversions get nearly none — the model's effort lands where the metric pays. Empirically (and later with some theory — it approximately optimizes NDCG), this works remarkably well; LambdaMART = these lambdas fed to gradient-boosted trees (Phase CV-02's boosting + this gradient), and it remains the production standard for tabular ranking (LightGBM's lambdarank objective). Modern alternates (softmax/ ListNet losses, differentiable sorting relaxations) exist; the lambda trick is the load-bearing idea to own — your lab implements it on a linear scorer where its effect is isolated and testable.

Chapter 6: Features and the Two-Stage Composition

The ranker's feature vector, by provenance:

  • Query features: length, type/intent class, historical CTR of the query.
  • Document features: quality/popularity priors, freshness, length.
  • Query-document interaction features — where ranking quality actually lives: BM25 score (Phase 04's scorer becomes a feature), dense similarity, field-level matches (title vs body), historical query-doc engagement.
  • The composition pattern to internalize: first-stage scores are second-stage features — retrieval, fusion, and ranking aren't competitors but stages, each consuming the previous one's outputs. (This is also why LTR "beats RRF" in Phase 04's framing: it includes it.)
  • Tabular rankers (LambdaMART) want engineered interactions; neural rankers (two-tower for scale — Phase 06; cross-encoders for quality — LLM track Phase 07) trade feature engineering for representation learning and serving cost. The pragmatic production stack is still: retrieval → GBDT ranker → (sometimes) a neural re-ranker on the top handful.

Chapter 7: Clicks Are Biased Labels

The label problem that defines industrial LTR: editorial labels are scarce; clicks are infinite — and clicks conflate relevance with examination. The examination hypothesis: $P(\text{click}) = P(\text{examined at its position}) \cdot P(\text{relevant})$. Users don't see rank 50, so it never gets clicked, so it looks irrelevant, so it stays at rank 50: training on raw clicks freezes the current ranking's prejudices (a feedback loop — Phase 06 meets its recsys twin).

The counterfactual-LTR response, at working level:

  • Estimate examination propensities $p_{pos}$ (position-bias curves — via result randomization/swap experiments, or jointly with relevance).
  • Inverse propensity weighting: weight each click by $1/p_{pos}$ — an unbiased (if noisy) estimate of relevance-driven clicks. Extension B builds the simulation that makes this visceral: naive click training provably learns the bias; IPW provably recovers.
  • The operational guards either way: exploration traffic (small randomization budgets), and never evaluating a new ranker only on logs collected under the old one (the same counterfactual sin — Phase 11's experimentation discipline is the real answer).

Chapter 8: Ranking Evaluation Discipline

  • Split by query group, always (Ch. 2's bug). Time-based query splits when the corpus/behavior drifts (it does).
  • Report per-query distributions, not just means: NDCG@10 = 0.71 hides whether hard queries (the head of complaints) are at 0.2; slice by query class (the Phase 04 lesson — navigational vs informational vs long-tail).
  • Compare paired (same queries, two rankers) with the significance machinery of Phase 11/the model-accuracy track — per-query NDCG deltas are the paired samples.
  • Offline ≠ online: NDCG on editorial labels and CTR online can disagree (presentation effects, bias in labels, diversity). The offline metric selects candidates for the A/B test (Phase 11); it doesn't replace it. Saying this sentence in interviews — with why — is a seniority marker.

Lab Walkthrough Guidance

Lab 01 — LTR from scratch, suggested order:

  1. dcg_at_k / ndcg_at_k exactly to Chapter 3's formulas; verify against a fully hand-computed 4-doc example (do the arithmetic on paper first — the test contains the numbers).
  2. Pair generation within query groups: all (i, j) with $rel_i > rel_j$ — and the group-boundary test that ensures no cross-query pairs.
  3. RankNet step on a linear scorer: per pair, $\lambda = -\sigma(-(s_i - s_j))$, accumulate ±λ·x into the gradient. Train on synthetic data; NDCG must rise.
  4. LambdaRank: multiply each pair's λ by |ΔNDCG| computed from the current ranking (swap i, j; recompute the two discount terms — you don't need full re-evaluation; deriving the two-term shortcut is part of the exercise).
  5. The discriminating experiment (provided as a test): data constructed so top-of- list errors and deep-list errors trade off — plain pairwise splits its effort, lambda concentrates at the top, NDCG@5 shows the gap.

Success Criteria

You are ready for Phase 06 when you can, from memory:

  1. Derive NDCG (gains, discount, normalization) and compute it by hand for 4 docs.
  2. State what each objective generation ignores (pointwise: order; pairwise: position impact) and write RankNet's pair gradient.
  3. Explain the zero-gradient obstruction and LambdaRank's gradient-first answer with the |ΔNDCG| factor.
  4. Explain why splits must be query-grouped and what breaks otherwise.
  5. Write the examination hypothesis and the IPW correction, and describe the feedback loop raw-click training creates.
  6. Argue why offline NDCG selects A/B candidates rather than replacing the A/B.

Interview Q&A

Q: Implement NDCG@k. (The actual coding question.) Narrate while writing: gains $2^{rel}-1$ (exponential by convention — top-heavy), discounts $1/\log_2(i{+}1)$, DCG@k as their dot product over the predicted order, IDCG from sorting relevance descending, ratio with the 0/0 → 0 convention, and the test cases you'd write: perfect order = 1, downward swap strictly decreases, invariance below k. The narration of conventions-as-choices is what separates senior answers.

Q: Your ranker improved NDCG offline but CTR dropped in the A/B. Hypotheses? (1) Label-objective mismatch: editorial labels reward relevance; users click on freshness/snippets/diversity the labels don't encode. (2) The offline eval was biased: logs from the old ranker (position bias) — the new ranker's wins were on queries the logs mis-labeled. (3) Presentation interaction: better documents, worse snippets at top. (4) Distribution: offline queries ≠ live mix (slice both). Actions: slice the A/B by query class, inspect rank-1 changes manually, check diversity metrics, and audit label provenance. Concluding "trust the online metric, fix the offline proxy" is the right posture.

Q: Why does everyone still use LambdaMART when neural rankers exist? Tabular interaction features (BM25, CTR priors, engagement counts) carry most industrial ranking signal, and GBDTs exploit them better per unit of compute and tuning than neural nets (the tabular-supremacy result, ranking edition); lambdas give trees a listwise objective; serving is microseconds on CPU. Neural wins arrive with representation problems (raw text/image relevance, cold start, semantic matching) — which is why production stacks are hybrid: GBDT on features that include neural similarity scores (Ch. 6's composition), not either/or.

References

  • Burges, From RankNet to LambdaRank to LambdaMART: An Overview (MSR-TR-2010-82) — the lineage paper; read it after the lab
  • Järvelin & Kekäläinen, Cumulated Gain-Based Evaluation of IR Techniques (2002) — NDCG's origin
  • Joachims, Optimizing Search Engines using Clickthrough Data (KDD 2002) and Joachims et al., Unbiased LTR with Biased Feedback (WSDM 2017) — Ch. 7's foundations
  • LightGBM lambdarank docs and MSLR-WEB10K dataset
  • Liu, Learning to Rank for Information Retrieval (2009) — the survey/book
  • Wang et al., Position Bias Estimation for Unbiased LTR (WSDM 2018)