26 · Inverted indexes and BM25

Break BM25 into term frequency, inverse document frequency, length normalization, and postings access. Combine algorithm definitions with real training-query experiments instead of only calling a library.

Predict first: Does repeating a query term 100 times in a document produce 100 times the score? Do long abstracts gain an advantage when length normalization is disabled?

Parameter-sensitivity experiments use only the first 30 training queries and the full corpus. Formal settings are not reselected on test scores.

Navigation: Previous · Next · Integrated experiment

English companion. All instructional Markdown is translated. Experiment code, Chinese language examples, execution counts, and saved outputs remain as in the source edition; historical output text may therefore be Chinese. The initial setup cell anchors the working directory and Python import path for this companion's deeper folder; it does not change the experiment. Saved outputs are historical evidence, not a new run. Run from the top after preparing the required data and models.

PYTHON · 01

# English companions live one directory deeper; keep the original experiment code unchanged.
from pathlib import Path as _TranslationPath
import os as _translation_os
import sys as _translation_sys
_translation_root = next((p for p in [_TranslationPath.cwd(), *_TranslationPath.cwd().parents]
                          if (p / "reclab").is_dir()), None)
if _translation_root is None:
    raise RuntimeError("Open this notebook from inside the Search Recommendation Ads Lab checkout.")
_translation_os.chdir(_translation_root)
if str(_translation_root) not in _translation_sys.path:
    _translation_sys.path.insert(0, str(_translation_root))

PYTHON · 02

from pathlib import Path
import os, sys
root = Path.cwd()
if not (root / 'reclab').exists(): root = root.parent
os.chdir(root); sys.path.insert(0, str(root))
import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
from reclab.search_lessons import context, query_vectors, score_query, labels
from reclab.search import BM25, rrf
from reclab.retrieval import topk, metrics
ctx = context()
print('Shared search run:', ctx['receipt']['run_id'])

Saved notebook output · not executed on this page

Shared search run: 20261030T124927-d1467622

1. A sparse matrix is an inspectable inverted index

X[d,t] counts term t in document d, with shape documents×vocabulary. Sparse storage keeps only nonzero entries; accessing a term column retrieves its documents. This implementation uses lowercase word tokenization without stopword filtering or stemming. That choice is itself an assumption.

PYTHON · 03

model=ctx['bm25']; index=model.index
print('document-term matrix:',index.shape,'nonzeros:',index.nnz)
term='vitamin'; col=model.vectorizer.vocabulary_.get(term)
if col is not None:
    posting=index[:,col].tocoo()
    print('term:',term,'documents containing term:',len(posting.data))
    display(pd.DataFrame({'internal_doc_idx':posting.row[:8]+1,'weighted_tf':posting.data[:8]}))
print('sparse bytes:',index.data.nbytes+index.indices.nbytes+index.indptr.nbytes)

Saved notebook output · not executed on this page

document-term matrix: (5183, 35954) nonzeros: 633946
term: vitamin documents containing term: 57

	internal_doc_idx	weighted_tf
0	256	4.455640
1	266	5.693689
2	307	8.608077
3	318	8.635369
4	328	4.074860
5	428	3.835336
6	433	8.454129
7	517	8.099405

sparse bytes: 7628088

2. Term-frequency saturation is not linear counting

Each query term contributes IDF * tf*(k1+1)/(tf+k1*(1-b+b*dl/avgdl)), with IDF=log(1+(N-df+.5)/(df+.5)). k1 controls saturation; b controls the length penalty. Frequent terms have lower IDF.

Change one variable: Hold length fixed, increase only tf, and plot saturation. The plot demonstrates the formula, not corpus-level effectiveness.

PYTHON · 04

tf=np.arange(1,51)
fig,ax=plt.subplots(figsize=(7,3))
for k1 in [.3,1.2,3.]: ax.plot(tf,tf*(k1+1)/(tf+k1),label=f'k1={k1}')
ax.set(xlabel='term frequency (fixed length)',ylabel='saturated TF factor');ax.legend();plt.show()
small=BM25(['cat cat dog','dog'])
expected=np.log(2)*(2*2.2)/(2+1.2*(.25+.75*3/2))
assert np.isclose(small.score('cat')[1],expected)

Saved notebook output · not executed on this page

<Figure size 700x300 with 1 Axes>

3. Actually change length normalization

Vary only b, fixing k1, documents, queries, and qrels. Each row is a macro-average on the same 30 training queries, never mixed with test. BM25 can build an index without labeled training data; that does not remove the need to validate parameters.

PYTHON · 05

qids=sorted(ctx['truth']['train'])[:30]
rows=[]
for b in [0.,.75,1.]:
    lexical=BM25(ctx['texts'],b=b)
    pred={q:topk(lexical.score(ctx['queries'][q]),10) for q in qids}
    rows.append({'b':b,**metrics(pred,labels(qids,'train'),10)})
display(pd.DataFrame(rows))
print('30 train queries, full corpus; no test-based selection.')

Saved notebook output · not executed on this page

	b	recall@10	ndcg@10	mrr@10	hit_rate@10
0	0.00	0.833333	0.735917	0.714815	0.833333
1	0.75	0.833333	0.777934	0.770833	0.833333
2	1.00	0.833333	0.765631	0.754167	0.833333

30 train queries, full corpus; no test-based selection.

4. Missing terms, repeated query terms, and ties

Query term frequencies are binarized, so repeating a term does not increase its weight. Out-of-vocabulary terms have no postings. If all query terms are unknown, every document scores 0 and topk returns stable internal-ID order; this is not evidence of a meaningful match. A production product may filter zero scores; this lesson exposes the boundary.

PYTHON · 06

assert np.array_equal(model.score('vitamin'),model.score('vitamin vitamin'))
unknown=model.score('zzzznonexistenttoken987654')
assert np.all(unknown[1:]==0)
print('OOV query top IDs (stable zero-score ties):',topk(unknown,5))
print('Interpretation: no lexical evidence, not five relevant matches.')

Saved notebook output · not executed on this page

OOV query top IDs (stable zero-score ties): [1, 2, 3, 4, 5]
Interpretation: no lexical evidence, not five relevant matches.

5. Inspect real failures before proposing a hypothesis

Count BM25 misses in the original 300-query results rather than showing only attractive examples. Vocabulary mismatch, synonyms, and technical abbreviations may explain failures, but scores alone cannot establish causes. Next, test semantic encoding on identical corpus and qrels.

PYTHON · 07

per=pd.DataFrame([{'qid':r['qid'],**r['metrics']['bm25']} for r in ctx['per_query']])
print('All test queries:',len(per),'zero-hit queries:',int((per['recall@10']==0).sum()))
display(per[per['recall@10']==0].head(8))

Saved notebook output · not executed on this page

All test queries: 300 zero-hit queries: 57

	qid	recall@10	ndcg@10	mrr@10	hit_rate@10
0	1	0.0	0.0	0.0	0.0
10	1049	0.0	0.0	0.0	0.0
13	1088	0.0	0.0	0.0	0.0
19	1110	0.0	0.0	0.0	0.0
31	1175	0.0	0.0	0.0	0.0
37	1191	0.0	0.0	0.0	0.0
39	1196	0.0	0.0	0.0	0.0
40	1197	0.0	0.0	0.0	0.0

Exercise: Change only k1 and rerun the same 30 training queries. Record improvements and regressions, and explain why an average change does not imply every query changed. Inspect reclab.search.BM25 and identify offline indexing versus online query work.

26 · Inverted indexes and BM25