Learning to rank

By the set over which a single term of the loss is computed, and everything else follows from that.

Pointwise models relevance itself (BCE on 0/1) — it gives calibrated probabilities but knows nothing about order or the structure of the slate: a mistake at position 1 and at position 50 are punished identically.

Pairwise models the observed order — it is aligned with AUC, because AUC is the share of correctly ordered pairs, but it loses calibration by construction.

Listwise models the structure of the slate — it is closest to NDCG, more expensive to train and even worse calibrated.

We postulate \(P(i^+ \succ i^- \mid u) = \sigma(f(u,i^+) - f(u,i^-))\). The likelihood of all observed preferences is a product of such probabilities; take the logarithm and flip the sign:

\(\mathcal{L}_{\mathrm{BPR}} = -\sum_{i^+ \in P}\sum_{i^- \in N} \log \sigma\bigl(f(u,i^+)-f(u,i^-)\bigr)\)

Two properties have to be named at once. The loss depends only on the difference of scores — so it is invariant to a shift and gives no calibration. And the gradient with respect to the positive's score equals \(-\sigma(-\Delta)\): a pair inverted by 3 weighs 0.95, one already separated by 3 weighs 0.047, that is, 20 times less. Mining of hard pairs is built into the shape of the loss.

Both metrics depend only on the order, and any monotone transformation of the score preserves the order. So a calibrated model and its own score passed through a monotone function are indistinguishable by AUC and NDCG.

It starts to hurt exactly when the score takes part in arithmetic. An example: five products, the ranking by score is the same for both models, but the ranking by expected revenue \(p \cdot \text{price}\) is different; the product that rises to the top has an expected revenue of 30 instead of 90, a loss of 67% at the top position. Log loss meanwhile worsens by 27% — it does see the difference.

Hence the practice: \(pCTR \cdot bid\) in an auction, \(P(\text{buy})\cdot\text{price}\), thresholds for business rules — everywhere a pointwise output is needed, even if the final order is produced by a different loss.

It is a pairwise loss in which every pair is weighted by the change of the metric from swapping it: \(\mathcal{L} = \sum_{(i,j)} \Delta\mathrm{NDCG}_{ij}\log(1+\exp(-s_{ij}(f_i-f_j)))\). The second factor is the same BPR; all the peculiarity is in the first.

Why: NDCG is piecewise constant and not differentiable, so it cannot be optimised directly, but the gradients can be weighted by a pair's contribution to the metric. The spread is enormous — a swap at positions (1,2) gives a ΔNDCG of 0.3691, at (9,10) 0.0120, that is, 31 times less.

And it is listwise because ΔNDCG is computed over the whole slate: you need the positions of all the other documents and the IDCG of the query. A formally pairwise loss carries information about the structure of the entire list.

The loss itself is pairwise, the same BPR. Everything is in the weights \(w_{ij} = N_{ij}\cdot c(l_i,l_j)\).

\(N_{ij}\): the scores are perturbed many times with logistic noise and re-sorted; only the pairs that turn out adjacent get weight, with an addition of \(1/R\) by the position of the adjacency. Hence the position discount is built in, the weight matrix is sparse (no more than 990 pairs out of 4950 at 100 documents and 10 perturbations, that is, linear in n rather than quadratic), and the weights are recomputed at every boosting iteration.

\(c(l_i,l_j)\): the probability that \(i\) really is better than \(j\), given a matrix of labelling errors. The pair «3 against 2» gets a cut weight, the pair «4 against 0» keeps nearly one.

The difference from LambdaRank: the latter weighs a pair by how much the metric changes when it is swapped, proceeding from the assumption that the current order is right. YetiRank weighs it by how likely the pair is to end up adjacent and high at all — that is, it models its own uncertainty explicitly.

Three cases. First, binary labels: the factor \(c(l_i,l_j)\) degenerates and a weighted BPR is all that is left. Second, labels from logs rather than assessors: a click is not «confused», it is biased by position and by impression, and a matrix of labelling errors does not describe that noise; bias corrections are what is needed. Third, when calibration is needed: like any pairwise loss it depends only on differences of scores.

The second case is the most common mistake in applying it: the method is taken into recommendations by analogy with search, where the labels really are from assessors.

The formula is one and the same. The difference is where the set in the denominator came from, and it is fundamental.

In candidate generation the denominator is sampled negatives: we set the distribution ourselves, so we know it and can correct the bias with LogQ. In ranking the denominator is the shown slate, that is, the result of the logging policy; its distribution is not under our control.

Plus a listwise output is particularly badly calibrated: add one strong item to a slate of four and the «probability» of the first falls from 0.4551 to 0.2034 — by 55%, though the item itself did not change.

All of them optimise a proxy under a fixed impression policy. The items the policy never showed are in neither the pointwise sum, nor the pairs, nor the denominator of the softmax — no loss will tell the model about them.

That is the feedback loop: the model learns from what the previous model showed. The circle cannot be broken by the choice of loss — you have to affect the impression policy itself, that is, do exploration.