Skip to content
Français

Ranking measures

  • Lesson 5
  • 40 min
  • Module 2: Measure relevance before you change anything

Where we are

We have judgments that say how good each result is. A ranked list needs one number that says how good the whole list is. In this lesson, we compute precision, recall, MRR and NDCG by hand, then on every test query.

Plays from YouTube. Nothing loads from YouTube until you press play. Privacy

What you will be able to do

Turn the grades of a ranked list into one number, and choose the number that fits the search. You compute precision, recall, MRR and NDCG by hand on one real query, then let the project compute them on every test query.

NotebookDo this lesson in a notebookColab · Kaggle · GitHub

The notebook computes the four measures for one query and asks you to write NDCG yourself. Then it runs the measures on every validation query and by kind of search. Its setup cells download the practice data, so it needs no local setup. About 35 minutes.

Colab and Kaggle open your own copy. They need a free Google or Kaggle account. Stuck? See the solution notebook.

Before you startWhat to know and to have readyAbout 40 minutes

What you need to know

  • Graded judgments (exact 2, partial 1, irrelevant 0), from Relevance judgments.
  • The kinds of search (known-item, specific, broad), from Kinds of search.
  • A logarithm, only as a number that grows more and more slowly. You do not need to compute one by hand: every value is in a table.

What you need on your computer (only for the guided practice)

  • The project larkfield-search with this module’s files, from the guided practice of Relevance judgments. search check must end with Setup check passed.

A customer asks the shop assistant for “a 3 piece rug set with runners”. She puts ten items on the counter, in a row from left to right. The customer looks at the first item, then the second, and maybe stops after three or four.

Now you must give the shop assistant one score for this row. You have a grade for each item. But a row has ten grades, and a score is one number. How do you make one number from ten grades?

The answer depends on what you care about. Do you care how many items are good? How many of the good items in the shop she found? How quickly the customer sees the first good item? Or all of these, with more weight on the first places? Each question gives a different ranking measure: a formula that turns the grades of a ranked list into one number.

The query is “3 piece rug set with runners” (W-236), a validation query. BM25 returns these ten products. The grades are real WANDS judgments.

Rank Product Product class Grade
1 ellington circle 3 piece area rug set Area Rugs 2 exact
2 cedric oriental ebony area rug set Area Rugs 1 partial
3 mokvist 3 piece floral border red area rug set Area Rugs 2 exact
4 wilkesboro 3 piece floral border blue area rug set Area Rugs 2 exact
5 braylei simple elegance 3 piece solid bath set Bath Rugs & Mats 0 irrelevant
6 fontenay 3 piece braided brown rug set Area Rugs 2 exact
7 kamberk floral teal area rug Area Rugs 1 partial
8 rhodes stripped checker 3 piece hand-knotted beige area rug set Area Rugs 2 exact
9 audrey 3 piece geometric brown/moss area rug set Area Rugs 2 exact
10 shawnna 3 piece bath rug set Bath Rugs & Mats 1 partial

The grades in order are 2, 1, 2, 2, 0, 2, 1, 2, 2, 1. Six of the ten are exact. One more fact matters: the WANDS judges called 28 products exact for this query. Ten results can never show all of them.

Count the exact products: precision and recall

Section titled “Count the exact products: precision and recall”

Tomás proposes the simplest score: “Count the good ones.” That is a real measure, and it has a name.

Precision@k (“precision at k”) is the share of the top k results that are exact. The course counts only exact products here.

  • Precision@5: ranks 1 to 5 have 3 exact products. 3 ÷ 5 = 0.6.
  • Precision@10: ranks 1 to 10 have 6 exact products. 6 ÷ 10 = 0.6.

Recall@k asks the opposite question: of all the exact products for this query, what share does the top k find?

  • Recall@10: 6 of the 28 exact products. 6 ÷ 28 = 0.214.

Precision speaks for the customer, who sees only the page. Recall speaks for the shop, which wants its good products to be findable. A search can have high precision and low recall: every result is good, but most good products never appear. This happens here, and it is not a fault: no page of ten can hold 28 products.

Recall matters most at a large k. The course reports recall@100: how many exact products are in the top 100. A later stage can only re-order what an earlier stage found. You use this in Two-stage ranking.

Now move the irrelevant bath set from rank 5 to rank 1. Every other product moves one place down. The customer now sees a bath mat first, for a rug-set query.

Precision@10 does not change: the same six exact products are still in the top 10. It is still 0.6. But the page is clearly worse. Counting cannot see the order. For search, the order is almost everything.

The reciprocal rank is 1 divided by the rank of the first exact product. “Reciprocal” means “1 divided by”.

  • In BM25’s order, the first product is exact. 1 ÷ 1 = 1.0.
  • With the bath set at rank 1, the first exact product is at rank 2. 1 ÷ 2 = 0.5.
  • If the first exact product were at rank 4, the score would be 1 ÷ 4 = 0.25. If no exact product is found, it is 0.

The MRR (mean reciprocal rank) is the mean of this value over many queries. It fits a search where one answer is enough. A person who types “kisner coffee table” wants the Kisner coffee table, and its rank is what they feel.

MRR sees the order, but only one place in it. It ignores everything after the first exact product, and it ignores partial products. For a broad query like “sofa”, where many products are good, that is not enough.

NDCG (normalised discounted cumulative gain) uses every grade and gives more weight to the first places. It is the main measure of this course. The name describes four steps. You can follow them on the diagram, then in a table.

Five steps from grades to NDCG@5 for the top 5 of the rug-set query. Grades 2, 1, 2, 2, 0 become gains 3, 1, 3, 3, 0. Each gain is divided by the discount log2(rank + 1): 1, 1.585, 2, 2.322, 2.585. The parts are 3, 0.631, 1.5, 1.292, 0. Their sum is DCG@5 = 6.423. The ideal top 5 (five exact products) has DCG@5 = 8.845. NDCG@5 = 6.423 ÷ 8.845 = 0.726.
NDCG@5 for BM25's top 5 of “3 piece rug set with runners”: gain, discount, sum, then divide by the best possible sum.
Text description of the diagram

The diagram is a row of boxes joined by arrows. “Grades of the top 5: 2, 1, 2, 2, 0” leads to “Gains: 2^grade − 1: 3, 1, 3, 3, 0”, then to “Divide by the discount log2(rank + 1): 1, 1.585, 2, 2.322, 2.585”, then to “Parts: 3, 0.631, 1.5, 1.292, 0”, then to “Add them: DCG@5 = 6.423”. A separate box, “Ideal top 5: five exact, ideal DCG@5 = 8.845”, and the DCG box both lead to the last box, with a thick border: “Divide: NDCG@5 = 6.423 ÷ 8.845 = 0.726”.

Each grade becomes a gain: 2 to the power of the grade, minus 1. Exact (2) gives 2² − 1 = 3. Partial (1) gives 2¹ − 1 = 1. Irrelevant (0) gives 2⁰ − 1 = 0. So an exact product is worth three partial products. This formula is a choice, and a common one. It says that the right product is much better than a close one.

Each gain is divided by a discount that grows with the rank: log2(rank + 1). At rank 1 the discount is 1, so the gain counts in full. At rank 2 it is 1.585. At rank 10 it is 3.459, so a gain there counts less than a third. The discount says that people look at the top of the page first.

Add the discounted gains. The sum is the DCG (discounted cumulative gain). “Cumulative” means “added up”.

Rank Grade Gain Discount Part (gain ÷ discount)
1 2 3 1.000 3.000
2 1 1 1.585 0.631
3 2 3 2.000 1.500
4 2 3 2.322 1.292
5 0 0 2.585 0.000
DCG@5 6.423

A DCG of 6.423 means nothing alone. Is it good? To know, compare it with the best possible list. The ideal DCG is the DCG of the ideal order: all judged products of the query, sorted from the best grade down. This query has 28 exact products. So the ideal top 5 is five exact products: 3 + 1.893 + 1.5 + 1.292 + 1.161 = 8.845 (after rounding).

NDCG@5 = DCG@5 ÷ ideal DCG@5 = 6.423 ÷ 8.845 = 0.726.

“Normalised” means “divided by the best possible value”. So NDCG is always between 0 and 1. A score of 1 means the best possible list. This makes queries comparable: a query with 28 exact products and a query with only 2 both have a best score of 1.

For the full top 10, the same steps give DCG@10 = 9.963 and ideal DCG@10 = 13.631, so NDCG@10 = 0.731.

Now you change the order and watch the numbers. First, make a prediction.

Explore

NDCG of one ranked list

DCG@10
9.963
Ideal DCG@10
13.631
NDCG@10
0.731

NDCG@10 is 0.731: the list earns 9.963 of the 13.631 points that the ideal top 10 would earn (DCG@10 ÷ ideal DCG@10). Precision@10: 6 of 10 results are exact.

The query "3 piece rug set with runners": each row adds gain ÷ discount to DCG@10
RankProductGradeGainDiscountPart of DCG
1ellington circle 3 piece area rug setArea Rugs2 exact31.0003.000
2cedric oriental ebony area rug setArea Rugs1 partial11.5850.631
3mokvist 3 piece floral border red area rug setArea Rugs2 exact32.0001.500
4wilkesboro 3 piece floral border blue area rug setArea Rugs2 exact32.3221.292
5braylei simple elegance 3 piece solid bath setBath Rugs & Mats0 irrelevant02.5850.000
6fontenay 3 piece braided brown rug setArea Rugs2 exact32.8071.069
7kamberk floral teal area rugArea Rugs1 partial13.0000.333
8rhodes stripped checker 3 piece hand-knotted beige area rug setArea Rugs2 exact33.1700.946
9audrey 3 piece geometric brown/moss area rug setArea Rugs2 exact33.3220.903
10shawnna 3 piece bath rug setBath Rugs & Mats1 partial13.4590.289
BM25's top 10 for “3 piece rug set with runners”, with the real WANDS grades. Move rows and watch DCG, the ideal DCG and NDCG.
Text description of the explorer

A list of the ten results of BM25 for “3 piece rug set with runners”. Each row shows the rank, the title, the product class, the grade, the gain, the discount and the part of DCG. The readout shows DCG, the ideal DCG and NDCG for the top 5 or the top 10. In BM25’s order, NDCG@10 is 0.731 and NDCG@5 is 0.726. With the bath set moved from rank 5 to rank 1, NDCG@10 is 0.615 and NDCG@5 is 0.548. With ranks 1 and 5 swapped, NDCG@5 is 0.518. “Best order of these ten” gives NDCG@10 0.797 and NDCG@5 1.000.

What happens

With the bath set at rank 1, NDCG@10 falls from 0.731 to 0.615, and precision@10 stays at 0.6. NDCG sees the order; counting does not. In the top 5, swapping ranks 1 and 5 drops NDCG@5 from 0.726 to 0.518. The exact product lost its best place.

Now press “Best order of these ten”. NDCG@5 becomes 1.000, but NDCG@10 is only 0.797. Why not 1? The ideal list has ten exact products, because the query has 28. These ten have only six. No order of these ten can reach 1: the search must find better products, not only order them better.

The discount is a guess about people. Larkfield’s query log can test that guess, with one warning: the log is synthetic. Our code made its clicks with a model of how people look down a page. The chart compares the NDCG discount with the click rate by position in that log.

  • NDCG weight (1 ÷ discount)
  • Clicks, relative to rank 1 (synthetic log)
NDCG's weight falls slowly with the rank. Clicks in Larkfield's synthetic log fall much faster: rank 2 gets about half the clicks of rank 1.
Text description of the chart

A line chart with ranks 1 to 10 on the horizontal axis and a weight from 0 to 1 on the vertical axis. Both lines start at 1 at rank 1. The NDCG weight goes 1, 0.631, 0.5, 0.431, 0.387 and ends at 0.289 at rank 10. The click line, relative to rank 1, goes 1, 0.52, 0.332, 0.251, 0.202 and ends at 0.092 at rank 10.

In this log, rank 2 gets about half the clicks of rank 1, and rank 10 gets less than a tenth. NDCG still gives rank 10 more than a quarter of the weight of rank 1. So NDCG is kinder to the lower places than these clicks are. Real shops often see a fast fall too, but check your own log. Learn from clicks studies this curve.

One query is an example, not a measure. To compare two searches, you compute a measure for every test query and take the mean. The project does this with search eval. Its code is the course’s compare.py. We checked it against pytrec_eval, a widely used library for these measures. On every test query, both gave the same NDCG@10, MRR and recall@100: the largest difference was 4.4 × 10⁻¹⁶, a rounding difference.

Here are Larkfield’s search today and BM25 on the 243 test queries:

Four measures for the same two searches on Larkfield's 243 test queries. BM25 is better on every measure; the gap is largest on recall@100.
Text description of the chart

Four small panels, each with two rows. NDCG@10: today’s search 0.195 (95% interval 0.155 to 0.237), BM25 0.429 (0.381 to 0.476). MRR: today 0.312, BM25 0.438. Precision@5: today 0.227, BM25 0.311. Recall@100: today 0.146, BM25 0.388.

Each measure tells a different story about the same lists. Today’s search returns nothing for two thirds of the test queries, so it finds few exact products: recall@100 is only 0.146. Its MRR (0.312) is less bad, because when it does return something, the first result is often right. The interval beside NDCG@10 says how sure the number is. Build a test set that represents your users explains it.

Two choices hide behind these numbers. You must know them to read any result in this course.

  1. An unjudged product counts as irrelevant. If nobody graded a product for a query, it adds a gain of 0. So the project prints judged in the top 10 beside NDCG: the share of the top-10 results that have a judgment. A low share warns you that the number may be unfair. Judgments from a language model deals with this.
  2. A query with no good product has no NDCG. The query “printers” has judgments, but every one is irrelevant: Larkfield sells no printers. Its ideal DCG is 0, and you cannot divide by 0. The project leaves such a query out of the mean. Two test queries are like this (“printers” and its French version), so a mean over “243 test queries” is really over 241.

Each kind of search from Kinds of search has a measure that fits it.

Kind of search Example What the person needs Measure that fits
Known-item “kisner coffee table” One product, as high as possible MRR
Specific “grey outdoor cushion 18x18” A few good products near the top NDCG@10, precision@5
Broad “sofa” Many good products, a good first page NDCG@10
First stage of two stages any The good products somewhere in the top 100 recall@100

In the notebook, you run these measures on the 121 validation queries. The search is Larkfield’s hybrid search, which you build in Hybrid search. Known-item queries get the highest MRR (0.670). Broad queries get a high MRR (0.632) but a low NDCG@10 (0.511): the first product is usually good, but the rest of the page is not. A single measure would hide this.

The course uses NDCG@10 as its main number, because it uses all grades and the order of the first page. It reports MRR and recall@100 beside it, so you can see a change that NDCG hides.

You now compute the measures for both searches on every test query.

  1. In larkfield-search, with the virtual environment active, measure Larkfield’s search today on the test split:

    Terminal window
    search eval --run current
    current on 243 test queries: NDCG@10 0.195 (95% interval 0.155 to 0.237)
    recall@100 0.146, MRR 0.312, zero results 66.7%, judged in the top 10 83.7%; 0.1 ms a query (p50), 0.6 ms (p95)
  2. Measure BM25 on the same queries:

    Terminal window
    search eval --run bm25
    bm25 on 243 test queries: NDCG@10 0.429 (95% interval 0.381 to 0.476)
    recall@100 0.388, MRR 0.438, zero results 12.8%, judged in the top 10 64.6%; 0.1 ms a query (p50), 0.3 ms (p95)

    Your times will differ. The measures must be the same.

  3. Split BM25’s result by kind of search:

    Terminal window
    search eval --run bm25 --by qtype

    The first two lines repeat step 2. Then:

    qtype queries ndcg@10 low high zero-result rate
    broad 27 0.506 0.366 0.648 0.185
    known-item 80 0.422 0.338 0.509 0.275
    specific 136 0.419 0.360 0.476 0.029

Read the output of step 1 and step 2 together. judged in the top 10 is higher for today’s search (83.7%) than for BM25 (64.6%). Today’s search shows fewer products, and the products it shows match every word, so the judges graded most of them. BM25 shows more products that nobody judged. Under the “unjudged counts as irrelevant” rule, this makes BM25’s number a little unfair to BM25. Even so, BM25 is clearly better.

In step 3, BM25 is weakest on known-item queries. Many of them are names and product codes, which BM25 does not treat in a special way. Exact matches and rules fixes the codes.

Change one thing: the run. Before you run it, predict which kind of query today’s search handles worst, and why.

Terminal window
search eval --run current --by qtype
The output, and what it shows
qtype queries ndcg@10 low high zero-result rate
broad 27 0.426 0.254 0.587 0.444
known-item 80 0.099 0.053 0.151 0.800
specific 136 0.209 0.157 0.269 0.632

Known-item queries are the worst: NDCG@10 0.099, and 80% of them return nothing. A known-item query is often long or exact, such as a product name or a code. Every word must match, so one word that is spelt differently empties the page. Broad queries, often one word, do best.

Common mistake

A slice that does not exist

Symptom: Tomás wants the result by colour and types search eval --run bm25 --by colour. The command stops with a long error that ends:

KeyError: "None of [Index(['colour'], dtype='str')] are in the [columns]"

Cause: --by splits the queries by a column of queries.csv. Colour is a column of the products, not of the queries. The query columns that make useful slices are band, language, source, qtype and has_number.

Fix: choose one of those columns, for example search eval --run bm25 --by language. To study colour, you would first add a column to the queries, such as “the query names a colour”.

Consequence in search work: a slice is a question about the queries, not about the products. Decide which groups of queries matter to your users, and record them as query columns before you measure.

Check your understanding

A search returns these grades for a query with 4 exact products in all: 0, 2, 1, 2, 0. Compute precision@5, recall@5 and the reciprocal rank (exact products only).

Show the answer
  • Precision@5 = 0.4. Two of the five results are exact: 2 ÷ 5.
  • Recall@5 = 0.5. The top 5 finds 2 of the 4 exact products: 2 ÷ 4.
  • Reciprocal rank = 0.5. The first exact product is at rank 2: 1 ÷ 2.

Check your understanding

Two lists have the same six exact products in the top 10, so the same precision@10. In list A, the irrelevant product is at rank 1; in list B, it is at rank 5. Which list has the higher NDCG@10, and why?

Show the answer

List B. NDCG divides each gain by a discount that grows with the rank. In list A, an exact product loses rank 1, where its gain counts in full. Every product below it also moves down. For the rug-set query, NDCG@10 is 0.731 in BM25’s order (irrelevant at rank 5) and 0.615 with the irrelevant product at rank 1.

Check your understanding

Omar wants one number for known-item searches such as “kisner coffee table”. Which measure fits best, and what does it ignore?

Show the answer

MRR. A known-item search has one right product, and the person feels its rank: 1 ÷ rank of the first exact product. MRR ignores everything after that product, and it ignores partial products. That is fine for known-item searches but not for broad ones, where NDCG@10 fits better.

Recap

  • Precision@k is the share of the top k that is exact. Recall@k is the share of all exact products that the top k finds. Neither sees the order.
  • MRR is the mean of 1 ÷ the rank of the first exact product. It fits known-item searches.
  • NDCG@k uses every grade and the order: gain 2^grade − 1, divided by log2(rank + 1), added up (DCG), then divided by the ideal DCG. For “3 piece rug set with runners”: NDCG@5 0.726, NDCG@10 0.731.
  • On Larkfield’s test queries, BM25 has NDCG@10 0.429 (0.381 to 0.476) and today’s search 0.195 (0.155 to 0.237).
  • Unjudged products count as irrelevant (watch judged in the top 10), and a query with no good product has no NDCG.

You can now score one search on many queries. But are these queries like the queries people really type? Next, you check the test set against the log, and you measure how sure each number is.

Next: Build a test set that represents your users