Chapter 4Term Weighting and Similarity

Documents as vectors

Chapter 3 showed that word frequencies are wildly uneven. Zipf’s law guarantees a handful of words dominate every corpus, while a long tail barely occurs at all.

This chapter turns that raw material into something a machine can compare. We need a numerical representation of a document, and a way to measure when two documents are alike.

The construction is the foundation of information retrieval. Its two ideas come back in almost every later chapter. Weight the words by how informative they are. Measure similarity as an angle.

Start with the simplest representation there is. Fix the vocabulary $V = \{w_1, \ldots, w_n\}$ of the corpus. Represent a document as a vector with one entry per vocabulary word, recording how often that word appears.

This is the bag of words. It keeps word counts and throws word order away completely, so “dog bites man” and “man bites dog” get the same vector.

That is a real loss. It is also tolerable for many tasks, where topic matters more than syntax. In exchange we get a document as a point in an $n$-dimensional space, which is a form we can do arithmetic on.

Keeping only presence or absence, rather than counts, gives the binary incidence matrix of classical Boolean retrieval . Counts are the richer choice.

Why the matrix is never stored

The matrix has one row per term and one column per document, so it holds $|V| \times N$ cells. That number gets large very fast.

Take a million documents over half a million distinct terms. The matrix has $5 \times 10^{11}$ cells. Even at one bit each, that is $62.5$ gigabytes. An average document contains perhaps a thousand distinct terms, so about $10^{9}$ cells are non-zero. The density is $0.2$ per cent.

The sparsity is not an accident of this example. It is Zipf’s law again. Most types are rare, so most rows are nearly empty.

So nobody stores the matrix. For each term you store the list of documents that contain it, which is the inverted index, and the empty cells cost nothing. The same argument returns for the co-occurrence matrices of Chapter 7.

The bit matrix has a second problem, and it is the one that motivates the rest of this chapter. A document that mentions caesar once and one that mentions it forty times look identical, so every matching document is equally good. Boolean retrieval cannot rank.

Weighting: not all words are equal

Raw counts bring the trouble Chapter 3 predicted. The most frequent word in a document is almost always the or of. Those words occur everywhere and say nothing about what the document is about.

So a representation dominated by its largest counts is dominated by its least informative words. We need to weight each term by how much it discriminates. The classic solution has two parts.

The first part measures how important a term is within a document. That is its term frequency. It can be the raw count $\mathrm{tf}_{t,d}$. It can be the count normalised by document length, $\mathrm{tf}_{t,d}/M_d$, so long documents do not win by sheer size. It can be a dampened log form, $1 + \log \mathrm{tf}_{t,d}$, so the tenth occurrence counts for less than the second.

The damping deserves a sentence of justification, because it looks arbitrary. Relevance does not grow linearly with occurrences. A document that says cricket twenty times is more about cricket than one that says it twice. It is not ten times more about cricket.

A thousandfold spread in raw counts becomes a fourfold spread in weight. The logarithm turns multiplicative differences into additive ones, which is the same trick that made Zipf’s law a straight line in Chapter 3. The $+1$ exists so that a single occurrence scores $1$ rather than $0$.

Length normalisation and log damping fix different problems, and they are often used together.

But term frequency alone still rewards the. So we multiply it by a second factor, measuring how informative the term is across the whole collection. That is the inverse document frequency:

$$\begin{equation} \mathrm{idf}_t \;=\; \log \frac{N}{\mathrm{df}_t}, \label{eq:idf} \quad\text{(4.1)} \end{equation}$$

where $N$ is the number of documents in the collection, and $\mathrm{df}_t$ is how many of them contain term $t$.

Note what $\mathrm{df}_t$ counts. It counts documents, not occurrences. A term used five hundred times in one document still has $\mathrm{df}_t = 1$. Since $\mathrm{df}_t \le N$ always, the ratio is at least $1$ and the idf is never negative.

Equation (4.1) behaves exactly as we want. A term appearing in every document has $\mathrm{df}_t = N$, so $\mathrm{idf}_t = \log 1 = 0$. It is useless for telling documents apart, and its weight is annihilated. A term appearing in few documents has a small $\mathrm{df}_t$ and so a large idf.

Why a logarithm

The logarithm is not a fudge factor. Pick a document from the collection at random. The chance that it contains $t$ is $P(t) = \mathrm{df}_t / N$. So

$$\begin{equation} \mathrm{idf}_t \;=\; \log \frac{N}{\mathrm{df}_t} \;=\; -\log P(t), \label{eq:idf-information} \quad\text{(4.2)} \end{equation}$$

which is the self-information of the event “this document contains $t$” . The weight is a count of bits of surprise, in whatever base the logarithm uses.

That reading explains the behaviour at both ends. A term you fully expected to see carries no information, and scores zero. A term you did not expect carries a lot, and scores high.

The logarithm also tames the scale. Without it, $N/\mathrm{df}_t$ ranges over five orders of magnitude, and one rare word would dominate every score it touched. The base of the logarithm only rescales every weight by a constant, so it never changes a ranking. Use base $10$ by hand and natural logs in code.

Two variants you will meet

Implementations rarely use Equation (4.1) unmodified. Two variants are common:

$$\begin{align} \text{smoothed} &\qquad \mathrm{idf}_t = \log\frac{N}{1 + \mathrm{df}_t} + 1, \label{eq:idf-smooth}\\ \text{probabilistic} &\qquad \mathrm{idf}_t = \log\frac{N - \mathrm{df}_t}{\mathrm{df}_t}. \label{eq:idf-prob} \end{align}$$

The $1 + \mathrm{df}_t$ in Equation (4.7) guards against a query term that appears in no document at all, where the plain formula divides by zero. The trailing $+1$ stops a term present in every document from collapsing the entire vector to zero. This is what scikit-learn computes by default. Its numbers will not match a hand computation unless you ask for the unsmoothed form.

Equation (4.8) goes negative for any term in more than half the collection, which is a stronger punishment of the head. It is the ancestor of BM25, developed in Chapter 20.

All three variants agree on the ordering of terms. They differ only in how hard they push the head down.

The product of the two factors is tf-idf:

$$\begin{equation} \text{tf-idf}_{t,d} \;=\; \mathrm{tf}_{t,d} \times \mathrm{idf}_t. \label{eq:tfidf} \quad\text{(4.3)} \end{equation}$$

It is high only when a term occurs often in this document but rarely across the collection. That is precisely the profile of a word that characterises the document.

This answers a puzzle Chapter 3 left open. At bottom, idf is a machine for undoing Zipf’s law. It discounts the frequent words that the frequency distribution guarantees you will have.

A worked weighting

Numbers make the mechanism concrete. Take a collection of $N = 100{,}000$ documents. The word moon occurs in $\mathrm{df} = 100$ of them, so

$$\mathrm{idf}(\mathit{moon}) = \log_{10}\frac{100{,}000}{100} = \log_{10} 1000 = 3.$$

Take a $427$ token document where moon appears $20$ times. Its length normalised term frequency is $20/427 \approx 0.047$. Its tf-idf is therefore $0.047 \times 3 \approx 0.141$.

Now take the, which appears in all $100{,}000$ documents. Its idf is $\log_{10}(100{,}000/100{,}000) = \log_{10} 1 = 0$. So its tf-idf is $0$ no matter how many times it occurs in the document.

The weighting has silenced the most frequent word in the language and amplified the one that signals the topic. It did so with nothing but a logarithm of a ratio of counts.

Try it yourself. code/worked_examples/weighting.py prints this table and the PMI one from Chapter 7. It adds a word that occurs once and still outscores the.

Run it in ColabNotebookSource

Similarity: measuring the angle

Now that documents and words are weighted vectors, “how similar are these two?” becomes a geometric question.

The natural first guess is the dot product $\vec{u}\cdot\vec{v}$. It has a flaw. It grows with the lengths of the vectors, so a long document scores high similarity with everything, purely by having large entries.

The fix is to divide the magnitudes out. Measure the angle between the vectors instead of their lengths. That is cosine similarity:

$$\begin{equation} \cos(\vec{u}, \vec{v}) \;=\; \frac{\vec{u}\cdot\vec{v}}{\lVert \vec{u}\rVert\,\lVert \vec{v}\rVert} \;\in\; [-1, 1]. \label{eq:cossim} \quad\text{(4.4)} \end{equation}$$

It is $1$ when the vectors point the same way, meaning maximally similar. It is $0$ when they are orthogonal, meaning no shared terms. It is negative only when they point oppositely, which is rare for count vectors, whose entries are never negative.

Cosine is the standard measure of similarity in this book. It compares word vectors in Chapter 6, embeddings in Chapter 9, and retrieved passages in Chapter 20.

The unnormalised dot product is not discarded, though. The attention mechanism at the heart of every transformer is built on exactly that operation. Chapter 16 puts it to a different use.

Euclidean distance is the third obvious choice. It is sensitive to magnitude, so it is rarely used for comparing these vectors directly.

There is one case where all three agree. For unit length vectors,

$$\begin{equation} \lVert \vec{u} - \vec{v} \rVert^{2} = \lVert \vec{u} \rVert^{2} + \lVert \vec{v} \rVert^{2} - 2\,\vec{u}\cdot\vec{v} = 2 - 2\cos(\vec{u}, \vec{v}), \label{eq:cos-euclid} \quad\text{(4.5)} \end{equation}$$

so ranking by cosine and ranking by Euclidean distance give the same order. Vector databases exploit exactly this. Normalise once at indexing time, then use whichever operation the hardware does faster.

A collection worked end to end

The moon example weighted one term. This section takes four documents all the way from raw text to a ranking. Every number is small enough to check by hand.

The collection is $N = 4$ documents:

Stage 1: count

Ten distinct terms, so the matrix is $10 \times 4$. Each cell is $\mathrm{tf}_{t,d}$.

By raw count, the is the most important word in all four documents. That is the problem this chapter exists to solve.

Stage 2: count documents, not occurrences

The is in every document, so $N/\mathrm{df} = 1$ and its weight is exactly zero.

One caveat, and it is an honest one. In this collection a has $\mathrm{df} = 1$, so it scores the highest idf available. idf is a statistic of a collection, not a judgement about language, and with $N = 4$ it is measuring almost nothing. Give it a hundred thousand documents and a falls to zero alongside the.

Stage 3: multiply

The entire first row is zero. Two documents that share only the now share nothing at all.

Stage 4: compare by angle

Take $\vec{d_1}$ and $\vec{d_2}$. Each has three non-zero entries of $0.301$, and they share two of them, orbits and earth:

$$\begin{align*} \vec{d_1}\cdot\vec{d_2} &= (0.301)(0.301) + (0.301)(0.301) = 0.1812, \\ \lVert \vec{d_1} \rVert = \lVert \vec{d_2} \rVert &= \sqrt{3 \times 0.301^{2}} = 0.301\sqrt{3} = 0.5214, \\ \cos(\vec{d_1}, \vec{d_2}) &= \frac{0.1812}{0.5214 \times 0.5214} = \boxed{\mathbf{0.6667}} \end{align*}$$

That is exactly $2/3$, two shared terms out of three equally weighted ones. Doing the same for $\vec{d_1}$ and $\vec{d_3}$, which share only moon, gives $0.0906 / (0.5214 \times 0.9031) = 0.1925$.

Table 1.1 scores all six pairs twice, once on raw counts and once on tf-idf.

Read the row for $d_2, d_3$. Raw counts call them $0.57$ similar. The only word they share is the. Under tf-idf their cosine is exactly zero, which is the right answer.

Now read $d_1, d_2$ against $d_1, d_3$. Raw counts separate them by a factor of $1.2$. tf-idf separates them by a factor of $3.5$. The ranking was already correct. The weighting made it decisive, and a retrieval system needs decisive.

Stage 5: rank for a query

A query is just a short document. Score each document by adding the tf-idf of the query terms it contains:

$$\begin{equation} \operatorname{score}(q, d) \;=\; \sum_{t \in q} \text{tf-idf}_{t,d}. \label{eq:query-score} \quad\text{(4.6)} \end{equation}$$

For the query “the moon”:

Raw counts rank $d_2$ third with a score of $2$, ahead of $d_4$. Neither document mentions the moon. tf-idf sends both to exactly zero, and keeps the correct tie between $d_1$ and $d_3$.

Notice what that means for the user. The word the contributed nothing to the score, so typing it cost nothing. Weighting is what lets people write queries in ordinary English.

Try it yourself. python3 weighting.py corpus prints every table in this section. Add a fifth document mentioning the moon and watch $\mathrm{idf}(\mathit{moon})$ move, taking every weight in the matrix with it.

A toolkit that keeps returning

Two ideas leave this chapter and never depart.

Weight terms by informativeness, so the frequent words Zipf’s law forces on us do not drown the signal. Measure similarity by angle, so comparison is about direction, not magnitude.

Together, tf-idf and cosine turn a corpus into a searchable, comparable space. They were the engine of information retrieval for decades.

But notice what they assume. Every word is still an independent dimension, orthogonal to every other. So cat and dog stay exactly as unrelated as cat and the. tf-idf weights the axes. It does not make similar words share them.

Repairing that is the next leap. We want cat and dog to have nearby directions, not perpendicular ones. That takes us to the distributional vectors of Chapter 6, and then to the learned embeddings of Chapter 9. The measuring stick, cosine, comes along unchanged. What improves is the space it measures.

Further reading.

Manning, Raghavan and Schütze’s Introduction to Information Retrieval is the definitive modern treatment of tf-idf weighting, the vector space model and cosine similarity. Manning and Schütze cover the incidence matrix and the statistical foundations. BM25, the probabilistic descendant of tf-idf, is developed in Chapter 20.