Bag of Words: Turning Text Into Sparse Count Vectors

The core idea and its defining invariant

Fix a vocabulary V — an ordered list of the distinct terms you care about — and assign each term a stable integer index, so V["machine"] = 4211. A document d becomes a vector x ∈ ℝ^|V| where x[i] is the number of times term i appears in d. That is the whole model: a document is a multiset (a bag) of its tokens, and the vector is the multiset's characteristic function over V.

The one property that defines BoW is the permutation invariance invariant: for any reordering π of a document's tokens, vectorize(d) = vectorize(π(d)). Word order carries zero information. This is simultaneously BoW's superpower (it collapses an astronomical space of sentences into a compact, comparable vector) and its fatal blind spot (negation, syntax, and phrase structure vanish). Two corollaries follow immediately:

• Bag-of-sets vs. bag-of-counts. If you replace counts with 0/1 presence flags you get the binary or set-of-words variant — the natural input to a Bernoulli Naive Bayes classifier.
• Additivity. The vector of two concatenated documents is the element-wise sum of their vectors, which is exactly why BoW plays so well with linear models: a per-word weight vector w scores a document by the dot product w · x = Σᵢ wᵢ·xᵢ.

How it works, step by step

Building the document-term matrix is a two-pass affair: pass one learns the vocabulary ("fit"), pass two emits vectors ("transform"). The pipeline:

• Tokenize. Split raw text into terms with a lexer/regex — commonly \w+ lowercased. This alone makes big decisions: "U.S.A.", hyphenation, and emoji all hinge on the tokenizer.
• Normalize. Case-fold, optionally stem or lemmatize (running → run), and drop stop words (the, of, is) that add dimensions but little signal.
• Fit vocabulary. Stream every training token into a hash map term → index, assigning the next free integer on first sight. This is the only pass that grows |V|.
• Transform. For each document, count terms into a local map, then emit (index, count) pairs into a sparse row.

function transform(doc, V):        # V is the fitted term→index map
    counts = HashMap()             # index → count, expected O(1) ops
    for tok in tokenize(doc):      # N tokens
        if tok in V:               # OOV terms are silently dropped
            i = V[tok]
            counts[i] += 1
    return sparse_row(counts)      # e.g. CSR (indices[], data[])

The output is stored as CSR (Compressed Sparse Row): three arrays — data (non-zero counts), indices (their column ids), and indptr (row boundaries). A dense |V|-wide row would be 99.9% zeros; CSR stores only the non-zeros (nnz), which is what makes BoW tractable at newspaper scale.

Complexity analysis and the derivation

Let D be the number of documents, N the total token count across the corpus, and nnz the number of non-zero matrix entries. Assume a hash map with expected-O(1) insert and lookup.

• Fit (build vocabulary): one pass over all tokens, one hash-map probe each ⇒ Θ(N) expected time, Θ(|V|) space for the map. Worst case with adversarial hash collisions degrades to O(N·|V|), which is why real libraries use randomized or well-mixed string hashes.
• Transform (per document of Nᵈ tokens): Θ(Nᵈ) to count. Across the corpus, Θ(N) time. Output size is Θ(nnz), and nnz ≤ N always (each token contributes to at most one non-zero, and repeats only increment it), so the matrix is never larger than the input token stream.
• Dot product with a weight vector (the classifier's inference step): scanning one sparse row costs Θ(nnzᵈ) — the number of distinct terms in that document — not Θ(|V|). This is the payoff: scoring a 200-word email against a million-word vocabulary touches ~150 dimensions.

Compare the naïve dense alternative: materializing a D × |V| dense matrix costs Θ(D·|V|) space. With D = 10⁶ documents and |V| = 10⁵, that is 10¹¹ floats ≈ 400 GB — utterly infeasible. The sparse representation collapses it to Θ(nnz) ≈ Θ(N), often a few gigabytes. Sparsity is not an optimization for BoW; it is the enabling condition.

The hashing trick: killing the vocabulary map

The fit pass has an operational cost the complexity hides: you must store the term→index map, and it must be shipped alongside the model to decode future documents. For streaming or memory-bounded systems that map is the bottleneck. Feature hashing (Weinberger et al., 2009) removes it entirely. Instead of a learned index, compute i = h(term) mod m for a fixed hash function h and a chosen output dimension m (e.g. 2²⁰).

• No vocabulary state. Fit becomes free — there is nothing to learn. Transform is a single pass, O(N), with O(1) memory beyond the output row.
• Collisions. Different terms can land on the same index, summing their counts. With m ≫ |V| collisions are rare and behave like mild, unbiased noise; a signed hash (multiply each count by ±1 from a second hash) makes the collision error zero-mean, so it cancels in expectation.
• Trade-off. You lose interpretability — you cannot invert index → word — and you fix m up front. This is scikit-learn's HashingVectorizer, and it is how large-scale online learners (e.g. Vowpal Wabbit) ingest text.

The regime: use a plain fitted vocabulary when you need feature names, a bounded corpus, and interpretability; reach for the hashing trick when the vocabulary is unbounded, streaming, or too large to persist.

Trade-offs, variants, and when BoW still wins

BoW's frozen invariant — order doesn't matter — is exactly what to weigh. It wins precisely when a document's label is driven by which words appear, not how they are arranged.

• Spam / topic detection. The presence of "viagra", "invoice", or "lottery" is nearly sufficient. Word order is noise. A BoW + Naive Bayes or logistic-regression model is fast, tiny, and shockingly hard to beat here.
• Bag of n-grams. To claw back local order, add bigrams/trigrams as vocabulary terms: "not good" becomes its own dimension, rescuing simple negation. The cost is a combinatorial blow-up of |V| (up to |V|ᵏ), so you prune by document frequency.
• TF-IDF reweighting. Raw counts over-weight frequent-but-uninformative words. Scaling each count by inverse document frequency (log(D / dfₜ)) downweights ubiquitous terms — the standard upgrade before feeding a linear classifier or cosine-similarity search.
• When to abandon it. Machine translation, question answering, anything where "the cat sat on the dog" vs "the dog sat on the cat" must differ — BoW is structurally incapable and you move to sequence models (RNNs, Transformers).

The honest summary: BoW is a strong, cheap baseline. On many classification tasks the gap between a tuned TF-IDF + linear SVM and a fine-tuned Transformer is a few points of F1 at a thousandth of the cost.

Real systems and the standard reference

The document-term matrix is the substrate of classical information retrieval; Salton's SMART system (1960s–70s) and the vector-space model formalized documents-as-count-vectors, and the canonical treatment is Manning, Raghavan & Schütze, Introduction to Information Retrieval (2008). Where you meet BoW in practice:

• scikit-learn: CountVectorizer (fitted vocabulary), TfidfVectorizer (counts + IDF), and HashingVectorizer (the hashing trick) — the three you will actually use.
• Search engines: the same term-count intuition underlies the inverted index and BM25 ranking in Lucene / Elasticsearch, though those index term → document rather than materialize a dense matrix.
• Spam and sentiment: Paul Graham's 2002 "A Plan for Spam" popularized BoW + Naive Bayes for email filtering, a design still embedded in many mail servers.
• Topic models: Latent Dirichlet Allocation (Blei et al., 2003) takes a BoW document-term matrix as its literal input — LDA is explicitly a bag-of-words generative model.

Pitfalls, edge cases, and failure modes

Most BoW bugs are not in the algorithm but at its edges:

• Out-of-vocabulary (OOV) terms. Any word unseen at fit time is silently dropped at transform. A test document written entirely in novel jargon vectorizes to the zero vector — and a linear model scores it as pure bias. Always monitor OOV rate.
• Vocabulary explosion. URLs, hex ids, and typos each mint a fresh dimension. Without min_df pruning (drop terms appearing in fewer than k docs) |V| bloats into the millions, most dimensions seen once, pure noise and overfitting fuel.
• Train/serve skew. The fitted vocabulary and the exact tokenizer must be frozen and reused at inference. Re-fitting on a new corpus reshuffles every index; a stale index map means your weight vector points at the wrong words.
• Length sensitivity. A 5,000-word article dwarfs a tweet in raw counts. Normalize each row (L1 or L2) — or use TF-IDF — before comparing documents, especially with cosine similarity, where L2-normalized BoW turns the dot product into a cosine.
• Negation and irony. "not a good movie" and "a good movie, not" are indistinguishable to unigram BoW; both look positive. Bigrams patch the common case, but sarcasm and long-range dependencies remain out of reach — a permanent consequence of the permutation invariant.

Bag of Words vs. neighbouring text-representation schemes

Representation	Word order	Dimensionality	Vector cost / doc	Semantics
Bag of Words (counts)	Lost	|V| (10⁴–10⁶)	O(N)	None — surface counts
TF-IDF	Lost	|V|	O(N)	Rarity-weighted counts
Bag of n-grams	Local (window k)	|V|ᵏ blow-up	O(kN)	Short phrases
Hashing (feature hashing)	Lost	Fixed m (chosen)	O(N)	None; collisions
Word embeddings	Preserved via model	d (50–1024 dense)	O(Nd)	Distributional meaning