Algo Ecom Bm25

BM25 Ranking Function

Overview

BM25 (Best Matching 25) is an improved TF-IDF ranking function that adds term frequency saturation and document length normalization. Score = Σ IDF(t) × (TF(t,d) × (k₁+1)) / (TF(t,d) + k₁ × (1 - b + b × |d|/avgdl)). Standard parameters: k₁=1.2, b=0.75. The backbone of most text search engines (Elasticsearch, Solr).

When to Use

Trigger conditions:

• Building product search with text-based relevance ranking
• Replacing basic TF-IDF with better document length normalization
• Tuning search relevance in Elasticsearch/Solr

When NOT to use:

• When semantic similarity matters more than keyword matching (use embeddings)
• For single-field exact matching (simpler methods suffice)

Algorithm

Copy code
IRON LAW: BM25 Has Two Critical Parameters — k₁ and b
k₁ controls term frequency saturation: higher k₁ = more weight to
repeated terms. k₁=0 ignores TF entirely (boolean).
b controls document length normalization: b=1 fully normalizes by
length, b=0 ignores length. Default k₁=1.2, b=0.75 works for most
cases but MUST be tuned for your specific corpus.

Phase 1: Input Validation + Tokenization

Tokenize each document to lowercase word tokens. Remove stop words before counting — the bundled script drops a standard English stop list (the, a, an, and, or, but, of, in, on, at, to, for, with, by, from, as, is, are, was, were, be, been, being). Then build an inverted index: term → list of (document, term frequency). Compute: document lengths (post stop-word removal), average document length, document frequency per term.

⚠️ Stop-word removal affects |d| and avgdl: because stop words are dropped before length is measured, hand-computing BM25 without removing them will give the wrong length normalization and scores will be off by 3–5%. If you're reproducing BM25 by hand to compare against the script, apply the same stop list first — or just run the script.

Gate: Index built, statistics computed, corpus non-empty.

Phase 2: Core Algorithm

For query Q with terms t₁...tₙ against document d:

1. For each query term tᵢ: compute IDF(tᵢ) = log((N - DF(tᵢ) + 0.5) / (DF(tᵢ) + 0.5) + 1)
2. Compute TF component: (TF(tᵢ,d) × (k₁+1)) / (TF(tᵢ,d) + k₁ × (1 - b + b × |d|/avgdl))
3. Score(d, Q) = Σᵢ IDF(tᵢ) × TF_component(tᵢ, d)
4. Rank documents by score descending

⚠️ IDF variant lock-in: BM25 has several IDF formulations in the wild (Robertson-Sparck Jones, classic Okapi, Lucene's smoothed +1, BM25+, BM25L). This skill — and the bundled script — uses the Lucene-style smoothed variant shown above (log((N - df + 0.5) / (df + 0.5) + 1)), which never returns negative IDF for very common terms. If you compare scores against another engine (Elasticsearch, Solr, Whoosh), they may differ by ~3–5% even on identical inputs. Do not "correct" the script unless you intend to change the variant globally.

Phase 3: Verification

Spot-check: query "red shoes" should rank documents containing both "red" and "shoes" higher than documents with only one term. Shorter product titles with both terms should rank above long descriptions with sparse mentions. Gate: Relevance spot-check passes on 10+ test queries.

Phase 4: Output

Return ranked results with scores.

Output Format

jsonCopy code
{
  "results": [{"doc_id": "SKU-123", "score": 12.5, "title": "Red Running Shoes"}],
  "metadata": {"query": "red shoes", "hits": 85, "k1": 1.2, "b": 0.75, "avg_doc_length": 45}
}

Examples

Sample I/O

Input: Query "wireless earbuds", corpus of 1000 product listings Expected: Products with "wireless earbuds" in title rank highest; "wireless headphones" ranks lower (no "earbuds" term).

Edge Cases

Gotchas

• Multi-field scoring: E-commerce products have title, description, brand, category. Weight fields differently: title match > description match. Use field-boosted BM25.
• Synonyms and stemming: BM25 is keyword-exact. "earphones" won't match "earbuds." Add synonym expansion and stemming in the query pipeline.
• Parameter tuning: Default k₁=1.2, b=0.75 is reasonable but not optimal. Tune on relevance judgments specific to your catalog.
• Numeric attributes: BM25 doesn't handle numeric filtering (price range, ratings). Use it for text relevance, then combine with numeric filters.
• Zero-result queries: When BM25 returns nothing, fall back to fuzzy matching or semantic search rather than showing empty results.

Scripts

Run python scripts/bm25.py --verify to execute built-in sanity tests.

References

• For BM25F multi-field extension, see references/bm25f.md
• For parameter tuning methodology, see references/parameter-tuning.md