Skip to content
Français

BM25

  • Lesson 9
  • 40 min
  • Module 3: Lexical search: the baseline to beat

Where we are

An inverted index finds every product that has our words. It does not say which product is best. In this lesson, we score products with BM25, see each part of the score, and give the title more weight than the description.

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

What you will be able to do

Put the best products first among the hundreds that match a query, with a score that you can explain word by word.

NotebookDo the calculations of this lesson in a notebookColab · Kaggle · GitHub

The notebook computes BM25 by hand for six products and checks it with the bm25s library. Then it explains a real score, part by part, and you tune the title weight on the validation queries. Its setup cells download the data, so it needs no local setup. About 25 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

What you need on your computer

  • The project larkfield-search with its virtual environment active, and the labs repository next to it, as in the earlier modules. This lesson adds four files and the README from the snapshot end-of-m03.

A customer gives the shop assistant a note: “garden hose”. She looks at two product labels. The first label is short: “garden hose with reel”. The second is a long catalogue page about a planter. It says “garden” twice and, near the end, “connects to your garden hose”.

She uses three clues.

  1. A rare word is a strong clue. Almost every garden product says “garden”. Few products say “hose”. So “hose” tells her more than “garden”.
  2. A repeated word is a clue, but less each time. A label that says “hose” three times is probably about hoses. But the third “hose” adds less than the first.
  3. A word in a short label means more than the same word lost in a long page. On a short label, every word is about the product.

She picks the short label. BM25 is a formula with the same three clues.

The last lesson ended with a problem. “garden hose” with “any word may match” finds 1,439 products. A person reads ten.

A first idea: count the query words in each product. But 24 products have both words, and they all get 2: a tie. The 1,415 others all get 1: another tie. The count treats “garden” and “hose” as equal, and a 7-word title like a 300-word description.

BM25 gives each product a score for a query, and the highest scores come first. BM25 means “Best Matching 25”: a ranking formula from the 1990s, named after the versions that its authors tried. It is still the default ranking of the common open-source search engines.

The score is a sum. Each query word adds one part. The part of a word is its rarity, multiplied by a share between 0 and 1. The share grows when the word appears more often in the product, and falls when the product is long. A word that is not in the product adds 0.

The rarity of a word is its IDF, the inverse document frequency. The document frequency (df) of a word is the number of products that contain it: the size of its postings list. “Inverse” means that a small df gives a large IDF. With N products in the catalogue:

IDF=ln⁡(1+N−df+0.5df+0.5)\text{IDF} = \ln\left(1 + \frac{N - \text{df} + 0.5}{\text{df} + 0.5}\right)

ln is the natural logarithm. It makes the IDF grow slowly: a word in 10 times fewer products gets about 2.3 more, not 10 times more. In Larkfield’s catalogue, with N = 40,066:

Word In how many products (df) IDF
the 28,152 0.353
chair 4,293 2.233
garden 1,352 3.389
headboard 1,089 3.605
hose 111 5.884
emma 6 8.727

“the” is almost worthless. “hose” is worth almost twice “garden”. “emma”, a name in six products, is worth the most.

The number of times a word appears in a product is its term frequency (tf). BM25 does not multiply by tf. It uses a share that grows quickly at first, then slowly:

share=tftf+k1×norm\text{share} = \frac{\text{tf}}{\text{tf} + k_1 \times \text{norm}}

For a product of average length, the norm is 1. With the usual setting k1 = 1.2, one appearance gives a share of 1 ÷ 2.2 = 0.455. Two give 0.625, and ten give 0.893. The share never reaches 1. This is saturation: after a few repeats, more repeats add almost nothing. So a seller cannot win by writing “hose hose hose”.

k1 sets how fast the share saturates. A small k1 (such as 0.5) means that the first appearance is almost all that counts. A large k1 (such as 3) gives repeats more weight.

The norm depends on the product’s length, compared with the average length of the catalogue:

norm=1−b+b×lengthaverage length\text{norm} = 1 - b + b \times \frac{\text{length}}{\text{average length}}

A short product has a norm below 1, so the same tf gives a larger share. A long product has a norm above 1. b sets how much length counts: b = 0 ignores length, and b = 1 counts it fully. The usual setting is b = 0.75.

The chart shows the share for three products of Larkfield’s catalogue: a short one, one of average length (71.7 words), and a long one.

The share of a word's IDF that a product gets, by tf and product length: 7 words, the average of 72 words, and 200 words (k1 1.2, b 0.75). Computed with the formula.
Text description of the chart

The x-axis is tf, from 0 to 10. The y-axis is the share of the IDF, from 0 to 1. There are three curves. All three start at 0 for tf 0, rise steeply, then flatten. A short product of 7 words gets 0.721 for one appearance and 0.963 for ten. A product of average length, 72 words, gets 0.455 for one appearance, 0.714 for three and 0.893 for ten. A long product of 200 words gets less for each tf: the curve is the lowest of the three. For every length, the step from tf 1 to tf 2 is much larger than the step from tf 9 to tf 10.

Put the three clues together. For each query word in a product:

part=IDF×tftf+k1×(1−b+b×lengthaverage length)\text{part} = \text{IDF} \times \frac{\text{tf}}{\text{tf} + k_1 \times \left(1 - b + b \times \frac{\text{length}}{\text{average length}}\right)}

The score of the product is the sum of the parts of the query words. Many books write an extra factor (k1 + 1) on top. It multiplies every score by the same number, so the order of the products does not change. The project’s library, bm25s, leaves it out, like the Lucene search library.

Take the six products of the last lesson and the query “outdoor hose”. There are N = 6 products, with an average length of 20 ÷ 6 = 3.333 tokens. “outdoor” is in 3 products, so its IDF is ln(1 + 3.5 ÷ 3.5) = 0.693. “hose” is in 2 products, so its IDF is ln(1 + 4.5 ÷ 2.5) = 1.030. Every word appears once, so tf = 1.

Product Length k1 × norm “outdoor” part “hose” part Score Rank
F hose reel cart 3 1.110 0 1.030 × 1 ÷ 2.110 = 0.488 0.488 1
C garden hose with reel 4 1.380 0 1.030 × 1 ÷ 2.380 = 0.433 0.433 2
A grey outdoor cushion 3 1.110 0.693 × 1 ÷ 2.110 = 0.329 0 0.329 3
B blue outdoor cushion cover 4 1.380 0.291 0 0.291 4
E outdoor sofa with cushions 4 1.380 0.291 0 0.291 4
D grey sofa 2 0.840 0 0 0 —

The hose products come first, because “hose” is rarer than “outdoor”. F beats C, because F has 3 words and C has 4. The notebook computes this table and checks it against bm25s.

The project’s run bm25 is this formula, with k1 1.2 and b 0.75, on the title and the description together. You measured it in Module 1: NDCG@10 0.429 on the test queries. Now you look inside one of its scores.

  1. Copy this module’s files from the snapshot end-of-m03. They are the field runs, the command search explain, the product-code rule of the next lesson, their tests and the README:

    Terminal window
    S=../nextia-learning-labs/C38/snapshots/end-of-m03
    for f in larkfield_search/runs/fields.py larkfield_search/rules.py larkfield_search/commands/explain.py tests/test_fields.py README.md; do
    cp "$S/$f" "$f"
    done
  2. Run the tests:

    Terminal window
    python -m pytest -q
    ................... [100%]
    19 passed in 1.01s

    Three tests are new. One checks that the parts of search explain add up to the library’s score. Your time will differ.

  3. Search “emma headboard” with BM25. It is a real WANDS validation query:

    Terminal window
    search query "emma headboard" --run bm25 -k 7
    bm25: "emma headboard" -> 7 results (query W-481: judged results are marked)
    1. LK-97580 emma large wooden playground bird activity center Bird Play Stand & Playce 51.99 [irrelevant]
    2. LK-33434 emma body pillowcase Sheets And Sheet Sets 173.99 [irrelevant]
    3. LK-78778 emma-lea solid wood low profile storage platform bed 113.99 [irrelevant]
    4. LK-39071 multicolor reversible floral cotton 4 piece quilt set Bedding Sets 14.99 [not judged]
    5. LK-19417 cumulus landscape ii by emma scarvey - wrapped canvas painti Wall Art 250.99 [out of stock] [irrelevant]
    6. LK-53888 neutral arrangement i by emma scarvey - wrapped canvas paint Wall Art 147.99 [out of stock] [irrelevant]
    7. LK-45931 bali hai open-frame headboard Headboards 11.99 [partial]

    A bird activity centre comes first. The first headboard is at rank 7.

  4. Ask for the parts of the first product’s score, then of the headboard’s:

    Terminal window
    search explain "emma headboard" LK-97580
    search explain "emma headboard" LK-45931
    BM25 of LK-97580 "emma large wooden playground bird activity center" for "emma headboard" (field all, k1 1.2, b 0.75)
    word tf df IDF length avg part
    emma 1 6 8.727 7 71.7 6.288
    headboard 0 1089 3.605 7 71.7 0.000
    sum of the parts 6.288; the index's score 6.288
    BM25 of LK-45931 "bali hai open-frame headboard" for "emma headboard" (field all, k1 1.2, b 0.75)
    word tf df IDF length avg part
    emma 0 6 8.727 48 71.7 0.000
    headboard 5 1089 3.605 48 71.7 3.054
    sum of the parts 3.054; the index's score 3.054

    Each row is one query word, with its tf, df and IDF, the product’s length in tokens, and the catalogue’s average length. The last line checks the sum of the parts against the index’s own score.

The diagram puts the two scores side by side.

Query emma headboard. Left: LK-97580, emma large wooden playground bird activity center. emma is in 6 products, IDF 8.73; it appears 1 time in 7 words, so 0.72 times 8.73 equals 6.29. headboard is not in this product, 0. Score 6.29, rank 1, judged irrelevant. Right: LK-45931, bali hai open-frame headboard. emma is not in this product, 0. headboard is in 1,089 products, IDF 3.60; it appears 5 times in 48 words, so 0.85 times 3.60 equals 3.05. Score 3.05, rank 7, judged partial. A dark bar for the emma part is about twice as long as a light bar for the headboard part. Below: the formula, with k1 1.2, b 0.75 and an average length of 71.7 words.
The BM25 score of two products for “emma headboard”, part by part. One rare word in a very short product beats a common word five times in a longer product.
Text description of the diagram

The query is “emma headboard”. On the left is product LK-97580, “emma large wooden playground bird activity center”. “emma” is in 6 products, so its IDF is 8.73. It appears once in a product of 7 words, which gives a share of 0.72. 0.72 × 8.73 = 6.29. “headboard” is not in this product and adds 0. The score is 6.29: rank 1, and the judges graded it irrelevant. On the right is LK-45931, “bali hai open-frame headboard”. “emma” adds 0. “headboard” is in 1,089 products, so its IDF is 3.60. It appears 5 times in 48 words, which gives a share of 0.85. 0.85 × 3.60 = 3.05: rank 7, graded partial. Under each product, a bar shows its score on the same scale. The bar of the bird centre is about twice as long.

The bird activity centre has no description, so its text is only its 7-word title. One rare “emma” in 7 words gives 72% of a very large IDF. The headboard gets 85% of a much smaller IDF, because 1,089 products say “headboard”.

BM25 did exactly what its three clues say. But the clues do not know what the person wants. In “emma headboard”, “headboard” is the kind of product, and “emma” is only a name. Module 4 detects the kind of product in the query, and Module 6 learns from judged queries which signals matter.

The project uses k1 = 1.2 and b = 0.75 for every BM25 run, the usual defaults. You can tune them on validation queries. Expect small gains: they change how much repeats and length count, not which words match. In the notebook, change K1 and B in the first cell and run it again.

So far, the title and the description are one block of text. But a product has fields: separate parts with different roles. Larkfield’s products have four that matter here:

  • title: a few words that name the product;
  • description: a long text from the seller;
  • category: the product class and the category path, such as “Headboards” and “Furniture / Bedroom Furniture / Headboards”;
  • attributes: colour, style, material and other details.

With one BM25 index for each field, the score becomes a weighted sum. If the title weight is 3, a title match counts three times as much as a description match:

score=wtitle×BM25title+wdescription×BM25description+wcategory×BM25category+wattributes×BM25attributes\text{score} = w_{\text{title}} \times \text{BM25}_{\text{title}} + w_{\text{description}} \times \text{BM25}_{\text{description}} + w_{\text{category}} \times \text{BM25}_{\text{category}} + w_{\text{attributes}} \times \text{BM25}_{\text{attributes}}

The run bm25-fields uses weights. Try it on the same query:

Terminal window
search query "emma headboard" --run bm25-fields -k 4
bm25-fields: "emma headboard" -> 4 results (query W-481: judged results are marked)
1. LK-33434 emma body pillowcase Sheets And Sheet Sets 173.99 [irrelevant]
2. LK-19612 phirun bookcase headboard Headboards 30.99 [partial]
3. LK-77778 prepac storage bookcase headboard Kids Headboards 605.99 [partial]
4. LK-83984 driftwood panel headboard Headboards 44.99 [partial]

The category field says “Headboards”, so headboards now fill ranks 2 to 10. A pillowcase named “emma” still comes first. But one query is a story, not a measurement.

Choose the weights on the validation queries

Section titled “Choose the weights on the validation queries”

Which weights are best? The project tried a grid of 96 settings: title 1, 2, 3 or 5; description 0.5 or 1; category 0, 0.5, 1 or 2; attributes 0, 0.5 or 1. It measured each one on the 121 validation queries, never on the test queries. The best was title 1, description 1, category 0.5, attributes 0: NDCG@10 0.459. This is the setting of bm25-fields:

Terminal window
search eval --run bm25-fields --split validation
bm25-fields on 121 validation queries: NDCG@10 0.459 (95% interval 0.388 to 0.529)
recall@100 0.400, MRR 0.392, zero results 11.6%, judged in the top 10 69.9%; 0.2 ms a query (p50), 0.8 ms (p95)

--set changes one weight for one command, without editing code. Try the setting that many people would pick by hand, with the title first:

Terminal window
search eval --run bm25-fields --set title=3 --set category=1 --set attributes=0.5 --split validation
bm25-fields on 121 validation queries: NDCG@10 0.453 (95% interval 0.383 to 0.521)
recall@100 0.416, MRR 0.377, zero results 11.6%, judged in the top 10 71.1%; 0.2 ms a query (p50), 0.5 ms (p95)

The hand-picked setting scores 0.453, so the tuned one wins on validation by 0.006. Notice that the title needs no extra weight here. Most titles repeat in the descriptions, so a title word is already counted twice.

The chart shows five settings on both sets of queries. The top panel is what we could see when we chose. The bottom panel is the test, measured once, after the choice.

NDCG@10 of five ways to use the fields, with 95% intervals. The tuned weights win on validation and lose on test. All the differences are small next to the intervals.
Text description of the chart

Two panels show NDCG@10 with 95% intervals. Validation (121 queries): one field 0.432 (0.363 to 0.502); title only 0.428; equal weights 0.416; hand-picked 3, 1, 1, 0.5 0.453 (0.383 to 0.521); tuned 1, 1, 0.5, 0 0.459 (0.388 to 0.529). Test (243 queries): one field 0.429 (0.381 to 0.476); title only 0.423; equal weights 0.400; hand-picked 0.447 (0.397 to 0.497); tuned 0.423 (0.375 to 0.471). The tuned row is highlighted. Every interval overlaps the others.

On the test queries, the order changes: tuned 0.423, hand-picked 0.447, one field 0.429. Is the change real? A paired comparison answers this, query by query, as in Build a test set that represents your users. Hand-picked minus tuned:

Queries Difference in NDCG@10 95% interval Better / worse / the same
Validation (121) −0.006 −0.029 to +0.014 33 / 36 / 52
Test (241 that have a right product) +0.024 +0.009 to +0.038 89 / 50 / 102

On validation, the difference of 0.006 is noise: its interval includes 0. In fact, 19 of the 96 settings scored within 0.01 of the best. The grid picked a winner among near-ties. On test, the hand-picked weights are better, and the interval does not include 0.

Priya keeps the tuned weights in the project. Tomás asks: “But the hand-picked ones are clearly better on test. Why not switch?”

Then the test queries would choose the weights. The reported score would look better than the search really is.

So the rule stays: choose on validation, report test once, and do not go back. The report is honest: “Per-field BM25 with tuned weights: 0.423 on test. It is not better than one field (−0.006, interval −0.025 to +0.012).”

Two lessons for next time:

  • A small win on validation is not a win. With 121 queries, differences below about 0.02 are noise. When many settings tie, prefer the simplest one, or get more validation queries.
  • “Title over description” is not a law. It depends on the catalogue. Here, title words are in the description too.

The machine learning course explains the same rule for models in Train, validation and test sets.

When to use BM25, when not, and what it costs

Section titled “When to use BM25, when not, and what it costs”

Use BM25 as the first ranking of any word search, and as the baseline that every later method must beat. It needs no training data and no model. In this course, it more than doubles NDCG@10 against Larkfield’s search today: 0.429 against 0.195.

What it costs. Very little. A query takes 0.6 milliseconds at the median, on one thread (measured in Module 8). All the lexical indexes of this module take 80.9 MB on the disk.

When it fails. It ranks by words, so it fails where words mislead:

  • a rare name pulls up anything with that name (“emma headboard”);
  • a misspelt word adds nothing (“grey outdor cushion”);
  • another word for the same thing adds nothing (“couch” and “sofa”);
  • a product code is not a word of the text (next lesson).

This is the module’s independent task. Choose your own field weights on the validation queries only, with --set and --split validation. For example:

Terminal window
search eval --run bm25-fields --set title=2 --set category=1 --split validation

Keep a table of your settings and their NDCG@10. Run your best setting once on the test queries, without --split. Report it against the one-field bm25 row (0.429 on test), with both intervals. Was your validation win larger than the noise?

What we got: title 2, description 1, category 1, attributes 0 scores 0.448 on validation (interval 0.378 to 0.515). That is below the tuned setting’s 0.459, so we would keep the tuned setting, and its test score of 0.423. The difference of 0.011 is also inside the noise.

Common mistake

Choosing the weights on the test queries

Symptom: you try ten weight settings with search eval and no --split. The best scores 0.447 on test, and you report 0.447. Next month, a new set of queries gives 0.42, and nobody understands why the search got worse.

Cause: search eval measures on the test queries by default. Ten tries on test are ten chances to find a setting that is lucky on these 243 queries. The reported score includes that luck.

Diagnosis: look at your notes or your terminal history. If any setting was chosen after a run on the test split, the test score is optimistic. There is no way to remove the luck afterwards.

Fix: choose with --split validation only. Run the chosen setting on test once and report it, even if it is lower. For a fresh, unbiased check later, keep a held-out set that nobody uses to choose, as in Build a test set that represents your users.

Consequence in AI work: every tuned weight, threshold or prompt carries this risk. A team that tunes on its test set reports progress that users never see.

Check your understanding

Compute the BM25 part of “hose” in product C “garden hose with reel” of the six products. Use N = 6, df = 2, tf = 1, length 4, average length 3.333, k1 1.2 and b 0.75.

Show the answer

IDF = ln(1 + (6 − 2 + 0.5) ÷ (2 + 0.5)) = ln(2.8) = 1.030. Norm = 1 − 0.75 + 0.75 × 4 ÷ 3.333 = 1.15, so k1 × norm = 1.38. Share = 1 ÷ (1 + 1.38) = 0.420. Part = 1.030 × 0.420 = 0.433. Product F is one word shorter, so its share is larger (0.474) and its part is 0.488.

Check your understanding

Explain, with the parts of the score, why BM25 puts a bird activity centre above a headboard for “emma headboard”.

Show the answer

The bird activity centre gets only the part of “emma”. “emma” is in 6 of 40,066 products, so its IDF is very high (8.727). The product has only 7 words, far below the average of 71.7, so one appearance gives 72% of that IDF: 6.288. The headboard gets only the part of “headboard”. Its share is 85% (5 times in 48 words), but of a small IDF (3.605, in 1,089 products): 3.054. BM25 cannot know that “headboard” is the kind of product and “emma” only a name.

Check your understanding

Omar says: “The hand-picked weights scored 0.447 on test, and our tuned ones 0.423. Switch to the hand-picked weights and report 0.447.” What do you answer?

Show the answer

We do not switch, and we report 0.423. If the test queries choose the weights, they stop being a fair test, and 0.447 would include the luck of that choice. On validation, where we could choose, the two settings differed by only −0.006 (interval −0.029 to +0.014): a tie. Next time, treat such small wins as ties, and prefer the simpler setting or get more validation queries.

Recap

  • BM25 scores a product as a sum of parts, one per query word. Each part is the word’s IDF (rarity) times a share that grows with tf (with saturation) and falls with the product’s length.
  • k1 sets how fast repeats saturate, and b how much length counts. The project uses the usual 1.2 and 0.75.
  • search explain shows every part. “emma headboard” puts a bird activity centre first. One rare word in a 7-word product (6.288) beats a common word five times in a 48-word product (3.054).
  • Fields with weights score the title, the description, the category and the attributes apart. Tuned on validation, they won by 0.006, which is noise, and lost on test (0.423 against 0.447). We keep them and report 0.423, because the test queries must not choose.

You can now rank any product by its words, and explain each score. But some queries have no useful words at all: “LK-91857” is a product code, and BM25 finds nothing for it. Next, you add an exact-match rule, and measure when a rule beats any score.

Next: Exact matches and rules