Evaluation in Information Retrieval

9.1 Why Search Engines Need Evaluation

A search engine earns continued use only when its results feel worth returning to. Looks alone do not keep users. Speed helps, cost helps, but the deciding factor is whether the results match what the user hoped to find. This section sets up that motivation and names the first group of measures that let us compare one engine against another. Indexing speed, latency, cost, relevance, and user happiness form the opening ledger against which every later score is read.

9.1.1 Three Quantifiable System Measures

Three measures can be counted directly without asking users for opinions. The first is indexing speed. Indexing speed (how fast new material becomes searchable), measured in documents per hour or gigabytes per hour, decides coverage. The example used is simple: an engine that indexes 100 gigabytes per hour can cover far more of the web in the same time than an engine that manages only 10 gigabytes per hour. With billions of pages waiting, that gap decides coverage.

To see the gap in concrete terms, take a 1,000-gigabyte crawl. At 100 gigabytes per hour the crawl finishes in 10 hours. At 10 gigabytes per hour the same crawl needs 100 hours, which is 90 hours longer. A news-heavy collection that changes each day cannot wait 100 hours, so the slower engine serves stale answers while the faster engine stays fresh.

The second is search latency, also called turnaround time. Latency (the gap between sending a query and seeing results) breaks flow when it grows. Users prefer 50 milliseconds over 5 seconds, even though 5 seconds sounds small on its own. Waiting breaks flow, and repeated waiting pushes users away. A useful picture is a shop counter: if the shopkeeper answers at once, the line keeps moving, but if each customer waits 5 seconds extra, a queue of 100 users loses more than 8 minutes in total.

The third is cost per query. Cost per query (computation and hardware burned for one request) decides whether an engine can run at scale. Every query burns computation and hardware. If one engine answers with half the hardware of another, it is more economical to run at scale. Large web engines serve millions of queries per hour, so a small per-query saving grows into a large operational saving. For instance, saving even a fraction of a cent on each of 10 million daily queries frees budget for larger indexes or faster machines.

These three — speed, latency, and cost — tell whether users can be served quickly and cheaply. They do not yet tell whether users are happy with what they got. That limit matters: an engine can index fast, answer in 50 milliseconds, and cost little, yet still lose users if its ranking misses the need.

Picture a chart with response time on the horizontal axis in milliseconds and share of users who stay on the page on the vertical axis. The line starts high near 50 milliseconds and bends down steeply past one or two seconds toward 5 seconds. The landmark is the drop between instant and slow: the same result set keeps users when fast and loses them when slow. The takeaway is that latency multiplies the value of relevance rather than replacing it.

Web-scale engines tune all three at once: crawl bandwidth for indexing speed, caching and index layout for latency, and cluster sizing for cost per query. Those choices set the stage on which relevance scores are later compared.

9.1.2 User Happiness and the Central Role of Relevance

Once hardware and setup are strong enough, attention shifts to user happiness. Happiness depends on several factors. Latency still matters because no one likes to wait. Size of the collection matters because a larger index can answer more needs. Ease of the user interface matters because even a person with no training should be able to type and search.

The most important factor is relevance. Relevance (whether a retrieved document actually helps with the need behind the query) decides continued use. A fast engine that returns off-target documents keeps a user for one try only. After that the user learns not to trust it and moves on. Think of a vending machine that returns change in one second but gives the wrong drink: the speed is noted once, the wrong drink is remembered.

A concrete habit shows how demanding users are. On average, a user stays on each page of top-ranked results for only about 8 seconds. That short window leaves no room for slow or weak ranking. If the first screen does not look useful, the user leaves. This 8-second behavior is one reason ranking quality and latency are treated together when judging web search. The 8-second glance motivates latency and relevance focus: the engine has seconds, not minutes, to show something useful.

9.2 Fair Comparison Setup and Information Need Versus Query

Before scores can be compared, the test itself must be fair. Every engine must face the same documents, the same queries, and the same judgments. This section explains that shared setup and then draws the key line between a short query and the larger human need behind it. Benchmark collection, queries, and judgments make fair comparison possible, while the wine need-versus-query case shows why keyword overlap alone cannot stand in for relevance.

9.2.1 Benchmark Document Collection Queries and Judgments

The standard method has three fixed parts. First, fix a benchmark document collection. For example, take 100,000 documents and require engine one, engine two, and engine three to all be tested on exactly that set. Only a shared collection puts scores on a common scale.

Second, fix a benchmark set of queries. Subject matter experts help build a pool of queries, and that same pool is run on every system. Call them S1, S2, and S3 for three engines under test. Shared queries stop an engine from looking good only because it faced easier questions.

Third, fix relevance judgments. For each query and each retrieved document, someone or some agreed measure must say relevant or not relevant. Human experts can supply those labels. In class the focus is on quantifiable measures that stand in for those labels. Only after all three parts are fixed can relevance scores be compared across engines.

An everyday picture helps. Think of three runners timed on different tracks, one downhill and two uphill. The times cannot be compared. A benchmark is the shared track: same distance, same surface, same stopwatch. Only then does a faster time mean a faster runner rather than an easier track.

9.2.2 Information Need Versus Query With the Wine Example

An information need — the real question in a person's mind — is written here as $I$. A query — the few words typed into a search box — is written here as $Q$. The two are not the same, and evaluation cares about the first, not just word overlap with the second.

$$I=\text{full statement of the underlying need},Q=\{q_1,q_2,\dots ,q_m\}$$

where $I$ is a statement such as a full sentence, $Q$ is the short typed form, each $q_i$ is a single query token, and $m$ is the number of tokens in the query.

The spoken description in class was: a person wants to know whether drinking red wine is more effective at reducing risk of heart attacks than white wine. That full sentence is the information need $I$, where $I$ is a statement of the underlying need. With recent language-model tools a person might paste the whole sentence, but a classic search engine gets only a short query such as red wine, white wine, heart attack. Here the query terms are $q_1=\text{red}$, $q_2=\text{wine}$, $q_3=\text{white}$, $q_4=\text{heart}$, $q_5=\text{attack}$, each $q_i$ a single query token.

The engine returns a document $D^{\prime }$, where $D^{\prime }$ is a retrieved item, that reads in spirit: at the heart of his speech was an attack on the wine industry lobby for downplaying the role of red and white wine in drunk driving. Every keyword matches. Overlap is close to 100 percent. Yet the document is about drunk driving and industry lobbying, while the need was about heart health and which wine helps more. So the document is not relevant.

The takeaway is direct: keyword overlap does not imply relevance. Matching words is not the same as satisfying the need. User happiness depends on useful information, not on shared tokens. This gap is why early keyword systems could look strong on term counts yet disappoint users, and why later models moved toward ranking by need rather than by count.

9.2.3 Why the Same Query Needs Shared Judges

The same short query can mean different things to different people, so judgments must come from a shared setup. Subject matter experts define the intended need for each benchmark query, fix the document set, and mark what counts as relevant. That shared ground lets engine one, two, and three be ranked fairly. Without it, a score difference might reflect different test conditions rather than better retrieval.

A single word shows the problem. The query python may mean a pet snake or a programming language. One judge marking snake pages relevant and another marking code pages relevant will rank the same engine differently. Fixing one reading, one collection, and one label set removes that swing.

Large programs follow the same habit. The Text Retrieval Conference supplies shared collections and topics, while NIST assessors supply relevance judgments, so teams compare results on common ground rather than on private tests.

9.3 Unranked Evaluation With Precision Recall F-Score and Accuracy

Unranked evaluation treats retrieval as a set with no order. A document is either pulled back or not, and either relevant or not. This matches a binary model where rank one versus rank ten has no meaning yet. Ranked lists come later. Here the tools are the classic supervised-learning scores, restated in retrieval language. Precision reports quality of what came back while recall reports completeness of the catch, with the combined F-score and the accuracy warning completing the set.

9.3.1 Mapping Retrieval Onto True Positive and Related Counts

Start from the familiar two-by-two table. Rows hold actual labels, columns hold predicted labels. In retrieval language, actual true means relevant, actual false means not relevant, predicted true means retrieved, predicted false means not retrieved.

That mapping gives four counts. A true positive — a relevant document that was retrieved — is written $TP$, where $TP$ is a count. A false positive — a not-relevant document that was retrieved — is written $FP$, where $FP$ counts retrieved items that miss the need. A false negative — a relevant document that was missed — is written $FN$, where $FN$ counts relevant items left behind. A true negative — a not-relevant document correctly left out — is written $TN$, where $TN$ counts correctly ignored items.

A practical tip for building the table without slips: keep rows for actual and columns for predicted every time. Then falsely predicted as positive can only sit in one cell, and the remaining off-diagonal cell must be the false negative. One student found the board layout flipped between actual and predicted, and this row-for-actual habit resolved the mismatch.

9.3.2 Precision as Quality and Recall as Completeness

Precision looks along the predicted column. The spoken form was: of the total predicted as true, how many were actually true. The reconstructed LaTeX is:

$$P=\frac{TP}{TP+FP}$$

where $P$ is precision, $TP$ counts retrieved-and-relevant, and $FP$ counts retrieved-but-not-relevant. The denominator $TP+FP$ is the total retrieved set. In retrieval words: how many retrieved documents are relevant. Precision measures quality of what came back. Precision of retrieved documents uses relevant counts among retrieved items, with true positive mass in the numerator.

Recall looks along the actual row. The spoken form was: of the available actual true values, how many were predicted as true. The reconstructed LaTeX is:

$$R=\frac{TP}{TP+FN}$$

where $R$ is recall, $TP$ is as above, and $FN$ counts relevant-but-not-retrieved. The denominator $TP+FN$ is the total relevant set in the collection. In retrieval words: how many relevant documents were retrieved. Recall measures completeness of the catch. Recall of relevant documents uses retrieved mass among relevant items, with false negative mass showing what was left behind.

A memory aid used in class: wherever the classic table shows true, read relevant; wherever it shows false, read not relevant; wherever it shows predicted true, read retrieved. That substitution turns the familiar table into the retrieval table without new memorization.

Picture precision and recall as two views of a fishing net. Precision asks what share of the net contents are keepers. Recall asks what share of the lake keepers ended in the net. A tiny net with two keepers has high precision but low recall, while a lake-wide net has high recall but low precision.

9.3.3 Tradeoff and the Combined F-Score

Pushing one score up often drags the other down. Tighten retrieval to raise precision and more relevant items get left out, so recall falls. Loosen retrieval to raise recall and more off-target items slip in, so precision falls. When false negatives are tuned hard, false positives tend to rise, and the reverse holds as well.

The combined score is the harmonic mean of the two. The spoken form was: harmonic mean of precision and recall, which with a common denominator puts the product in the numerator. The reconstructed LaTeX is:

$$F_1=\frac{2\cdot P\cdot R}{P+R}$$

where $F_1$ is the balanced F-score, $P$ is precision as defined above, and $R$ is recall as defined above. The harmonic mean of precision recall gives a combined score that stays low when either input is low. If a task needs high sensitivity to relevant items, recall is weighted more. If false alarms hurt more, precision is weighted more. By default the balanced form reports overall behavior in one number that respects the tradeoff.

The general weighted form lets a task tilt the balance:

$$F_{\beta }=\frac{(1+{\beta }^2)\cdot P\cdot R}{{\beta }^2\cdot P+R}$$

where $\beta$ sets the tilt, values below 1 stress precision, and values above 1 stress recall. The balanced $F_1$ is the case $\beta =1$.

9.3.4 Why Accuracy Alone Can Mislead With One Million Documents

Accuracy sounds like the best single number, but with skewed classes it can deceive. The worked case in class used 1,000,000 documents in total. Out of that total, 20 are relevant and 999,980 are not relevant. Here counts are exact: total $N=1,000,000$, relevant $=20$, not relevant $=999,980$.

Now suppose a system predicts every document as not relevant. The table becomes: $TP=0$ because no relevant document was retrieved, $FP=0$ because nothing was retrieved at all, $FN=20$ because all 20 relevant items were missed, and $TN=999,980$ because every not-relevant item was correctly left out. Students first guessed other splits, then settled on this split by checking row and column totals against the 1,000,000 total.

Accuracy in LaTeX is:

$$Accuracy=\frac{TP+TN}{TP+TN+FP+FN}$$

where each symbol is the count defined above and the denominator equals $N$. Here accuracy uses true negatives and total documents in one ratio. Substitution gives:

$$Accuracy=\frac{0+999980}{1000000}$$

which equals about 99.998 percent, reported in class as 99.99 percent. Yet the engine retrieved zero relevant documents. The user received nothing useful. The model learned nothing; it only exploited the imbalance between 20 and 999,980. Precision for this run is $0/(0+0)$, which is undefined and treated as 0 for reporting, while recall is $0/(0+20)=0$. Ninety nine percent accuracy pairs with total retrieval failure.

The lesson is pointed: never trust accuracy alone in retrieval or in any skewed supervised task. Always ask for precision, recall, and the combined score alongside it. Papers that report only accuracy on skewed collections should prompt a check for the other measures before trusting the claim.

9.4 Ranked Lists Precision-Recall Curves and Interpolated Precision

Real engines return ranked lists as in web search, with rank one, rank two, rank three, and so on. Users scan from the top, so evaluation must respect order. This section moves from set-based scores to rank-aware curves and shows how to smooth them for fair visual comparison. Ranked curve precision uses sawtooth recall behavior that interpolated smoothing then calms.

9.4.1 From Unranked Sets to Rank-Aware Scoring

Classic precision, recall, and F-score look at the whole retrieved set at once. Rank-aware scoring instead asks at each cutoff $K$, where $K$ is a rank position such as 1, 2, 3, and onward: what are precision and recall among the top $K$ only. That family includes precision at $K$, mean average precision, mean reciprocal rank for binary relevance with two states relevant or not relevant, and normalized discounted cumulative gain for graded relevance with levels such as not relevant, fairly relevant, good, and excellent.

Binary relevance keeps two states. Graded relevance allows many levels. Both appear in practice because some needs accept partial matches while others need a single right answer. The next subsections build the curve machinery that binary ranked measures share.

Think of reading a ranked list as climbing stairs with a basket. Each step $K$ adds one document to the basket. Precision asks how full of keepers the basket is at that step, while recall asks how many of all keepers in the building are already in the basket. The basket view makes clear why scores change at each rank.

9.4.2 Precision-Recall Curve at Each Rank With a Four-Document Walkthrough

For one query, compute precision and recall at cutoff one, then top two, then top three, and so on, and plot precision against recall. Each engine then owns one curve. A stronger engine sits closer to the upper right, where both precision and recall stay high together. With only two engines a glance can decide, but with ten or more engines overlapping curves become hard to read, which motivates numeric summaries later.

The toy walkthrough used four documents in rank order, labeled A, B, C, D. Labels in class were A relevant, B not relevant, C relevant, and the last item relevant. At $K=1$ only the top item counts. Precision is 1 out of 1, which is 1. Recall was reported as 1 out of 4, which is 0.25. The spoken accounting treated the denominator as 4 in this walkthrough, so the numbers below keep that accounting exactly as given.

At $K=2$ the top two are considered. One of two is relevant, so precision is 1 out of 2, which is 0.5. Recall stays 1 out of 4, which is 0.25, since no new relevant item entered. At $K=3$ two of three are relevant, so precision is 2 out of 3, about 0.667. Recall becomes 2 out of 4, which is 0.5. At $K=4$ three of four are relevant, so precision is 3 out of 4, which is 0.75, and recall is 3 out of 4, which is 0.75.

Plotted across cutoffs, precision jumps up and down while recall climbs and never falls. That up-and-down shape is the sawtooth, also called jigsaw, pattern. The reason is simple. When the next item at $K+1$ is not relevant, recall stays flat but precision drops because the denominator grew without a new hit. When the next item is relevant, both can rise. So precision creates the teeth, while recall is monotone increasing as more of the list is included. Precision teeth with flat recall at dead ranks explain the jagged line.

Picture recall on the horizontal axis from 0 to 1 and precision on the vertical axis from 0 to 1. The raw line starts high on the left, drops straight down at fixed recall when a miss arrives, then jumps up and right when a hit arrives. Landmarks are the vertical drops at dead ranks and the rising jumps at hits. The takeaway is that the raw shape is honest but hard to read across engines.

9.4.3 Interpolated Precision for Smooth Comparison

Jagged curves are hard to compare, so each recall level is replaced by the best precision at or beyond it. The spoken form was: at each recall take the maximum precision over all ranks with recall at least that large. The reconstructed LaTeX is:

$$P_{interp}(R)=\underset{R^{\prime }\ge R}{\max }P(R^{\prime })$$

where $P_{interp}(R)$ is interpolated precision at recall $R$, $P(R^{\prime })$ is measured precision at a recall $R^{\prime }$ from the raw curve, and the maximum runs over all $R^{\prime }$ greater than or equal to $R$. The interpolated precision maximum recall envelope smooths teeth by carrying the best later value backward. Bounds not stated beyond the observed curve are handled by carrying forward the available maximum, as in the examples below.

A small illustration from class used recall points 0.25, 0.4, 0.55, 0.8, and 1.0. At recall 0.25 the maximum over all later precisions is 1, so the interpolated value is 1. At recall 0.4 the later maximum is 0.8, even though the raw value near 0.4 was about 0.6, because the higher 0.8 occurs later and the goal is a smooth envelope rather than the dip. At recall 0.55 the later maximum among the remaining points is again 0.8, since the top two points are now ignored and the best of the rest rules. At recall 0.8 with fewer points left the value follows the remaining maximum, and at recall 1 the last point closes the curve. The result is a decreasing smooth line that is far easier to compare across engines than the raw teeth. No quantifiable single number comes out yet; the gain at this stage is visual comparability, with numbers to follow.

9.5 Eleven-Point Interpolated Average Precision and the TREC Benchmark

Even smoothed curves are awkward when many engines or many queries are involved. The eleven-point method fixes a shared x-axis so curves can be averaged and overlaid fairly. This section explains the eleven levels, the mapping rule, and the large benchmark where the average is taken. Eleven point average fixed recall levels turn many jagged runs into one comparable line.

9.5.1 Eleven Fixed Recall Levels and the Averaging Idea

Researchers fixed eleven recall levels from 0 to 1 in steps of 0.1. In symbols the set is $r\in \{0.0,0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9,1.0\}$, where each $r$ is a standard recall level and the step is 0.1, giving 11 points in total. For each level, bring the interpolated precision and plot it. For many queries, take the arithmetic mean at each level across queries and plot that mean curve. That mean curve is the eleven-point interpolated average precision picture for the engine.

$$P_{11}(r)=P_{interp}(r),r\in \{0.0,0.1,\dots ,1.0\},{\bar{P}}_{11}(r)=\frac{1}{|Q|}\sum _{q=1}^{|Q|}{P}_{11}^{(q)}(r)$$

where $P_{11}(r)$ is the eleven-point value at standard recall $r$ for one query, $P_{interp}(r)$ is the smoothed precision from the prior section, $|Q|$ is the number of queries, and ${\bar{P}}_{11}(r)$ is the mean across queries at that fixed level.

The Text Retrieval Conference — a large evaluation program co-sponsored by NIST, the national standards body, and started in 1992 to support large-scale text retrieval experiments — supplies the kind of shared infrastructure this needs. The plot discussed in class showed such a curve for 50 different queries on one system of that family. Each query first yields its own precision-recall behavior, then the 50 are averaged level by level. The x-axis never moves since it is always the same eleven points; only the averaged precisions on the y-axis change. That shared scale is what makes cross-engine comparison fair.

Picture eleven vertical slots along the recall axis. Each query drops one smoothed height into each slot. The engine line joins the eleven slot means. With 50 queries the line is stable: one odd query moves a slot mean by at most one-fiftieth of its swing.

9.5.2 Mapping Raw Interpolated Values Onto the Eleven Points

Raw ranks do not land on 0.0, 0.1, and so on, so a mapping rule is needed. The rule stated in class: map every standard recall level to the nearest available recall value that is greater than or equal to it, and carry over that interpolated precision. In other words, look forward to the next real recall at or above the standard level and borrow its score.

The worked mapping used a top-10 list whose raw interpolated behavior was: at recall 0.25 the value is 1, at recall 0.5 the value is 0.67, at recall 0.75 the value is 0.6, and at recall 1.0 the value is 0.5. Note the duplicate-recall detail: when two rows share recall 0.25, both keep interpolated precision 1, because recall did not move and there is no second value to plot at the same x. Smoothing keeps one value per recall position.

Now build the eleven-point row. Recall 0 in the new table looks forward to 0.25 in the raw table and takes 1. The same holds for 0.1 and 0.2, so all three take 1, since 0.25 is the closest available value at or above them and 0.3 would already lie beyond 0.25 and cannot borrow from it. For 0.3, 0.4, and 0.5, the next available value at or above is 0.5, so all three take 0.67. For 0.6 and 0.7, the next available at or above is 0.75, so both take 0.6. For 0.8, 0.9, and 1.0, the closing value is 0.5, since 0.8 lies beyond 0.75 and must look forward to 1.0. That forward-looking maximum rule is the whole logic, repeated level by level.

This construction is per query. With 50 queries, repeat the eleven-point row for each query and then average. For example, at recall 0 the mean is the sum of the 50 interpolated values at 0 divided by 50. If each is 1, the mean is $(1+1+\cdots +1)/50=1$. Do the same at 0.1 through 1.0 and plot the 11 means. That final line is the engine summary that can sit next to another engine summary on identical axes. The arithmetic mean over fifty interpolated precisions at each level is the whole averaging step.

9.5.3 Small-Number Check of the Duplicate-Recall Rule

When recall stays at 0.25 across two rows, the interpolated precision stays at 1 for both rows rather than dropping to 0.67 on the second row. The reason is smoothing: with no movement on the x-axis there cannot be two different y-values at the same x. The maximum over all points at or beyond 0.25 is still 1, so both rows report 1. The later 0.67 belongs to recall 0.5 and only starts to apply once the standard level reaches forward to 0.5.

9.6 Precision at K R-Precision Average Precision and Mean Average Precision

Curves help the eye, but a single number per engine helps decisions. Users also care most about the first screen, not the whole list. This section introduces the top-$K$ family that rewards putting relevant items early, with worked numbers and a textbook exercise comparing two systems. Precision among top cutoff results, average precision over relevant positions per query, and mean average precision across queries form one ladder.

9.6.1 Precision at K and Its User-First Motivation

Most users look at first-page results and rarely open page two or three. After years of web use, people expect the answer within the first few clicks. None of the full-list curves isolates that habit directly. Precision at $K$, also written $P@K$, does exactly that by scoring only the top $K$.

The spoken form was: among top $K$ results, how many are relevant. The reconstructed LaTeX is:

$$P@K=\frac{\text{number of relevant documents in top }K}{K}$$

where $K$ is the cutoff rank and the numerator counts relevant items with rank less than or equal to $K$. Precision among top cutoff results uses only the head of the list. For example, $P@10$ asks in the first 10 how many are relevant. That matches lived behavior where low-ranked items are seldom checked. Web engines tune heavily for the first page because that is where continued use is won or lost.

A five-item demo used green for relevant and red for not relevant in order. The order is relevant, not relevant, relevant, not relevant, relevant. Precision at one is 1 out of 1, which is 1. Precision at two is 1 out of 2, which is 0.5. Precision at three is 2 out of 3, about 0.667. Precision at four is 2 out of 4, which is 0.5. Precision at five is 3 out of 5, which is 0.6. If the second item had also been relevant, the top three would all be relevant and the early precisions would all be 1, which previews why averaging only at relevant positions rewards early hits.

9.6.2 R-Precision When the Total Relevant Count Is Known

R-precision — precision at $R$ where $R$ is the known total number of relevant documents — fixes $K$ from knowledge rather than from habit. The spoken form was: if $R=4$ relevant documents exist, score only the top 4. The reconstructed LaTeX is:

$$R\text{-}precision=\frac{\text{number of relevant documents in top }R}{R}$$

where $R$ is that known relevant total. If 3 of the top 4 are relevant, the score is 3 out of 4. Use this when there is a rough prior idea of how many relevant items exist; otherwise a free $K$ such as 10 or 20 is more natural. At this cutoff precision equals recall, since both divide the same head count by the same $R$, which is why this point is also called the break-even point.

Picture two engines on the same need with $R=4$. Engine A head is R, R, N, N for 0.50. Engine B head is R, N, N, N for 0.25. The gap is read in one glance without curves.

9.6.3 Average Precision Per Query and Mean Across Queries

Average precision goes one step further by rewarding early placement directly. It averages $P@K$ but only at positions where the item is relevant, ignoring non-relevant positions entirely. Earlier the demo scored every $K$ including $K=2$ even though rank two was not relevant. Average precision skips such positions.

The per-query LaTeX in class notation, with $m$ marking the relevant total, is:

$$AP=\frac{1}{m}\sum _{k=1}^{n}P(k)\times rel(k)$$

where $AP$ is average precision for one query, $n$ is the length of the ranked list considered, $P(k)$ is $P@K$ at cutoff $k$, $rel(k)$ equals 1 when the item at rank $k$ is relevant and 0 otherwise, and $m$ is the total number of relevant documents for that query. Average precision over relevant positions per query keeps only hits in the sum. The verbal bridge is: for every relevant document measure precision up to its rank, add those precisions, then divide by the number of relevant documents. The $m$ symbol in the board formula marks the relevant total, not a second $R$.

The same five-item demo gives $AP$ at relevant ranks one, three, and five only. At rank one precision is 1 out of 1. At rank three precision is 2 out of 3. At rank five precision is 3 out of 5. With $m=3$ relevant items:

$$AP=\frac{1}{3}\left(\frac{1}{1}+\frac{2}{3}+\frac{3}{5}\right)$$

which was reported as about 0.76 for that query. Step by step, the bracket sums to $1.00+0.667+0.60=2.267$, divided by 3 gives about 0.756, rounded to 0.76. A two-query illustration then gave average precision 0.65 for query one and 0.25 for query two, showing how early versus late placement moves the per-query number even when totals match.

Mean average precision averages those per-query values across the query set. The reconstructed LaTeX is:

$$MAP=\frac{1}{|Q|}\sum _{q=1}^{|Q|}AP(q)$$

where $MAP$ is mean average precision, $|Q|$ is the number of queries, and $AP(q)$ is average precision for query $q$. Mean average precision across queries gives the engine number. The words average and mean mark two stages: average within one query across its relevant positions, then mean across queries for the engine. Same documents and same queries must be used for every engine, or the means are not comparable.

A sharp contrast makes the intent plain. Engine A places relevant items at ranks 1, 2, 3, 4, 5. Engine B places them at ranks 20, 50, 60, 70, 80. Engine A is preferred because users meet useful items at once, while engine B buries them where few look. Higher $MAP$ signals relevant items consistently near the top; lower $MAP$ signals they exist but sit far down with high rank numbers. The board formula with the sum over relevance indicators and the outer mean over $Q$ is exactly this two-stage idea written compactly. Early ranks lift average reciprocal intuition: hits near the top enter with $P(k)$ near 1, while hits at rank 50 enter with $P(k)$ near a small fraction.

A longer two-query table made the arithmetic concrete. Query one had relevant marks at ranks 1, 3, 6, 8, and 9. Precisions used were 1 out of 1, 2 out of 3, 3 out of 6, and onward through the later relevant ranks, summed and divided by the relevant count to form query-one average precision. Query two had its own marks with precisions 1 out of 2, 2 out of 3, 3 out of 7, and 4 out of 10, summed and divided by 4 to form query-two average precision. Students called out each fraction in turn — 1 by 2, 2 by 3, 3 by 7, 4 by 10 — and the per-query averages followed. The mean of the two per-query averages is the two-query $MAP$.

9.6.4 Textbook Exercise With Systems S1 and S2

A short exercise compared two systems on one query with four relevant documents in total, so $R=4$. This is the textbook exercise with systems precision comparison where early placement wins. Mean average precision for system one was 0.6, built from precisions at its relevant positions including 1 out of 4-type terms at ranks such as 1, 3, 9, and 10 as worked on the board. Mean average precision for system two was 0.492. The inference is that both return four relevant items, yet system one earns more by placing them earlier. Getting relevant items into top ranks matters most for a strong $MAP$.

The rank strings in the exercise read, leftmost as top rank: System 1 as R, N, R, N, N, N, N, N, R, R and System 2 as N, R, N, N, R, R, R, N, N, N. Both return four relevant documents, yet System 1 shows them earlier with hits at 1 and 3, while System 2 waits until 2 and 5. Both return four and earlier placement gives higher score, which is the whole lesson.

R-precision on the same exercise uses $R=4$ directly. System one shows pattern RNRN in the top four, with 2 relevant among the first 4, so R-precision is 2 out of 4. System two shows fewer early hits with pattern NRNN-type behavior in the top four, with 1 relevant among the first 4, so R-precision is 1 out of 4. The order matches the $MAP$ order, with system one ahead.

9.7 Mean Reciprocal Rank for Single-Answer Needs

Some needs have only one right answer. Asking who leads a well-known company has one correct response, not a set of equally good documents. The same holds for many question-answering setups, chatbots, FAQs, and voice helpers where one short answer is expected. Scoring a full set of relevant items misses the point there. What matters is where the first correct answer lands. Reciprocal first relevant answer mean scoring fits that habit.

9.7.1 Reciprocal Rank and Its Mean Across Queries

The method finds the rank of the first relevant document and takes its reciprocal. The spoken form was: identify the first relevant rank, then invert it so farther answers score less. The reconstructed LaTeX is:

$$RR=\frac{1}{ran{k}_{first}}$$

where $RR$ is reciprocal rank for one query and $ran{k}_{first}$ is the position of the first relevant item. Across queries take the mean:

$$MRR=\frac{1}{|Q|}\sum _{q=1}^{|Q|}\frac{1}{ran{k}_q}$$

where $MRR$ is mean reciprocal rank, $|Q|$ is the number of queries, and $ran{k}_q$ is the first-relevant rank for query $q$. Reciprocal rank first relevant answer mean averaging is the full two-step habit: invert the first-hit rank per query, then average across the query set.

The discount is steep by design. Rank one gives 1 out of 1, which is 1. Rank two gives 1 out of 2, which is 0.5. Rank five gives 1 out of 5, which is 0.2. That rapid fall matches the user cost: an answer buried fifth is far less useful when only one answer was wanted. Like other cross-engine scores, the same queries must be run everywhere before means are compared.

A tiny demo fixed the idea. If the list starts relevant, non-relevant, non-relevant, non-relevant, the first relevant rank is 1 and the score is 1. If the relevant item slips to second, the score drops to half, so the second engine must rank below the first. Averaging those reciprocals over all queries gives the engine-level $MRR$. Like precision at $K$, average precision, and R-precision, this is a binary-relevance measure with two states, but it looks only at the first hit rather than at all hits.

Picture rank on the horizontal axis and reciprocal score on the vertical axis. The points 1, 0.5, 0.33, 0.25, 0.2 trace a curve that falls fast then flattens. The landmark is the halving from rank 1 to rank 2: one slip costs half the credit. The takeaway is that single-answer tuning lives or dies on the very first ranks.

Single-answer scoring fits who-is-leader questions, factoid help, FAQ lookup, and voice-helper prompts where users expect one spoken answer rather than a reading list. A voice helper that speaks the fifth candidate first fails even when the correct name sits second.

9.8 Graded Relevance and Normalized Discounted Cumulative Gain

Binary labels are not enough when results can be excellent, good, fair, or not relevant. A fair item in rank one should not earn the same credit as an excellent item in rank one, and an excellent item on page five should not earn the same credit as the same item on top. Normalized discounted cumulative gain, widely used for web and learning-to-rank evaluation, handles both ideas at once. Graded excellent discount with cumulative ideal normalized ratio scoring is the core habit here.

9.8.1 Two Guiding Ideas and the Gain Scale

Two ideas drive the design. First, highly relevant documents are more valuable than marginally relevant ones. An excellent match should contribute more gain than a fair match. Second, the usefulness of a relevant document falls as its rank drops. Users rarely open lower ranks, and even when they do they give those items less weight. A useful item seen late still counts, but it counts for less. Excellent late items earn discounted credit because attention fades down the page, which the logarithm encodes.

To make that concrete, assign graded gains. The scale used in class was excellent $=3$, good $=2$, fair $=1$, and not relevant $=0$. Here each number $re{l}_i$ is the gain of the item at rank $i$, where $i=1,2,3,$ and onward. A top item with gain 3 contributes 3 if it sits first. The same gain placed lower must be discounted rather than discarded.

Think of concert seats. Excellent seats in row one are worth full price, the same excellent seats in the last row are still excellent seats but worth less because the view is distant. Grade sets the seat type, rank sets the row, and discounted gain sets the ticket value.

9.8.2 Discounted Cumulative Gain With Worked Numbers

Discounting uses the inverse of the logarithm of the rank. The spoken form was: each gain multiplied by 1 over log base 2 of rank, then added across ranks. The lecture form keeps rank one whole and discounts from rank two onward, while the compact textbook form shifts the denominator to avoid dividing by zero. Both habits give the same worked numbers when applied consistently.

The lecture shorthand writes the per-rank weight as 1 over ${\log }_2$ of rank with rank one taken as undiscounted. The compact reconciled form used for scoring is:

$$DC{G}_p=\sum _{i=1}^p\frac{re{l}_i}{{\log }_2(i+1)}$$

where $DC{G}_p$ is discounted cumulative gain up to rank $p$, $re{l}_i$ is the graded gain at rank $i$, and the denominator ${\log }_2(i+1)$ is the discount that grows with rank. Discounted cumulative gain with logarithm rank discount is the standard classroom reduction. The verbal bridge is: relevance score times 1 over log base 2 of rank, with rank-one handled as full gain since ${\log }_2(1)=0$ cannot divide. In class the first item kept its full gain of 3, the second used 2 times 1 over ${\log }_2(2)$, the third used its gain times 1 over ${\log }_2(3)$, the fourth rank used 1 over ${\log }_2(4)=1/2$, and so on.

Notation note: texts often write the gain as $2^{re{l}_i}-1$ over ${\log }_2(1+i)$ to stress excellent items even more, while the lecture uses linear $re{l}_i$ values 3, 2, 1, 0 for hand arithmetic. The lecture keeps $re{l}_i$ in the numerator to match the board; the exponential variant is noted as the standard text form and both share the same rank-one handling once denominators match.

Why the two writings agree can be checked line by line. Lecture shorthand says weight at rank $i$ is $1/{\log }_2(i)$ for $i\ge 2$ with rank 1 whole. Compact form says weight is $1/{\log }_2(i+1)$ for all $i$ with no special case. In the worked lists both give weight 1 at $i=1$ (lecture by rule, compact since ${\log }_2(2)=1$), weight 1 at $i=2$ only under the lecture shorthand versus $1/{\log }_2(3)$ under compact, so small numeric gaps can appear if forms are mixed. The fix used throughout is to pick one form per query and use it for both actual and ideal lists, which keeps the ratio fair. Dimensional check passes since gain over a pure number stays a gain, boundary check passes since deeper ranks discount more, and spot-check at rank 4 gives weight $1/{\log }_2(4)=1/2$ in lecture shorthand, which halves the gain as expected.

The ten-item walkthrough assigned gains across ranks, for example document one excellent with 3, document two good with 2, document three with 3, and several zeros and lower gains after. Discounted terms were formed one by one. The third rank needed ${\log }_2(3)$, about 1.59, so its discounted contribution was its gain divided by about 1.59, about 1.68 in the worked line. A zero gain times any discount stays zero, so not-relevant positions add nothing. Cumulative addition then ran: 3 alone, then 3 plus 2 equals 5, then 5 plus about 1.68 equals about 6.89, then plus 0 stays 6.89, then plus 0.39 reaches about 7.28, continuing to a total $DCG$ of about 9.61 at the end of the list. Ten item discounted cumulative gain total 9.61 is the reconciled lecture total.

Without discounting the same gains would have summed directly to 16 through steps like 3 plus 2 equals 5, then 8, 9, 10, 11, 12, 13, up to 16. The drop from 16 to 9.61 shows the price of placing strong gains late. That price is the point: higher ranks keep more of their gain, lower ranks keep less, which mirrors how attention fades down the page.

The logarithmic form is not arbitrary. Users are far less likely to inspect deep ranks, so weight should fall quickly at first and then more gently. An inverse-log discount captures that behavior in one simple denominator. Think of folding paper: early folds halve attention fast, later folds add less change, which is the log shape in daily form.

9.8.3 Ideal Ranking and Normalization With Two Examples

Raw $DCG$ cannot be compared across queries with different numbers of relevant items. A query with 30 relevant documents can pile up far more gain than a query with 3, even when both engines order equally well. The fix is to divide by the best achievable score on that query. Normalized gain actual divided by ideal puts every query on a 0 to 1 scale.

Build the ideal order by sorting the same retrieved gains from large to small: all excellent 3 items first, then good 2 items, then fair 1 items, then zeros. Score that ideal list with the same discount and cumulative steps to get ideal discounted cumulative gain:

$$IDC{G}_p=\text{DCG of the ideally sorted gains up to }p$$

where $IDC{G}_p$ is the ideal score and $p$ is the same cutoff. Then normalize:

$$NDC{G}_p=\frac{DC{G}_p}{IDC{G}_p}$$

where $NDC{G}_p$ is normalized discounted cumulative gain at cutoff $p$. Every score now lies on a 0 to 1 scale, so a three-relevant query and a thirty-relevant query can be compared fairly. Steps stay the same in both worlds: assign gains, apply discounts, take cumulative sums; only the input order changes from actual to ideal before the ratio.

In the ten-item example the actual discounted cumulative values reached 3, then 5, then about 6.89, and on to 9.61, while the ideal discounted cumulative values ran higher at each point, for example about 7.89 where actual showed 6.89. Point-by-point ratios such as 3 over 3, 5 over 6, 6.89 over 7.89, and so on form the normalized curve. The same receive-discount-then-accumulate routine appears on both sides; the ratio is the only new step.

A compact top-five check used gains 2, 1, 0, 2, 0 across ranks one through five. The ideal sort of those gains is 2, 2, 1, 0, 0. Actual $DCG$ at 5 summed the discounted terms, including 2 at rank one, 1 times 1 over ${\log }_2$ at rank two, 0 skipped, and 2 times 1 over log at rank four, for a total of 4. Ideal $IDCG$ summed the sorted version, including 2 at rank one, 2 times log term at rank two, and 1 times 1 over log base 3 at rank three, for a total reported as 4.63. The top five normalized ratio ideal comparison gives the ratio:

$$NDC{G}_5=\frac{4}{4.63}$$

about 0.86, or 86 percent. On the same documents and same top-five cutoff, 90 percent would beat this system and anything below 86 percent would lose to it. A separate four-document ground-truth table with two ranking functions and precomputed $NDCG$ scores was left for hands-on comparison on the same principle.

Exam Guidance Summary

Open-book final-term access is expected, so study should stress why each operation exists and when it helps, not memorized arithmetic alone. Pre-midterm material was smaller in volume but dense with tiny details, so review those details alongside the newer ranking measures. The stated split is at most about 20 percent from pre-midterm and about 80 percent from post-midterm. The closing paper is expected to cover the full syllabus within that split.

Be able to map any confusion table into retrieved versus relevant in seconds, using rows for actual and columns for predicted. Expect small-number tasks on $P@K$, R-precision with $R$ equal to the known relevant total, per-query average precision, two-query $MAP$, reciprocal rank and $MRR$, and $DCG$ with $IDCG$ and $NDCG$ at a stated cutoff such as 5. Show work in tables where ranks and gains are involved, since stepwise precision, discount, and cumulative columns make partial credit and checking far easier. Write assumptions in direct words when a denominator or rank-one rule is ambiguous, for example how rank-one discount was handled. Precision reports quality of what came back while recall reports completeness of the catch; higher $MAP$ means relevant items sit consistently near the top, while lower $MAP$ with the same count means they sit farther down.

Key Industry Applications

Web search engines such as large general engines and scholarly engines are compared on shared document and query benchmarks before relevance claims are trusted. Indexing speed in gigabytes per hour, latency in milliseconds versus seconds, and hardware cost per query decide whether an engine can serve at web scale even before relevance is judged. The first-results-page habit and the roughly 8-second glance per top page explain why $P@K$, R-precision, average precision, $MAP$, and $MRR$ reward early placement. Single-answer needs such as factoid lookup, FAQ answering, chatbots, and voice helpers motivate reciprocal-rank scoring where only the first correct position matters. Multi-level judgments such as excellent, good, fair, and not relevant motivate $NDCG$ for web and learning-to-rank evaluation where partial relevance is common. The Text Retrieval Conference program with its shared collections and query sets provides the common ground that lets different teams compare results fairly.

For example, a shopping site tunes $P@10$ and $MAP$ for its first page, a help assistant tracks $MRR$ for one-answer prompts, and a video or news feed tracks $NDCG$ with excellent, good, fair, and not relevant levels because near-misses still hold value. In each case the Text Retrieval Conference habit applies: fix documents, queries, and judgments first, then compare engines.