2  Text as Data: Tokens, Normalization, Zipf

Chapter status: drafted. Every number and every code output on this page was produced by running the code shown, with scikit-learn 1.9; the full environment is in Appendix A. The LogisticRegression experiments here use the default lbfgs solver. It draws no random numbers, so the random_state=0 in the code does not affect the result. Different library versions or computing environments can still produce small numerical differences. The chapter’s interactive tools let you explore the Zipf distribution and relations in the vector space.

Learning objectives. After this chapter you can:

2.1 The problem, in one sentence

The models we use in this chapter work on numerical inputs. To give them text, we have to turn strings of characters into a numerical representation. We will build count-based representations out of two basic decisions: deciding which units to cut the text into (tokenization), and computing the value of each unit in the document vector (weighting).

We will study this approach through bag-of-words and TF-IDF. These methods are also a useful starting point for evaluating more complex text models.

This chapter builds sparse text representations. Only a small part of a vocabulary built from a large corpus usually occurs in any one document, so most components of a document vector are zero. Chapter 3 moves to dense vectors, which describe each word with far fewer coordinates, most of them non-zero. Simple models that use sparse representations can be a strong baseline where labelled examples are few, where long documents are classified by topic, or where literal word matching matters. Such a model helps us weigh what a more complex method gains against what it costs.

In building these representations we decide which units to cut the text into, which differences to keep and which units to count. Large language models involve similar design decisions; but when you use a pretrained model you inherit a large part of them from the tokenizer that ships with it. This chapter examines the options and the libraries’ assumptions, to show how each decision affects the representation.

What we will look at. First how text is cut into tokens, and what normalization decisions merge and what they delete. Then the distribution of word frequencies, with Zipf’s law, and the growth of the number of distinct words as a corpus grows, with Heaps’ law. Then we turn four short sentences into document vectors in six steps and compute the similarity between them, showing the intermediate results. Finally we discuss what information this representation loses and why the next chapter moves to other representations. On a first reading you can skip the collapsible “Deep dive” boxes and come back to them later.

Preprocessing decides what information reaches the model, so it is part of the modelling process. Treat the choices in this chapter as modelling decisions and record your reasons for them. If you present your work in a paper, name the preprocessing steps that affect the results in the methods section.

2.2 From characters to tokens

tokenization — cutting text into the tokens a model will process as separate units. The tool that does it is a tokenizer. Where the units begin and end is set by the method and the rules used. The structure of the language affects how well suited and how efficient those choices are. ↩︎

token — an item the model processes as a separate unit. Depending on the tokenizer it can stand for a word, part of a word, a punctuation mark, a space or a sequence of bytes; it is not always a piece of text that can be read on its own. There are also special tokens, used for functions such as marking the start or the end of a sequence. In a service billed per token, the units counted are set by the tokenizer of the model in use. ↩︎

Before we can represent text we have to decide which units to use; this step is called tokenization. The choice affects the size of the vocabulary, how new words are represented, and how many tokens a text is cut into. In services billed per token, the number of tokens also affects the cost. When you build your own pipeline, the sequence of steps that turns raw text into a model’s input, these choices are yours to make. When you use a pretrained model you usually inherit the model’s tokenizer. Either way you need to know what the library does.

A simple place to start is to split the text at whitespace characters such as spaces, tabs and line ends. In Python, str.split() with no arguments does this. But it does nothing separate about punctuation, upper and lower case, or suffixes. The example below shows which further decisions a task may call for.

text = "The pump P-101 didn't fail; it's the seal (again!)."
print(text.split())
['The', 'pump', 'P-101', "didn't", 'fail;', "it's", 'the', 'seal', '(again!).']

The output keeps fail;, The and it's as units of their own. The and the both occur in it, and count as two different tokens. If another text processed the same way contained fail or it is, those would be counted as different tokens from fail; and it's. Whether such forms are counted separately or mapped to a common form depends on the task. In deciding, weigh which distinctions carry meaning and which only create an unnecessary number of different entries for the same information.

This example shows the limits of splitting on whitespace alone. A tokenizer that works at the word level can use separate rules for punctuation, apostrophes, URLs, numbers and abbreviations. Normalization decisions, though, such as mapping The and the to the same form, are separate operations from deciding where tokens begin and end.

Even with a fixed word-level vocabulary, new text can contain words that are not in it. We first look at how normalization brings different forms of a word together, and then briefly at the limit of the word level and how today’s models get past it (Section 2.2.2).

The normalization ladder

normalization — in this chapter, the general term for operations that reduce orthographic or morphological differences judged not to matter for the task. Erasing case (Pump → pump) and mapping inflected forms onto a shared stem or dictionary form (pumps → pump) are examples. The output of a stemmer need not be the linguistic root. Unicode normalization is a separate operation: it brings character sequences that look the same into one standard form. ↩︎

The example above calls for three different decisions. Should The and the be mapped to the same form? Should the semicolon in fail; be kept as a token of its own, or removed? Should it's be kept whole, or mapped to it is? These decisions affect case, punctuation and grammatical information, respectively. Normalization can shrink the vocabulary by merging the counts of some forms. Whether it erases a useful distinction has to be judged for the task.

These operations can delete useful information too. Which distinction an operation removes can be read from its definition; what that does to the task has to be evaluated. The table below compares common normalization and preprocessing options, with what each may gain and what it may lose. The table is not a required order of application; stemming and lemmatization are in most cases alternatives to each other.

This table is for a pipeline you build yourself. If the text is going into a pre-trained model, stay with the tokenizer and the preprocessing assumptions that model was trained under; adding the operations below on your own moves your input away from the form the model expects.

The normalization ladder
Operation Possible benefit Possible loss or cost Recommendation
Lowercasing Pump = pump: two columns merge into one and their counts add up. US and us become the same form; the capitalisation that helps tell proper nouns and acronyms apart is lost. Python’s str.lower() does not apply the Turkish mappings I–ı and İ–i. Decide by language and task. Where a conversion faithful to Turkish spelling is needed, use a method that supports the Turkish letter mappings; with a pretrained model, follow the model’s own preprocessing rules.
Removing punctuation By removing selected marks, can match forms such as fail; with fail. Deleting marks indiscriminately can change identifiers such as P-101, decimals, URLs and chemical notation that contains punctuation. Instead of deleting in bulk, decide by task which marks to keep, split off or remove.
Stop word removal Leaves the listed words out of the count. The English list used in this chapter removes 43.9% of all tokens, on the corpus and tokenization rule given below. If not is on the list, negation can be lost; the content of phrases like to be or not to be changes too. Measure its effect, especially with sparse count-based methods. Check that the list does not delete words that matter for the task.
Stemming Can merge different word forms into one shared output. The Porter stemmer, for example, turns replaced into replac, and the Snowball Turkish stemmer turns kitaplarımızdan (“from our books”) into kitap. Can wrongly merge different words, or leave forms of the same word apart. In Porter, both university and universe become univers. Try it in lexical search and sparse models; decide by looking at the outputs and at task performance.
Lemmatization Aims to map a word to the appropriate dictionary form: replace for replaced used as a verb. Depending on the method it can need a dictionary, rules, part-of-speech or context information. It can err on ambiguous forms; its cost depends on the tool. Before adding it as an extra step for a pretrained transformer, check what input the model expects. Evaluate its benefit in sparse models and linguistic tasks.

What is Unicode? Computers store text by encoding it as numbers. Unicode is the standard that gives the characters of many writing systems shared numbers, called code points: A is 65, ç is 231, İ is 304, 😀 is 128512. A sign that looks like one letter on screen is sometimes made of more than one code point. How code points relate to bytes is covered together with subword tokenization (Section 8.3.2).

Start with the first row of the table, lowercasing: it needs care with the letter mappings of the language. Python’s str.lower() applies Unicode’s default lowercase mapping; it takes no locale parameter for Turkish. Turkish has two separate mappings: I → ı and İ → i. The examples below show how the default conversion departs from them:

"İSTANBUL".lower()              # 'i̇stanbul': starts with U+0069 + U+0307; 9 code points in all
"İSTANBUL".lower() == "istanbul"  # False
"IĞDIR".lower()                 # 'iğdir' — should be 'ığdır'

These conversions raise no error, but they can produce unexpected results downstream. Different spellings of the same word may fail to match, or the tokenizer may split the word in an unexpected way. The default CountVectorizer, for example, produces the token stanbul from the input İSTANBUL. Chapter 4 shows the problem on a corpus, and Chapter 16 covers a conversion that suits Turkish. Once the preprocessing is fixed, the vocabulary and the models that depend on it may have to be rebuilt.

The table’s Recommendation column is a starting point. Each operation rests on the assumption that the distinction it removes is not needed for the task. Lowercasing, for example, can help in some topic classification tasks, and removes a cue that comes from capital letters in named entity recognition (NER). Take the model’s requirements and the properties of the data into account; compare the suitable options on validation data, and keep the test set apart for the final evaluation.

Stemming and lemmatization are both used to gather different forms of a word under one form, but they do not do the same thing. Stemmers such as Porter’s (Porter 1980) apply rules aimed at inflectional or derivational suffixes, and do not guarantee that the result is a word found in a dictionary. Lemmatization aims to map a word to its base form in a dictionary, the form you would look it up under: the infinitive of a verb, the uninflected form of a noun. Some methods use tables and rules alone; choosing the right result for an ambiguous form can need context. In English, for example, left can be the past tense of leave in one sentence and the word for a direction in another.

The choice between stemming and lemmatization depends on your pipeline. With a pretrained transformer, use the model’s tokenizer and the preprocessing it expects; do not add stemming or lemmatization on your own. Subword tokenization (Section 8.3.1) helps to represent rare or new words with smaller units. It does not map inflected forms to the same dictionary form, though: for the Turkish kullanıyorum (“I am using”) and kullandık (“we used”), for instance, it does not by itself create one shared column in a count representation.

Stemming can help in lexical search or sparse classification, where you want inflected forms gathered into one matching unit. But check which forms your tool actually merges: the Snowball Turkish stemmer used in this book (snowballstemmer 3.1.1) produces kullanıyor for kullanıyorum and kulla for kullandık, and does not merge the two.

Chapter 16 runs a BM25 experiment with queries built from the target documents, most of whose terms are in a different inflected form from the one the document uses. In that experiment Snowball stemming raises the share of queries whose target document comes first (recall@1) from 28.0% to 95.3%. The result shows what stemming can gain in that experimental design; the same gain should not be expected on real user queries.

stop word — a word so common that some pipelines throw it away before counting anything. The, of, is. Whether that is a saving or a mistake depends entirely on the task. ↩︎

vocabulary — the finite set of token ids a tokenizer can emit. A word does not have to be in it whole: the tokenizer can split it into smaller pieces that are. ↩︎

Weigh the information lost when you remove stop words. scikit-learn’s English stop word list has 318 entries. In this chapter’s 20 Newsgroups measurement, 311 of them occur in the corpus under the tokenization rule used. They are about 0.4% of the vocabulary (78,649 distinct token types) but 43.9% of all tokens in the corpus. So nearly half of the tokens are left out of the count. That share does not mean the text shrinks by the same share in bytes, or the sparse matrix in memory; the memory saved also depends on how many documents the removed words occur in. And if a word that matters for the task, such as not, is removed, the information needed to tell meanings apart can be lost.

The limit of the word level

For the rest of this chapter a token is a normalized word form, obtained with the rules above. That unit is enough for bag-of-words and TF-IDF: we build the vocabulary from the training text and count how often each word occurs in each document.

The choice has a limit, and it is worth knowing from the start. Once the vocabulary is fixed, new text can contain word forms that are not in it; a word-level representation has no column for those forms and leaves them out of the counts. In an agglutinative language such as Turkish, where one stem has many inflected forms, that happens more often. The next section measures how the vocabulary keeps growing as the data grows, with Heaps’ law (Section 2.3.2).

Today’s language models get past this limit with units smaller than a word: the vocabulary holds pieces of words learned from data (subwords), not whole words, and a new word is written with those pieces. Byte-pair encoding (BPE), WordPiece and their relatives are covered together with the pretrained models that use them (Section 8.3). That is also where we measure why the same text is cut into more tokens in Turkish. For now we continue with words.

2.3 Zipf and Heaps: the long tail of words

So far we have seen how to cut text and what each choice costs. This section looks at two empirical relationships used to describe how word frequencies are distributed and how the number of distinct word forms grows as data is added. They are easy to conflate, so here they are as two separate questions:

Question 1. How are frequencies distributed between the commonest and the rarest words in a corpus? Answer: Zipf’s law.

Question 2. As you add more text, how does the number of distinct words grow? Answer: Heaps’ law.

Zipf’s law describes how frequencies are distributed within a given corpus; Heaps’ law describes how the number of distinct word forms changes as the corpus grows. Both are approximate, observed regularities; neither dictates how tokenization has to be done. The two can be connected under specific assumptions (Lü et al. 2010). We look at the frequency distribution first and vocabulary growth second.

Zipf: how frequencies are distributed

We use the 11,314-document training split of the 20 Newsgroups collection (Lang 1995). After applying the options that strip headers, signatures and quoted text, we lowercase the text and count every string matched by the regular expression [a-z']+ as a token. That yields 2,288,401 tokens, about 2.29 million. These units do not always coincide with linguistic words:

from collections import Counter
import re
from sklearn.datasets import fetch_20newsgroups

docs = fetch_20newsgroups(subset="train",
                          remove=("headers", "footers", "quotes")).data
tokens = re.findall(r"[a-z']+", "\n".join(docs).lower())
counts = Counter(tokens)
print("tokens:", len(tokens), " distinct types:", len(counts))
tokens: 2288401  distinct types: 78649

Two numbers come out, and they need to be kept apart. In this count a type is each distinct string our splitting produces, and a token is each occurrence of such a string in the text: if pump occurs a hundred times, that is one type and a hundred tokens. Both counts depend on the normalization and splitting rules. Now the shape of the distribution:

top     10 types -> 20.99% of all tokens
top    100 types -> 46.99% of all tokens
top   1000 types -> 71.04% of all tokens
top  10000 types -> 92.50% of all tokens

types appearing exactly once: 38571  (49.0% of the vocabulary,
                                      1.69% of all tokens)

The ten most frequent types make up about a fifth of the tokens in this corpus. Meanwhile about 49% of the types are seen exactly once. Those single-occurrence types (hapax legomena) are nearly half of the observed types and only 1.7% of the tokens in this corpus. Whether all of them belong in a model’s vocabulary depends on the task and on how the vocabulary is built.

This result shows that most observed types are rare. How many new types more data would bring is a separate question, taken up below with Heaps’ law (Section 2.3.2).

Zipf’s law (Zipf 1949) is the observation that, when types are ranked by frequency, frequency follows an approximate power relationship with rank:

\[ f(r) \propto r^{-\alpha}. \]

Here \(r\) is the type’s position in the ranking and \(f(r)\) the number of times the type at that position occurs. On a plot with both axes logarithmic the relationship looks approximately like a straight line.

“Approximately” matters here. If we take the 106,425 occurrences of the top-ranked the as the scale and choose \(\alpha = 1\), we expect about 10,600 occurrences at rank ten. The observed value is 26,985, roughly two and a half times that simple reference. The comparison shows that the first ranks do not follow the \(1/r\) curve we chose.

The Zipf–Mandelbrot form,

\[ f(r) \propto (r + b)^{-\alpha}, \]

adds a parameter \(b\) to the rank, which gives the head of the distribution more flexibility. We do not estimate these parameters here or compare how well the two forms fit. Take the straight line as a reference that summarizes the shape of the distribution, not as a model estimated from the data.

Fitting a straight line by least squares (OLS) to a log-log rank–frequency plot can be used to describe the shape of a distribution. The slope alone, however, is neither a reliable estimate of a power-law exponent nor evidence that a power law fits. The sampling structure of ranked frequencies, the dependence between observations and the large number of rare types can mislead the uncertainty calculations of a simple regression. The range chosen for the fit and the weighting of the points also affect the slope. Heteroscedasticity by itself does not make OLS coefficients biased. There are three separate questions here: estimating the coefficient, computing its standard error, and whether a power law is an appropriate model at all.

A stronger analysis starts by defining which quantity is being modelled and over what range. The approach of Clauset and colleagues (Clauset et al. 2009) estimates a discrete or continuous power-law model by maximum likelihood, together with a lower cutoff \(x_{\min}\) estimated from the data. It assesses the fit with the Kolmogorov–Smirnov (KS) distance rather than \(R^2\): the distance in the data is compared with the distances in synthetic samples drawn from the model, and the parameters are re-estimated on every synthetic sample. The power law is also compared with alternative distributions. The exponent this method estimates belongs to the distribution of occurrence counts; it is not the same parameter as the rank–frequency exponent \(\alpha\) above. We do no such estimation in this chapter, and no result here depends on the exact value of the exponent.

Rank and frequency in 20 Newsgroups — 50 ranks chosen at logarithmic intervals from 78,649 types

These observations bring out three practical points for vocabulary design and feature selection:

  1. A fixed word vocabulary may not cover new input completely. Text whose topic and source are not restricted keeps bringing new names, part numbers, spellings and compounds. Subwords help represent those new forms with existing pieces.
  2. Reliable statistics are hard to learn for rare types, yet a rare term can still matter. A single observation is weak ground for generalizing, but a rare product code or proper name can be decisive for a task. scikit-learn’s min_df parameter drops terms that occur in few documents: an integer is a number of documents, a float a proportion of documents. On this corpus, with CountVectorizer’s defaults, min_df=2 removes 62,208 of 101,631 columns (61%); the removed columns carry only 3.4% of token occurrences. The English stop word list removes 309 columns, but those carry 43% of the occurrences (the default setting does not produce the one-letter tokens a and i, so the count is two short of the 311 in the normalization section). The numbers belong to this corpus and this threshold; how the filter affects accuracy has to be measured separately.
  3. How frequent a term is does not by itself determine how useful it is for a task. Terms found in many documents may do less to tell documents apart. IDF, in the next section, takes that spread into account. But occurring in few documents is no guarantee of meaning or usefulness either, as the 'ax example below shows.

Heaps: why the vocabulary keeps growing

Now the second question: as the number of tokens processed grows, how many distinct types do we meet? We first measure the cumulative number of types along the corpus we have, then fit a straight line to that curve in log-log space. The line is a descriptive summary of cumulative growth in the present document order. Because we measure ever-longer prefixes of the same token sequence, the points are not independent samples. The coefficients belong to this order and this range; they should not be read as a confidence interval or as a prediction validated on new data.

import numpy as np

seen, curve = set(), []
for i, tok in enumerate(tokens, 1):
    seen.add(tok)
    if i % 10_000 == 0:
        curve.append((i, len(seen)))

N, V = np.array(curve).T
# Descriptive straight-line fit in log-log space to the cumulative curve.
beta, logK = np.polyfit(np.log(N), np.log(V), 1)
print(f"|V| ~ {np.exp(logK):.1f} * N^{beta:.3f}")
print("new types in the first 100,000 tokens:", V[9])
print(f"new types in tokens {N[-11] + 1:,}-{N[-1]:,}:", V[-1] - V[-11])
|V| ~ 16.5 * N^0.580
new types in the first 100,000 tokens: 13497
new types in tokens 2,180,001-2,280,000: 1814

Heaps’ law (Heaps 1978) relates the number of tokens processed, \(N\), to the number of distinct types observed, approximately as

\[ |V(N)| \approx K N^{\beta}. \]

\(K\) and \(\beta\) depend on the corpus and on the preprocessing. On this corpus, in this document order, we found \(K \approx 16.5\) and \(\beta \approx 0.58\); the values reported for the Reuters-RCV1 corpus are \(K \approx 44\) and \(\beta \approx 0.49\) (Manning et al. 2008).

With \(K > 0\) and \(0 < \beta < 1\) this continuous model grows, but ever more slowly:

\[ \frac{\mathrm{d}|V|}{\mathrm{d}N} = K\beta N^{\beta-1} > 0 \qquad (N > 0). \]

Our measurement shows the same thing: the first 100,000 tokens bring 13,497 types, while the last 100,000 tokens we measured bring only 1,814 new ones. New types keep arriving, but ever more rarely. Because \(\beta > 0\) in the model, its value grows without bound as \(N\) does. That is a property of the model; it does not mean that finite data has proved the language will produce new types forever. The measured type count is also a step-wise integer sequence, and the power curve is an approximate summary of it.

On many natural-language corpora new types keep appearing as data grows; how fast depends on the content of the corpus and on preprocessing. Heaps’ law is an empirical regularity that models that growth approximately over a given range, not a proven theorem.

Continuing to meet new forms is one of the things that make subword representations useful. The effect of the min_df filter, however, does not follow from Heaps’ law; it follows from how types are spread over documents, that is, from document frequencies. In the measurement above many rare columns were dropped while a small share of token occurrences was left out; whether that holds on another corpus has to be measured. min_df does not change the source text; it only drops features from the vectorizer’s vocabulary.

Always look at your top-50 list. In this count the second most frequent token is 'ax, with 62,043 occurrences, ahead of to, a and of. It is not a word of natural language. All of its occurrences sit in 13 of the 11,314 documents. Twelve of those are parts 3–14 of a fourteen-part posting of a file called roman.bmp. Their bodies hold the file’s content encoded as text (uuencode), and runs of identical bytes produce lines of the form >'AX>'AX>'AX. The thirteenth document is a separate posting with another encoded file and contributes a single occurrence. One document alone, part 12, accounts for 11,147 of the 62,043 occurrences.

By total count 'ax ranks second in this processed corpus, yet it is found in only 0.1% of the documents. The example shows that frequency in the corpus as a whole and spread across documents are different things.

TF-IDF uses both pieces of information, but it does not recognize non-language content by itself: a noise string that occurs in few documents can receive a high IDF. That is why looking at the list of most frequent tokens is a simple way to catch data and preprocessing problems before any weighting.

The leading apostrophe of the token 'ax is already in the raw data: the lines read >'AX>'AX. Our regular expression [a-z']+ keeps that character inside the token, and lowercasing turns AX into ax. scikit-learn’s default token_pattern does not include the apostrophe and produces the token ax from the same documents; under that setting too, ax ranks second after the, with 62,387 occurrences. The source content stays the same, but the form of the token depends on a preprocessing decision.

Before moving on, keep three counts apart: the number of times a term occurs in one particular document, its total number of occurrences in the whole corpus, and the number of documents that contain it. For 'ax the corpus total is high and the number of documents containing it is low. TF-IDF combines the term’s frequency in each document (TF) with an IDF weight computed from how many documents contain the term.

2.4 How a text becomes a vector

This is the core of the chapter. We will take four short maintenance logs all the way from strings to vectors you can compute distances on, skipping no step and showing every intermediate number.

corpus = [
    "the pump failed",           # d1
    "the pump was replaced",     # d2
    "the valve failed",          # d3
    "the seal leak was repaired", # d4
]
From string to vector: the six steps of this chapter
RAW TEXT TOKENIZE STEP 1 · INDEX STEP 2 · ONE-HOT "the pump failed" the · pump · failed failed→0 pump→2 the→6 pump = [0 0 1 0 0 0 0 0 0] STEP 3 · SUM = COUNTS STEP 4 · TF-IDF WEIGHTS STEP 5 · L2 NORMALIZE [1 0 1 0 0 0 1 0 0] word order is gone [1.51 0 1.51 … 1.00 …] terms in few documents get a high IDF [0.64 0 0.64 … 0.42 …] the vector's L2 norm is now 1 STEP 6 · COMPARE cos(d1, d3) = 0.528 In this pipeline the search, clustering and classification steps use the properties of the text these vectors represent.

The whole chapter in one picture. Steps 1–3 build the vocabulary and the term counts and throw away word order; the two accented steps, 4–5, weight those counts by document frequencies and scale them by the vector norm; step 6 compares the vectors. Every number shown is the one the code actually produces for d1 = "the pump failed". The vocabulary index is alphabetical, so failed is column 0, pump is column 2 and the is column 6.

Step 1 — the vocabulary is just an index

After preprocessing and tokenization we sort the distinct terms and map each one to a column number. That number is the term’s address in the vocabulary; by itself it says nothing about closeness in meaning. With its default settings CountVectorizer lowercases the text and counts runs of two or more letters or digits as tokens.

from sklearn.feature_extraction.text import CountVectorizer

cv = CountVectorizer()
X = cv.fit_transform(corpus)
print(cv.get_feature_names_out())
['failed' 'leak' 'pump' 'repaired' 'replaced' 'seal' 'the' 'valve' 'was']

Nine terms, so every vector from here on lives in \(\mathbb{R}^9\). The order in which the columns are numbered does not change any result, as long as training and use keep the same mapping. In word-level or n-gram systems the vocabulary can reach tens or even hundreds of thousands of entries. That size matters especially for sparse storage and for learning reliable patterns from rarely seen terms.

Step 2 — one-hot: a word as a vector, and why it is not enough

So we have an index. The numerical difference between two column numbers, however, says nothing about how close two words are in meaning: pump at 2 is no closer to repaired at 3 than to valve at 7. How do we turn a word into a vector a model can compute with?

The simplest possible encoding of a single word: a vector of zeros with a single 1 at the word’s address.

index of 'pump': 2
one-hot: [0 0 1 0 0 0 0 0 0]

This vector encodes the word’s identity; it does not show closeness in meaning between different words. Take the dot product of any two distinct one-hot vectors and you get zero — the single 1 in one vector always lands on a 0 in the other, so every product in the sum is zero:

pump  : [0 0 1 0 0 0 0 0 0]
valve : [0 0 0 0 0 0 0 1 0]
        ------------------- multiply position by position
        [0 0 0 0 0 0 0 0 0]  -> sum = 0

Under this encoding, pump is exactly as similar to valve as it is to repaired. The one-hot vectors of different words are orthogonal. The vector of a word matches itself exactly (dot product 1); closeness in meaning between different words is not part of this encoding. The vector for pump says which column the word is kept in, and nothing about what it is like.

One-hot is used here as an intermediate structure — a way to see how a document count vector is built, which is exactly the next step — not as the final way to represent word meaning. To address that gap we can move to learned dense vectors, that is, embeddings. Chapter 3 looks at how relations between words are reflected in a vector space, and at the limits of that.

Step 3 — a document is the sum of its one-hots

One word, one vector. But we did not set out to compare words — we set out to compare documents, and a document is many words at once. What do we do with all of them?

The simplest possible answer works: add them up. Add up the one-hot vectors of every token in a document and you get a count vector. That is bag-of-words: the multiset of tokens, order discarded.

d1 tokens: ['the', 'pump', 'failed']
d1 vector: [1 0 1 0 0 0 1 0 0]

Do it for all four documents and you have the document-term matrix, the central object of classical NLP. Rows are documents, columns are words:

          d1  d2  d3  d4
failed     1   0   1   0
leak       0   0   0   1
pump       1   1   0   0
repaired   0   0   0   1
replaced   0   1   0   0
seal       0   0   0   1
the        1   1   1   1
valve      0   0   1   0
was        0   1   0   1

Note the orientation. In the standard layout rows are documents and columns are terms; here the matrix is 4 documents × 9 terms. The block above is only shown transposed so that it fits the page.

feature — a variable that describes an observation. Here each feature says how many times a particular term occurs in the document, and it is represented by one column of the document-term matrix. If you come from statistics, this is a predictor variable under a different name. ↩︎

A statistician will recognize the structure: a design matrix with many correlated, mostly-zero predictors. Each document is an observation and each term’s count is a feature. Regularization, feature selection and generalization need attention here as well, and the assumptions of whichever method we use have to be checked separately.

Step 4 — does every word deserve the same weight?

We now have term counts. The next step is to decide how much weight each term should get when we compare documents.

Look at the row for the. It appears in all four documents, so it contributes to every comparison while distinguishing nothing. Meanwhile valve appears once and is the only thing that makes d3 distinctive. Raw counts give them the same treatment.

Two questions before the formula. To give a term a high weight we want two things:

  1. It is frequent in this document. The factor that measures this is TF.
  2. It is not ordinary across all documents. The factor that measures this is IDF.

TF-IDF is the product of the answers. The formulas below are one particular way of turning those two questions into numbers.

We want a weight that is high when a word is frequent in this document and rare across documents. Splitting that into two factors gives TF-IDF.

Term frequency is how often the word occurs in this document — the raw count we already have. scikit-learn does not divide that count by document length. Had we divided the counts by document length first, the same IDF weights and the L2 normalization in step 5 would still give the same vector: a common positive factor applied to every component of a row cancels in the final division. That does not mean every effect of document length disappears.

Many textbooks define term frequency as \(\mathrm{tf} = c(t,d)/|d|\), or as the logarithmic \(1 + \log c(t,d)\), and the resulting numbers differ. The classical shorthand for naming a variant is SMART notation, a three-letter code for (tf) × (idf) × (normalization). In that notation scikit-learn’s default is summarized roughly as ntc: natural (raw) tf, idf and cosine normalization. The code does not specify the details of IDF smoothing, though; the full formula has to be written out separately. Its counterpart with logarithmic tf is ltc, a common choice in classical IR. Setting sublinear_tf=True switches the TF component from the raw count to the logarithmic weight \(1 + \ln c(t,d)\). In the experiment at the end of this chapter that option’s accuracy is slightly higher than the basic TF-IDF configuration’s (0.843 against 0.831). Say which variant produced a number you report; “TF-IDF” on its own is not a specification.

document frequency (df) — in how many documents a word shows up at all, no matter how often it shows up in each. A word that occurs in every document does not distinguish documents by its mere presence; how often it is used in each can still differ. ↩︎

Document frequency, \(\mathrm{df}(t)\), is how many documents contain the word at all. We want the weight to fall as df rises, so we invert it. But raw inversion, \(1/\mathrm{df}\), is too aggressive, because its range is far too wide. In a collection of a thousand documents, a term in one document gets \(1/\mathrm{df} = 1\) and a term in every document gets \(0.001\): a thousandfold gap. A ratio that large can let rare terms contribute excessively to the weight in some documents. Those terms include distinctive technical names as well as typos. A logarithm compresses that range: \(\log(n/\mathrm{df})\) stays between \(\ln 1000 \approx 6.9\) and 0 in the same collection, and doubling the document frequency costs the same amount (\(\ln 2 \approx 0.69\)) wherever it happens. The second justification comes from information theory: in a model where documents are drawn with equal probability, \(\log(n/\mathrm{df})\) is the self-information of the event that the drawn document contains the term (see the intuition check below) (Spärck Jones 1972). The basic form is:

\[ \mathrm{idf}(t) = \ln\!\left(\frac{n}{\mathrm{df}(t)}\right) \]

Libraries adjust that basic form a little. In a vocabulary extracted from the training corpus every term occurs in at least one document; a vocabulary fixed in advance, however, can contain terms never seen in training, with \(\mathrm{df} = 0\). To handle a zero document frequency safely and to keep terms that occur in every document, scikit-learn uses this smoothed form:

\[ \mathrm{idf}(t) = \ln\!\left(\frac{1 + n}{1 + \mathrm{df}(t)}\right) + 1 \]

Read the formula one symbol at a time. \(t\) is a term, \(n\) is the number of documents in the collection, and \(\mathrm{df}(t)\) counts how many of them contain \(t\) at least once. The \(1+\) terms are smoothing, and they have a clean reading: the formula behaves exactly as if the collection held one extra document containing every term once. That reading explains why the denominator \(1 + \mathrm{df}\) always stays positive. For a fixed \(n\) the IDF is finite; as \(n\) grows, that upper bound grows too. The add-one here resembles the Laplace smoothing we will meet in Chapter 6; the denominators of the two formulas are not the same. The trailing \(+1\) then makes the IDF of a term that occurs in every document 1 rather than 0. The term is not zeroed out; it gets a smaller IDF factor than terms found in fewer documents. This is scikit-learn’s exact formula; other libraries differ in the details, which is a frequent source of “why don’t my numbers match”.

Work two of them by hand. Our corpus has \(n = 4\) documents. The word pump appears in d1 and d2, so \(\mathrm{df} = 2\):

\[ \mathrm{idf}(\texttt{pump}) = \ln\!\left(\frac{1+4}{1+2}\right) + 1 = \ln(1.667) + 1 = 0.511 + 1 = 1.511 \]

The word the appears in all four, so \(\mathrm{df} = 4\):

\[ \mathrm{idf}(\texttt{the}) = \ln\!\left(\frac{1+4}{1+4}\right) + 1 = \ln(1) + 1 = 0 + 1 = 1 \]

The second calculation sums up the design. The presence of a word that occurs in every document carries no information about which document you are holding, so the ratio inside the log falls to 1, the log falls to 0, and the term is left on the floor IDF value of 1. The term is not deleted: pump gets a factor of 1.51 and the a factor of 1.

The librarian’s version. Ask for “the book about pumps” and the word the narrows the shelf down not at all, while pumps narrows it to a metre of shelving. IDF weights a term inversely to how widespread it is across the documents of the collection: the documents that contain a high-IDF term make up a smaller part of the collection.

The use of the logarithm can be explained from two angles: it compresses the range of the weights, and under a particular probability model it can be related to self-information.

It compresses the range. Informativeness is not linear in rarity, but that alone does not call for a logarithm: \(1/\mathrm{df}\) is also a decreasing, flattening curve. The difference is the range of the weights. In a collection of 10,000 documents, \(1/\mathrm{df}\) gives a term found in one document ten thousand times the weight of a term found in every document. In some comparisons that can inflate the effect of rare shared terms. \(\log(n/\mathrm{df})\) stays between 9.2 and 0 and treats equal ratios equally: raising df from 1 to 10 costs the same weight (\(\ln 10 \approx 2.3\)) as raising it from 1,000 to 10,000.

Its relation to the self-information of occurring in a document. When a document is drawn from the collection with equal probability, the event “this document contains the term \(t\)” has probability \(P(t) = \mathrm{df}(t)/n\). Unsmoothed IDF equals the self-information of that event, in the information-theoretic sense: \(\log \frac{n}{\mathrm{df}(t)} = -\log P(t)\). This reading does not guarantee that the term matters semantically or is useful for every task. Robertson’s paper (Robertson 2004) is the careful treatment. The historical order is that Spärck Jones proposed IDF on empirical grounds in 1972, and the theoretical readings were developed later.

Its relation to Zipf. A logarithm turns ratios into differences and makes wide ranges of values easier to compare; that is why log transforms are common for skewed quantities such as income or city size. A Zipf-type power law looks approximately like a straight line on log-log axes, but that does not hold for every distribution. Moreover, the total frequency of use in Zipf’s law and the document frequency in IDF are different quantities.

Here are the document frequencies and IDF values for our corpus, computed by hand and then checked against the library:

import numpy as np

n = len(corpus)
df = (X.toarray() > 0).sum(axis=0)
idf_manual = np.log((1 + n) / (1 + df)) + 1
          df     idf
failed     2  1.5108
leak       1  1.9163
pump       2  1.5108
repaired   1  1.9163
replaced   1  1.9163
seal       1  1.9163
the        4  1.0000
valve      1  1.9163
was        2  1.5108

sklearn idf_: [1.5108 1.9163 1.5108 1.9163 1.9163 1.9163 1. 1.9163 1.5108]
max abs diff vs manual: 0.0

the is in all four documents and lands exactly on the floor of 1.0. Every word unique to one document gets 1.9163. The ordering is the point: the weight is a monotone decreasing function of how many documents a word appears in.

On the real corpus the spread is much larger:

the            df=  9477  df/N= 0.838  idf= 1.18
is             df=  7034  df/N= 0.622  idf= 1.48
car            df=   394  df/N= 0.035  idf= 4.35
encryption     df=   169  df/N= 0.015  idf= 5.20
gravitational  df=     8  df/N= 0.001  idf= 8.14
The IDF curve — drag to see how document frequency becomes an IDF value

Step 5 — multiply, then normalize

Two ingredients are on the table: a count that says how often a word appears here, and a weight that says how unusual it is everywhere. Combining them is the last piece of arithmetic in this chapter, and it is a multiplication followed by a division.

Before the mathematics, the reason for that division, as a question: why should two documents that use similar terms in similar proportions — one 20 words long, the other 2,000 — look far apart only because one is longer? In longer documents some term counts and the vector norm can grow, but not every term’s count necessarily does. L2 normalization brings the norm of a non-zero vector to 1 while keeping the ratios between its components. The comparison then turns on the vector’s direction rather than its absolute size.

TF-IDF — score each word in a document by how often it appears here, and reduce that score as the word becomes more widespread across the collection. Other things being equal, the TF-IDF weight rises with the term’s count in the document, and the IDF factor falls as more documents contain the term. ↩︎

TF-IDF is the product, computed cell by cell. For d1 (the pump failed):

from sklearn.feature_extraction.text import TfidfVectorizer

counts = X.toarray()[0]
weighted = counts * idf_manual
norm = np.linalg.norm(weighted)
print("counts        :", counts)
print("times idf     :", weighted.round(4))
print("l2 norm       :", round(norm, 4))
print("normalized    :", (weighted / norm).round(4))
print("sklearn row d1:", TfidfVectorizer().fit_transform(corpus).toarray()[0].round(4))
counts        : [1 0 1 0 0 0 1 0 0]
times idf     : [1.5108 0.     1.5108 0.     0.     0.     1.     0.     0.    ]
l2 norm       : 2.3591
normalized    : [0.6404 0.     0.6404 0.     0.     0.     0.4239 0.     0.    ]
sklearn row d1: [0.6404 0.     0.6404 0.     0.     0.     0.4239 0.     0.    ]

The last two lines show that our hand computation and the TfidfVectorizer result agree to the four decimal places displayed. On this example, comparing the two results without rounding also gives a largest absolute difference of 0.0. In general, floating-point results should be compared with a tolerance, for instance with np.allclose. The library performs the same calculation we have just built step by step.

Follow one row all the way through. d1 is the pump failed, so three positions are non-zero, each with a count of 1. Multiply each by its IDF and you get \(1.5108\) for failed, \(1.5108\) for pump, and \(1.0000\) for the. The length of that vector is the ordinary Pythagorean one, extended to nine dimensions — square, add, take the root:

\[ \lVert v \rVert_2 = \sqrt{1.5108^2 + 1.5108^2 + 1.0000^2} \approx \sqrt{2.28259 + 2.28259 + 1.00000} = \sqrt{5.56518} \approx 2.3591 \]

Intermediate values are rounded for display; carried at full precision the norm is \(2.35906509\ldots\), which is what the library uses.

The six zero entries do not change the sum. To benefit from that during computation on large vocabularies we keep the matrix in sparse form; the toarray() conversion used here to display intermediate values is not something to apply to large matrices. Divide through:

\[ \frac{1.5108}{2.3591} = 0.6404 \qquad \frac{1.0000}{2.3591} = 0.4239 \]

and those are exactly the numbers TfidfVectorizer printed above.

That final division by \(\lVert v \rVert_2\) is L2 normalization. It changes how a model uses the size of the vector. Without it, a long document usually has a vector with a larger norm, and every comparison based on a dot product or Euclidean distance — including a linear classifier’s score — becomes partly a comparison of vector sizes. (Cosine divides by the norms itself, so it is unaffected; see below.) Normalizing moves every non-zero document vector onto the unit sphere, so only direction, the weighted mix of terms, is left in the comparison. That is useful when we want the size effect removed; its effect on classification accuracy is something we measure on validation data.

The particular combination you have just built — term frequency, times inverse document frequency, then length-normalized — is not the only one anyone tried. Salton and Buckley (Salton and Buckley 1988) compared different term-weighting schemes empirically. The combination used here — raw TF, smoothed IDF and L2 — is scikit-learn’s default; other tools may choose a different formula and normalization.

Think of it as putting every document on a sphere of the same radius. A 50-word report and a 5,000-word report both end up at unit length — the squares of the components sum to one, not the components themselves — so the question becomes which direction each one points, not how far it reaches.

A document left with no active term after preprocessing and vocabulary filtering gives the zero vector. The cause can be empty text, only out-of-vocabulary terms, or every term being filtered out. Such a document has \(\lVert v \rVert_2 = 0\); the zero vector has no direction, and cosine with it is \(0/0\), undefined. scikit-learn returns a zero row and a cosine of 0, which is a convention. Count these rows and handle them separately. Do not read the 0 the library returns for them as a measured semantic dissimilarity between two valid documents.

The document-term matrix — switch between counts and TF-IDF

Step 6 — comparing documents with cosine similarity

Every document is now a point in \(\mathbb{R}^9\). That lets us ask the question the chapter has been building towards: how similar are the weighted term mixes of these two documents?

cosine similarity — how closely two documents point in the same direction, ignoring how long they are. That is why a short note and a long report can get a high cosine score when their weighted term proportions are similar. The score alone does not prove that they share a topic or a meaning. ↩︎

The sentence to keep: cosine similarity compares direction, not length. Two normalized vectors are compared by their dot product, which is the cosine of the angle between them. That number is their cosine similarity: For the non-zero vectors without negative components used here, 1 means identical direction and 0 means no shared term with positive weight. That reading does not carry over directly to representations that can have negative components. The equivalence with Euclidean distance in the box below is a detail on top of that intuition, not a replacement for it.

\[ \cos(a, b) = \frac{a \cdot b}{\lVert a \rVert \, \lVert b \rVert} = \sum_{i} a_i b_i \quad \text{(when both are already unit length)} \]

Compute one cell by hand. d1 is the pump failed and d3 is the valve failed; they share failed and the and disagree everywhere else. Only positions where both vectors are non-zero can contribute, so the whole nine-dimensional sum has exactly two live terms:

\[ \cos(\text{d1}, \text{d3}) = \underbrace{0.6404 \times 0.5729}_{\texttt{failed}} + \underbrace{0.4239 \times 0.3792}_{\texttt{the}} = 0.3669 + 0.1607 = 0.528 \]

Notice how uneven that is. failed supplies 70% of the similarity and the supplies 30%, even though each word occurs exactly once in each document. Under raw counts they would have contributed equally. The weighting is what decides which shared word counts as evidence.

from sklearn.metrics.pairwise import cosine_similarity

T = TfidfVectorizer().fit_transform(corpus)   # the TF-IDF rows from step 5
print(cosine_similarity(T).round(3))          # top panel
print(cosine_similarity(X).round(3))          # bottom panel: raw counts from step 1

Row and column labels were added to the output for readability:

       d1     d2     d3     d4          <- TF-IDF
d1  1.000  0.458  0.528  0.112
d2  0.458  1.000  0.125  0.286
d3  0.528  0.125  1.000  0.100
d4  0.112  0.286  0.100  1.000

       d1     d2     d3     d4          <- raw counts
d1  1.000  0.577  0.667  0.258
d2  0.577  1.000  0.289  0.447
d3  0.667  0.289  1.000  0.258
d4  0.258  0.447  0.258  1.000

Compare the two panels. Under raw counts, d1 and d4 sit at a cosine of 0.26 — but they share only the word the. By reducing the relative contribution of the shared the, TF-IDF brings that score down to 0.11. (A cosine is the cosine of the angle between the two vectors. It is not a calibrated percentage of semantic similarity, which is what reporting it as “26% similar” implies.) In this example every score between different documents drops, and the proportional drop is largest for the pairs that share only the. Each document’s similarity with itself stays at 1.

Why cosine and not Euclidean distance
RAW COUNT VECTORS · MAGNITUDE DOMINATES pump leak A (2, 1) B (20, 10) · 10 × A C (1, 4) Euclid says: ‖A−C‖ = 3.16 nearest — but C has different term proportions ‖A−B‖ = 20.12 far away — but B is exactly 10 × A A and B sit on one ray: same proportions, ten times the counts. AFTER L2 NORMALIZATION · DIRECTION ONLY unit circle a = b c 49.4° A and B land on the same point; only the angle survives.

Left: three documents as raw count vectors over two words, with both axes drawn to the same scale. In this example every term count of B is exactly ten times A’s, so A and B lie on the same ray out of the origin. C has different term proportions. On raw counts, Euclidean distance puts A more than six times closer to C than to B. Right: after L2 normalization every vector has length 1, A and B become the same point, and the only thing left to measure is the angle between directions. This is why classical text pipelines normalize before they compare.

Because on unnormalized vectors Euclidean distance is strongly affected by vector magnitude. Two reports of the same failure can produce vectors of different magnitude but similar direction if their term proportions are similar. The extra detail in a longer report can change the direction too, however. Cosine looks only at direction: it compares the proportions of the terms, not their total amount.

The simplest way to hold this: after L2 normalization, all vectors lie on the unit sphere, and there cosine similarity and Euclidean distance are monotonically related — \(\lVert a - b \rVert^2 = 2 - 2\cos(a,b)\). If non-zero vectors have been L2-normalized, the two measures give the same ranking in an exact nearest-neighbour search. Numerical thresholds have to be converted, though, and the equivalence does not mean that every clustering method or approximate search implementation will return the same result. On unnormalized vectors the two measures can give very different rankings.

Check it against the figure. The angle between \(a\) and \(c\) gives \(\cos = 0.651\), so \(\lVert a - c \rVert^2 = 2 - 2(0.651) = 0.698\) and the distance is \(\sqrt{0.698} = 0.836\). Before normalization that same pair was 3.16 apart; after normalization it is 0.836, and — this is the part that matters — the ordering of every pair now agrees with cosine.

Two lines of algebra, and they are worth doing once because the identity turns up again in Chapter 3 whenever someone swaps a cosine index for an L2 index and expects the same neighbours.

Expand the squared distance the way you would expand \((x-y)^2\), except that the products are dot products:

\[ \lVert a - b \rVert^2 = (a - b) \cdot (a - b) = a \cdot a - 2\,(a \cdot b) + b \cdot b \]

Now use what normalization bought us. A vector dotted with itself is its squared length, and every normalized vector has length exactly 1, so \(a \cdot a = 1\) and \(b \cdot b = 1\). And since both are unit length, their dot product is the cosine. Substitute:

\[ \lVert a - b \rVert^2 = 1 - 2\cos(a,b) + 1 = 2 - 2\cos(a,b) \]

Distance is a strictly decreasing function of similarity: as the cosine climbs from 0 to 1, the squared distance falls from 2 to 0. So a nearest-neighbour search under Euclidean distance and one under cosine return the same ranked list — provided the vectors were normalized first. Without normalization this ranking equivalence no longer holds. L2 distance is affected by both the magnitude and the direction of a vector, so documents with a similar mix of terms can look far apart because their counts are on different scales.

2.5 What bag-of-words cannot do

Now look at what this representation loses while the vector is still being built. These losses explain why the order- and context-based representations of the later chapters are needed.

It cannot represent word order. Not “represents it poorly” — cannot represent it at all:

pair = ["the pump failed and the valve is fine",
        "the valve failed and the pump is fine"]
vocabulary: ['and','failed','fine','is','pump','the','valve']
row 1: [1 1 1 1 1 2 1]
row 2: [1 1 1 1 1 2 1]
vectors identical: True
cosine similarity: 1.0

Two reports naming opposite pieces of failed equipment are the same point in space. No classifier, however good, can separate them, because the information was destroyed before the classifier saw it. Information discarded at the representation stage cannot be recovered by a stronger classifier.

n-grams buy back a little. Using pairs of adjacent words instead of single words:

bigram vocabulary: ['and the','failed and','is fine','pump failed',
                    'pump is','the pump','the valve','valve failed','valve is']
cosine similarity: 0.714
vocabulary size: unigrams 7 -> bigrams 9

Now they are distinguishable. That gain has a cost: on real corpora an n-gram vocabulary can become very large. How large depends on the corpus, on the n-gram range and on the filters applied. In the experiment below, adding bigrams took the feature count from 32,318 to 249,522, a 7.7× increase, and accuracy fell. n-grams buy back some local order information, and for jobs like language identification, spam filtering or short-text classification they can be enough on their own. But the feature space grows quickly as the context gets longer; long-range, context-sensitive relations need a more general representation, which is what Chapter 7 is about.

It cannot represent the scope of negation. The word not is a feature like any other, and a classifier can learn that its presence shifts the odds — what a bag of words cannot recover is what was negated. The example below shows it:

"no leak was found"  vs  "a leak was found"
vocabulary (the default token_pattern drops the one-letter "a"):
    ['found', 'leak', 'no', 'was']
raw counts  ->  cosine 0.866
TF-IDF      ->  cosine 0.777

Two sentences with opposite operational meaning sit at cosines of 0.78 to 0.87 depending on the weighting. The example shows that sentences with opposite meanings can get a high cosine. If no is kept, the vectors differ and a classifier can use that difference. Which expression the negation attaches to, however, is not encoded directly by single-word counts. If your stop word list contains no — as scikit-learn’s built-in English list does — you delete the difference between the two sentences before the vector is even built, and the two vectors become identical (cosine 1). A model that uses only these vectors then cannot tell the two sentences apart. In tasks where negation changes the decision, the stop word list therefore needs to be checked separately.

It does not encode synonymy or polysemy directly. pump failed and pump broke share nothing beyond pump. In a lowercased bag of words, Apple the company and apple the fruit land in the same column — keep the case and they are two columns, which is a direct consequence of the preprocessing decision in Section 2.2.1. In this representation different terms sit in separate columns, and the semantic relation between them is not encoded directly, as we saw with one-hot vectors in Step 2. The dense representations of Chapter 3 help to learn those relations. Separating the senses a word takes in different uses additionally requires taking context into account.

2.6 Does any of this still matter?

Yes, and you should be able to say why with numbers rather than opinion. Here is a real experiment: four newsgroups, 2,327 training documents, 1,550 test documents, logistic regression; no hyperparameter search was done, and max_iter=2000 was set for convergence.

from sklearn.datasets import fetch_20newsgroups
from sklearn.feature_extraction.text import CountVectorizer, TfidfVectorizer
from sklearn.linear_model import LogisticRegression
from sklearn.metrics import accuracy_score
from sklearn.pipeline import make_pipeline

cats = ["sci.med", "sci.space", "rec.autos", "talk.politics.guns"]
drop = ("headers", "footers", "quotes")
train = fetch_20newsgroups(subset="train", categories=cats, remove=drop)
test = fetch_20newsgroups(subset="test", categories=cats, remove=drop)

setups = {
    "raw counts": CountVectorizer(),
    "counts + stop words": CountVectorizer(stop_words="english"),
    "tf-idf": TfidfVectorizer(),
    "tf-idf + stop words": TfidfVectorizer(stop_words="english"),
    "tf-idf + bigrams": TfidfVectorizer(ngram_range=(1, 2)),
    "tf-idf + sublinear tf": TfidfVectorizer(sublinear_tf=True),
}

for name, vec in setups.items():
    clf = make_pipeline(vec, LogisticRegression(max_iter=2000, random_state=0))
    clf.fit(train.data, train.target)
    acc = accuracy_score(test.target, clf.predict(test.data))
    print(f"{name:<24} accuracy {acc:.3f}   "
          f"features {len(clf[0].get_feature_names_out()):>7}")
raw counts               accuracy 0.767   features   32318
counts + stop words      accuracy 0.795   features   32014
tf-idf                   accuracy 0.831   features   32318
tf-idf + stop words      accuracy 0.853   features   32014
tf-idf + bigrams         accuracy 0.819   features  249522
tf-idf + sublinear tf    accuracy 0.843   features   32318

This table is a demonstration of a mechanism and a baseline comparison. Do not read small differences as universal superiority; the caveat below says why, in numbers.

Read those six lines carefully, because they contain four conclusions:

  1. TF-IDF is worth 6.4 accuracy points over raw counts, without collecting more training documents and without a hyperparameter search. Computing IDF and normalizing still take extra computation.
  2. Stop word removal helps here (+2.2 points): on this dataset and this topic-classification task, the function words it removes do not appear to carry a strong signal for separating the classes. In sentiment analysis or negation detection the same step can hurt if the list removes words that matter for the task. The gain here does not by itself show that every removed word was useless. One note on that list: scikit-learn’s own documentation calls stop_words='english' problematic — it is not a general-purpose list, its selection criteria are undocumented, and a few of its entries can never be produced by the default token_pattern in the first place. If stop words matter to your result, write the list yourself and print it.
  3. Accuracy fell when bigrams were added, while the feature count grew 7.7-fold. More features do not guarantee higher accuracy. The added sparse n-grams can raise the risk of overfitting; pinning down the cause of the difference in this experiment would take a separate comparison of regularization and feature selection.
  4. sublinear_tf points the same way (0.843 vs 0.831). That option replaces the raw count with \(1 + \log(\text{tf})\) — the same range-compression argument we made for IDF, applied to the term-frequency side.

A caution before you quote any of those six numbers. They are point estimates with no intervals attached. The test set holds 1,550 documents; under a binomial approximation that treats documents as independent, a single accuracy near 0.83 carries a 95% interval of roughly ±1.9 points. If two accuracies are treated as independent estimates, the interval of their difference is roughly ±2.6 points. Those intervals give a rough idea of the scale of the uncertainty; but the six models are measured on the same test documents, so deciding about the differences under an independence assumption is not appropriate. The uncertainty of the differences has to be computed from the paired predictions, which the note below does. Because six configurations are compared, selection of results and multiple comparisons also have to be taken into account.

The six models see the identical test documents. That is the setting for a paired test such as McNemar’s (McNemar 1947). McNemar’s test compares the number of documents one model classifies correctly and the other incorrectly; documents that both models get right, or both get wrong, do not affect the result. That is how the pairing through the shared test documents is taken into account.

The numbers from this experiment for the comparisons behind the four conclusions are below; the p-values come from the exact McNemar test, which is based on the binomial distribution:

Paired results for the four comparisons (1,550 test documents)
Comparison Only the first correct Only the second correct p
TF-IDF and raw counts 119 20 2.4 × 10⁻¹⁸
TF-IDF + stop words and TF-IDF 86 52 0.0048
TF-IDF + bigrams and TF-IDF 17 35 0.018
TF-IDF + sublinear tf and TF-IDF 29 11 0.0064

With four comparisons, a Bonferroni correction puts the threshold at 0.05/4 = 0.0125. The TF-IDF, stop word and sublinear_tf differences fall below it; the bigram difference does not. These p-values measure only the uncertainty from sampling the test documents. They rest on a single train–test split and a single training run, and do not generalize to other datasets or tasks.

One more warning about generalising from six lines. Every number here comes from English topic classification on long documents, and two of the four lessons reverse when the task changes. On Turkish product reviews — short documents, sentiment rather than topic — the first table in Chapter 4 points the opposite way on both counts: at a fixed label budget bigrams give the largest gain, and plain counting beats TF-IDF. But the second result does not come from IDF. That chapter’s ablation refutes the obvious “IDF down-weights the frequent sentiment words” explanation (L2 normalization costs the points; adding IDF on top wins them back) and shows the result hinged on an untuned C and reverses under an equal tuning budget. The transferable lesson is the method, not the ranking.

The other reason to care is that the model is readable. Ask a TF-IDF-plus-logistic-regression model what it learned and it will tell you, in words:

rec.autos            car, cars, engine, ford, oil, dealer, drive, price
sci.med              msg, doctor, disease, medical, pain, patients, treatment
sci.space            space, nasa, orbit, moon, launch, earth, spacecraft
talk.politics.guns   gun, guns, weapons, fbi, law, government, firearms

In a linear bag-of-words model the coefficients can be tied to the terms or n-grams of the vocabulary. In a multi-class model we inspect those coefficients class by class; the table above shows the terms with the largest coefficients for each class. The contribution to the score of a particular document depends on the product of the coefficient and the feature value, and a large coefficient is not by itself a causal explanation. Dense representations rarely offer a term–coefficient mapping that clear. (Attribution, SHAP-style explanations and probing exist for dense models too — none of them reads as directly as the table above.) When you have to explain a model to a safety board, a regulator, or a sceptical plant manager, that readability makes it easier to examine errors and to discuss the model’s decisions. The trade-off against accuracy is set by the requirements of the application.

The computational cost is low as well:

shape: (2327, 32318)
stored non-zeros: 234281
density: 0.312%
dense float64 would need :    601.6 MB
sparse csr actually needs:      2.8 MB
ratio: 213x

The matrix is 99.7% zeros, so a sparse representation stores it in 2.8 MB instead of 601.6 MB. This example needs no GPU. Computing the classification scores comes down to sparse dot products; end-to-end inference also includes preprocessing and vectorization. The 2.8 MB is the storage cost of the sparse matrix alone; the vocabulary, the IDF values, the model coefficients and working memory come on top. Training time depends on hardware and solver settings: on the CPU of the laptop used for this chapter’s measurements, each of the six configurations above finished in under 2 seconds, including vectorization, training and prediction on the test set.

Putting the whole chapter’s evidence in one place:

Bag-of-words, honestly
Why bag-of-words survives Why it is not enough
A small sparse matrix. In this example the matrix for 2,327 documents takes 2.8 MB; total model memory is larger. No GPU needed. No word order. pump failed, valve fine and valve failed, pump fine are the same vector.
Legible. The model names its own features — gun, orbit, doctor. That makes it easier to inspect how terms contribute to a score. No synonymy. car and automobile are as unrelated as car and banana. Exact match or nothing.
Strong baseline. 0.853 here, and it beat averaged embeddings in Chapter 3 — then beat them again on Turkish data in Chapter 4. No polysemy. One column for bank, whatever it meant.
No training data beyond your own. Nothing pretrained, nothing downloaded, no vendor. Out-of-vocabulary terms can occur. New documents can contain terms that are not in the fixed vocabulary built in training.
Reproducible with a fixed pipeline. With preprocessing, vocabulary, IDF and model parameters fixed, the same input gives the same output, and term contributions can be inspected. Negation has no scope. not is a feature like any other and can carry signal; what a bag cannot recover is what was negated — and removing stop words deletes it outright.

The right reading is not “old technology, still surprisingly good.” The two columns of the table show the strengths and the limits of one and the same representation. Which side weighs more depends on what the task requires.

When exact term matching, speed and traceability matter, bag-of-words is a strong starting option. Make the final decision by weighing accuracy, latency, memory and the kinds of error together.

When the task needs order or context information, the representation has to be extended beyond single-word counts. N-grams can help with local relations, and character features with new forms. For broader semantic relations we will look at dense and contextual representations, starting with Chapter 3.

Where this is actually deployed

The examples below show sparse text representations in use. Some rest on dated system reports published by companies, others on method papers; read the architectures described as limited to the period those sources cover. Three new terms appear below; each is an applied form of an idea from this chapter:

  • BM25: the TF-IDF family’s weighting, developed for search.
  • Feature hashing: a way to get a fixed-size sparse representation without holding a vocabulary in memory.
  • Shingling: an n-gram representation that keeps part of the word order.

The deployments themselves:

  • Ticket triage at Uber. COTA, the customer support system Uber described in 2018, uses most of the pipeline from this chapter: clean the text, tokenize, remove stop words, lemmatize, compute TF-IDF, reduce with LSA (latent semantic analysis, a truncated SVD of the TF-IDF matrix; see the interview questions below). It then feeds the cosine similarity computed from the LSA vectors, together with ticket and trip features, to a random-forest matching model and ranks candidate solutions by that model’s score (Uber Engineering 2018). According to the write-up the system can reduce ticket resolution time by over 10%. The same write-up compares this ranker with a multi-class classifier fed the LSA topic vectors directly, on the same dataset, with the same type of algorithm and the same hyperparameters; the ranker is 25% better in relative accuracy. The result shows that, in this experiment, deriving matching features from the LSA vectors was more useful than using the vectors directly. The problem the write-up mentions is that most of the hundreds or thousands of dimensions needed for a meaningful representation have values close to zero; that is not the same kind of sparsity as the many exact zeros of the original count matrix.
  • Search ranking. Lucene, and therefore Elasticsearch and OpenSearch, scores documents with BM25 by default. BM25 comes from the TF-IDF family and adds document-length normalization and a saturating term frequency (Robertson and Zaragoza 2009). Elastic’s Practical BM25 series explains the formula and its two tuning constants with detailed examples. BM25 is a common scoring method in many Lucene-based text search systems; it cannot be assumed that every search box uses it.

\[ \mathrm{BM25}(q, d) = \sum_{t \in q} \mathrm{idf}(t) \cdot \frac{c(t,d)\,(k_1 + 1)}{c(t,d) + k_1\!\left(1 - b + b\,\frac{|d|}{\mathrm{avgdl}}\right)} \]

In this simplified formula the sum runs over the distinct terms of the query; repeated query terms are not weighted separately. \(c(t,d)\) is the count of term \(t\) in the document, \(|d|\) the number of tokens in the analysed document, and \(\mathrm{avgdl}\) the average document length in the same collection.

Read it against what you just built. The \(\mathrm{idf}\) factor is the same idea as ours (BM25 uses a probabilistic variant). The fraction replaces raw term frequency with a saturating one: with the other variables fixed, document length in particular, the fraction approaches the limit \(k_1 + 1\) as \(c(t,d)\) grows, and additional repetitions contribute less and less. sublinear_tf also slows the effect of repetitions, but \(1 + \log(\mathrm{tf})\) grows without bound and is not the same function as BM25. And \(b \in [0,1]\) interpolates between ignoring document length (\(b = 0\)) and dividing the term frequency by the document’s length relative to the corpus average (\(b = 1\)). That is the same concern L2 normalization addresses — long documents should not win on length alone — handled by a different formula and with a dial instead of a switch; the two are not the same operation. In Lucene 9.12.1 the defaults of the BM25Similarity class are \(k_1 = 1.2\) and \(b = 0.75\).

  • Google’s text classification guide recommends this representation (Google Developers 2022): it reports TF-IDF n-grams as the most accurate of the encodings it compares. In the guide’s experiments on English text, accuracy levels off at around 20,000 selected features for many datasets; more features contribute very little and sometimes lower performance. That is not a fixed threshold for every language. Our bigram result (249,522 features, lower accuracy) likewise shows that more features do not bring an automatic gain; whether the drop has the same cause in the two experiments would have to be tested separately.
  • Hybrid retrieval. Modern retrieval stacks combine dense embedding search with sparse BM25 search, because the sparse half catches the exact matches — part numbers, error codes, surnames — that embeddings can miss. You will build one in Chapter 19; Chapter 20 wires it to a language model.
  • Spam and abuse filtering at scale. Sparse text features remain a first-line filter because they are cheap enough to run on every message and, depending on data size, model and hardware, can be retrained quickly when attackers change tactics. One method that can be used for this is feature hashing, which maps terms to a fixed number of columns with a hash function (Weinberger et al. 2009). It stores no explicit vocabulary; in exchange, different terms can fall into the same column, and tracing a coefficient back to a single term becomes harder.
  • Near-duplicate detection. Hash-based methods have an important place in near-duplicate detection at web scale: short signatures make comparison feasible over very large document collections. Google’s web-crawl deduplication work, published in 2007 (Manku et al. 2007), is one example; it computes simhash fingerprints from weighted document features. The other standard method is MinHash over sets of shingles (Broder 1997). A shingle is a fixed-length window of words (or characters) slid across the document; the windows overlap like roof tiles, which is where the name comes from. The three-word shingles of the pump failed last night are the pump failed and pump failed last and failed last night. So shingles have the same structure as the n-grams we used above to recover some word order.

The practical rule: reach for TF-IDF when your labels are few, your documents are long, your vocabulary is technical and exact-match matters, or when you need a baseline quickly. For tasks it suits, such as text classification and lexical retrieval, include a TF-IDF baseline in the comparison. If your transformer cannot beat it, you have learned something important about your data, and you have learned it cheaply.

2.7 Intuition checks

Answer these before reading the answer. If you can answer all six, you understand the material beyond what running the code shows.

Not for the reason you think. Do not panic about memory just because you see 200,000 columns: in a sparse matrix the real memory cost depends mostly on the number of non-zeros, not on rows × columns.

The real worry is statistical: 5,000 observations against 200,000 features. That is a p ≫ n problem, a situation in which regularization and the design of validation become important.

The usual answers are strong regularization (L2 or L1) and cutting the feature count with min_df.

The Zipf section showed why that second lever removes so many columns: most of the vocabulary occurs in few documents, which can make the effect of those terms hard to learn reliably. Some rare terms are nevertheless useful for telling particular classes apart. On the four-category corpus from the classification experiment above, min_df=5 takes the vocabulary from 32,318 down to 6,281 — 81% of the columns gone.

Do not mistake that for something free. The deleted columns carry 11.6% of the token occurrences. min_df=5 does not only drop terms seen once in total (hapax legomena); it drops every term that occurs in fewer than five different documents. Such a term may be repeated many times within one document, which is why we report the share of columns removed and the share of token occurrences removed separately. Whether the trade is worth it is an empirical question rather than a rule, and Exercise 3 asks you to measure it.

In a supervised classification evaluation the vocabulary and the IDF are learned from the training portion only and applied unchanged to validation and test data. In cross-validation that learning is repeated on each training fold. IDF is a parameter estimated from data, so computing it over train + test leaks information about the test distribution into your features. In search systems, computing IDF from the indexed document collection is a separate evaluation setting.

In scikit-learn this is exactly what fit_transform on train and transform on test does — and it is why calling fit_transform twice is a real and common bug. In production the same logic says the IDF vector is a model artifact you version and ship, not something you recompute per batch; otherwise your features drift silently as traffic changes.

With scikit-learn’s smoothed formula, \(\mathrm{df} = n\) gives \(\ln\frac{1+n}{1+n} + 1 = 1\), so the IDF factor is 1. Before normalization the TF-IDF value is the term’s TF value. L2 divides the whole row by one common norm; the step that creates the difference in weight relative to rarer terms is the multiplication by IDF.

With the textbook unsmoothed formula \(\log(n/\mathrm{df})\) it would be exactly 0 and the term would drop out of the vector. smooth_idf=True is the default. With smooth_idf=False, however, scikit-learn still keeps the outer \(+1\): \(\mathrm{idf} = \ln(n/\mathrm{df}) + 1\). A term that occurs in every document therefore has an IDF of 1 under that setting too, and the result is not the textbook formula.

Because the two normalizations answer different questions. L2 row normalization brings non-zero document vectors to unit norm, so that comparisons rest on the proportions of the weighted terms rather than on the absolute size of the vector.

Subtracting non-zero column means and storing the result explicitly turns the existing zeros into non-zero values and destroys sparsity. In the example about 99.7% of all cells of the matrix are zero; that share need not be the same in every column. If we subtract the column means and store the result in a dense float64 array, this 2.8 MB matrix needs about 601.6 MB. Not every column scaling behaves this way, though: scaling without centring, for instance StandardScaler(with_mean=False), can keep the sparse structure. Sparsity is a constraint that determines which operations are practical.

Start by comparing the tokens produced by the query analyser and the document analyser. scikit-learn’s default token_pattern=r"(?u)\b\w\w+\b" requires two or more word characters and does not cross the hyphen, so it loses the prefix of P-101:

text = ["P-101 / P-102 pump tripped"]
for name, pattern in [("default", r"(?u)\b\w\w+\b"), ("custom", r"(?u)\b\w[\w-]*\w\b")]:
    cv = CountVectorizer(token_pattern=pattern).fit(text)
    print(f"{name:<10} : {list(cv.get_feature_names_out())}")
default    : ['101', '102', 'pump', 'tripped']
custom     : ['p-101', 'p-102', 'pump', 'tripped']

Your equipment tag P-101 silently became 101, and P-102 also became a bare number. The two are still different tokens, but the equipment prefix is gone: 101 is now the same token as the 101 in a page number, a quantity or a pressure reading. If the same transformation is applied on the query side and the document side, a match through 101 is still possible; getting no result at all can also come from a mismatch between the query and index analysers or from other filters. In technical domains tokenization errors of this kind lose important identifiers and can seriously affect model performance. They are also easy to miss: nothing raises an error, and accuracy just stays lower than it should.

The habit that prevents it: after fitting any vectorizer, print get_feature_names_out() and read it. Actually read it.

As a practical starting heuristic, a bag-of-words baseline is especially attractive when several of these hold together: you have very few labelled examples per class; your vocabulary is domain-specific and exact matching matters (part numbers, gene names, legal citations); you must explain every prediction to someone with authority over you; you have no GPU or a hard latency budget; or your documents are long and topical rather than short and nuanced.

In suitable classification and retrieval tasks, use it also as a strong classical baseline for measuring what more complex methods gain. When a team reports “our transformer gets 0.91” without reporting that TF-IDF gets 0.89, we simply do not know how much of a gain 0.91 is (Chapter 22).

2.8 Interview questions

Text representation is one of the core topics to study when preparing for applied NLP interviews; it is a topic that can show whether a candidate understands the material or only knows the library calls. Below, the questions are grouped by what they test.

On attribution — please read this once. You will find a great many pages online headed “NLP questions asked at Google and Amazon”. Not every company attribution on such pages rests on a verifiable source. We will say that a question was asked at a particular company only where an open source supports it, and present the others as practice on the topic.

The question groups below were prepared by drawing on the topics covered in two free sources; the examples and answers were adapted to the scope of this chapter: Introduction to Machine Learning Interviews by Chip Huyen (Huyen 2021), which states that most of its questions have been asked in real machine-learning interviews but attributes none of them to a named company; and AIMLInterviews, compiled by an engineer from his own loops at several large technology companies, which grounds the topics without tagging individual questions. Where a question corresponds to a system a company has actually documented, that system is cited so you can check the claim yourself.

Testing whether you understand the weighting

Q: Explain TF-IDF to someone who has not seen it. Then explain why the IDF term uses a logarithm.

Give the two-factor decomposition first: other things being equal, TF-IDF gives a higher weight to a term that is frequent in this document and found in few documents. That weight is not the same thing as importance for a task. Then give the information-theoretic reading from the intuition check above: in a model where documents are drawn with equal probability, \(\log(n/\mathrm{df})\) is the self-information of drawing a document that contains the term. Mention range compression as well: \(1/\mathrm{df}\) gives rare terms thousands of times the weight of common ones, while the log keeps the weight between 0 and \(\log n\) for positive df. Do not reach for “1 versus 2 documents matters more than 100 versus 200”; the log counts both doublings as equal. If you add that Spärck Jones proposed it empirically in 1972 (Spärck Jones 1972) and the theory came later (Robertson 2004), you have shown that you read primary sources.

Q: When would raw term counts outperform TF-IDF?

Raw counts can be enough when document frequency adds nothing for telling terms apart. If the df values of the terms are close to one another, for instance, IDF adds very little extra discrimination to raw counts; if all IDFs are equal, that common factor cancels in the final L2 normalization. Whether raw counts are actually better still has to be measured. A second case is generative models: the generative reading of multinomial naive Bayes rests on integer counts. Fractional inputs such as TF-IDF can nevertheless work well in practice, so keep the probabilistic interpretation and empirical classification accuracy apart. And when the numbers feed a statistical test directly rather than a model: tests like chi-square or the log-likelihood ratio expect counts, because counts add up — “this term occurs 47 times across the two categories” is a meaningful sentence. A sum of TF-IDF weights is not a raw count of events. Putting TF-IDF values in place of counts in a contingency table built from raw frequencies therefore does not amount to applying the same test. One warning: in Chapter 4, raw counts beating TF-IDF on short Turkish reviews came not from IDF but from an untuned C interacting with L2 normalization, and it reversed under an equal tuning budget. Give both sides the same tuning budget before you credit the representation.

Q: You add bigrams and accuracy drops. What happened?

One possible cause is that the added sparse n-grams increase overfitting: the feature space grew by roughly an order of magnitude while the data stayed fixed. That cannot be concluded from the accuracy difference alone, though; the n-gram frequencies, the strength of regularization, convergence and the paired test results all have to be examined. In this chapter’s experiment the feature count went from 32,318 to 249,522 and accuracy from 0.831 to 0.819; in the paired test that difference did not clear the threshold corrected for four comparisons. Things to try: raise min_df (the threshold for how many separate documents a term must appear in before it earns a column of its own; raising it removes the bigrams seen in only one or two documents before they ever enter the vocabulary), strengthen regularization, or select among bigrams that meet a minimum frequency by pointwise mutual information (PMI). Measure the effect of each choice separately on validation data.

Q: Why does removing stop words sometimes hurt a sentiment model?

Because some stop word lists also contain negation and emphasis words that matter for a particular task. If the list in use removes not, no, never, very, only or but, for example, distinctions useful for sentiment can be lost; scikit-learn’s English list contains all six. In that case This is not good and this is good become the same vector. The chapter’s own numbers show both sides: stop word removal showed a 2.2-point gain on topic classification, and would make the two sentences of the negation example indistinguishable. The rule to state out loud is that preprocessing must be chosen against the task, not applied because it is the default.

Q: How does the curse of dimensionality show up in text, specifically?

As high dimensionality together with sparsity. A TF-IDF matrix can have 10⁵ dimensions and 0.3% density. That dimensionality can make learning harder, but how many terms pairs of documents share cannot be read off the density figure alone. The distribution of similarities and how well neighbours can be told apart have to be examined in the data. Note what makes text unusual: the dimensionality is very large but so is the sparsity. Linear models with strong regularization can work better on text than the raw dimension count would suggest (Joachims 1998). The escape routes are feature selection (min_df), projection (truncated SVD), and learning a dense representation instead (Chapter 3).

Testing whether you understand the geometry

Q: Why cosine similarity instead of Euclidean distance for documents?

Length invariance — see the intuition check. The strong follow-up answer is that on L2-normalized vectors the two are monotonically equivalent via \(\lVert a-b\rVert^2 = 2 - 2\cos(a,b)\), so the question is really about whether you normalized.

Q: Two documents have cosine similarity 0. What does that mean, and how likely is it in practice?

If both vectors are non-zero and have no negative components — as with this chapter’s bag-of-words and TF-IDF vectors — a cosine of zero means there is no shared feature with positive weight. For zero vectors the mathematical cosine is undefined; the 0 a library returns has to be kept apart from that case. In general a cosine of 0 means the vectors are orthogonal, which in representations that can carry negative components does not mean “no shared words”; the distinction starts to matter with the embeddings in Chapter 3. On long English documents with stop words retained this is rare, because they tend to share common function words. On short ones — this book’s 19-word Turkish reviews, a log line, a search query — it is routine, and so is it on domain text where two documents genuinely have no vocabulary in common. If you see many zero scores, first check for empty vectors, out-of-vocabulary terms and filters, and whether the pairs being compared are actually related. If related texts are worded differently, measure the benefit of dense representations on an evaluation set (Chapter 3).

Q: Your document-term matrix is 10⁶ × 10⁵. How do you store and work with it?

Start by saying what the number means: a million documents against a hundred-thousand-word vocabulary is \(10^{11}\) cells. Stored as 8-byte float64 values, the data area of the matrix alone is 800 GB. That is a very high cost for an ordinary computer, and the memory for intermediate computations and the model comes on top.

Then say what rescues it: almost all of those cells are zero. A single document uses maybe a few hundred of the hundred thousand words, and text matrices typically run 0.1–1% non-zero. There is no point storing the zeros.

Compressed sparse row (CSR) does exactly that: it holds the matrix not as a grid but as three lists — the non-zero values, the column each value belongs to, and where each row starts in that list. Cost then scales with the number of non-zeros rather than the number of cells. At 0.1% density that is \(10^8\) values. With float64 values and 32-bit column indices, 12 bytes per entry come to roughly 1.2 GB; the row pointers and object overhead are extra. That is about 1.2 GB in place of 800 GB, roughly a 670× saving. Under the same assumption, values and column indices take about 12 GB at 1% density. Where 64-bit indices are needed the cost is higher.

What separates a good answer is the next part: sparsity is not a storage trick, it is a constraint on which operations you are allowed to perform.

  • Operations that destroy sparsity. Subtracting non-zero column means and storing the centred matrix explicitly makes the zeros in those columns non-zero and brings back the cost of a dense matrix. A textbook PCA mean-centres first as well. Some solvers apply the centring implicitly (in recent scikit-learn versions particular solvers support sparse input this way), so check the sparse-input support and memory behaviour of the PCA solver you use.
  • Operations that preserve it. Row-wise L2 normalization keeps the sparse structure. A sparse matrix–vector product can also be computed without densifying the input matrix, but the resulting vector can be dense.
  • Operations whose input stays sparse and whose output need not. An all-pairs similarity matrix is the one to watch. If the non-zero rows of \(X\) have been L2-normalized beforehand, \(XX^{\top}\) gives the cosines. With non-negative weights a single shared positive term makes the dot product of that pair positive, so on a corpus where every document contains one common word the matrix is completely dense — \(n^2\) floats, which at \(n = 50{,}000\) is 20 GB. cosine_similarity returns a dense array by default, and asking for a sparse one changes the storage format rather than the number of non-zeros. Compute it in blocks, or keep only each row’s nearest neighbours.
  • Truncated SVD if you want fewer dimensions. Unlike PCA it skips the centering step, so it runs directly on the sparse matrix. Truncated SVD applied in this way to a term-count or TF-IDF matrix is called latent semantic analysis (LSA). It can process sparse input, but the low-dimensional document vectors and the component matrix are usually dense, so include those outputs in the memory estimate. LSA is the historical bridge to Chapter 3.

Testing whether you have shipped something

Q: You trained a text classifier that performs well offline and badly in production. Walk me through your debugging.

The expected structure is a checklist, in cost order.

  1. Train/serve skew. “Serving” is the stage after training, where the model answers real requests. The question to ask: is the identical preprocessing pipeline running in both places? That includes the TfidfVectorizer object itself. Once fitted, it is no longer just code — it carries two things learned from the training data: the vocabulary that maps each word to a column, and the per-term IDF vector. Production has to use the same preprocessing rules, vocabulary and IDF values as training. Refitting the vectorizer on different data can change the column mapping or the weights; the problem then arises in the feature pipeline, before the classifier.
  2. Vocabulary drift. New product names, new error codes — absent from the vocabulary, they map to no column at all, so the model never sees them.
  3. Distribution shift in the label mix.
  4. A leak in the offline evaluation, such as fitting the vectorizer before the train/test split.
  5. Only then, the model.

The fitted vectorizer is a component that has to be stored with the model: saved, versioned and shipped alongside the model weights. A good answer is expected to name that nuance.

Q: Design a system to detect near-duplicate documents in a corpus of 100 million.

They are testing one reflex: do not try to look at every pair. A hundred million documents have \(\binom{10^8}{2} \approx 5 \times 10^{15}\) pairs; at a billion comparisons a second that is 58 days. So the answer cannot be “make it faster” — it has to be “never enumerate the pairs”.

Naming the expected pipeline is enough: turn each document into a set of sliding word windows (shingles), define similarity as Jaccard overlap, compress those sets into fixed-length signatures with MinHash, spread the signatures into buckets with locality-sensitive hashing (LSH) so that only documents sharing a bucket become candidate pairs, and compute the true Jaccard only on the candidates. With a suitable data distribution and parameters this pipeline can cut the number of pairs to examine substantially. The number of candidates can still grow quadratically in large buckets, and LSH can miss some similar pairs. Both the candidate cost and the recall have to be measured; Section 11.3 builds it with measured numbers and shows how the number of bands sets the threshold.

This chapter’s material is the first step, and it matters more than it looks: shingles come out of the tokenization decisions discussed above. Did you case-fold, did you strip punctuation, did you use character windows instead of word windows — each of those changes what counts as a duplicate.

Q: Build a search engine for internal technical documentation. Where do you start?

Start with BM25 (Robertson and Zaragoza 2009) via Elasticsearch or a similar engine, because it is a strong baseline that can ship quickly and, with a suitable analyser and field mapping, makes good use of exact matches on part numbers. Check in the token output that the part numbers survive intact, and measure the matching behaviour of dense retrieval on the same test queries. Then add dense retrieval for paraphrase and combine the two — hybrid retrieval, the architecture you will build in Chapter 19. A good answer justifies the starting method by the requirements and proposes measuring the gain of the more complex approach by comparison.

Testing your preprocessing decisions

Q: Stemming versus lemmatization — and would you use either today?

Define both, then describe current practice. With a pretrained transformer you keep the tokenization and normalization pipeline the model expects, and you do not add stemming or lemmatization on top. Subwords can increase the sharing of pieces between different forms, but they are not a one-to-one replacement for morphological analysis. For sparse retrieval or classification, measure the benefit of these transformations on the task; they can help in morphologically rich languages where you have a good analyser (Oflazer 1994). Interviewers are checking whether you apply techniques by habit or by argument.

2.9 Where to go deeper

The list below is long, and you do not need all of it. Decide what you want first:

Reading paths by goal
Your goal Starting sources
I have thirty minutes the 3Blue1Brown video, the scikit-learn text-features page
I want the TF-IDF and IR side Manning et al.’s IR book (the idf and BM25 pages), the scikit-learn docs
I want the academic reference Jurafsky & Martin, the original papers (Zipf, Heaps)

Sources on BPE, WordPiece and tokenizer tools are at the end of the chapter that covers subword tokenization (Chapter 8).

Watch.

Textbooks.

Reference documentation and courses.

2.10 Exercises

The label on each exercise marks its level: Basic consolidates a concept, Applied makes you measure something on your own data, and Advanced goes past this chapter.

  1. Break the vectorizer. (Applied) Fit a CountVectorizer on ten documents from your own domain and print get_feature_names_out(). Find at least two tokens that are wrong — a destroyed identifier, a merged pair, a lost unit. If the problem comes from token boundaries, fix it with token_pattern; where needed, also adjust lowercasing, preprocessing or a custom tokenizer. Report which example each change fixes and which new errors it could introduce.
  2. Derive it by hand. (Basic) For the four-document corpus in this chapter, compute the TF-IDF vector for d3 with pen and paper, then verify against TfidfVectorizer. If they disagree, first compare the TF definition, the IDF formula, the L2 normalization and the token output. Check the column order, the corpus used and the rounding precision as well, and state where the difference comes from.
  3. Replicate and extend. (Applied) Reproduce the classification table above, then add one row: TF-IDF with min_df=5. Does accuracy fall? By how much did the feature count fall? Compare the two configurations on a validation portion split off from the training data, by accuracy, feature count, memory and processing time. Justify your choice to a colleague with those criteria, and use the final test set only after the choice is made.
  4. Find the negation failure. (Applied) Construct two documents from your own field with opposite operational meaning and cosine similarity above 0.9 under TF-IDF. Then write a design-review sentence explaining why it is not appropriate to conclude, from a high TF-IDF cosine alone, that the two documents express the same operational decision. Add that a classifier can use distinguishing terms such as not when they are kept.
  5. Zipf on your own data. (Basic) Plot rank against frequency on a log-log scale for a corpus you own. Does the line look straight? What are the top five tokens, and is any of them an artifact like 'ax?
  6. The interview exercise. (Advanced) Work through the five-document TF-IDF ranking problem in §8.2.1 of Chip Huyen’s book with pen and paper, including its follow-up: if one document mentions the query term three times instead of once, what happens to its rank, and is that a desirable property of TF-IDF? Before checking with the library, define explicitly the term set of the question, the mappings between word forms and the TF-IDF variant; say, for instance, how you map birds → bird, gets → get and loves → love. Then configure TfidfVectorizer to use the same vocabulary, preprocessing, IDF and normalization. In the follow-up, look at both the contribution of the repeated term to the numerator and the change in the normalization denominator. With the other variables fixed, BM25 brings the term-frequency contribution towards a finite limit; sublinear_tf slows its growth logarithmically but sets no finite ceiling. ::: {.callout-note collapse=“true”} ## Expected observations

Not solutions — but knowing what you are meant to see makes it easier to check yourself.

  1. The default token_pattern drops single-character tokens and punctuation, which is what splits identifiers (P-101, version numbers, code fragments).
  2. With the same definitions and enough precision, the hand computation should match the library within numerical tolerance. If there is a difference, check the TF and IDF definitions, the normalization, the tokens, the column order and the rounding.
  3. min_df=5 drops the terms that occur in fewer than five documents. Measure how much the feature count and the accuracy change, and report the share of token occurrences the dropped terms carried. Do not assume in advance that the loss in accuracy will be small.
  4. Adding a separate negation word can change a single column of the raw counts; L2 normalization then changes the other active values too. Negation expressed inside a word form can produce different term columns. Show on your own example that a high cosine can hide an opposite meaning.
  5. Part of the log-log plot may show an approximately linear trend, with deviations at the head and in the tail. Inspect the top five tokens and explain any artefacts that come from the corpus. Do not take visual resemblance alone as evidence of a power law.
  6. After increasing the number of repetitions of the term, recompute the score and the ranking. In a cosine both the dot product and the document norm change, so more repetitions do not always give a higher score or rank. Explain the result together with the TF-IDF variant and query vector you chose. :::

2.11 What to remember

If you can say the following eight points in your own words, you have the core of this chapter.

  1. Tokenization is a design decision about which units the model is shown.
  2. Normalization rules can merge some distinctions of spelling or encoding. Which distinctions to keep depends on the task and on the input the model in use expects.
  3. A fixed word-level vocabulary cannot cover every word form in new text; a form that is not in it stays out of the counts. Today’s language models get past that limit with units smaller than a word, learned from data (Section 8.3).
  4. Zipf describes the approximate empirical relation between word frequencies and their ranks, Heaps the one between the amount of text processed and the number of distinct terms observed. How well they fit depends on the corpus, the tokenization and the range measured.
  5. Bag-of-words represents a document by which terms occur and how often, and loses word order.
  6. Other things being equal, TF-IDF gives more weight to a term that is frequent in the document and found in few documents of the corpus.
  7. Cosine similarity compares the direction of vectors rather than document length; L2 normalization is what makes that geometry convenient.
  8. Bag-of-words is a fast, sparse, readable baseline that cannot directly represent order, the scope of negation, or semantic similarity.