Class Notes

Lab 04

Ranked Retrieval: TF-IDF, Cosine Similarity and BM25

TF-IDF Cosine similarity BM25 Cranfield
Work in progress These notes are still being written and reviewed: content may change, and some parts may still contain mistakes.

Overview of the lab

The move from "Does this document match?" to "How strongly does this document match, and where should it rank?" The focus is conceptual understanding, supported by small calculations and a short live retrieval demo.

Boolean matching → term weighting → TF-IDF → vector-space ranking → cosine similarity → BM25
  1. Why ranking? Boolean retrieval cannot order the documents that match.
  2. TF, DF and IDF: how often a term occurs, in how many documents, and how discriminative it is.
  3. TF-IDF: local frequency times global rarity.
  4. The vector-space model and cosine similarity: documents and queries as vectors.
  5. Live demo: TF-IDF on Cranfield.
  6. Why BM25? Term-frequency saturation and document-length normalization.
  7. TF-IDF vs BM25: different ranking functions give different ranked lists.
  8. Summary, and an optional exercise.

Learning objectives

By the end you should be able to explain:

  • why Boolean retrieval is insufficient for ranked search;
  • the difference between term frequency, document frequency and inverse document frequency;
  • why TF-IDF gives high weight to discriminative terms;
  • how documents and queries become vectors, and why cosine similarity is used;
  • why TF-IDF has limitations, and how BM25 introduces term-frequency saturation and document-length normalization;
  • why BM25 remains an important lexical retrieval baseline.
Part I

Why ranking?

Boolean retrieval, from the earlier labs, gives each document a yes or no:

query: information AND retrieval
D1match
D2no match
D3match
D4match

D1, D3 and D4 all match. But which one should be first? A retrieval system needs a scoring function \(\operatorname{score}(q, d)\), and then sorts the documents by score: \(d_{(1)}, d_{(2)}, d_{(3)}, \ldots\)

  • Boolean retrieval answers: does the document satisfy the query?
  • Ranked retrieval answers: how relevant does the document appear to be?

Worked example

A tiny corpus of five documents and the query retrieval relevant documents:

idtext

Which document would you put first? Most people choose D1: it has all three query words. How can we make a machine arrive at a similar ranking? That question motivates term weighting.

Part II

TF, DF and IDF

Term frequency

How often does term \(t\) occur in document \(d\)? That is \(tf(t, d)\). For retrieval: D1 → 1, D2 → 1, D3, D4, D5 → 0. A first intuition: more occurrences, perhaps more evidence of relevance. But raw frequency is not enough.

Document frequency

In how many documents does term \(t\) appear? That is \(df_t\). In the toy corpus retrieval appears in 2 documents, relevant in 1 and documents in 4. So relevant is more discriminative than documents.

Try it: the tf / df table

Edit the query; the table has one row per query term. Click a row to highlight that term in the documents. D4 says document, not documents, so with this simple tokenization it does not match: documents and queries must be preprocessed the same way.

Inverse document frequency

📐 Inverse document frequency

With \(N\) the number of documents and \(df_t\) the number of documents containing \(t\):

\[ idf(t) = \log \frac{N}{df_t} \]

If a term appears in every document, \(df_t = N\) and \(idf(t) = \log 1 = 0\).

The intuition: a term is useful for retrieval when it helps distinguish documents. Common terms carry less information; rare terms carry more. For \(N = 5\): retrieval gets \(\log(5/2)\), relevant \(\log(5/1)\), documents \(\log(5/4)\). The exact digits matter less than the ordering: relevant > retrieval > documents.

Part III

TF-IDF

📐 TF-IDF weight
\[ tfidf(t, d) = tf(t, d) \times idf(t) \]

It combines two signals: the term is frequent in this document, and the term is rare in the collection. A document receives a high score when it contains terms that are both locally important and globally discriminative.

See it: the TF-IDF matrix of the toy corpus

One column per document and one for the query; rows are the 27 vocabulary terms. The query's weights use the collection's IDF values. Query terms are highlighted; empty cells are 0.

Why raw TF is imperfect

Suppose a term appears 1 time, 2 times, 20 times. Should 20 occurrences give 20 times the evidence of one occurrence? Usually not. A common fix is to use \(1 + \log tf\) instead of \(tf\) (the second option above); BM25 takes this further.

Part IV

The vector-space model and cosine similarity

Once every term has a weight, a document can be represented as a vector. With the vocabulary [information, retrieval, relevant, documents], a document might be \(d = [0.8,\ 1.2,\ 1.5,\ 0.3]\) and a query \(q = [0,\ 1.0,\ 1.4,\ 0.2]\). The retrieval problem becomes: which document vector is closest to the query vector?

📐 Cosine similarity
\[ \cos(q, d) = \frac{q \cdot d}{\|q\| \, \|d\|} \]

The dot product rewards shared weighted terms; the denominator normalizes for vector magnitude. For the example: \(q \cdot d = 1.2 + 2.1 + 0.06 = 3.36\), \(\|q\| = \sqrt{3} \approx 1.732\), \(\|d\| = \sqrt{4.42} \approx 2.102\), so \(\cos(q, d) \approx 0.923\).

  • Why normalize? Without it, long documents may get large scores simply because they contain many terms. Cosine compares the direction of the vectors, not their magnitude.
  • Geometry: a small angle between \(q\) and \(d\) means a high cosine, a large angle a low one. For non-negative TF-IDF vectors, a cosine near 1 means very similar and near 0 means little overlap.

Try it: rank the toy documents

Each bar is \(\cos(q, d)\) with the TF-IDF vectors above; the table shows the dot product and the two lengths. D1 comes first, as intuition said. Try a query with an unseen word, or document (singular).

Recap so far

tfHow common is the term inside this document?
dfHow common is the term across documents?
idfHow discriminative is the term?
tf-idfHow important is the term for this document?
cosine similarityHow similar are the query and document vectors?
Part V

Live demo: TF-IDF on Cranfield

Now on an actual retrieval collection. The Cranfield collection of aeronautics abstracts has 1,400 documents, 225 queries and relevance judgments. Here we use it only to demonstrate ranking; formal evaluation with the judgments comes in Lab 05 (dataset documentation).

setup.py Python 
# pip install ir_datasets scikit-learn
import ir_datasets

dataset = ir_datasets.load("cranfield")
docs = list(dataset.docs_iter())
queries = list(dataset.queries_iter())
print(len(docs))       # 1400
print(len(queries))    # 225

doc_ids = [d.doc_id for d in docs]
titles = [d.title for d in docs]
texts = [f"{d.title} {d.text}" for d in docs]

Build TF-IDF

tfidf.py Python 
from sklearn.feature_extraction.text import TfidfVectorizer

vectorizer = TfidfVectorizer(lowercase=True, norm="l2")
X = vectorizer.fit_transform(texts)
print(X.shape)   # (1400, 7435)

Rows are documents, columns are terms. The matrix is sparse because most terms do not occur in most documents:

💡 scikit-learn uses a smoothed IDF, \(\ln\frac{1 + N}{1 + df_t} + 1\), not the textbook \(\log(N / df_t)\), so its numbers differ from a hand calculation while the idea is the same. Its default tokenizer keeps words of two or more letters and digits.

Search function

search_tfidf.py Python 
from sklearn.metrics.pairwise import cosine_similarity

def search_tfidf(query, k=5):
    q = vectorizer.transform([query])
    scores = cosine_similarity(q, X).ravel()
    top = scores.argsort()[::-1][:k]
    return [(doc_ids[i], titles[i], scores[i]) for i in top]

print(queries[0].query_id, queries[0].text)
search_tfidf(queries[0].text)
# ('13', 'similarity laws for stressing heated wings .', 0.285...)
# ('184', 'scale models for thermo-aeroelastic research .', 0.268...)
# ('12', 'some structural and aerelastic considerations of high speed flight .', 0.201...)
# ('875', 'models for aeroelastic investigation .', 0.192...)
# ('486', 'similarity laws for aerothermoelastic testing .', 0.172...)

Try it: search the 1,400 Cranfield abstracts

The same TF-IDF model, computed in the page. Choose one of the 225 Cranfield queries or type your own; click a result to read the start of its abstract.

The pipeline to remember

documents → TF-IDF matrix  ·  query → TF-IDF query vector  ·  query vector vs matrix → cosine similarity → scores → sorting → ranked documents
Part VI

Why BM25?

TF-IDF is elegant, but it has two important limitations: term frequency should saturate, and document length should affect scoring.

Problem 1: term-frequency saturation

The query contains engine. Document A has it once, document B 5 times, document C 50 times. Is C really 50 times stronger than A? Probably not: after several occurrences, each additional one provides less new evidence.

Problem 2: document length

Document A has 50 words and engine 3 times; document B has 5,000 words and engine 3 times. The same term frequency means something different in the two documents.

📐 BM25
\[ \operatorname{BM25}(q, d) = \sum_{t \in q} idf(t) \, \frac{tf(t,d)\,(k_1 + 1)}{tf(t,d) + k_1 \left(1 - b + b \, \frac{|d|}{\operatorname{avgdl}}\right)} \]

No need to memorize it; read it piece by piece. \(|d|\) is the length of the document and \(\operatorname{avgdl}\) the average length in the collection.

BM25 piece by piece

  • \(idf(t)\): rare query terms matter more; the same broad idea as in TF-IDF.
  • \(tf(t, d)\): a term appearing more often usually contributes more, but because it also appears in the denominator, the gain gradually saturates.
  • \(k_1\): controls the saturation; typical value about 1.2. Higher values let repeated terms keep contributing more.
  • \(b\): controls document-length normalization; typical value about 0.75. \(b = 0\) ignores document length; \(b = 1\) gives strong length normalization.

See it: saturation (\(k_1\))

The term's contribution for \(tf = 1 \ldots 30\), with \(idf = 1\). Compare with raw TF, which grows linearly.

1.2
1

BM25 (b = 0.75)   raw tf × idf (linear)   ceiling \(k_1 + 1\)

See it: length normalization (\(b\)) on real documents

Cranfield documents that contain a term the same number of times but have different lengths. The table shows the \(tf\) part of the formula (\(idf = 1\), \(k_1 = 1.2\)) for four values of \(b\).

💡 BM25 in one sentence: does this document contain the query terms often enough to matter, while accounting for how rare the terms are and how long the document is?

Part VII

TF-IDF vs BM25

For the comparison we use an existing BM25 implementation, rank-bm25: the point is the ranking behaviour, not implementing the formula from scratch.

search_bm25.py Python 
# pip install rank-bm25
from rank_bm25 import BM25Okapi

tokenized_docs = [text.lower().split() for text in texts]
bm25 = BM25Okapi(tokenized_docs)

def search_bm25(query, k=5):
    tokens = query.lower().split()
    scores = bm25.get_scores(tokens)
    top = scores.argsort()[::-1][:k]
    return [(doc_ids[i], titles[i], scores[i]) for i in top]

query = queries[0].text
print("TF-IDF")
for x in search_tfidf(query):
    print(x)
print("\nBM25")
for x in search_bm25(query):
    print(x)

💡 BM25Okapi's defaults are \(k_1 = 1.5\) and \(b = 0.75\). Its IDF is \(\ln\frac{N - df_t + 0.5}{df_t + 0.5}\); for terms in more than half of the documents that would be negative, so it is replaced by 0.25 × the average IDF. With text.lower().split() the tokens keep punctuation, and a word repeated in the query is counted each time. The widgets below reproduce this.

Try it: side by side

Pick a query. Lines connect the same document in the two top-5 lists; documents in only one list have no line. Move \(k_1\) and \(b\) to see BM25 re-rank.

1.5
0.75

See it: the first five queries

Are the rankings identical? Which one is better?

Usually the rankings are not identical. Which one is better cannot be decided from visual inspection alone: different ranking functions → different ranked lists → we need evaluation. Without relevance judgments and metrics we cannot make a rigorous claim that one ranking is superior. That is the bridge to Lab 05.

Summary: key takeaways

MethodMain idea
Boolean retrievalexact match / logical conditions
TF-IDFweight terms by local frequency and global rarity
Cosine similaritycompare query and document vectors
BM25lexical ranking with TF saturation and length normalization
  1. Retrieval is usually a ranking problem, not just a matching problem.
  2. Rare terms are often more discriminative than common terms.
  3. TF-IDF gives a practical weighted vector representation.
  4. Cosine similarity provides a normalized comparison between query and document vectors.
  5. BM25 improves lexical ranking by modelling saturation and document length.
Lab 04: how do we rank documents? → Lab 05: how do we know whether the ranking is good?

Optional exercise

Reproduce the demo and compare TF-IDF and BM25 for five Cranfield queries. For each query: print the top 5 TF-IDF results, print the top 5 BM25 results, and identify whether the rankings differ. Do not yet decide which system is better; that decision needs the material from Lab 05.