Suppose the Cranfield collection were a live search service. Its production ranker shows 20 abstracts for each query, and the service logs which ones users click. Clicks cost nothing, arrive by the thousand, and reflect what users wanted, where every relevance judgment has to be made by an assessor. Can a better ranker be chosen, or trained, from the click log alone? It can, but not by counting clicks: a count of clicks mostly records where the production ranker placed each abstract, and a ranker judged or trained on raw clicks is rewarded for agreeing with the one that collected them.
Learning from clicks, also called unbiased or counterfactual learning to rank, treats a click as a relevance judgment that was observed only with some probability, the propensity, which depends on where the result was shown. Dividing each click by its propensity undoes the selection. Joachims, Swaminathan and Schnabel (2017) set out the framework this article follows.
Here is the route. First we state the model of clicking and the loss to be estimated. Then we show what the naive click count estimates, and prove that the propensity-weighted estimate is unbiased, with its variance. Next we estimate the propensities themselves by a small randomized intervention, turn the estimator into a training objective, and work out what click noise does to it. Finally we run all of it on simulated clicks over the Cranfield judgments, where the truth is known, and state the method's limits. The article assumes online evaluation, which measures position bias, describes click models and derives the reweighting estimator for logged actions, and the pairwise loss of RankNet. The numbers are computed by tools/experiments/ltr/learning-from-clicks.py, with exact fractions where a quantity is an expectation and 30 seeded runs where it is a simulation.
The model: examine, then click
Online evaluation introduced the two-factor model of a click: a user clicks a result only if they examine it, which depends on its position, and find it attractive once examined, which depends on the document. Chuklin, Markov and de Rijke (2015, §3.3) call the first part the examination hypothesis: a document is clicked if and only if it was examined and it attracted the user. The simplest model built on it gives each rank its own examination probability and each query-document pair its own attractiveness. This is the position-based model, which Chuklin and colleagues credit to Craswell, Zoeter, Taylor and Ramsey (2008) as its formal introduction:
$$P(\text{click on the result at rank } r) = p_r \cdot P(\text{click} \mid \text{examined}).$$
Here $p_r$ is the probability that the user examines rank $r$. In this article $r$ with a subscript always names a ranking: $r_0(d)$ is the rank at which the production ranker showed document $d$, and $r_f(d)$ is the rank a ranker $f$ under study would give it.
For the derivations we take the simplest form of the second factor, as Joachims and colleagues do in their §5.1: relevance is binary, $\mathrm{rel}(d) \in \{0, 1\}$, and an examined document is clicked exactly when it is relevant. Three consequences follow, and each is used below.
- A click proves relevance. Only relevant documents are ever clicked.
- No click proves nothing. The document may be nonrelevant, or relevant and never examined.
- The probability that a relevant document's relevance is revealed is $p_{r_0(d)}$, which depends only on where it was shown. This is its propensity.
The section on noise relaxes the first assumption. The model is an assumption throughout; the last section says what happens when it is wrong.
The loss. We need a measure of a ranking that is a sum over documents, so that it can be estimated one click at a time. Joachims and colleagues (2017, eq. 2) use the sum of the ranks of the relevant documents:
$$\Delta(f) = \sum_{d} r_f(d)\, \mathrm{rel}(d).$$
Lower is better: a ranker that puts the relevant documents first has a small sum. For one query with relevant documents at ranks 1 and 3 it is 4. The mean of $\Delta(f)$ over queries is the ranker's risk $R(f)$. Nothing below depends on the particular weight $r_f(d)$: the same argument works for any loss of the form $\sum_d \lambda\big(r_f(d)\big)\, \mathrm{rel}(d)$, such as a negative discounted gain with $\lambda(r) = -1/\log_2(1 + r)$, the discount of nDCG.
The running example. For each of the 225 Cranfield queries the candidates are the 20 abstracts that BM25 ranks highest, described by the eight features of the overview's experiment. Among the 4,500 candidates 703 are relevant, 3.124 for each query on average, and 20 queries have none. Eight rankers are compared, each of which sorts the 20 candidates by one feature. The production ranker is the one that sorts by the Binary Independence Model score. It is a weak ranker, seventh of the eight by the true loss, which makes the effect of logging easy to see. Simulated users examine rank $r$ with probability $p_r = 1/r$, the curve online evaluation used: every user reads the first result, half read the second, one in twenty reads the twentieth. The script knows this curve, so every estimate can be compared with the truth.
What a click count estimates
The natural estimate of $\Delta(f)$ from one logged impression adds up the ranks that $f$ gives to the clicked documents:
$$\hat\Delta_{\text{naive}}(f) = \sum_{d\,:\,\text{clicked}} r_f(d).$$
It treats the clicked documents as the relevant ones. Its expectation shows what is wrong with that. A document is clicked with probability $p_{r_0(d)}\,\mathrm{rel}(d)$, so
$$\mathbb{E}\big[\hat\Delta_{\text{naive}}(f)\big] = \sum_{d} p_{r_0(d)}\; r_f(d)\, \mathrm{rel}(d).$$
Each relevant document's term is shrunk by the chance that it was examined, and that chance was set by the production ranker. A relevant document the production ranker showed at rank 20 counts for a twentieth of one it showed first. So a ranker is charged mainly for where it puts the documents that the production ranker already ranked well.
Example (the production ranker grades itself). With $p_r = 1/r$, the naive estimate of the production ranker's own loss is the number of relevant documents, however badly it ranks them. Put $f$ equal to the production ranker, so $r_f(d) = r_0(d)$: each term is $p_{r_0(d)}\, r_0(d)\,\mathrm{rel}(d) = \frac{1}{r_0(d)} \cdot r_0(d) \cdot \mathrm{rel}(d) = \mathrm{rel}(d)$. The expected estimate is $\sum_d \mathrm{rel}(d)$ whatever the production ranker is. On the running example it is 3.124 for every one of the eight rankers when that ranker does the logging, although their true losses run from 21.760 to 31.880.
The exact expectations for the eight rankers, with the Binary Independence Model (BIM) logging, are these. The true loss is the mean of $\Delta(f)$ over the 225 queries, computed from the judgments.
| Ranker (one feature) | True loss $R(f)$ | Expected naive estimate | Rank by truth | Rank by naive estimate |
|---|---|---|---|---|
| BM25 | 21.760 | 2.952 | 1 | 1 |
| proximity | 21.844 | 3.100 | 2 | 2 |
| title BM25 | 22.787 | 4.968 | 3 | 7 |
| TF-IDF | 22.827 | 3.730 | 4 | 6 |
| query likelihood | 23.787 | 3.352 | 5 | 4 |
| coverage | 26.787 | 3.512 | 6 | 5 |
| BIM (the production ranker) | 27.129 | 3.124 | 7 | 3 |
| length (shortest first) | 31.880 | 8.896 | 8 | 8 |
Two things are wrong with the naive column. Its values are on another scale, 3 to 9 where the truth is 22 to 32, because most relevant documents were never examined. That alone would not matter for choosing a ranker. The second fault does: the order is wrong. The production ranker rises from seventh to third, and title BM25, the third best, falls to seventh. Of the 28 pairs of rankers, 9 are ordered one way by the truth and the other way by the expected naive estimate. These are expectations, so no amount of logged data repairs them. With title BM25 as the production ranker instead, the naive estimate rates title BM25 best of the eight, at 3.124 against 4.498 for BM25, which is in truth the better of the two.
Inverse propensity weighting
Here is the idea in one sentence: a clicked document that had only a one-in-twenty chance of being examined stands for twenty relevant documents in its situation, nineteen of which went unseen, so it is counted twenty times. The estimator that does this is called inverse propensity scoring (IPS), or inverse propensity weighting:
$$\hat\Delta_{\text{IPS}}(f) = \sum_{d\,:\,\text{clicked}} \frac{r_f(d)}{p_{r_0(d)}}.$$
Theorem (unbiasedness; Joachims, Swaminathan and Schnabel, 2017, §4). Under the model above, if $p_{r_0(d)} > 0$ for every relevant document $d$, then $\mathbb{E}\big[\hat\Delta_{\text{IPS}}(f)\big] = \Delta(f)$ for every ranker $f$.
Proof. Write $c(d)$ for the indicator that $d$ is clicked, 1 if it is and 0 if not. The sum over clicked documents is a sum over all documents with $c(d)$ as a factor:
$$\hat\Delta_{\text{IPS}}(f) = \sum_{d} c(d)\, \frac{r_f(d)}{p_{r_0(d)}}.$$
The ranks $r_f(d)$ and $r_0(d)$ are fixed numbers once the query is given; only the clicks are random. By linearity of expectation, which needs no independence between the clicks,
$$\mathbb{E}\big[\hat\Delta_{\text{IPS}}(f)\big] = \sum_{d} \mathbb{E}[c(d)]\, \frac{r_f(d)}{p_{r_0(d)}} = \sum_{d} p_{r_0(d)}\, \mathrm{rel}(d)\, \frac{r_f(d)}{p_{r_0(d)}} = \sum_d r_f(d)\, \mathrm{rel}(d) = \Delta(f).$$
The second equality uses $\mathbb{E}[c(d)] = P(c(d) = 1) = p_{r_0(d)}\,\mathrm{rel}(d)$. The third cancels the propensity, which is allowed because it is positive wherever $\mathrm{rel}(d) = 1$; where $\mathrm{rel}(d) = 0$ the term is zero before and after. $\blacksquare$
Averaging over logged impressions gives an unbiased estimate of the risk $R(f)$, since each impression's query is drawn from the query distribution and the estimate is unbiased for each query. On the running example the script computes the expectation of the weighted estimate in exact fractions for all eight rankers, and each equals the true loss in the table exactly.
Three features of the proof are worth stating, because each is used later.
- Only clicked documents need a propensity. The estimator never asks whether an unclicked document was examined, or whether it is relevant. Joachims and colleagues point this out as the property that makes the estimator computable: negative judgments are never needed.
- The condition is positivity for relevant documents. A relevant document that the production ranker never shows has propensity zero, never produces a click, and is missing from every estimate. Nothing can be learned about it from this log.
- The new ranker enters only through $r_f(d)$. One log evaluates any number of rankers, including rankers that did not exist when it was collected. That is what "counterfactual" refers to: the estimate answers what the loss would have been had $f$ been serving.
How this differs from reweighting logged actions. Online evaluation proves a similar result for the estimator of Horvitz and Thompson: an outcome is divided by the probability that the logging system chose the action it did. There the logging system had to randomize, and the probability belonged to its choice. Here the production ranker is deterministic and shows every user the same list. The randomness is the user's: whether they examined a rank. The propensity is the probability that a judgment was revealed, not that an action was taken. That is why this method can use ordinary logs, and also why it needs a model of the user that the earlier estimator did not.
The price: variance
Unbiasedness says the estimate is right on average, not that one log gives a good estimate. Suppose, as the position-based model does, that clicks at different ranks are independent given the query. The term of a relevant document $d$ is $r_f(d)/p$ with probability $p = p_{r_0(d)}$ and 0 otherwise. Its second moment is $p \cdot r_f(d)^2/p^2 = r_f(d)^2/p$ and its mean is $r_f(d)$, so its variance is
$$\frac{r_f(d)^2}{p} - r_f(d)^2 = r_f(d)^2\, \frac{1 - p}{p}.$$
The variances of independent terms add, so for one query
$$\operatorname{Var}\big[\hat\Delta_{\text{IPS}}(f)\big] = \sum_{d} \mathrm{rel}(d)\; r_f(d)^2\; \frac{1 - p_{r_0(d)}}{p_{r_0(d)}}.$$
The same calculation for the naive estimate gives $\sum_d \mathrm{rel}(d)\, r_f(d)^2\, p_{r_0(d)}\big(1 - p_{r_0(d)}\big)$. The weighted estimate's variance grows as $1/p$ where the naive one's shrinks as $p$: a relevant document shown at rank 20 contributes $19\, r_f(d)^2$ to the first and $0.0475\, r_f(d)^2$ to the second. On the running example, one impression's estimate of BM25's loss has variance 3,530.5 with weighting and 24.92 without, and one impression's weighted estimate of the production ranker's own loss has variance 5,381.7. (These include the variation between queries, by the law of total variance; the script computes them exactly.) From $N$ impressions the standard error is the square root of the variance over $N$: for BM25 and $N = 20{,}000$ it is $\sqrt{3530.5/20000} = 0.420$. Bias does not shrink with $N$, and variance does. The naive estimate is precisely wrong; the weighted estimate is right within a margin that more data narrows.
Estimating the propensities
The estimator divides by $p_r$, which no log states. The second contribution of Joachims and colleagues (2017, §5.3) is a way to measure it with a small experiment.
Two observations make the experiment cheap. First, the propensities are needed only up to a common factor. If every $p_r$ is multiplied by a constant $\kappa > 0$, every estimate $\hat\Delta_{\text{IPS}}(f)$ is divided by $\kappa$, and the order of any two rankers, and the minimizer of any training objective built from the estimate, are unchanged. So it is enough to learn the ratios $p_r / p_1$. Second, a ratio can be read from the click rate of one document shown in two places.
The swap intervention. Choose a landmark rank, here rank 1. For a small share of impressions, before showing the list, exchange the result at rank 1 with the result at rank $r$. Let $d^\ast$ be the document that the production ranker put first, and let $a$ be the probability that $d^\ast$ is clicked once examined, averaged over the queries and users that reach the experiment. Under the position-based model,
$$P(d^\ast \text{ clicked} \mid \text{not swapped}) = p_1 \cdot a, \qquad P(d^\ast \text{ clicked} \mid \text{swapped with rank } r) = p_r \cdot a.$$
The factor $a$ is the same on both sides, because the swap changes where $d^\ast$ is shown and nothing about the document, the query or the user. Dividing,
$$\frac{P(d^\ast \text{ clicked} \mid \text{swapped with rank } r)}{P(d^\ast \text{ clicked} \mid \text{not swapped})} = \frac{p_r}{p_1}.$$
Both click rates can be estimated from counts, so their ratio estimates $p_r/p_1$. The argument needs random assignment of impressions to swaps, so that the same mix of queries reaches each arm. It does not need the top documents to be relevant, or equally relevant: whatever $a$ is, it cancels.
Joachims and colleagues ran this on a search engine for arXiv with landmark rank 1 and a swap position drawn uniformly from the first 21 ranks, for seven days (§7.6). They contrast its impact on users with the uniform randomization of results used in earlier work for a different propensity estimation problem, which they describe as of much higher impact (§5.3).
On the running example. The simulated experiment has 200,000 impressions, each with a random query and a swap rank drawn uniformly from 1 to 20 (rank 1 means no swap), so about 10,000 impressions for each rank. The production ranker's first document is relevant for 57 of the 225 queries, so about a quarter of the unswapped impressions produce a click on it. Over 30 seeded repetitions:
| Rank $r$ | True $p_r / p_1$ | Estimate, median | Interquartile range | Clicks on $d^\ast$, median |
|---|---|---|---|---|
| 1 | 1.000 | 1.000 | 2,539 | |
| 2 | 0.500 | 0.501 | 0.493 to 0.506 | |
| 5 | 0.200 | 0.199 | 0.192 to 0.206 | |
| 10 | 0.100 | 0.099 | 0.096 to 0.105 | |
| 20 | 0.050 | 0.051 | 0.049 to 0.053 | 130 |
The estimates are centered on the truth, and their relative error grows with the rank: the median relative error is 0.014 at rank 2 and 0.055 at rank 20, where the estimate rests on 130 clicks. The low ranks are where precision is hardest to get and matters most, since those propensities are the ones that become large weights. Problem 2 computes the standard error of such a ratio.
From estimator to training objective
An unbiased estimate of the risk can be minimized. Joachims and colleagues call this propensity-weighted empirical risk minimization: choose the ranker in a family that minimizes the average of $\hat\Delta_{\text{IPS}}$ over the log. The rank of a document is not a differentiable function of the scores, so, as everywhere in this unit, a smooth bound replaces it.
Let $s_d$ be the score a model gives document $d$. If no two scores are equal, the rank of $d$ is one more than the number of documents that outscore it:
$$r_f(d) - 1 = \sum_{d' \ne d} \big[\, s_{d'} > s_d \,\big] \;\le\; \sum_{d' \ne d} \log_2\!\big(1 + e^{-(s_d - s_{d'})}\big).$$
The inequality holds term by term. If $s_{d'} > s_d$ the exponent is positive, so the argument of the logarithm exceeds 2 and the right side exceeds 1, the value of the indicator. If $s_{d'} < s_d$ the indicator is 0 and the right side is positive. The bound on each term is the pairwise loss of RankNet with $\sigma = 1$, measured in bits. Substituting it into the weighted estimate gives the objective
$$\hat{L}_{\text{IPS}}(f) = \frac{1}{N} \sum_{\text{impressions}}\; \sum_{d\,:\,\text{clicked}} \frac{1}{p_{r_0(d)}} \sum_{d' \ne d} \log_2\!\big(1 + e^{-(s_d - s_{d'})}\big),$$
which is an upper bound on the weighted estimate of the mean of $\Delta(f) - \sum_d \mathrm{rel}(d)$. Each click becomes a set of pairwise preferences, the clicked document over every other candidate, with the weight of the click. Joachims and colleagues make the same move with the hinge loss in place of the logistic loss and obtain a ranking SVM whose slack variables carry the weights $1/p$, which they call Propensity SVM-Rank (§6). Ranking SVM derives the unweighted method.
The proof of the theorem applies to the objective unchanged. For fixed scores, the inner sum over $d'$ is a fixed number for each $d$, just as $r_f(d)$ was. So
$$\mathbb{E}\big[\hat{L}_{\text{IPS}}(f)\big] = \mathbb{E}_{q}\Big[\sum_{d} \mathrm{rel}(d) \sum_{d' \ne d} \log_2\!\big(1 + e^{-(s_d - s_{d'})}\big)\Big],$$
which is the objective one would write down with the judgments in hand. Training on weighted clicks is, in expectation, training on the judgments. The unweighted objective has $p_{r_0(d)}\,\mathrm{rel}(d)$ in place of $\mathrm{rel}(d)$: it is training on judgments in which each relevant document has been discounted by the production ranker's opinion of it.
Clicks that are not judgments
Users click nonrelevant results and skip relevant ones. Joachims and colleagues (2017, §5.2) add this to the model: an examined relevant document is clicked with probability $\epsilon_+$, and an examined nonrelevant one with probability $\epsilon_-$, where $1 \ge \epsilon_+ > \epsilon_- \ge 0$. They show that the weighted estimate is then biased, but that the bias preserves the order of any two rankers in expectation. For the rank-sum loss the bias can be written out exactly, which gives a little more than the order.
Proposition. Under the noisy model, for a query with $n$ candidates, all with positive propensity,
$$\mathbb{E}\big[\hat\Delta_{\text{IPS}}(f)\big] = (\epsilon_+ - \epsilon_-)\,\Delta(f) + \epsilon_-\,\frac{n(n+1)}{2}.$$
Proof. The click probability of $d$ is now $p_{r_0(d)}\,\alpha(d)$, where $\alpha(d) = \epsilon_+$ if $d$ is relevant and $\epsilon_-$ if not, that is, $\alpha(d) = \epsilon_- + (\epsilon_+ - \epsilon_-)\,\mathrm{rel}(d)$. The steps of the theorem's proof, with $\alpha(d)$ in place of $\mathrm{rel}(d)$, give
$$\mathbb{E}\big[\hat\Delta_{\text{IPS}}(f)\big] = \sum_d \alpha(d)\, r_f(d) = (\epsilon_+ - \epsilon_-) \sum_d \mathrm{rel}(d)\, r_f(d) + \epsilon_- \sum_d r_f(d).$$
The first sum is $\Delta(f)$. The second is the sum of the ranks of all $n$ candidates, and since $f$ assigns the ranks $1, 2, \dots, n$ once each, it is $n(n+1)/2$ for every $f$. $\blacksquare$
The expected estimate is an increasing linear function of the true loss, the same function for every ranker, so the ranker with the smallest true risk has the smallest expected estimate. The constant $n(n+1)/2$ is where the argument uses the shape of the loss: for another weight $\lambda(r)$ the second sum is $\sum_r \lambda(r)$, again the same for every $f$. On the running example with $\epsilon_+ = 1$ and $\epsilon_- = 1/10$, the script confirms in exact fractions that the expected weighted estimate of every one of the eight rankers is $0.9\,R(f) + 0.1 \times 210$; for BM25 that is 40.584. The naive estimate has no such property, since its nonrelevant clicks are also weighted by position.
A simulation over the Cranfield judgments
The exact expectations above say what the estimators converge to. The simulation shows what happens with a finite log and estimated propensities. All of it is a simulation of the model stated above on real judgments. It shows the mechanism under that model, and is not evidence about real users.
Estimating the loss of a ranker
Each run draws 20,000 impressions with random queries, lets the simulated users click on the production ranker's lists, and estimates the loss of each ranker three ways: without weights, with the true propensities, and with propensities estimated by a separate swap experiment of 200,000 impressions. Medians and interquartile ranges over 30 seeded runs, for the best ranker and for the production ranker:
| Ranker | True loss | Naive | Weighted, true $p_r$ | Weighted, estimated $p_r$ |
|---|---|---|---|---|
| BM25 | 21.760 | 2.962 (2.940 to 2.977) | 21.82 (21.62 to 22.14) | 22.01 (21.65 to 22.44) |
| BIM | 27.129 | 3.131 (3.119 to 3.151) | 27.26 (26.99 to 27.48) | 27.36 (27.10 to 28.02) |
The weighted estimates land on the true losses to within their spread, which for BM25 agrees with the standard error of 0.420 computed above. The naive estimates are tightly concentrated around their own expectations, 2.952 and 3.124, and are far from the truth. Estimated propensities widen the spread a little and shift the median slightly upward, because an error in a small propensity is magnified in its reciprocal.
For choosing between rankers the difference is decisive. The comparison of title BM25 (true loss 22.787) with the production ranker (27.129) came out the right way in all 30 runs with either weighted estimate, and the wrong way in all 30 runs with the naive estimate. Not every comparison is affected: BM25 was estimated better than the production ranker in all 30 runs by all three estimates.
Training a ranker
Each run now splits the queries at random into 112 for training and 113 for testing. A linear ranker over the eight features is trained on 50,000 simulated impressions of the training queries by the pairwise logistic objective of the previous section, in four ways: without weights, with the true propensities, with estimated propensities, and, as a reference, on the training queries' judgments themselves. Each is tested on the held-out queries against the judgments. MAP and nDCG@10 are computed as in the overview, on the re-ranked 20 candidates followed by the rest of BM25's list; the loss is the mean rank-sum of this article. Medians over 30 seeded runs:
| Trained on | MAP | nDCG@10 | Loss $R(f)$ | Weight on the BIM feature |
|---|---|---|---|---|
| (production ranker, not trained) | 0.259 | 0.302 | 27.2 | |
| clicks, no weights | 0.299 | 0.363 | 22.7 | 3.22 |
| clicks, weighted by true $p_r$ | 0.305 | 0.378 | 20.4 | 0.06 |
| clicks, weighted by estimated $p_r$ | 0.305 | 0.378 | 20.4 | 0.09 |
| the judgments (full information) | 0.306 | 0.377 | 20.4 | 0.04 |
The weighted rankers match the ranker trained on the judgments: the largest difference in MAP between the two over the 30 runs is 0.004. The unweighted ranker is worse on every measure. The last column shows why. The BIM feature is the production ranker's own score. Given the judgments, the model finds it nearly useless beside the other seven features, with a weight of 0.04. Given unweighted clicks, it receives a weight of 3.22, the largest of the eight: the clicks are concentrated on documents with a high BIM score, because those are the documents users examined. The unweighted learner has learned, in part, to imitate the ranker that collected its data.
Example (a common misstatement). "Weighting always helps." In this experiment the weighted ranker had the higher test MAP than the unweighted one in 23 of the 30 runs, not in all of them. The gap between the two medians, 0.006 in MAP, is small beside the variation between runs, each with its own split of the queries and its own clicks: the interquartile ranges of test MAP over the 30 runs are from 0.297 to 0.316 for the weighted ranker and from 0.292 to 0.313 for the unweighted one. With a production ranker close to the best, the gap in MAP can vanish or reverse. Rerun with the proximity ranker, second of the eight by true loss, as the production ranker, the weighted ranker had the higher test MAP in only 8 of the 30 runs, and its median MAP, 0.306, was below the unweighted ranker's 0.311 and the same as the production ranker's own, 0.306 (the interquartile ranges of test MAP in this rerun are from 0.297 to 0.316 for the weighted ranker and from 0.302 to 0.318 for the unweighted one). Its median nDCG@10 was also lower, 0.378 against 0.381. On the loss $R(f)$, which the weighted objective bounds, it was still ahead, with a median of 20.3 against 20.8 (lower is better). Why the order reversed on MAP and nDCG@10 was not tested. One candidate is that a learner that imitates a good production ranker loses little by it while the weights add variance, but the script did not measure that variance. Weighting removes a bias; how much that bias costs depends on how wrong the production ranker is and on what features can express the error. Joachims and colleagues report the corresponding observation from their experiments on the Yahoo! Learning to Rank Challenge data: weighting helps whenever the bias is substantial, and more training data improves the weighted method while leaving the naive one unchanged (§7.3).
With noisy clicks, $\epsilon_- = 0.1$, the same experiment gives a larger gap. The unweighted ranker falls to a MAP of 0.289 and an nDCG@10 of 0.347 with a loss of 24.1. The weighted rankers stay at 0.308 and 0.379 or 0.380 with losses of 20.4 and 20.3, and the weighted ranker has the higher MAP in 29 of 30 runs. Noise clicks are spread over nonrelevant documents in proportion to how often they were examined, which adds a second position-shaped error to the unweighted objective.
The proposition does not by itself explain why the weighted ranker is unharmed. It concerns the rank-sum estimate, in which noise adds only a constant, while the ranker is trained on the pairwise bound. The same calculation for the training objective, with $\ell(x) = \log_2(1 + e^{-x})$ and $\alpha(d) = \epsilon_- + (\epsilon_+ - \epsilon_-)\,\mathrm{rel}(d)$ in place of $\mathrm{rel}(d)$, gives
$$\mathbb{E}\big[\hat{L}_{\text{IPS}}(f)\big] = (\epsilon_+ - \epsilon_-)\,\mathbb{E}_q\Big[\sum_d \mathrm{rel}(d) \sum_{d' \ne d} \ell(s_d - s_{d'})\Big] + \epsilon_-\,\mathbb{E}_q\Big[\sum_{\{d, d'\}} \big(\ell(s_d - s_{d'}) + \ell(s_{d'} - s_d)\big)\Big].$$
The first term is the full-information objective, scaled. The second comes from $\epsilon_- \sum_d \sum_{d' \ne d} \ell(s_d - s_{d'})$, a sum over every ordered pair of candidates, which collects into a sum over unordered pairs $\{d, d'\}$, each taken in both orders. It is not a constant. For one pair with score difference $x$, $\ell(x) + \ell(-x) = \log_2\big((1 + e^{-x})(1 + e^{x})\big) = \log_2(2 + e^{x} + e^{-x})$, which is 2 at $x = 0$ and grows with $|x|$. It is the same for $x$ and $-x$, so it prefers no order of any pair; what it penalizes is distance between scores, and for a linear model it pulls the weights toward zero. To see why, write $\phi(x) = \ell(x) + \ell(-x)$ and $\Delta = \mathbf{x}_d - \mathbf{x}_{d'}$ for a pair, so that the pair contributes $\phi(\mathbf{w}^{\mathsf{T}}\Delta)$. The gradient of the term is the sum over pairs of $\phi'(\mathbf{w}^{\mathsf{T}}\Delta)\,\Delta$, and its inner product with $\mathbf{w}$ is the sum of $\phi'(x)\,x$ with $x = \mathbf{w}^{\mathsf{T}}\Delta$. Each of these products is at least 0, since $\phi$ is even and increasing in $|x|$, so that $\phi'(x)$ has the sign of $x$. The gradient therefore never points toward the origin, and a small enough step against it shortens $\mathbf{w}$ whenever the inner product is positive. The run shows the pull. The median weights of the weighted ranker with noise are about half of those without: +1.85 against +3.74 on BM25, −0.77 against −1.57 on query likelihood and −0.64 against −1.34 on coverage. Over the other features the factors run from 0.44 on proximity to 0.61 on title BM25, leaving out the BIM feature, whose weight is near zero with and without noise. To rule out slow training as the cause, the script also minimizes the expected objective itself on the first run's training queries, to convergence (3,000 steps; doubling them changes no weight by as much as 0.001): the BM25 weight is 4.38 without noise and 1.98 with it, a factor of 0.45. The pull is not a rescaling. In the same minimization the factor is 0.18 for TF-IDF and 0.55 for title BM25, and the small weight on log length grows, from 0.04 to 0.13. So the noise changes the direction of the weight vector as well as its length, though here only a little: the cosine between the two converged weight vectors is 0.990. A linear ranker's ranking depends only on the direction of its weight vector, so the shrinking alone would change nothing, and the change of direction did not hurt the rankings here: the weighted ranker's median MAP was 0.305 without noise and 0.308 with it.
Limits
- Documents that were never shown. The theorem needs a positive propensity for every relevant document. In the running example every candidate is shown and the smallest propensity is 0.05. A real results page shows ten results of thousands, and the relevant documents below the cut are invisible to the method. The weighted estimate is then unbiased for the loss over the shown documents only.
- Large weights. Nineteen relevant documents sit at rank 20 of the production ranker's lists, and each click on one is counted twenty times. A handful of such clicks can dominate an estimate. Joachims and colleagues include a clipped variant, which caps the weights, among their experiments, and observe that overestimating small propensities is tolerable where underestimating them can be harmful (§7.5). Problem 4 shows the trade on one document.
- The model can be wrong. The position-based model says examination depends on the rank alone. In the cascade model of Craswell and colleagues (2008), as Chuklin, Markov and de Rijke (2015, §3.4) describe it, a user reads from the top and the chance of reaching a result depends on the results above it; and online evaluation describes trust bias, in which the position changes the click decision itself. Under either, a single number per rank is not the right propensity. Joachims and colleagues list both as extensions (§5.4).
- Interventions cost something. Swapping results degrades what users see. Wang, Golbandi, Bendersky, Metzler and Najork (2018) measured the cost of two randomization schemes on email and file-storage search, found that randomizing the top results harmed users more than swapping adjacent pairs, and proposed estimating the position bias from ordinary click logs with a regression-based expectation-maximization algorithm, without randomization.
What is proved, what is cited, what the experiment shows
Proved on this page: the expectation of the naive estimate, and that with $p_r = 1/r$ it grades every production ranker's own lists at the number of relevant documents; the unbiasedness of the weighted estimate; its variance under independent clicks; that the swap intervention's click rates are in the ratio of the propensities; the pairwise logistic bound on the rank, and that the weighted objective has the full-information objective as its expectation; the exact form of the expected weighted estimate under click noise, and of the expected training objective, whose noise term penalizes differences between scores without preferring any order.
Cited: the examination hypothesis and the position-based model (Chuklin, Markov and de Rijke, 2015; Craswell et al., 2008); the framework, the swap intervention, the order-preservation under noise and Propensity SVM-Rank (Joachims, Swaminathan and Schnabel, 2017), together with their experimental findings; the cost of randomization and its alternative (Wang et al., 2018).
Shown by the experiment, for simulated users on Cranfield: the sizes of the bias and of the variance; that propensities estimated from 200,000 swapped impressions serve nearly as well as the true ones; that a ranker trained on weighted clicks matched one trained on the judgments, and that the unweighted ranker put a large weight on the production ranker's own feature; that click noise shrank the weighted ranker's weights by different factors, about half on the largest, changing their direction a little without lowering its MAP; and that with a better production ranker the weighted ranker's MAP and nDCG@10 fell below the unweighted ranker's while its loss $R(f)$ stayed lower, for reasons not tested.
Worked problems
This unit has no course assignments, so the problems below are posed on small exact cases and on the running example. The script recomputes every number.
Problem 1 (the three estimates on three documents). A production ranker shows documents $a, b, c$ in that order. Users examine the three ranks with probabilities $1$, $1/2$ and $1/4$, and click an examined document exactly when it is relevant. Documents $a$ and $c$ are relevant. A new ranker would show $c, a, b$. Find the true loss of both rankings, the expected naive estimate of both, and the distribution, mean and variance of the weighted estimate of the new ranking.
Solution. The true losses are 4 for the old ranking and 3 for the new; the naive estimate expects 7/4 and 9/4, preferring the wrong one; the weighted estimate of the new ranking is 2 with probability 3/4 and 6 with probability 1/4, with mean 3 and variance 3.
The old ranking has relevant documents at ranks 1 and 3, so $\Delta = 1 + 3 = 4$. The new ranking has $c$ at rank 1 and $a$ at rank 2, so $\Delta = 1 + 2 = 3$: the new ranker is better. Document $a$ is clicked with probability 1 and $c$ with probability $1/4$. The naive estimate of the old ranking expects $1 \cdot 1 + \tfrac14 \cdot 3 = 7/4$, and of the new ranking $1 \cdot 2 + \tfrac14 \cdot 1 = 9/4$. The naive estimate charges the new ranker fully for moving $a$ down a rank and credits it only a quarter for moving $c$ up two.
For the weighted estimate of the new ranking, a click on $a$ contributes $r_f(a)/p_1 = 2/1 = 2$ and a click on $c$ contributes $r_f(c)/p_3 = 1/(1/4) = 4$. Document $a$ is always clicked, so the estimate is 2 when $c$ is not clicked (probability 3/4) and $2 + 4 = 6$ when it is (probability 1/4). The mean is $\tfrac34 \cdot 2 + \tfrac14 \cdot 6 = 3$, the true loss. The variance is $\tfrac34 \cdot 4 + \tfrac14 \cdot 36 - 9 = 3$, which agrees with the formula: $a$ contributes $2^2 (1 - 1)/1 = 0$ and $c$ contributes $1^2 \cdot (3/4)/(1/4) = 3$.
Problem 2 (a propensity from a swap, with its uncertainty). In a swap experiment the production ranker's first document was clicked 300 times in 1,000 impressions when left at rank 1, and 81 times in 1,000 impressions when swapped to rank 4. Estimate $p_4/p_1$ and give an approximate standard error.
Solution. The estimate is 0.27, with a relative standard error of about 0.117, so about $0.27 \pm 0.03$. The click rates are $300/1000 = 0.3$ and $81/1000 = 0.081$, and their ratio is $0.081/0.3 = 0.27$. A proportion $\hat{x}$ from $m$ independent trials has variance $x(1 - x)/m$, so its relative variance, the variance divided by the square of the mean, is $(1 - x)/(m x)$: with the estimates plugged in, $0.919/81 = 0.01135$ for the swapped arm and $0.7/300 = 0.00233$ for the other. For a ratio of two independent estimates with small relative errors, the relative variances add to first order. So the relative standard error is $\sqrt{0.01135 + 0.00233} = 0.117$, and the standard error is $0.27 \times 0.117 = 0.03$. The script checks the first-order formula against 200,000 simulated ratios. Almost all of the uncertainty comes from the arm with 81 clicks: it is the count of clicks at the low rank, not the number of impressions, that decides the precision.
Problem 3 (noise). A query has four candidates. A ranker $f$ places the two relevant ones at ranks 1 and 3. Users click an examined relevant document always and an examined nonrelevant one with probability $1/10$. All propensities are positive and known. Find the expected weighted estimate of $\Delta(f)$, and say what the estimate can and cannot be used for.
Solution. The expected estimate is 4.6, where the true loss is 4. By the proposition with $\epsilon_+ = 1$, $\epsilon_- = 1/10$ and $n = 4$, it is $0.9 \times 4 + 0.1 \times \tfrac{4 \cdot 5}{2} = 3.6 + 1.0 = 4.6$. Directly: the relevant documents contribute their ranks, $1 + 3$, and the nonrelevant ones at ranks 2 and 4 contribute a tenth of theirs, $0.2 + 0.4$. The estimate cannot be read as the loss. It can be used to compare rankers on this query, because every ranker's expected estimate is the same increasing function $0.9\,\Delta + 1$ of its true loss. If $\epsilon_-$ and $\epsilon_+$ were known, the true loss could be recovered as $(4.6 - 1)/0.9 = 4$.
Problem 4 (clipping one large weight). A relevant document was shown at rank 20, with propensity $1/20$, and a new ranker puts it first. Compare its term in the weighted estimate with its term when propensities below $1/10$ are replaced by $1/10$.
Solution. Unclipped, the term has mean 1 and variance 19; clipped, it has mean 0.5 and variance 4.75. Unclipped, the term is $1/(1/20) = 20$ with probability $1/20$ and 0 otherwise: the mean is 1, the document's true contribution $r_f(d) = 1$, and the variance is $1^2 \cdot (19/20)/(1/20) = 19$. Clipped, the term is $1/(1/10) = 10$ with probability $1/20$: the mean is $0.5$, and the variance is $100 \cdot \tfrac{1}{20} \cdot \tfrac{19}{20} = 4.75$. Clipping has divided the variance by four and introduced a bias: the document now counts for half of what it should. In the running example 19 relevant documents were shown at rank 20 and carry this weight. Whether the trade is worth making depends on the size of the log, since the variance falls with more impressions and the bias does not.
What we have learned
A click reveals relevance only if the result was examined, and examination depends on where the production ranker put the result. Counting clicks therefore estimates a loss in which each relevant document is discounted by the production ranker's placement of it: with examination probability $1/r$, every production ranker scores its own lists at the number of relevant documents, and on the Cranfield example the seventh-best of eight rankers is rated third. Dividing each click by its propensity gives an estimate whose expectation is the true loss, by a three-line proof that needs propensities only for clicked documents and positivity only for relevant ones. The cost is variance that grows as the reciprocal of the smallest propensities. The propensities can be measured up to a constant by swapping the first result with another and comparing click rates. The weighted estimate is bounded above by a weighted pairwise loss, and a ranker trained on it matched one trained on the judgments in the simulation, while the unweighted ranker learned to imitate the production ranker.
This article closes the unit. Its methods all took the features as given; Features for Ranking, the unit's first article, is where they come from, and the unit page lists the rest.
References
- Chuklin, A., Markov, I., and de Rijke, M. (2015). Click Models for Web Search. Morgan & Claypool. record · 2 pages
- Craswell, N., Zoeter, O., Taylor, M., and Ramsey, B. (2008). An experimental comparison of click position-bias models. In Proceedings of WSDM 2008, 87–94. record · 2 pages
- Joachims, T., Swaminathan, A., and Schnabel, T. (2017). Unbiased learning-to-rank with biased feedback. In Proceedings of WSDM 2017, 781–789. https://doi.org/10.1145/3018661.3018699 record
- Wang, X., Golbandi, N., Bendersky, M., Metzler, D., and Najork, M. (2018). Position bias estimation for unbiased learning to rank in personal search. In Proceedings of WSDM 2018, 610–618. record