Searching & Clustering · Natural Language Processing

01 · Motivation

What is information retrieval?

Information retrieval (IR) is the task of returning, from a large collection, the documents most relevant to a query — ranked, best first. Search engines, e-commerce, code search, and the retrieval step of a RAG pipeline (Ch. 10) all sit on the same vector-space foundations.

The same six-sentence toy corpus from Chapter 2 threads through here — TF-IDF, cosine, and the inverted index all operate on it:

👍 the film was brilliant and moving · a brilliant and clever film · the acting was great and moving
👎 the film was boring and dull · a dull and predictable film · the acting was boring and weak

Classic IR has two ingredients: a way to score a document against a query, and a data structure that finds high-scoring documents without touching the rest.

02 · Weighting

TF-IDF — counts that pay attention to the corpus

Raw counts treat the and parliament as interchangeable. TF-IDF asks: how surprising is it that this word appears at all? Term importance is inversely related to how many documents a term appears in — the rarer the term, the more it restricts the result set. Let $N$ be the corpus size and $\operatorname{df}(w)$ the document frequency (how many documents contain $w$ ). The inverse document frequency:

IDF

\operatorname{idf}(w) = \log\!\left(\frac{N}{\operatorname{df}(w)}\right)

A word in every document (like “the”) gets idf = 0 — pure noise. A word in one document gets idf = log N — maximally discriminative. This is exactly Shannon’s surprise $-\log p$ .

Multiply by term frequency $\operatorname{tf}(w, d)$ — a document mentioning climate twenty times is more about climate than one mentioning it once:

TF-IDF

\operatorname{tfidf}(w, d) = \operatorname{tf}(w, d) \cdot \log\!\left(\frac{N}{\operatorname{df}(w)}\right)

Counts saturate, so most systems use log-TF, $1 + \log\operatorname{tf}$ — going from 1→2 matters a lot, 50→100 barely moves. That saturating curve is where BM25 comes from.

Hands-on

TF-IDF — counts that pay attention to the corpus

Pick a document; its terms are ranked by tf·idf. Words common across the corpus (idf ≈ 0) sink; words distinctive to this document rise to the top.

Documents (one per line)

Document6 docs · |V| = 14

term	tf	df/N	idf	tf·idf
brilliant	1	2/6	1.099	1.099
moving	1	2/6	1.099	1.099
the	1	4/6	0.405	0.405
film	1	4/6	0.405	0.405
was	1	4/6	0.405	0.405
and	1	6/6	0.000	0.000

Takeawaytf·idf = (how often here) × log(how rare across the corpus). It is the default weighting for search and for the BoW vectors a classifier sees — distinctive words get the weight.

Q

Worked example — compute TF-IDF

$N = 100$ ; climate appears in 25 documents and 3 times in document $d$ . idf $= \log(100/25) = \log 4 \approx 1.386$ ; tf·idf $= 3 \cdot \log 4 \approx$ 4.16 (natural log). The log base only rescales the column. Trap: df counts documents, not occurrences — 50 hits in one document still means df = 1.

03 · Similarity

Cosine similarity — angle, not magnitude

A document’s TF-IDF vector lives in $\mathbb{R}^{|V|}$ ; so does a query’s. A 50-word tweet and a 5000-word essay on the same topic should rank as similar, but their vectors differ hugely in magnitude. Euclidean distance would call them far apart. What’s the same is the direction — the word proportions. So measure the angle:

Cosine

\cos(\mathbf{u}, \mathbf{v}) = \frac{\mathbf{u} \cdot \mathbf{v}}{\lVert\mathbf{u}\rVert\,\lVert\mathbf{v}\rVert} = \frac{\sum_i u_i v_i}{\sqrt{\sum_i u_i^2}\,\sqrt{\sum_i v_i^2}}

For non-negative vectors (TF-IDF is ≥ 0), cosine ∈ [0, 1]: 1 = same direction, 0 = orthogonal (no shared vocabulary). Equivalent to L2-normalising both vectors onto the unit sphere, then taking the dot product.

Hands-on

Cosine similarity — angle, not magnitude

Type a query; documents are ranked by cos(query, doc). Cosine ignores length and measures direction. Switch between TF-IDF and raw counts and watch the ranking shift.

Documents (one per line)

Query

D10.684

the film was brilliant and moving

D20.648

a brilliant and clever film

D50.391

a dull and predictable film

D30.242

the acting was great and moving

D40.142

the film was boring and dull

D60.000

the acting was boring and weak

TakeawayCosine = dot product of unit-normalised vectors. It is length-invariant, which is exactly what you want when ranking documents of wildly different sizes against a short query.

Q

Why cosine, not Euclidean distance

Euclidean distance grows with document length (magnitude); cosine strips magnitude and keeps direction, so it ranks a short query against documents of any length fairly. For unit-normalised vectors, cosine similarity and Euclidean distance give the same ranking — but TF-IDF vectors aren’t unit-norm until you divide by $\lVert\cdot\rVert$ , which is exactly what cosine does.

04 · Data structure

Inverted index — what makes search fast

Scoring every document against every query would be hopeless at web scale. The inverted index maps each term to its posting list — the documents that contain it. A boolean query (AND / OR / NOT) is answered by intersecting, unioning, and complementing posting lists, never by scanning documents.

Hands-on

Inverted index — what makes search fast

Each term maps to its posting list (the docs that contain it). Boolean queries combine those lists with AND / OR / NOT — try film AND NOT dull or brilliant OR great.

Documents (one per line)

Query

Inverted index (top 8 terms by df)

and

→ D1, D2, D3, D4, D5, D6

the

→ D1, D3, D4, D6

film

→ D1, D2, D4, D5

was

→ D1, D3, D4, D6

brilliant

→ D1, D2

moving

→ D1, D3

a

→ D2, D5

acting

→ D3, D6

Query result · 2 documents

D1 the film was brilliant and moving

D2 a brilliant and clever film

TakeawaySearch never scans documents at query time — it intersects pre-built posting lists. That is why web-scale boolean and ranked retrieval is fast.

key

From boolean to ranked — BM25

Real search ranks, not just filters. BM25 is the standard ranking function: a saturating TF term (the 10th occurrence adds little), multiplied by IDF, with a document-length normalisation so long documents don’t win automatically. It is TF-IDF’s battle-tested cousin and still a strong baseline against neural rerankers.

05 · Ranking

Learning to rerank — combining many signals

A production search stack rarely relies on one score. A fast first stage (BM25 over the inverted index) retrieves a few hundred candidates; a learned reranker then orders them using many features — lexical overlap (BM25), semantic similarity (dense embeddings, Ch. 4), freshness, popularity, click signals. Learning-to-rank trains a model on relevance-labelled query–document pairs with a ranking loss (pairwise or listwise), so the final order reflects learned relevance rather than any single hand-tuned formula.

Q

Two-stage retrieval, why

A cheap recall-oriented stage (BM25) narrows millions of documents to hundreds; an expensive precision-oriented reranker (cross-encoder / learned model) orders those few. You get the recall of lexical search and the precision of a heavy model without running the heavy model over the whole corpus.

06 · Clustering

k-means — the textbook clustering algorithm

So far everything was supervised or query-driven. Clustering is unsupervised: group documents (or their vectors) by similarity with no labels. k-means minimises within-cluster squared distance by alternating two moves (Lloyd’s algorithm):

Assign each point to its nearest centroid.
Update each centroid to the mean of its assigned points.

Repeat until assignments stop changing.

Hands-on

k-means — the textbook clustering algorithm

Pick k, then alternate Step (assign points to nearest centroid → move centroids to cluster means) until it converges. Set k ≠ 3 and watch it split or merge the three natural blobs.

k3iter 0

Takeawayk-means minimises within-cluster squared distance by alternating assignment and update. It is fast and unsupervised, but you must choose k, and the result depends on the (here, seeded) initialisation.

!

k-means caveats

You must choose $k$ up front (use the elbow method or silhouette score). The result depends on initialisation (k-means++ seeds it better). And it assumes roughly spherical, equally-sized clusters — on text it is usually run over reduced or normalised vectors, not raw sparse BoW.

07 · Topic models

Latent Dirichlet Allocation — documents as mixtures of topics

k-means assigns each document to exactly one cluster. LDA is softer and generative: each document is a mixture of latent topics, and each topic is a distribution over words. “Animals” might put mass on cat, dog, mouse; “Finance” on bank, market, stock. A document about a pet insurance startup is then, say, 60% Animals + 40% Finance.

LDA’s generative story: to write a document, draw a topic mixture $\theta_d \sim \text{Dir}(\alpha)$ , then for each word draw a topic $z \sim \theta_d$ and a word from that topic’s distribution $\beta_z$ . Inference (collapsed Gibbs sampling or variational methods) runs this backwards: given the documents, recover the topics and per-document mixtures.

Q

LDA vs k-means

k-means is hard clustering (one cluster per document) over a chosen distance; LDA is soft, probabilistic clustering — a document is a distribution over topics, and a topic is a distribution over words. LDA also gives interpretable topics (their top words), which k-means centroids do not directly.

why

On the topic-mixer widget

The legacy interactive topic-mixer is intentionally omitted here — its hard-coded colour palette and animated Gibbs sampler don’t map cleanly onto the design tokens, and the generative story above conveys the idea without it. The k-means lab covers the hands-on clustering intuition.

08 · Self-check

Questions before you move on

A word appears in every document of a corpus. What is its IDF?

Why is cosine similarity preferred over Euclidean distance for ranking documents?

What does an inverted index map?

Which best distinguishes LDA from k-means?

09 · Recap

One-screen summary

Chapter 03 — load-bearing ideas

TF-IDF = term frequency × inverse document frequency. idf = log(N/df) downweights common words (the → 0) and rewards rare, discriminative ones.
Cosine similarity ranks by the angle between vectors — length-invariant, so short queries rank fairly against long documents. cos ∈ [0, 1] for non-negative vectors.
The inverted index (term → posting list) makes search fast: boolean queries combine posting lists; BM25 is the standard ranked scorer with saturating TF and length normalisation.
Two-stage retrieval — cheap recall (BM25) then expensive precision (learned reranker).
k-means — hard, unsupervised clustering by alternating assign/update; you choose k, and init matters.
LDA — soft, generative topic model: documents are mixtures of topics, topics are distributions over words.

10 · Exam · past papers

Past-paper questions

Answered 0 / 8 · 0 correct

Q14What does the IDF (inverse document frequency) of a term measure?
Q15A corpus has N = 1000 documents; the term "neural" appears in 10 of them. What is idf("neural") using log base 10?
Q16Why is cosine similarity, rather than Euclidean distance, the standard for comparing document vectors?
Q17What is the primary purpose of an inverted index in information retrieval?
Q18Two documents share no words at all. Their TF-IDF cosine similarity is:
Q19In k-means, the two alternating steps of each iteration are:
Q20Which statement about Latent Dirichlet Allocation (LDA) is TRUE?
Q130Replacing raw term frequency with 1 + log(tf) is motivated by: