Bag of words and TF-IDF

We have token ids and a way to measure a classifier. The task for this note is concrete: 120,000 news articles, four topics (World, Sports, Business, Sci/Tech), and a model that assigns a topic to an unseen article. A linear classifier needs a fixed-length vector per document, but documents have different lengths. The simplest way to get a fixed-length vector is to ignore order entirely and count.

Notation. $V$ is the vocabulary with $|V|$ entries, $D$ the training corpus with $|D|$ documents. $N(t, d)$ counts occurrences of token $t$ in document $d$; $\mathrm{df}(t) = |\{d \in D : t \in d\}|$ is the number of documents containing $t$. A document is represented by a vector $x_d \in \mathbb R^{|V|}$.

Baseline: counting tokens#

The bag of words representation sets

$$(x_d)_t = N(t, d) \qquad \text{for every } t \in V.$$

A document becomes a vector whose coordinate for each vocabulary entry is how many times that entry appears. Word order is discarded: “dog bites man” and “man bites dog” get the same vector. What survives is which tokens appear and how often, and for topic classification that is most of the signal: an article about a football match contains match, goal and coach whatever order the sentences come in.

Shapes make the cost visible. With the AG News vocabulary from the preprocessing note, $|V| = 29{,}350$, and the training matrix $X$ has shape $120{,}000 \times 29{,}350$. Stored densely that would be $3.5 \times 10^9$ entries; stored sparsely it is tiny, because an article of 40 distinct tokens has 40 non-zero coordinates out of 29,350. Everything in this note works on sparse matrices.

A linear classifier on counts#

Multinomial logistic regression maps the vector to one score per class and normalizes with a softmax:

$$z = W x_d + b, \qquad W \in \mathbb R^{K \times |V|},\; b \in \mathbb R^K, \qquad p(y = k \mid d) = \frac{e^{z_k}}{\sum_{j=1}^K e^{z_j}}.$$

Row $k$ of $W$ holds one weight per vocabulary entry; a positive weight for goal in the Sports row raises the Sports score whenever goal appears, in proportion to how often it appears. The model is trained by minimizing the cross-entropy of the true label under the predicted distribution, averaged over the corpus:

$$\mathcal L = -\frac{1}{|D|}\sum_{d \in D} \log p(y_d \mid d).$$

Why this loss, and how it relates to entropy and KL divergence, is derived in the Generative Models course; the n-gram note restates the four equivalent forms for the language-model case. For now: minimizing $\mathcal L$ maximizes the likelihood of the training labels.

Worked example#

Three one-line documents and a five-word vocabulary:

	cat	dog	sat	ran	fast
$d_1$ = “the cat sat”	1	0	1	0	0
$d_2$ = “the dog ran fast”	0	1	0	1	1
$d_3$ = “the cat ran fast fast”	1	0	0	1	2

the was removed as a stopword. $d_3$ has a 2 in the fast column because the token appears twice. A classifier that has to separate “animal” from “motion” articles can put positive weights on sat/cat/dog in one row and ran/fast in the other; $d_3$, which mixes both, gets a score that depends on the counts.

Where raw counts fail#

Two effects distort the count vectors.

Length. A long document has larger counts than a short one on the same topic, so its vector is longer and its scores $z = Wx$ are scaled up. The classifier’s confidence then measures length, not evidence.

Common tokens. After stopword removal, some tokens are still in most documents of a corpus: in a news corpus, said, year, new. Their counts are large, so they dominate the dot products $Wx$ while saying nothing about the topic. A token that appears in every document says nothing through its presence alone. Its count can still differ between classes (once per article in one topic, ten times in another), but such tokens usually carry little topical signal. IDF down-weights them by a fixed rule that ignores the labels; a trained classifier can also learn small weights for them.

TF-IDF: reweighting the counts#

Term frequency is the count, normalized by document length in some variants:

$$\mathrm{tf}(t, d) = \frac{N(t, d)}{\sum_{k \in V} N(k, d)}.$$

Inverse document frequency measures how rare a token is across documents:

$$\mathrm{idf}(t) = \log\frac{|D|}{\mathrm{df}(t)}.$$

A token in every document has $\mathrm{df}(t) = |D|$ and $\mathrm{idf} = \log 1 = 0$: it is switched off. A token in one document out of a thousand has $\mathrm{idf} = \log 1000 \approx 6.9$. The logarithm compresses the range so that a token in 1 % of documents is not 100 times more important than one in 100 %; it is $\log 100 \approx 4.6$ units more important. The product

$$\text{tf-idf}(t, d) = \mathrm{tf}(t, d)\cdot \mathrm{idf}(t)$$

is the new coordinate. The results below use the scikit-learn implementation, which differs in three details that matter when reproducing numbers: it uses the raw count $N(t, d)$ as tf; it smooths the idf as $\log\frac{1 + |D|}{1 + \mathrm{df}(t)} + 1$, as if one extra document contained every token, so that no weight is infinite, and the added 1 keeps a token found in every document at weight 1 instead of 0; and it rescales every document vector to unit Euclidean norm, which removes the length effect directly and makes dividing the counts by the length unnecessary.

Worked example, continued#

On the three documents above, $|D| = 3$. Document frequencies: cat 2, dog 1, sat 1, ran 2, fast 2. With the plain definition, $\mathrm{idf}(\text{cat}) = \ln(3/2) = 0.405$, $\mathrm{idf}(\text{dog}) = \ln 3 = 1.099$. For $d_3$ (five tokens including the, four after stopword removal):

Token	$N(t, d_3)$	$\mathrm{tf}$	$\mathrm{idf}$	tf-idf
cat	1	0.25	0.405	0.101
ran	1	0.25	0.405	0.101
fast	2	0.50	0.405	0.203

Had fast appeared in all three documents, its idf would be 0 and the largest count in the vector would contribute nothing. The weighting does what we asked: counts still matter, but only for tokens that discriminate between documents.

The whole method on the three documents, from counts to the classifier:

Figure

From counts through TF-IDF to a linear model

Results on AG News#

The pipeline is: fit the vectorizer on the training texts (vocabulary and idf), transform both splits, train logistic regression, measure accuracy.

Features	Vocabulary	Train acc.	Test acc.
TF-IDF, unigrams, min_df=4, max_df=0.95	29,350	0.940	0.918
TF-IDF, 1- to 3-grams, min_df=10, max_df=0.95	101,284	0.951	0.920

Two frequency cuts shape the vocabulary. min_df=4 drops tokens seen in fewer than four training documents, which are too rare to estimate a weight for and are mostly typos and names; max_df=0.95 drops tokens in more than 95 % of documents, which idf would nearly zero out anyway.

The second row adds n-grams: contiguous pairs and triples of tokens as extra vocabulary entries. This is the standard partial fix for the order problem: not done becomes a feature of its own, distinct from not and done. The price is vocabulary size. With $|V|$ unigrams there are up to $|V|^2$ bigrams, so the frequency cut has to be raised (min_df=10) to keep the matrix manageable, and the gain here is 0.2 points, within the sampling error of a 7,600-example test set: one standard error of an accuracy near 0.92 is $\sqrt{0.92 \cdot 0.08 / 7600} \approx 0.003$, or 0.3 points. On this corpus, topic is carried by individual tokens and bigrams add little.

The 2–3 point gap between train and test accuracy is mild overfitting: with 29,350 weights per class and 120,000 documents, the model can memorize some training-specific tokens.

What changed#

	Bag of words	TF-IDF
Coordinate	$N(t, d)$	$\mathrm{tf}(t,d)\cdot\mathrm{idf}(t)$, vector normalized
Common tokens	Dominate	Down-weighted to ~0
Document length	Scales the vector	Removed by normalization
Word order	Ignored	Ignored (n-grams recover adjacent pairs)
Cost	One sparse matrix	Same, plus one pass for idf

The representation is still a sparse count vector; what changed is the weighting, and that alone makes a linear model competitive. The 0.92 test accuracy is the number to remember: in the CNN note, convolutional networks over word embeddings reach 0.90–0.91, below this baseline, and only a fine-tuned pretrained Transformer clearly exceeds it in the transfer learning note.

Limitations#

• No order beyond n-grams. “The film was not bad, it was great” and “the film was not great, it was bad” share most unigrams and bigrams.
• No similarity between tokens. cat and dog are orthogonal coordinates; weight learned for one says nothing about the other. Every token must be seen often enough in training to get its own weight. The embeddings note is the response to this.
• Open vocabulary. A token absent from the training set has no coordinate and is silently dropped at test time.
• Dimensionality. $|V|$ coordinates per document, and $|V|^2$ with bigrams; the representation does not compress.
• Topic, not meaning. The method works where the label is predictable from which words occur. It cannot answer a question, translate, or tell who did what to whom.

What you should remember#

• Bag of words: a document is the vector of its token counts. Order is discarded; the matrix is sparse.
• A linear classifier on these counts, trained with cross-entropy, is a strong baseline for topic classification.
• TF-IDF multiplies each count by $\log(|D|/\mathrm{df}(t))$, switching off tokens that occur everywhere, and normalizes the vector to cancel length.
• Fit the vocabulary and idf on training data only.
• AG News: 0.918 test accuracy with unigrams, 0.920 with 1- to 3-grams. Neural models in the next notes must beat 0.92 to justify their cost.

Notebook#

week01_word_embeddings.ipynb. Cell numbers count every cell, markdown included, from 1. Quoted numbers come from the run saved with the course; cells changed since then for current library versions have no saved output.

• Cells 33–36 load AG News (120,000 train, 7,600 test, tab-separated text and label columns); cell 38 plots the balanced class histogram.
• Cells 42–43 state the tf and idf formulas used above.
• Cells 44–48 fit TfidfVectorizer(min_df=4, max_df=0.95) on the training texts, transform both splits (the training matrix has shape (120000, 29350)), train LogisticRegression(max_iter=500), and print 0.94 train and 0.918 test accuracy.
• Cells 49–52 repeat with ngram_range=(1, 3) and min_df=10: 0.951 train, 0.92 test. The notebook does not print the size of this vocabulary; 101,284 comes from fitting the same vectorizer separately.

Next#

Counting tokens answers “what is this document about”. It cannot answer “what comes next”, which is the question behind every generative model in the course. The next note keeps the counting approach but counts short sequences of tokens, which gives the first language model, a way to generate text, and the metric (perplexity) that every later language model is measured by.

References#

• K. Spärck Jones. A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28(1), 1972. The idf weighting.
• C. D. Manning, P. Raghavan, H. Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. §6.2 (tf-idf) and §13 (text classification).
• D. Jurafsky, J. H. Martin. Speech and Language Processing, 3rd ed. draft. Chapter 5 (logistic regression for text).
• scikit-learn developers. TfidfVectorizer and Feature extraction, §6.2.3.4. The smoothed idf and the L2 normalization used in the notebook.
• X. Zhang, J. Zhao, Y. LeCun. Character-level Convolutional Networks for Text Classification. NeurIPS, 2015. The AG News benchmark; Table 4 reports bag-of-words and TF-IDF baselines in the same range as above.