Chapter 4Term Weighting and Similarity

Documents as vectors

Chapter 3 showed that word frequencies are wildly uneven, because 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, which means 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, and its two ideas come back in almost every later chapter: weight the words by how informative they are, and measure similarity as an angle.

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

This is the bag of words, and it keeps word counts while throwing word order away completely, so “dog bites man” and “man bites dog” get the same vector. That is a real loss, and 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 (Manning and Schütze 1999), and 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, and that number gets large very fast. Take a million documents over half a million distinct terms and the matrix has $5 \times 10^{11}$ cells, which even at one bit each is $62.5$ gigabytes. An average document contains perhaps a thousand distinct terms, so only about $10^{9}$ cells are non-zero and the density is $0.2$ per cent.

The sparsity is Zipf’s law again, because most types are rare and so most rows are nearly empty.

Nobody therefore 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 and Boolean retrieval cannot rank.

Weighting: not all words are equal

Raw counts bring the trouble Chapter 3 predicted, because the most frequent word in a document is almost always the or of, and those words occur everywhere while saying nothing about what the document is about.

A representation dominated by its largest counts is therefore dominated by its least informative words, so 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, which is its term frequency. It can be the raw count $\mathrm{tf}_{t,d}$, or the count normalised by document length, $\mathrm{tf}_{t,d}/M_d$, so that long documents do not win by sheer size, or a dampened log form, $1 + \log \mathrm{tf}_{t,d}$, so that 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, so while 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, because 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.

Term frequency alone still rewards the, though, 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, which is documents and not occurrences, so 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$, which annihilates the weight of a term that is useless for telling documents apart, while 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, and 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$” (Manning et al. 2009). The weight is a count of bits of surprise, in whatever base the logarithm uses.

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

The logarithm also tames the scale, because 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, which is why you can 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{1 + 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, and the matching $1 + N$ above it keeps the ratio at exactly $1$ for a term that appears everywhere, so the trailing $+1$ leaves such a term with a weight of exactly $1$ rather than $0$. Smoothing both counts is the part that is easy to get wrong: drop the $1$ from the numerator and a term present in every document scores $\log\frac{N}{N+1} + 1$, which is slightly under $1$ and drifts with $N$. Equation (4.7) as written, with natural logarithms, is what scikit-learn computes by default, so its numbers will not match a hand computation in base $10$ 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, and it is the ancestor of BM25 as developed in Chapter 21.

All three variants are monotonically decreasing in $\mathrm{df}_t$, so all three agree on the ordering of terms and 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, which 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, because it discounts exactly 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, so that its length normalised term frequency is $20/427 \approx 0.047$ and its tf-idf is therefore $0.047 \times 3 \approx 0.141$.

Now take the, which appears in all $100{,}000$ documents, so its idf is $\log_{10}(100{,}000/100{,}000) = \log_{10} 1 = 0$ and 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, and 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, the question “how similar are these two?” becomes a geometric one.

The natural first guess is the dot product $\vec{u}\cdot\vec{v}$, and 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 and measure the angle between the vectors instead of their lengths, which gives 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 and so are maximally similar, $0$ when they are orthogonal and share no terms, and negative only when they point oppositely, which cannot happen 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 21.

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

Euclidean distance is the third obvious choice, and being sensitive to magnitude it is rarely used for comparing these vectors directly. There is one case where all three agree, because 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, normalising once at indexing time and then using whichever operation the hardware does faster.

A collection worked end to end

The moon example weighted a single term, whereas this section takes four documents all the way from raw text to a ranking, with every number small enough to check by hand.

The collection is $N = 4$ documents:

Stage 1: count

There are ten distinct terms, so the matrix is $10 \times 4$, and each cell holds $\mathrm{tf}_{t,d}$.

By raw count, the is the most important word in all four documents, and 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 is worth making, and it is an honest one. In this collection a has $\mathrm{df} = 1$ and so scores the highest idf available, which is a reminder that idf is a statistic of a collection rather than 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, so 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$, being two shared terms out of three equally weighted ones, and 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$, where raw counts call the pair $0.57$ similar even though 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$ while tf-idf separates them by a factor of $3.5$, so the ranking was already correct and the weighting made it decisive. A retrieval system needs decisive.

Stage 5: rank for a query

A query is just a short document, so score each document by adding the tf-idf of whichever 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$, even though neither document mentions the moon at all. Weighting 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, and 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 that the frequent words Zipf’s law forces on us do not drown the signal, and measure similarity by angle, so that comparison is about direction rather than magnitude.

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

Notice what they assume, though. Every word is still an independent dimension orthogonal to every other, so cat and dog stay exactly as unrelated as cat and the. Weighting scales the axes without making similar words share them.

Repairing that is the next leap, because we want cat and dog to have nearby directions rather than 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, and what improves is the space it measures.

Further reading.

Manning, Raghavan and Schütze’s Introduction to Information Retrieval (Manning et al. 2009) is the definitive modern treatment of tf-idf weighting, the vector space model and cosine similarity. Manning and Schütze (Manning and Schütze 1999) cover the incidence matrix and the statistical foundations. BM25, the probabilistic descendant of tf-idf, is developed in Chapter 21. The implementation nearly everyone uses is sklearn.feature_extraction.text.TfidfVectorizer, and the last exercise below asks what it does to the four documents worked through above.

Code for this chapter

Each one reproduces the tables above. Open it in Colab, change an input and watch which numbers move.

• weighting.pytf-idf and PMI, by hand

  The weighting arithmetic the chapters print, on the four document matrix.

  standard library only Run it in Colab Notebook Source

From Natural Language Processing: From Corpus Statistics to Grounded LLMs, by Ramaseshan Ramachandran.