Bag of words

Intuition

A model wants a fixed-length vector of numbers. A document is a variable-length sequence of symbols. The bag-of-words representation resolves that mismatch in the bluntest way available: pick a vocabulary, give every word a column, and fill each cell with how many times that word occurs [2, §8.2.3.1].

What survives is a tally. What does not survive is order — and order is where a great deal of meaning lives [1, §6.2]. That sounds fatal, and it is not, because for many tasks the tally is enough [2, §8.2.3.7]. Whether a review is positive, which of twenty categories an article belongs to, whether two documents are about the same thing: these are largely questions about which words are present, and the words are still all there.

The representation is worth understanding precisely because it is the floor. Everything later in natural language processing is an answer to something this throws away, so knowing exactly what it throws away tells you what the rest of the field is for.

Formal definition

The name comes from information retrieval, where it describes what is left of a document once you keep only its term weights. Those weights "may be viewed as a quantitative digest of that document. In this view of a document, known in the literature as the bag of words model, the exact ordering of the terms in a document is ignored but the number of occurrences of each term is material" [1, §6.2].

The consequence is stated as bluntly as it deserves: the document "Mary is quicker than John" is, in this view, identical to the document "John is quicker than Mary" [1, §6.2]. Two sentences, opposite claims, one vector.

The same idea has a second, sharper statement as a probabilistic assumption. In text classification it appears as positional independence: the conditional probability of a term is the same regardless of where in the document it occurs. The textbook makes the identity explicit — "positional independence is equivalent to adopting the bag of words model" [1, §13.4].

That framing is the more useful one, because it says what is being assumed rather than what is being deleted, and it comes with an honest admission: "in reality, the conditional independence assumption does not hold for text data. Terms are conditionally dependent on each other" [1, §13.4]. The model is known to be wrong. It is used because the alternative is estimating a number of parameters exponential in the vocabulary size [1, §13.4].

In implementation terms the pipeline is three steps — "tokenizing strings and giving an integer id for each possible token", "counting the occurrences of tokens in each document", and "normalizing and weighting"; that strategy "is called the Bag of Words or 'Bag of n-grams' representation" [2, §8.2.3.1].

How it works

The matrix is enormous and almost entirely empty. A collection of 10,000 short documents "will use a vocabulary with a size in the order of 100,000 unique words in total while each document will use 100 to 1000 unique words individually", so "the resulting matrix will have many feature values that are zeros (typically more than 99% of them)" [2, §8.2.3.2]. Storing it densely is not an option; sparse storage is not an optimisation here but the only way the representation exists at all.

The standard repair for lost order is to widen the unit. Count adjacent pairs as well as single words — the "bag of n-grams" of the same reference [2, §8.2.3.1] — and Mary is quicker becomes a feature in its own right. This works, and it is why the phrase appears in the name. It also multiplies the vocabulary, which was already the expensive part, and it only ever recovers order locally: a bigram model still cannot tell that the subject of a sentence is what its final clause refers back to.

Not every frequent word is worth keeping. Some are dropped outright as stop words, and "using a stop list significantly reduces the number of postings that a system has to store" [1, §2.2.2]. But the practice has been quietly abandoned: the trend "has been from standard use of quite large stop lists (200-300 terms) to very small stop lists (7-12 terms) to no stop list whatsoever", and "web search engines generally do not use stop lists" [1, §2.2.2]. The reason is that tf-idf already down-weights them, without the risk of destroying a query like To be or not to be [1, §2.2.2].

Where it's used

• Text classification baselines — spam, sentiment, topic. Counts plus a linear model is the number every neural result should be compared against.
• Retrieval, where the representation began: a query "viewed as a bag of words" is treated "as a very short document" and scored against every other [1, §6.3.2].
• Deduplication and clustering, where two documents sharing a vocabulary usually share a subject.
• Anything with no GPU and no time. A count matrix and logistic regression fit in seconds on a laptop, which still makes it the right first attempt.
• Non-text sequences — items in a basket, events in a log, k-mers in a genome. The trick is not about language; it is about any set where membership matters more than arrangement.

Why & when

Start here whenever the task is about topic or vocabulary. If a human could answer the question by skimming for words rather than reading sentences, counts will get most of the way [2, §8.2.3.7].

Do not use it when the task turns on structure — negation, who did what to whom, sarcasm, anything where two sentences share words and differ in claim. The representation cannot express the difference, so no amount of model capacity downstream will recover it [2, §8.2.3.8].

Add n-grams before adding a neural network. Bigrams are cheap and keep "some of the local ordering information" — scikit-learn's example uses is this to tell a question from a statement [2, §8.2.3.3], and not good becomes a feature of its own — and on sentiment tasks they give consistent gains [3, Abstract].

Expect the vocabulary to be the hyperparameter that matters. Minimum document frequency, maximum document frequency and n-gram range change the feature count by orders of magnitude, and results depend on the features used as much as on the model [3, Abstract].

Worked example

The textbook's own example, computed rather than asserted — plus what a bigram representation does to it.

import numpy as np

docs = [
    "Mary is quicker than John",
    "John is quicker than Mary",
    "Mary is slower than John",
]
toks = [d.lower().split() for d in docs]


def matrix(units):
    vocab = sorted({u for row in units for u in row})
    X = np.zeros((len(units), len(vocab)), dtype=int)
    for i, row in enumerate(units):
        for u in row:
            X[i, vocab.index(u)] += 1
    return vocab, X


vocab, X = matrix(toks)
print("  vocabulary:", vocab)
for d, row in zip(docs, X):
    print(f"  {d:<28} {row}")

print(f"\n  rows 1 and 2 identical: {np.array_equal(X[0], X[1])}")
print(f"  rows 1 and 3 identical: {np.array_equal(X[0], X[2])}")

bigrams = [[f"{r[i]}_{r[i+1]}" for i in range(len(r) - 1)] for r in toks]
bvocab, B = matrix(bigrams)
print(f"\n  with bigrams ({len(bvocab)} features instead of {len(vocab)}):")
print(f"  rows 1 and 2 identical: {np.array_equal(B[0], B[1])}")
print("  bigrams unique to row 1:", [bvocab[j] for j in np.where(B[0] > B[1])[0]])

  vocabulary: ['is', 'john', 'mary', 'quicker', 'slower', 'than']
  Mary is quicker than John    [1 1 1 1 0 1]
  John is quicker than Mary    [1 1 1 1 0 1]
  Mary is slower than John     [1 1 1 0 1 1]

  rows 1 and 2 identical: True
  rows 1 and 3 identical: False

  with bigrams (8 features instead of 6):
  rows 1 and 2 identical: False
  bigrams unique to row 1: ['mary_is', 'than_john']

The third sentence is the control, and it is what makes the first result precise. Swapping two words is visible — slower is a different column from quicker, so row 3 differs. Swapping two roles is invisible, because roles are carried by position and position is exactly what was discarded.

Bigrams separate rows 1 and 2, and the two features that do it are mary_is and than_john — the pairs that only exist when Mary is the subject. That is the whole repair in miniature: order was recovered by making a slightly larger unit the thing being counted. Note the cost, though. Five-word sentences over a six-word vocabulary produced eight bigram features, and on a real corpus that ratio is what turns a hundred thousand columns into millions.

Pitfalls

Fitting the vocabulary on the test set. The vocabulary is a parameter learned from data. Building it over all documents before splitting leaks the test set's word distribution into training.

Assuming a high count means importance. The most frequent word in almost any English document is the. Raw counts rank it first; this is precisely the problem tf-idf exists to fix [1, §6.2.1].

Reflexively removing stop words. Modern practice mostly does not, and phrase-sensitive tasks are damaged by it [1, §2.2.2].

Comparing documents by raw dot product. Long documents have larger counts everywhere and win every comparison. Normalise first.

Reading positional independence as a claim about language. It is a modelling convenience known to be false [1, §13.4]; the justification is parameter count, not linguistics.