E2.1 Bag-of-Words

The simplest way to turn a document into a vector, and still one of the most used: count the words. Each word of the vocabulary becomes a column, each document becomes a row, and the cell holds how many times that word occurs in that document. Nothing is learned except the vocabulary; there is no model and no training. The overview showed how text is cut into tokens; this page builds the count matrix from those tokens, by hand and with scikit-learn, measures how sparse it gets, and shows what it throws away. The next page reweights the same counts.

Every number below comes from running the code next to it; the figures are produced by short Python scripts that sit next to this page.

How this lesson is organized

The lesson has two approaches. Each has slides, text and a lab to do in class; the quiz at the end covers the fundamental one. Start with the fundamental approach: the advanced one builds on it.

Both labs use the same lab notebook (download it and open it in Jupyter or Colab, File → Upload notebook): the fundamental part runs from step 1 to 5, the advanced part steps 6 and 7. It uses only scikit-learn and runs in well under a minute.

Fundamental approach

One question drives this part: how does a document become a row of numbers, and how do you tell whether two rows are alike? The answer is counting: one column per word, one row per document, and the cosine of the angle between two rows. Everything is done first by hand, on three short sentences, and then checked against scikit-learn.

This part follows one path in three stages, drawn below: 1. count the words, turning each document into a row of counts; 2. compare two bags with the cosine; 3. what the bag loses, word order, and how bigrams buy part of it back. Each stage links to its section, and in the slides a strip at the bottom shows which stage you are in.

Fundamental approach slides

Click the slides and use the ← → arrows to navigate; F opens full screen and Esc shows every slide. Open the slides in a new tab

1. Counts, by hand

Stage 1. Three short documents, the same as in the overview (English glosses in the comments):

from sklearn.feature_extraction.text import CountVectorizer

docs = ["O gato comeu o peixe.",                 # the cat ate the fish
        "O cachorro comeu a ração do gato.",     # the dog ate the cat's food
        "Gato dorme, gato sonha."]               # cat sleeps, cat dreams
analyzer = CountVectorizer().build_analyzer()
for d in docs:
    print(analyzer(d))

['gato', 'comeu', 'peixe']
['cachorro', 'comeu', 'ração', 'do', 'gato']
['gato', 'dorme', 'gato', 'sonha']

The vocabulary is the set of distinct tokens, sorted alphabetically: cachorro, comeu, do, dorme, gato, peixe, ração, sonha, 8 words. Each document becomes a vector of 8 counts:

By hand: d1 has a 1 under comeu, gato and peixe; d2 a 1 under its five words; d3 a 2 under gato and a 1 under dorme and sonha.

CountVectorizer builds the same matrix:

import numpy as np
import pandas as pd

bow = CountVectorizer()
X = bow.fit_transform(docs)
print(pd.DataFrame(X.toarray(), columns=bow.get_feature_names_out(), index=['d1', 'd2', 'd3']))
print(type(X).__name__, X.shape, 'non-zeros:', X.nnz)
print(bow.vocabulary_)

    cachorro  comeu  do  dorme  gato  peixe  ração  sonha
d1         0      1   0      0     1      1      0      0
d2         1      1   1      0     1      0      1      0
d3         0      0   0      1     2      0      0      1
csr_matrix (3, 8) non-zeros: 11
{'gato': 4, 'comeu': 1, 'peixe': 5, 'cachorro': 0, 'ração': 6, 'do': 2, 'dorme': 3, 'sonha': 7}

vocabulary_ is the dictionary from word to column that fit learned. The name "bag" is literal: pour the words of a document into a bag, shake it, and only the counts survive. The phrase is old; Harris (1954) already argued that "language is not merely a bag of words", and information retrieval has represented documents this way since the 1960s. Salton, Wong & Yang (1975) made the geometric view explicit: documents are points in a space with one axis per word, and similar documents are nearby points.

fit learns the vocabulary, transform only applies it

Like the scalers and encoders of Preprocessing, a vectorizer is a fitted step. fit fixes the vocabulary; transform counts only the words that are in it:

new = bow.transform(["O gato comeu o gato.",       # the cat ate the cat
                     "O cachorro latiu.",          # the dog barked
                     "Um felino adormeceu."])      # a feline fell asleep
print(new.toarray())

[[0 1 0 0 2 0 0 0]
 [1 0 0 0 0 0 0 0]
 [0 0 0 0 0 0 0 0]]

"latiu" (barked) has no column and is silently dropped; "um felino adormeceu" (a feline fell asleep) is made only of unseen words and becomes the zero vector. When you split data into training and test sets, fit the vectorizer on the training documents only, exactly as you would a scaler: words that exist only in the test set must not shape the columns.

2. Counts or presence: binary=True

Sometimes the fact that a word occurs matters more than how often. binary=True replaces every count by 1:

print(CountVectorizer(binary=True).fit_transform(docs).toarray())

[[0 1 0 0 1 1 0 0]
 [1 1 1 0 1 0 1 0]
 [0 0 0 1 1 0 0 1]]

d3's 2 under gato became 1. For short texts (titles, tweets, search queries), where a word rarely repeats, the two versions are almost identical. For long documents, counts let a single word that a post repeats many times dominate its vector; the lab measures which version finds similar posts better.

3. Comparing two bags

Stage 2. Once documents are vectors, "how similar are these two documents?" becomes geometry. For text, the standard measure is the cosine of the angle between the two vectors:

For counts it goes from 0 (no word in common) to 1 (the same words in the same proportions). By hand, with the table above: d1 and d2 share comeu and gato, so \(x_1 \cdot x_2 = 1 + 1 = 2\); \(\lVert x_1 \rVert = \sqrt{3}\) and \(\lVert x_2 \rVert = \sqrt{5}\), hence \(\cos = 2 / \sqrt{15} = 0.516\). d1 and d3 share only gato, with count 2 in d3: \(\cos = 2 / (\sqrt{3}\sqrt{6}) = 0.471\).

from sklearn.metrics.pairwise import cosine_similarity

print(pd.DataFrame(cosine_similarity(X), index=['d1', 'd2', 'd3'], columns=['d1', 'd2', 'd3']).round(3))

       d1     d2     d3
d1  1.000  0.516  0.471
d2  0.516  1.000  0.365
d3  0.471  0.365  1.000

The simulator redoes both hand computations of this page, one click at a time: each of the 12 tokens adds one to its cell of the count matrix, and then each pair of documents is compared by the cosine, with the dot product and the two lengths in view. It reproduces the table of section 1 and the three cosines above (0.516, 0.471 and 0.365). Before stepping, predict which pair will be the most similar.

Why the angle and not the ordinary (Euclidean) distance? Because the length of a document is not what it is about. Paste d1 twice and compare the result with d1:

C2 = bow.transform(["O gato comeu o peixe.",
                    "O gato comeu o peixe. O gato comeu o peixe."]).toarray()
print(C2)
print(f"euclidean distance {np.linalg.norm(C2[0] - C2[1]):.3f} · cosine similarity {cosine_similarity(C2)[0, 1]:.3f}")

[[0 1 0 0 1 1 0 0]
 [0 2 0 0 2 2 0 0]]
euclidean distance 1.732 · cosine similarity 1.000

The two texts say the same thing. The Euclidean distance, \(\sqrt{3} = 1.732\), grows with the difference in length; the cosine looks only at the direction and reports 1. This is why nearest-neighbor search and clustering on text use metric='cosine', or first divide each row by its length (which the TF-IDF vectorizer does by default).

4. Word order is lost

Stage 3. The bag keeps which words occur, not where. Two sentences with opposite meanings:

pair = ["O cachorro mordeu o homem.",        # the dog bit the man
        "O homem mordeu o cachorro."]        # the man bit the dog
for ngrams in [(1, 1), (1, 2)]:
    cv = CountVectorizer(ngram_range=ngrams)
    P = cv.fit_transform(pair)
    print(ngrams, list(cv.get_feature_names_out()))
    print('   ', P.toarray().tolist(), f" cosine {cosine_similarity(P)[0, 1]:.2f}")

(1, 1) ['cachorro', 'homem', 'mordeu']
    [[1, 1, 1], [1, 1, 1]]  cosine 1.00
(1, 2) ['cachorro', 'cachorro mordeu', 'homem', 'homem mordeu', 'mordeu', 'mordeu cachorro', 'mordeu homem']
    [[1, 1, 1, 0, 1, 0, 1], [1, 0, 1, 1, 1, 1, 0]]  cosine 0.60

With single words the two sentences are the same vector: who bit whom is gone. Adding bigrams (pairs of neighboring tokens, ngram_range=(1, 2)) buys back local order: "cachorro mordeu" and "mordeu homem" belong to the first sentence only, "homem mordeu" and "mordeu cachorro" to the second, and the cosine falls to 0.60. The price is more columns, most of them rare. Note also that the bigram joins tokens that are neighbors after tokenization: the article "o" was dropped, so "mordeu o homem" gave "mordeu homem".

Bigrams are not the only n-grams: the advanced approach cuts words into pieces of letters, which catches plurals and typos.

Simulator: build the bag yourself

Type one document per line and watch the vocabulary and the count matrix update. The rules are scikit-learn's: lowercase, tokens of two or more letters or digits, stop words removed before the bigrams. The presets reproduce the examples of this page.

Things to try:

• word order: the first two sentences get identical vectors (the simulator flags "d1 = d2"). Tick add bigrams and they separate;
• sábado/sábados: three sentences about the same thing, and the singular, plural and capitalized forms of the same words land in different columns once you untick lowercase;
• binary: in the lesson preset, only d3 changes (gato 2 → 1).

5. Summary: the bag in five lines

1. A document becomes its word counts: one column per vocabulary word, one row per document, and the order of the words is thrown away.
2. fit fixes the vocabulary; transform only applies it: unseen words are dropped silently, so the vectorizer is fitted on the training documents only.
3. Counts or presence: binary=True keeps only whether a word occurs, which matters for long documents.
4. Compare with the cosine: the angle between two rows; the length of a document is not its subject.
5. Order is lost: "the dog bit the man" and "the man bit the dog" are the same vector; bigrams buy back local order, at the price of many more columns.

Fundamental lab — bag-of-words on real posts

Four newsgroups of the 20 Newsgroups collection (computer graphics, baseball, electronics and Christianity), about 2,100 posts. The lab builds the count matrix, looks at what it contains, and measures how each choice (stop words, min_df, binary, bigrams, character n-grams) changes the answer to one question: are the most similar posts about the same subject? It uses only scikit-learn and runs in well under a minute.

This part loads the posts, builds the count matrix, reads it and compares counts, presence and stop words; n-grams and shuffled words are left to the advanced lab.

Step 1 — load the posts

Predict. Posts from four newsgroups: do you expect the four groups to have similar sizes? And how long is a typical post: a sentence, a paragraph or a page?

import numpy as np
import pandas as pd
from sklearn.datasets import fetch_20newsgroups

cats = ['comp.graphics', 'rec.sport.baseball', 'sci.electronics', 'soc.religion.christian']
raw = fetch_20newsgroups(subset='train', categories=cats,
                         remove=('headers', 'footers', 'quotes'), random_state=0)
keep = [i for i, t in enumerate(raw.data) if len(t.split()) >= 20]   # drop empty/very short posts
docs = [raw.data[i] for i in keep]
y = raw.target[keep]
names = np.array(raw.target_names)

print(f"{len(raw.data)} posts downloaded, {len(docs)} kept")
print(pd.Series(names[y]).value_counts().sort_index())
print(f"words per post: median {np.median([len(d.split()) for d in docs]):.0f}")
print(' '.join(docs[0].split())[:160])

2371 posts downloaded, 2116 kept
comp.graphics             521
rec.sport.baseball        495
sci.electronics           535
soc.religion.christian    565
Name: count, dtype: int64
words per post: median 97
Their phone number is 1-800-377-9777. The last catalog shows three Oaks jerseys: 36 Home, 42 Home, 39 Home - they're each $165.00. All their merchandise is hand

Of the 2,371 posts, 2,116 have at least 20 words once headers, signatures and quoted replies are removed; many of the others are empty. The four groups are balanced (495 to 565 posts) and a median post has 97 words. Removing the headers matters: they carry e-mail addresses and organizations, and anything that compares posts could match the senders instead of the subject. The first post, about baseball jerseys, shows what a document looks like: informal, with numbers and prices.

Step 2 — the count matrix

Predict. The vocabulary of 2,116 posts will have tens of thousands of words. What share of the cells do you expect to be zero? Which words will top the frequency list?

from sklearn.feature_extraction.text import CountVectorizer

counts = CountVectorizer()
C = counts.fit_transform(docs)
vocab = counts.get_feature_names_out()
freq = np.asarray(C.sum(axis=0)).ravel()

print(C.shape, f"{1 - C.nnz / (C.shape[0] * C.shape[1]):.2%} zeros")
print(f"distinct words per post (median): {np.median(np.diff(C.indptr)):.0f}")
print('10 most frequent words:', list(vocab[np.argsort(-freq)[:10]]))
print(f"words seen only once: {(freq == 1).mean():.0%} of the vocabulary")

(2116, 25715) 99.62% zeros
distinct words per post (median): 67
10 most frequent words: ['the', 'to', 'of', 'and', 'is', 'in', 'that', 'it', 'for', 'you']
words seen only once: 45% of the vocabulary

How to read it:

• 2,116 posts × 25,715 words, 99.62% zeros: a median post uses 67 distinct words out of 25,715.
• The ten most frequent words are all function words: "the", "to", "of" are in almost every post and say nothing about the subject.
• 45% of the vocabulary appears once in the whole corpus: the long tail of names, numbers, typos and rare words that Zipf's law predicts (overview).

Step 3 — what each newsgroup talks about

Predict. Sum the rows of each newsgroup, with the English stop words removed. Will the top words name the subject? Which non-topical words could survive the stop list?

cv_stop = CountVectorizer(stop_words='english')
S = cv_stop.fit_transform(docs)
words = cv_stop.get_feature_names_out()
for c in range(4):
    total = np.asarray(S[y == c].sum(axis=0)).ravel()      # add up the rows of one group
    print(f"{names[c]:24s}", list(words[np.argsort(-total)[:8]]))

comp.graphics            ['image', 'graphics', 'edu', 'jpeg', 'file', 'use', 'data', 'files']
rec.sport.baseball       ['year', 'game', 'good', 'team', 'think', 'don', '00', 'just']
sci.electronics          ['use', 'like', 'power', 'don', 'wire', 'ground', 'used', 'know']
soc.religion.christian   ['god', 'jesus', 'people', 'church', 'think', 'does', 'know', 'believe']

Once the English stop words are removed, summing the rows of each group gives a readable portrait of it: image, graphics, jpeg, file for graphics; game, team, year for baseball; power, wire, ground for electronics; god, jesus, church, believe for Christianity. The bag-of-words does carry the subject. It also carries noise that a stop list does not catch: "don" (what the tokenizer leaves of "don't"), "think", "just", "use", "edu" (from e-mail addresses) and "00" (from baseball statistics) are frequent in some groups without being about anything.

Step 4 — shrinking the vocabulary

Predict. A stop list, min_df=2 and max_df=0.5 all shrink the vocabulary. Which one removes the most columns? Which one removes the most frequent words?

for params in [{}, {'stop_words': 'english'}, {'min_df': 2}, {'stop_words': 'english', 'min_df': 2},
               {'max_df': 0.5}]:
    cv = CountVectorizer(**params).fit(docs)
    print(f"{str(params):42s} {len(cv.vocabulary_):6d} columns")

cv_half = CountVectorizer(max_df=0.5).fit(docs)
print('dropped by max_df=0.5:', sorted(set(vocab) - set(cv_half.vocabulary_)))

{}                                          25715 columns
{'stop_words': 'english'}                   25411 columns
{'min_df': 2}                               12297 columns
{'stop_words': 'english', 'min_df': 2}      12001 columns
{'max_df': 0.5}                             25703 columns
dropped by max_df=0.5: ['and', 'be', 'for', 'have', 'in', 'is', 'it', 'of', 'that', 'the', 'this', 'to']

The knobs act on opposite ends of the frequency scale:

• the stop list removes only 304 columns (25,715 → 25,411), but they are the most frequent words;
• min_df=2 removes more than half of the vocabulary (→ 12,297): words present in a single post, which cannot help compare two posts;
• max_df=0.5 drops the words present in more than half of the posts. Here that is only 12 words, all of them function words ("and", "the", "of", ...): a stop list learned from the data itself, without choosing a language.

Step 5 — comparing posts: counts, presence, stop words

Predict. Raw counts, presence, stop words removed: which representation will find neighbors from the same newsgroup most often? Will presence help more with or without the stop words?

from sklearn.neighbors import NearestNeighbors

def agreement(V, k=5):
    """Share of each post's k nearest posts (cosine) that come from the same newsgroup."""
    nn = NearestNeighbors(n_neighbors=k + 1, metric='cosine').fit(V)
    _, idx = nn.kneighbors(V)
    return (y[idx[:, 1:]] == y[:, None]).mean()

print(f"chance level: {np.sum(np.bincount(y) ** 2) / len(y) ** 2:.3f}")
for params in [{}, {'binary': True}, {'stop_words': 'english'}, {'stop_words': 'english', 'binary': True}]:
    V = CountVectorizer(**params).fit_transform(docs)
    print(f"{str(params):42s} agreement {agreement(V):.3f}")

chance level: 0.251
{}                                         agreement 0.490
{'binary': True}                           agreement 0.650
{'stop_words': 'english'}                  agreement 0.793
{'stop_words': 'english', 'binary': True}  agreement 0.768

A way to score a representation without training any model: for every post, find its 5 nearest posts by cosine and count how many come from the same newsgroup. Picking neighbors at random would give 0.251 (the chance that two random posts share a group).

• Raw counts: 0.490. Posts are "near" when they use the, to, of in similar proportions, which has little to do with the subject.
• binary=True: 0.650. Presence limits how much a repeated function word can weigh, and the score jumps.
• Stop words removed: 0.793. Removing the function words helps most. With them gone, counts (0.793) are slightly better than presence (0.768): once the words that remain are about something, repeating them is informative.

The TF-IDF page goes further, weighing every word by how many posts contain it instead of removing a fixed list.

Simulation: a stop list learned from the data. Step 4 showed that max_df=0.5 drops 12 function words without choosing a language. Lower the threshold (max_df 0.5, 0.2 and 0.1) and measure the neighbor agreement of the raw counts each time; compare with the English stop list. Can a threshold learned from the posts do as well as a list written by hand?

for params in [{'max_df': 0.5}, {'max_df': 0.2}, {'max_df': 0.1}, {'stop_words': 'english'}]:
    cv = CountVectorizer(**params).fit(docs)
    print(f"{str(params):26s} {len(vocab) - len(cv.vocabulary_):4d} words dropped · agreement {agreement(cv.transform(docs)):.3f}")

{'max_df': 0.5}              12 words dropped · agreement 0.617
{'max_df': 0.2}              57 words dropped · agreement 0.767
{'max_df': 0.1}             124 words dropped · agreement 0.814
{'stop_words': 'english'}   304 words dropped · agreement 0.793

To close the fundamental part. In one sentence each: (1) why is a vectorizer fitted on the training documents only? (2) Why is the cosine, and not the Euclidean distance, the default way to compare two bags? (3) How can two sentences with opposite meanings get cosine 1, and what partly fixes it?

Your turn (fundamental)

At home:

1. Most similar posts. Pick a post, compute cosine_similarity(V[i], V) with the best representation of step 5, and print the three most similar posts with their newsgroup. Do the same with raw counts. Which words make the raw-count neighbors "similar"?
2. Your own stop list. Add the words of step 4's max_df=0.5 list and the most frequent non-topical words of step 3 ("don", "just", "think") to scikit-learn's English list, and rerun step 5. Does the agreement go up?
3. Portuguese. Write five short sentences in Portuguese about two different subjects, and build their bag with and without the tiny stop list of the overview. Which words does the default tokenizer drop before any stop list is applied?

Advanced approach

The fundamental part built the count matrix of three sentences and compared its rows. This part changes what is counted (pieces of words instead of words), looks at the count matrix of a real corpus (almost all zeros, and stored that way), and reads what raw counts consider important, which is the problem the TF-IDF page solves. The code blocks continue those of sections 1 to 4.

This part follows one path in three stages, drawn below: 1. pieces of words; 2. a real corpus; 3. what raw counts put first. Each stage links to its section, and in the slides a strip at the bottom shows which stage you are in.

Advanced approach slides

Click the slides and use the ← → arrows to navigate; F opens full screen and Esc shows every slide. Open the slides in a new tab

6. Character n-grams

Stage 1. The bigrams of section 4 are made of words; n-grams can also be taken over characters. analyzer='char_wb' cuts each word, padded with spaces, into overlapping pieces of a few letters. Two forms of the same word, which are unrelated columns for a word-level bag, now share most of their pieces:

for pair in [("sábado", "sábados"), ("gato", "gatos"), ("gato", "pato")]:
    cv = CountVectorizer(analyzer='char_wb', ngram_range=(3, 3))
    P = cv.fit_transform(pair)
    shared = sorted(set(cv.build_analyzer()(pair[0])) & set(cv.build_analyzer()(pair[1])))
    print(f"{pair[0]:7s} / {pair[1]:8s} cosine {cosine_similarity(P)[0, 1]:.2f}   shared trigrams: {shared}")

sábado  / sábados  cosine 0.77   shared trigrams: [' sá', 'ado', 'bad', 'sáb', 'ába']
gato    / gatos    cosine 0.67   shared trigrams: [' ga', 'ato', 'gat']
gato    / pato     cosine 0.50   shared trigrams: ['ato', 'to ']

"sábado" and "sábados" now have cosine 0.77, with no stemmer. Character n-grams tolerate plurals, conjugations and typos, which helps with short, noisy texts. The last row shows the cost: "gato" (cat) and "pato" (duck) also get 0.50, because they share spelling, not meaning.

7. Sparsity

Stage 2. The three documents filled 11 of 24 cells. A real corpus: the training part of 20 Newsgroups (Lang, 1995), 11,314 posts from 20 Usenet discussion groups, with headers, signatures and quoted replies removed:

from sklearn.datasets import fetch_20newsgroups

news = fetch_20newsgroups(subset='train', remove=('headers', 'footers', 'quotes'))
Xn = CountVectorizer().fit_transform(news.data)
cells = Xn.shape[0] * Xn.shape[1]
print(Xn.shape, f"non-zeros: {Xn.nnz:,}  ->  {1 - Xn.nnz / cells:.2%} zeros")
print(f"distinct words per post (median): {np.median(np.diff(Xn.indptr)):.0f}")
print(f"memory as a dense float64 array: {cells * 8 / 1e9:.1f} GB")
print(f"memory as a sparse CSR matrix:   {(Xn.data.nbytes + Xn.indices.nbytes + Xn.indptr.nbytes) / 1e6:.1f} MB")

(11314, 101631) non-zeros: 1,103,627  ->  99.90% zeros
distinct words per post (median): 61
memory as a dense float64 array: 9.2 GB
memory as a sparse CSR matrix:   13.3 MB

A typical post uses 61 of the 101,631 columns. Stored as an ordinary array, the matrix would take 9.2 GB; scikit-learn returns it in CSR (compressed sparse row) format, which keeps only the non-zero values and their column positions: 13.3 MB, about 700 times less. This is why vectorizers return sparse matrices, and why .toarray() is for toy examples only.

(figure script)

The right panel is the price of n-grams on the whole corpus: bigrams multiply the columns by 9, trigrams by 25, while each post fills only a few hundred of them. Most word pairs occur once in the whole corpus. min_df=2 (keep only terms present in at least 2 documents) or max_features keep the size under control.

8. What raw counts put first

Stage 3. Sum each column and sort: which words does a bag-of-words consider most important?

for params in [{}, {'stop_words': 'english'}]:
    cv = CountVectorizer(**params)
    Xc = cv.fit_transform(news.data)
    freq = np.asarray(Xc.sum(axis=0)).ravel()
    top = np.argsort(-freq)[:8]
    print(params, list(cv.get_feature_names_out()[top]))
    print(f"    '{cv.get_feature_names_out()[top[0]]}' occurs {freq[top[0]]:,} times, in {(Xc[:, top[0]] > 0).sum():,} posts")

{} ['the', 'ax', 'to', 'of', 'and', 'in', 'is', 'that']
    'the' occurs 106,381 times, in 9,475 posts
{'stop_words': 'english'} ['ax', 'max', 'people', 'like', 'don', 'just', 'know', 'use']
    'ax' occurs 62,387 times, in 20 posts

(figure script)

Two lessons in one figure. On the left, the columns with the largest counts are the, to, of, and: words present in almost every post ("the" in 9,475 of 11,314), which say nothing about the subject. An English stop list removes them. On the right, the new leader is "ax": 62,387 occurrences, in only 20 posts. Those posts contain binary files pasted as text, where "ax" repeats thousands of times. Raw counts let one strange document dominate the whole column. Both problems have the same cure, which is the subject of the next page: weigh each word by how many documents contain it, not only by how often it occurs.

Advanced lab — what the bag cannot see

The fundamental lab compared counts, presence and stop words with one measure, the neighbor agreement. This part measures what n-grams of words and of characters add, and shows what the bag cannot see at all. Continue in the same notebook, in the same session: the steps below use docs, y, counts, vocab and agreement from steps 1 to 5.

Step 6 — n-grams of words and of characters

Predict. Bigrams double the columns; character n-grams of 3 to 5 letters multiply them by eight. Will either find better neighbors than single words?

for params in [{'stop_words': 'english', 'min_df': 2},
               {'stop_words': 'english', 'min_df': 2, 'ngram_range': (1, 2)},
               {'analyzer': 'char_wb', 'ngram_range': (3, 5), 'min_df': 2}]:
    V = CountVectorizer(**params).fit_transform(docs)
    print(f"{str(params):70s} {V.shape[1]:6d} columns · agreement {agreement(V):.3f}")

{'stop_words': 'english', 'min_df': 2}                                  12001 columns · agreement 0.793
{'stop_words': 'english', 'min_df': 2, 'ngram_range': (1, 2)}           25184 columns · agreement 0.793
{'analyzer': 'char_wb', 'ngram_range': (3, 5), 'min_df': 2}             94920 columns · agreement 0.529

Bigrams double the vocabulary (12,001 → 25,184 columns) and do not change the agreement (0.793 both ways): telling baseball from electronics is a matter of vocabulary, which single words already capture. Character n-grams of 3 to 5 letters give 94,920 columns and a worse agreement (0.529): their pieces are shared by words of every subject, and they include the pieces of the function words that the stop list had removed. They pay off elsewhere: short and noisy texts, typos, languages with rich morphology.

Simulation: how rare are n-grams? Without min_df, build the vocabulary with ngram_range (1, 1), (1, 2) and (1, 3). For each, count the columns and the share of them that occur in a single post. Where do the extra columns of the n-grams come from?

for ngrams in [(1, 1), (1, 2), (1, 3)]:
    V = CountVectorizer(ngram_range=ngrams).fit_transform(docs)
    df = np.diff(V.tocsc().indptr)                       # in how many posts each column appears
    print(f"{str(ngrams):7s} {V.shape[1]:9,d} columns · {(df == 1).mean():.0%} of them in a single post"
          f" · a median post fills {np.median(np.diff(V.indptr)):.0f}")

(1, 1)     25,715 columns · 52% of them in a single post · a median post fills 67
(1, 2)    218,676 columns · 77% of them in a single post · a median post fills 154
(1, 3)    535,837 columns · 86% of them in a single post · a median post fills 240

Step 7 — the bag cannot tell a post from its shuffled words

Predict. Shuffle the words of a post at random. How much does its count vector change?

rng = np.random.default_rng(0)
analyzer = counts.build_analyzer()
shuffled = [' '.join(rng.permutation(analyzer(d))) for d in docs[:3]]
print(shuffled[0][:120])

A = counts.transform(docs[:3])
B = counts.transform(shuffled)
print('same count vectors:', (A != B).nnz == 0)

42 couple merchandise last wool 165 on 800 if call shows number also replica home jackets three even and they 39 afford
same count vectors: True

The first post with its words shuffled is unreadable, and its count vector is exactly the same as the original's, as are those of the next two posts: (A != B).nnz == 0 checks that no cell differs. Everything a bag-of-words knows about a document survives a random shuffle of its words.

To close the lesson. In one sentence each: (1) why do character n-grams bring "sábados" close to "sábado", and "pato" close to "gato"? (2) Why must a count matrix be stored in a sparse format? (3) Which two problems of raw counts does the next page solve with one rule?

Your turn (advanced)

At home, with more time:

1. Shuffled with bigrams. Repeat step 7 with CountVectorizer(ngram_range=(1, 2)). Are the vectors still the same? Why?

2. Characters for short texts. Keep only the first 20 words of each post (' '.join(d.split()[:20])) and redo step 6. On short texts, do character n-grams catch up with words?

Exercises

1. By hand, compute the cosine between d2 and d3 of the table above, and check the value 0.365.
2. Add the document "O peixe dorme." to the three of the lesson. How many columns does the vocabulary have now? Write the new row by hand, then check with CountVectorizer.
3. A post of 300 words and a post of 30 words are about the same subject. Why can their Euclidean distance be large while their cosine is high? What changes if you use binary=True?
4. With ngram_range=(1, 3), how many columns do the three documents of the lesson produce? Count by hand first.

Class materials

References

• Harris, Z. S. "Distributional Structure." Word 10, no. 2–3 (1954): 146–162 — where "language is not merely a bag of words" appears. DOI
• Salton, G.; Wong, A.; Yang, C. S. "A Vector Space Model for Automatic Indexing." Communications of the ACM 18, no. 11 (1975): 613–620 — documents as vectors, one axis per term. DOI
• Lang, K. "NewsWeeder: Learning to Filter Netnews." Proceedings of ICML (1995): 331–339 — the origin of the 20 Newsgroups collection. DOI
• Manning, C. D.; Raghavan, P.; Schütze, H. Introduction to Information Retrieval. Cambridge University Press (2008) — chapter 2 (tokens and terms) and chapter 6 (the vector space model). Full text

Quiz

The quiz covers the fundamental approach.