The worked ranking of this topic has relevant documents at ranks 1, 3, 6 and 9 of ten, and misses a fifth. Evaluating ranked results ended with a table that matched each measure to a user: precision at $k$ for one who reads exactly $k$ results, reciprocal rank for one who stops at the first relevant result, nDCG for one whose attention declines. Those were descriptions in words. Can "models a user" be made exact, so that a measure is derived from a stated model of reading and not merely described by one? It can: write down the probability that the user reads each rank, say what the user gains from each document read, and the measure is the expected gain.
A user model, or browsing model, is a probability model of how a person moves down a ranking: where they start, when they continue, when they stop. Two measures were designed this way from the start. Rank-biased precision (RBP; Moffat and Zobel, 2008) assumes a user who continues past each result with a fixed probability. Expected reciprocal rank (ERR; Chapelle, Metzler, Zhang, and Grinspan, 2009) assumes a user who stops when a document satisfies them. This article is the home of both, and the articles on mean average precision and nDCG refer to it for them.
Here is the route. First we set up the common frame and read precision at $k$ and the DCG discount in it. Then we derive RBP from the persistence model, and its residual, which bounds the effect of unjudged documents. Next we derive ERR from the cascade model. Finally we place average precision in the same frame, compare all the measures on the worked ranking, and compute RBP and ERR on Cranfield. The article assumes evaluating ranked results, mean average precision and nDCG.
Every number is computed by tools/experiments/eval_measures/user_models.py in the site's repository, which also asserts each identity derived below. Values are rounded to three decimals.
Measures as expected gain
A ranking presents documents at ranks $1, 2, 3, \dots$ Write $r_i$ for the gain of the document at rank $i$: 1 or 0 for binary judgments, or a number computed from a grade. A user model supplies probabilities for the user's path through the ranks. The measures in this article are all of one of two kinds.
- Position-based. The chance that the user reads rank $i$ depends only on $i$. The measure is a weighted sum $\sum_i w_i r_i$ with fixed weights. Precision at $k$, DCG and RBP are of this kind.
- Cascade. The chance that the user reads rank $i$ depends on the documents above it, because a good document may end the search. Reciprocal rank, ERR and average precision are of this kind.
Precision at $k$ is the simplest position-based case. The user reads exactly the first $k$ results and no more. Each relevant one is worth 1, and the effort is $k$ documents, so the gain per document read is
$$P@k = \frac{1}{k} \sum_{i=1}^{k} r_i.$$
The weights are $w_i = 1/k$ for $i \le k$ and 0 beyond. They sum to 1, so $P@k$ is also the probability that a document drawn uniformly from the top $k$ is relevant. For the worked ranking, $P@5 = 2/5 = 0.4$ and $P@10 = 4/10 = 0.4$. The model's weakness is visible in its weights: the user is certain to read rank $k$ and certain not to read rank $k + 1$.
The DCG discount softens the cliff. In its common form (nDCG gives the variants), DCG weights rank $i$ by $1/\log_2(i + 1)$, which falls slowly and never reaches zero. It is tempting to read these weights as the probability of reading rank $i$, and that reading fails in one precise way: the weights cannot be scaled to sum to 1 over an unbounded ranking, because their sum diverges. Since $\log_2(i + 1) \le i$ for every $i \ge 1$ (both sides are 1 at $i = 1$, and from there each step raises the left side by $\log_2((i+2)/(i+1)) \le \log_2(3/2) < 1$ and the right side by 1), each weight is at least $1/i$, and the harmonic series $\sum 1/i$ has no finite sum. The script shows the growth: the first 10 weights sum to 4.54, the first 100 to 20.94, the first 1,000 to 123.09.
So DCG needs a cutoff, and then a normalizer. With a cutoff of 10, the ten weights sum to 4.544. Dividing by that sum makes them probabilities, 0.220 for rank 1 down to 0.064 for rank 10, and the worked ranking's binary DCG@10 of 2.157 becomes $2.157/4.544 = 0.475$: the chance that a document drawn with those probabilities is relevant. nDCG divides by the ideal ranking's DCG instead (2.948 here, giving 0.732), which answers a different question: how close the ranking is to the best one possible for this query. The logarithmic discount is therefore a choice of weights. Järvelin and Kekäläinen (2002, §2.2), whose own form divides by $\log_b i$ from rank $b$ on and leaves the earlier ranks undiscounted, present it that way: a function chosen to fall off gently, with a base to be set to suit the searcher's persistence. It was not derived from a model of when users stop. RBP was.
Rank-biased precision
Here is the idea in one sentence: a user who reads on with probability $p$ after every result reaches rank $i$ with probability $p^{i-1}$, and RBP is the number of relevant documents that user expects to see for each document read.
The persistence model. The user always reads the first result. After each result, whatever it was, the user goes on to the next with probability $p$ and stops with probability $1 - p$, independently each time. The parameter $p$, between 0 and 1, is the user's persistence. To reach rank $i$ the user must continue $i - 1$ times, so
$$P(\text{user reads rank } i) = p^{\,i-1}.$$
Derivation. Two expectations are needed. The expected number of documents read is the sum over ranks of the probability of reading each, a geometric series:
$$\sum_{i=1}^{\infty} p^{\,i-1} = \frac{1}{1 - p}.$$
With $p = 0.5$ the user reads 2 documents on average, with $p = 0.8$ five, and with $p = 0.95$ twenty. The expected number of relevant documents read, by the same reasoning, is $\sum_i r_i\, p^{\,i-1}$. Rank-biased precision is the ratio of the two, the expected rate at which the user meets relevant documents:
$$\mathrm{RBP} = (1 - p) \sum_{i=1}^{\infty} r_i\, p^{\,i-1}.$$
This is the formula of Moffat and Zobel (2008). The weight of rank $i$ is $(1 - p)\,p^{\,i-1}$, and it has a second reading. It is the probability that the user reads rank $i$ and then stops, that is, the probability that rank $i$ is the last document read. So RBP is also the probability that the last document the user reads is relevant. The weights are a geometric distribution, and they sum to 1.
On the worked ranking. The relevant documents are at ranks 1, 3, 6 and 9, so the sum has four terms, $p^0 + p^2 + p^5 + p^8$. With $p = 0.8$:
$$\mathrm{RBP} = 0.2 \times (1 + 0.640 + 0.328 + 0.168) = 0.2 \times 2.135 = 0.427.$$
| Persistence $p$ | Documents read on average | RBP of the worked ranking | Residual at depth 10 |
|---|---|---|---|
| 0.5 | 2 | 0.643 | 0.001 |
| 0.8 | 5 | 0.427 | 0.107 |
| 0.95 | 20 | 0.167 | 0.599 |
The impatient user's score is dominated by the relevant document at rank 1, which alone contributes $1 - p = 0.5$. The persistent user spreads the same total weight of 1 over many more ranks, so each of the four relevant documents counts for little, and most of the weight lies beyond rank 10, where this ranking has nothing. A simulation of 200,000 users for each $p$ agrees with all three readings: with $p = 0.8$ the simulated users read 5.004 documents on average, saw 0.4268 relevant documents per document read, and ended on a relevant document 42.71 percent of the time.
Example (RBP does not use the number of relevant documents). The fifth relevant document, which the system never retrieved, appears nowhere in the calculation, and RBP would be the same if the query had four relevant documents or forty. Average precision divides by $R$ and nDCG by an ideal built from all the judged documents; RBP needs neither. That is its practical attraction for collections where $R$ is unknown. It is also why RBP is not normalized per query. The best possible ranking for a query with $R$ relevant documents puts them at ranks 1 to $R$ and scores $(1 - p)(1 + p + \dots + p^{R-1}) = 1 - p^R$, which is below 1. For $R = 5$ and $p = 0.8$ the ceiling is $1 - 0.8^5 = 0.672$, so the worked ranking's 0.427 is 64 percent of what was attainable.
The residual
The same geometric series gives RBP its most useful property: an exact bound on what the unexamined part of a ranking could change.
Suppose a ranking is judged completely down to depth $d$ and nothing is known beyond. The weight of all the ranks after $d$ is
$$(1 - p) \sum_{i=d+1}^{\infty} p^{\,i-1} = (1 - p) \cdot \frac{p^{\,d}}{1 - p} = p^{\,d}.$$
If every one of those documents were nonrelevant, RBP would be the value computed from the top $d$; if every one were relevant, it would be larger by $p^d$. So the true value lies in an interval of width $p^d$ above the computed one. Moffat and Zobel call the width the residual. Unjudged documents within the top $d$ are handled the same way. Each could add its own weight if it turned out relevant, so with $U$ the set of unjudged ranks in the top $d$,
$$\text{residual} = (1 - p) \sum_{i \in U} p^{\,i-1} \;+\; p^{\,d}, \qquad \mathrm{RBP}_{\text{base}} \;\le\; \mathrm{RBP} \;\le\; \mathrm{RBP}_{\text{base}} + \text{residual},$$
where the base value counts unjudged documents as nonrelevant. The two bounds are attained, by the all-nonrelevant and the all-relevant completions.
For the worked ranking at depth 10 the residual is $p^{10}$, the last column of the table above. With $p = 0.5$ it is 0.001: ten results settle the score. With $p = 0.95$ it is 0.599, more than three times the score itself: for so persistent a user, ten results say little, and the measure reports that openly. The missed fifth relevant document shows what the residual covers. Had it been at rank 11, it would add $(1 - p)\,p^{10} = 0.021$ at $p = 0.8$, well inside the residual of 0.107.
Example (two unjudged documents). Suppose, as in implementing evaluation measures, that the documents at ranks 2 and 4 were never judged. The base value is unchanged, 0.427 at $p = 0.8$, and the residual grows by the weights of those two ranks: $0.2 \times (0.8 + 0.8^3) + 0.8^{10} = 0.262 + 0.107 = 0.370$. The score is reported as 0.427 with a residual of 0.370, that is, somewhere between 0.427 and 0.797. If both documents are in fact relevant, the true value at depth 10 is 0.690, inside the interval. Average precision gives a single number in the same situation, 0.522, with no indication that two of the top four results are unknown.
How deep to judge. The residual of a fully judged ranking falls below a tolerance $\varepsilon$ once $p^d \le \varepsilon$, that is, from depth $d = \lceil \ln \varepsilon / \ln p \rceil$. For $\varepsilon = 0.01$ that is depth 7 at $p = 0.5$, depth 21 at $p = 0.8$ and depth 90 at $p = 0.95$. The choice of $p$ is therefore also a statement of how much judging the measure needs.
What RBP rewards
Moving a relevant document up one place, from rank $k$ to rank $k - 1$, past a nonrelevant one, exchanges the weight $(1 - p)p^{k-1}$ for $(1 - p)p^{k-2}$. The gain is
$$(1 - p)\,p^{\,k-2} - (1 - p)\,p^{\,k-1} = (1 - p)^2\, p^{\,k-2},$$
whatever the rest of the ranking contains. With $p = 0.8$ the move from rank 3 to 2 gains 0.032 and the move from rank 9 to 8 gains 0.008. Compare average precision, where the same move gains $j/(Rk(k-1))$, with $j$ the moved document's position among the relevant documents (one more than the number of relevant documents above it) and $R$ the number that exist. In RBP each document's contribution is independent of every other document. That independence is the mark of a position-based model, and it is the assumption the next model drops.
The cascade model and expected reciprocal rank
The persistence model has the user continue or stop without regard to what was just read. A user who has just found the answer is unlikely to behave that way.
The cascade model. Craswell, Zoeter, Taylor, and Ramsey (2008) proposed a model of clicks in which the user examines results from the top, one at a time. At each result the user either clicks it, with a probability that depends on the document, or skips it and moves to the next. A user who clicks stops; a user who skips always continues. The probability of a click at rank $i$ is then the document's own probability times the probability that every document above was skipped. In a comparison with position-based alternatives on a large log of perturbed rankings, they found that the cascade model best explained the position bias in the top ranks. Online evaluation describes the family of click models this belongs to.
From clicks to a measure. Chapelle, Metzler, Zhang, and Grinspan (2009) turned the cascade model into an effectiveness measure. Let $R_i$ be the probability that the document at rank $i$ satisfies the user. Under the cascade model the user stops at rank $r$ when the documents at ranks 1 to $r - 1$ all failed to satisfy and the one at rank $r$ succeeded:
$$P(\text{user stops at rank } r) = R_r \prod_{i=1}^{r-1} (1 - R_i).$$
A user who stops at rank $r$ has read $r$ documents to be satisfied once, and the measure scores that outcome $1/r$, as reciprocal rank does. Expected reciprocal rank is the expectation of that score:
$$\mathrm{ERR} = \sum_{r=1}^{n} \frac{1}{r}\, R_r \prod_{i=1}^{r-1} (1 - R_i).$$
A user whom no document satisfies contributes 0. It remains to say where $R_i$ comes from. Chapelle and colleagues map the relevance grade $g$ of a document to a probability with the same exponential form as the gain of nDCG:
$$R(g) = \frac{2^{g} - 1}{2^{\,g_{\max}}}, \qquad g \in \{0, 1, \dots, g_{\max}\}.$$
With grades 0 to 3 the probabilities are 0, 1/8, 3/8 and 7/8. Even a document of the top grade leaves a chance of $1/2^{g_{\max}}$ that the user reads on.
Two properties follow at once. First, ERR lies between 0 and 1. The stopping probabilities are those of disjoint events, so they sum to at most 1, and each is multiplied by $1/r \le 1$. Second, ERR generalizes reciprocal rank. If every relevant document satisfied with probability 1 and every nonrelevant one with probability 0, the user would stop at the first relevant document with certainty, the only nonzero term would be that rank's, and ERR would be exactly the reciprocal rank. With the mapping above this limit is never reached, because $R(g_{\max}) < 1$.
On the graded example. The nDCG article's worked example has grades 3, 2, 3, 0, 1, 2 at ranks 1 to 6, with $g_{\max} = 3$:
| Rank $r$ | Grade | $R_r$ | Probability of reaching rank $r$ | Probability of stopping there | Contribution, divided by $r$ |
|---|---|---|---|---|---|
| 1 | 3 | 0.875 | 1.000 | 0.8750 | 0.8750 |
| 2 | 2 | 0.375 | 0.125 | 0.0469 | 0.0234 |
| 3 | 3 | 0.875 | 0.0781 | 0.0684 | 0.0228 |
| 4 | 0 | 0 | 0.0098 | 0 | 0 |
| 5 | 1 | 0.125 | 0.0098 | 0.0012 | 0.0002 |
| 6 | 2 | 0.375 | 0.0085 | 0.0032 | 0.0005 |
| ERR | 0.922 |
Each "reaching" probability is the one above it times $1 - R$ of the rank above: $0.125 = 1 - 0.875$, then $0.125 \times 0.625 = 0.0781$, and so on. The first document alone supplies 0.875 of the 0.922. The second grade-3 document, at rank 3, adds only 0.023, although nDCG credits it with half its gain there. The reason is that only 7.8 percent of users are still reading by rank 3. A fraction 0.0053 of users reach the end unsatisfied.
Example (diminishing returns). The same grade-3 document at rank 3 contributes $0.875/3 = 0.292$ when the two documents above it are nonrelevant, and $(1/8)(1/8)(7/8)/3 = 0.005$ when they are both of grade 3. Under a cascade, a document's worth depends on what stands above it. No position-based measure can express that, since its weights are fixed in advance. It is ERR's argument for itself: a second excellent answer below a first is of little use to a user who wanted one.
The simulation. The script simulates 400,000 cascade users on this ranking, each stopping at rank $r$ with the probabilities above and scoring $1/r$. Their mean score is 0.9219, against the formula's 0.9220. The satisfied users' mean stopping rank is 1.206, and its reciprocal, 0.829, is not ERR: as with mean reciprocal rank, the mean of the reciprocals is not the reciprocal of the mean.
On the rankings that divided the gain formulas. The nDCG article used pairs of rankings to show that measures can disagree. ERR takes a side in each:
| Ranking (grades by rank) | nDCG@6, linear gain | nDCG@6, exponential gain | ERR |
|---|---|---|---|
| X: 3, 0, 0, 2, 2, 1 | 0.699 | 0.672 | 0.894 |
| Y: 2, 2, 1, 3, 0, 0 | 0.708 | 0.576 | 0.583 |
| U: 1, 1, 1, 3, 0, 0 | 0.750 | 0.601 | 0.358 |
| V: 3, 0, 1, 1, 1, 0 | 0.946 | 0.971 | 0.886 |
ERR prefers X to Y by a wide margin, where linear-gain nDCG narrowly prefers Y. The single excellent document at rank 1 satisfies seven users in eight before anything else is read. It prefers V to U more strongly than either form of nDCG does: U makes the user pass three documents that each satisfy with probability 1/8 before the one that satisfies with probability 7/8. These are four rankings, chosen in the nDCG article because measures disagree on them. They illustrate how ERR weighs a ranking; they are not evidence about how often it disagrees with nDCG in general.
With binary judgments. For the worked ranking, with relevant as grade 1 and $g_{\max} = 1$, each relevant document satisfies with probability 1/2:
$$\mathrm{ERR} = \frac{1}{2} + \frac{1}{2}\cdot\frac{1}{2}\cdot\frac{1}{3} + \frac{1}{4}\cdot\frac{1}{2}\cdot\frac{1}{6} + \frac{1}{8}\cdot\frac{1}{2}\cdot\frac{1}{9} = 0.500 + 0.083 + 0.021 + 0.007 = 0.611.$$
Its reciprocal rank is 1. The difference is the model's allowance for a relevant document that does not end the search.
Average precision as a user model
Average precision was defined in its own article without any user in view, and Moffat, Webber, and Zobel (2007) argued that no plausible search model corresponds to it, "because no user knows in advance the number of relevant answers in the collection they are addressing" (quoted in Robertson, 2008, §3). Robertson (2008) supplied one, and showed that the user needs no such knowledge.
Robertson's model. The user reads down the ranking and stops at a relevant document, the one at which their need is met. Different users need different amounts: one is satisfied by the first relevant document, another needs the third. Let $p_s(n)$ be the probability that a user's stopping point is the relevant document at rank $n$. A user who stops at rank $n$ has read $n$ documents, and the natural score for that outcome is the precision there. The expected precision at the stopping point is
$$\mathrm{NCP} = \sum_{n} p_s(n)\, P@n,$$
which Robertson calls normalized cumulative precision. Two choices of the stopping distribution recover familiar measures.
- If the stopping point is uniform over all the relevant documents of the query, each with probability $1/R$, and a relevant document that was not retrieved scores a precision of 0, then $\mathrm{NCP} = \frac{1}{R}\sum_{n} P@n \cdot \mathit{rel}(n)$, which is average precision exactly.
- If every user stops at the first relevant document, NCP is the precision at that rank, which is $1/k$ for a first relevant document at rank $k$: reciprocal rank.
For the worked ranking the five equally likely outcomes are precisions of 1.000, 0.667, 0.500, 0.444 and 0, with mean 0.522, the AP. In the script, 200,000 simulated users with a uniformly chosen stopping point averaged 0.5227.
The model also shows what AP assumes: that a user is as likely to need all five relevant documents as to need one. Robertson notes that this is probably wrong, since many users stop after few relevant documents. The frame makes the alternative easy to state. If the chance of stopping at the $j$-th relevant document is proportional to $1/2^j$, the same five precisions average to 0.781, much closer to reciprocal rank. Robertson also marks the difference from RBP. In RBP the chance of stopping is the same at every document and does not depend on relevance; in his model the user stops only at relevant documents, at a point fixed in advance by how much they need.
The measures side by side
On the worked ranking, with binary judgments:
| Measure | User model | Uses $R$? | Value |
|---|---|---|---|
| P@10 | reads exactly ten results | no | 0.400 |
| Reciprocal rank | stops at the first relevant result | no | 1.000 |
| Average precision | stops at a relevant result chosen uniformly among all $R$ | yes | 0.522 |
| nDCG@10 | logarithmic weights, normalized by the ideal ranking | yes, through the ideal | 0.732 |
| RBP, $p = 0.5$ | continues with probability 0.5 | no | 0.643 (residual 0.001) |
| RBP, $p = 0.8$ | continues with probability 0.8 | no | 0.427 (residual 0.107) |
| RBP, $p = 0.95$ | continues with probability 0.95 | no | 0.167 (residual 0.599) |
| ERR, $g_{\max} = 1$ | cascade; a relevant result satisfies with probability 1/2 | no | 0.611 |
The values are not comparable with one another: each is an expectation of a different quantity under a different model. What can be compared is what each model claims about the reader, and that is the basis for choosing. A measure whose model fits the application's users is the better instrument for that application, whatever its number.
On Cranfield
Cranfield's judgments are graded, and the unit's scripts keep the grades, so both measures can be computed on the BIM, TF-IDF and BM25 runs used throughout this topic. RBP uses binary relevance (grades 1 to 4 relevant). ERR uses the gain $5 - \text{grade}$ of the nDCG article, so $g_{\max} = 4$ and the stopping probabilities are $15/16$ for a complete answer, then $7/16$, $3/16$ and $1/16$ for grades 2, 3 and 4. That mapping is our choice for this collection, following the form of Chapelle and colleagues; Cranfield's grades were not designed for it. Means over the 225 queries, with rankings of depth 1,000:
| Model | MAP | RBP, $p = 0.5$ | RBP, $p = 0.8$ | RBP, $p = 0.95$ | ERR |
|---|---|---|---|---|---|
| BIM | 0.220 | 0.241 | 0.191 | 0.102 | 0.186 |
| TF-IDF | 0.294 | 0.324 | 0.259 | 0.130 | 0.245 |
| BM25 | 0.307 | 0.343 | 0.268 | 0.131 | 0.255 |
Every measure orders the three models the same way. They differ in how far apart they place them. BM25 leads TF-IDF by 0.018 under the impatient user of $p = 0.5$ and by 0.002 under the persistent user of $p = 0.95$. That agrees with the precision-recall curves of evaluating ranked results, where the two models differ at the top of the ranking and converge lower down. Per query, BM25 beats TF-IDF on 121 queries and loses on 91 under RBP with $p = 0.95$, and wins 126 and loses 87 under ERR. These are observations on one small collection of exhaustively judged abstracts.
The residual shows what a shallower evaluation would have cost. Evaluated to depth 10 only, BM25's mean RBP is 0.343 with a residual of 0.001 at $p = 0.5$, 0.259 with a residual of 0.107 at $p = 0.8$, and 0.100 with a residual of 0.599 at $p = 0.95$. The full-depth values (0.343, 0.268, 0.131) lie inside all three intervals, near their lower ends, because few of the documents below rank 10 are relevant.
Limits
- The parameters are assumptions. RBP's $p$ and ERR's mapping from grades to probabilities are chosen, not measured, in this article. Moffat and Zobel report results at $p = 0.5$, 0.8 and 0.95; the right value for a service is an empirical question about its users, answerable from logs of the kind online evaluation describes.
- The models are simple. No model here lets a user skip a result, return to an earlier one, or be put off by a run of poor results. Chapelle and colleagues report that ERR correlated better with measures derived from clicks than other judgment-based measures did on their search-engine data, which is evidence for the cascade assumption in web search and not a general result.
- RBP is not normalized. Its ceiling for a query is $1 - p^R$, so means over queries mix different ceilings, as means of precision at $k$ do.
- ERR's top-heaviness is extreme. With a top-graded document at rank 1, at most $1/2^{g_{\max}}$ of the score's range is left for everything below. That suits a need one document can meet, and it suits poorly a need for many documents.
Worked problems
The course text predates both measures and sets no exercise on them, so the problems below are posed on this unit's rankings. Each answer is asserted in tools/experiments/eval_measures/user_models.py.
Problem 1 (RBP of the second worked query). The second query of mean average precision has relevant documents at ranks 2, 5 and 8 of ten judged results. Compute its RBP at $p = 0.8$ with its residual, and compare the ordering of the two worked queries under RBP and under average precision.
Solution. RBP is 0.284 with a residual of 0.107; both measures score the first query higher. The weights of ranks 2, 5 and 8 are $0.2 \times 0.8^1$, $0.2 \times 0.8^4$ and $0.2 \times 0.8^7$:
$$\mathrm{RBP} = 0.2 \times (0.800 + 0.410 + 0.210) = 0.2 \times 1.419 = 0.284.$$
All ten results are judged, so the residual is $0.8^{10} = 0.107$. The first query scores 0.427 and the second 0.284 under RBP, against 0.522 and 0.425 under AP. RBP separates them more. AP divides the second query's sum by its smaller $R = 3$, which raises its score; RBP makes no such adjustment, and sees only that the second ranking's first result is not relevant.
Problem 2 (the residual as a judging budget). A team will judge every run to a fixed depth and wants the residual of RBP to be at most 0.05. Find the depth required at $p = 0.5$, 0.8 and 0.95.
Solution. Depths 5, 14 and 59. The residual of a ranking judged to depth $d$ is $p^d$, so the condition is $d \ge \ln 0.05/\ln p$. At $p = 0.5$: $\ln 0.05/\ln 0.5 = 4.32$, so $d = 5$ ($0.5^5 = 0.031$, while $0.5^4 = 0.0625$ is too large). At $p = 0.8$: $13.4$, so $d = 14$ ($0.8^{14} = 0.044$). At $p = 0.95$: $58.4$, so $d = 59$ ($0.95^{59} = 0.048$). The depth grows roughly in proportion to the expected number of documents read, $1/(1 - p)$: 2, 5 and 20.
Problem 3 (the ordering that maximizes ERR). For the six judged documents of the graded example, with grades 3, 3, 2, 2, 1 and 0, find the ordering with the largest ERR and the one with the smallest, and prove that the first is the largest for any set of documents.
Solution. The descending order 3, 3, 2, 2, 1, 0 has the largest ERR, 0.933, and the ascending order the smallest, 0.289. The script confirms both over all 180 distinguishable orderings.
Proof that sorting by grade is best. Take any ranking and two adjacent ranks $r$ and $r + 1$ holding documents with stopping probabilities $a$ at rank $r$ and $b$ at rank $r + 1$, where $a < b$. Let $Q$ be the probability of reaching rank $r$. The two ranks contribute
$$Q\left(\frac{a}{r} + \frac{(1 - a)\,b}{r + 1}\right).$$
After exchanging the two documents they contribute $Q\left(\frac{b}{r} + \frac{(1 - b)\,a}{r + 1}\right)$. The difference, new minus old, is
$$Q\left(\frac{b - a}{r} - \frac{b - a}{r + 1}\right) = Q\,(b - a)\left(\frac{1}{r} - \frac{1}{r + 1}\right) \ge 0,$$
since the terms in $ab$ cancel. The probability of reaching rank $r + 2$ is $Q(1 - a)(1 - b)$ in both orders, so no later term changes, and no earlier term involves these documents. So moving a higher grade above a lower one never lowers ERR. Any ranking can be sorted into descending order by such exchanges, and therefore the descending order has the largest ERR. Run in the other direction, the same argument shows the ascending order has the smallest. The worked example's own ranking, 3, 2, 3, 0, 1, 2, scores 0.922, within 0.011 of the best, because its first document is already of the top grade.
Problem 4 (the cost of two unjudged documents, for three users). With ranks 2 and 4 of the worked ranking unjudged, compute the base RBP and the residual at depth 10 for $p = 0.5$, 0.8 and 0.95, and say for which user the missing judgments matter most relative to the tail.
Solution. The base values are those of the complete judgments, 0.643, 0.427 and 0.167, since the two documents were counted as nonrelevant before. The two unjudged ranks add $(1 - p)(p + p^3)$ to the residual:
| $p$ | Weight of ranks 2 and 4 | Tail $p^{10}$ | Residual |
|---|---|---|---|
| 0.5 | $0.5 \times (0.5 + 0.125) = 0.313$ | 0.001 | 0.313 |
| 0.8 | $0.2 \times (0.8 + 0.512) = 0.262$ | 0.107 | 0.370 |
| 0.95 | $0.05 \times (0.95 + 0.857) = 0.090$ | 0.599 | 0.689 |
For the impatient user almost all of the uncertainty comes from the two unjudged documents, which stand where that user reads; for the persistent user most of it comes from the unexamined tail, and the two documents add little. Judging effort is best spent where the model's weight is: at the top for small $p$, and in depth for large $p$.
What we have learned
A measure can be derived from a model of the reader instead of being described by one. Precision at $k$ is the gain per document for a user who reads exactly $k$ results. The DCG discount is a set of weights that cannot be normalized over an unbounded ranking. Rank-biased precision follows from a user who continues with probability $p$: it is $(1 - p)\sum r_i p^{i-1}$, it needs no count of relevant documents, and the unjudged part of a ranking can change it by at most the residual, $p^d$ plus the weights of unjudged ranks. Expected reciprocal rank follows from the cascade model: it is the expected reciprocal of the rank at which a user is satisfied, it lies between 0 and 1, it is largest for the ranking sorted by grade, and it discounts a document by the quality of those above it. Average precision is the expected precision for a user who stops at a uniformly chosen relevant document. On Cranfield all of these order BIM, TF-IDF and BM25 alike.
The residual puts a number on what unjudged documents could do to a score. The next article, Relevance Judgments, Pooling, and Agreement, turns to the judgments themselves: who makes them, why most documents are never judged, and what that does to comparisons of systems.
References
- Chapelle, O., Metzler, D., Zhang, Y., and Grinspan, P. (2009). Expected reciprocal rank for graded relevance. In Proceedings of CIKM 2009, 621–630. 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
- Järvelin, K., and Kekäläinen, J. (2002). Cumulated gain-based evaluation of IR techniques. ACM Transactions on Information Systems, 20(4), 422–446. record · 2 pages
- Manning, C. D., Raghavan, P., and Schütze, H. (2008). Introduction to Information Retrieval, section 8.4. Cambridge University Press. record · 93 pages
- Moffat, A., Webber, W., and Zobel, J. (2007). Strategic system comparisons via targeted relevance judgments. In Proceedings of SIGIR 2007, 375–382. record
- Moffat, A., and Zobel, J. (2008). Rank-biased precision for measurement of retrieval effectiveness. ACM Transactions on Information Systems, 27(1), article 2. record · 2 pages
- Robertson, S. (2008). A new interpretation of average precision. In Proceedings of SIGIR 2008, 689–690. record · 2 pages