The Bag-of-Words Model

Formally, fix a vocabulary $V = \{w_1, w_2, \dots, w_{|V|}\}$, the set of distinct terms across a corpus after tokenization (and often after stemming or lemmatization to collapse inflectional variants like "running" and "run" into one vocabulary entry). Every document $d$ is mapped to a vector

where $c_i$ is the number of times word $w_i$ occurs in $d$. This is the count vector (sometimes a binary presence vector with $c_i \in \{0,1\}$ is used instead, ignoring frequency entirely). The name "bag of words" captures the key discarded information: a bag, unlike a sequence, has no order. "Dog bites man" and "man bites dog" produce identical vectors — a fact that is either irrelevant or catastrophic depending on the downstream task. The bag-of-words model rests on an explicit independence assumption, most visible when it is paired with a Naive Bayes classifier: the probability of a document given a class is modeled as a product over positions,

treating each word token as drawn independently from a class-conditional distribution over the vocabulary, with no memory of neighboring words. This is the bag-of-words assumption, a special case of the broader "naive" conditional-independence assumption in statistical NLP. It is known to be false — words are highly context-dependent — yet the resulting models are cheap to estimate, robust to overfitting given limited data, and surprisingly competitive. A second implicit assumption is exchangeability: the identity of which position a word occupies carries no information, only the multiset of words does. This means the representation is invariant under any permutation of the tokens, which is exactly why syntax, negation scope ("not good" vs "good"), and multi-word idioms are invisible to a pure BoW model unless special-cased (e.g., by including bigrams as vocabulary items, a common patch called bag-of-n-grams).

Building a bag-of-words representation for a corpus is a two-pass algorithm: first establish the vocabulary (the coordinate system for every document vector), then count.

Pass 1 — Vocabulary construction. Tokenize every document in the corpus (assumed already done via Text Preprocessing and Tokenization), optionally apply stemming/lemmatization and stopword removal, and collect the set of distinct surviving tokens. This defines $|V|$, the dimensionality of every document vector, and a fixed mapping from token string to integer index (a hash map in practice).

Pass 2 — Vectorization. For each document, walk its token stream and increment the count at the vocabulary index of each token. Tokens not in the fixed vocabulary (out-of-vocabulary, or OOV, words — common at inference time on unseen documents) are either dropped or routed to a special `` bucket. Because most documents use only a small fraction of the full vocabulary, the resulting vectors are sparse — mostly zeros — and are almost always stored in sparse formats (dictionaries of `{index: count}`, or compressed sparse row matrices) rather than dense arrays, which is what makes the model practical even for vocabularies of hundreds of thousands of words. ``` function BUILD_VOCABULARY(corpus, min_freq = 1): freq = empty hashmap from token -> integer count for document in corpus: for token in TOKENIZE(document): freq[token] += 1 vocabulary = sorted list of tokens where freq[token] >= min_freq index = hashmap mapping vocabulary[i] -> i for i in 0..len(vocabulary)-1 return index // O(|V|) entries function VECTORIZE(document, index, binary = false): vector = sparse map from int -> number, default 0 for token in TOKENIZE(document): if token in index: i = index[token] if binary: vector[i] = 1 else: vector[i] = vector[i] + 1 // else: OOV token, silently dropped (or mapped to index) return vector function VECTORIZE_CORPUS(corpus, index, binary = false): matrix = empty list for document in corpus: matrix.append(VECTORIZE(document, index, binary)) return matrix // list of sparse rows ``` Two design choices matter in practice, and both are worth naming explicitly:

• Min-frequency / max-frequency pruning. Extremely rare tokens (typos, IDs) add dimensions with almost no statistical signal; extremely common tokens (stopwords) add dimensions with almost no discriminative signal. Pruning both keeps $|V|$ manageable and the vectors more informative — this pruning step is also the seed of the idea behind TF-IDF Weighting, which instead of dropping common words, down-weights them continuously.
• Binary vs. count vectors. Binary (presence/absence) vectors are more robust to a single word being repeated many times in one document (a phenomenon sometimes called "burstiness") and are the natural choice for the Bernoulli variant of Naive Bayes; raw counts preserve more information and are the natural choice for the Multinomial variant.

Time complexity. Let $N$ be the total number of tokens across the corpus and $D$ the number of documents. Vocabulary construction (Pass 1) touches every token exactly once and performs a constant-time (amortized) hash-map update per token, giving $O(N)$ time. Vectorization (Pass 2) again touches every token once, doing an $O(1)$ amortized hash lookup and increment, giving $O(N)$ time. Total: $O(N)$, i.e., linear in corpus size, independent of vocabulary size $|V|$ — this is the algorithmic reason BoW scales to web-scale corpora when, say, a quadratic pairwise-comparison method would not.

Space complexity. The vocabulary index stores $O(|V|)$ entries. The corpus representation, if stored as dense $D \times |V|$ matrix, would need $O(D \cdot |V|)$ space — but because each document typically uses only a small number of distinct words $|d| \ll |V|$, the sparse representation needs only $O(\sum_d |d|) = O(N)$ space, which is the practical reason sparse matrix formats (CSR, dict-of-dicts) are used rather than dense arrays. This sparsity is not an implementation detail — it is a direct consequence of Zipf's Law: a small number of words account for most tokens, so any single document's vocabulary footprint is a small, biased sample of $V$.

Correctness argument. "Correctness" for a representation, rather than an algorithm with a single right answer, means: the mapping from document to vector is well-defined, deterministic, and faithfully preserves exactly the information the model claims to preserve — word identity and frequency, nothing else. Two invariants make this precise: 1. Determinism / well-definedness. Given a fixed vocabulary index and tokenizer, `VECTORIZE` is a pure function: the same document always produces the same vector, because the algorithm never depends on token order — it only accumulates counts into a map keyed by token identity. This is the formal content of "bag" — the vector is invariant under any permutation $\pi$ of the token sequence, since summation is commutative: $\sum_i \mathbb{1}[w_{\pi(i)} = w_j] = \sum_i \mathbb{1}[w_i = w_j]$ for any permutation $\pi$. 2. Information preservation, exactly at the level claimed. The count vector is a sufficient statistic for the multiset of tokens: from $\vec d$ one can reconstruct exactly which words occurred and how many times, but never their order or adjacency — this is not a bug in the implementation but the definition of the representation. Any algorithm (Naive Bayes, cosine similarity, logistic regression) that consumes only $\vec d$ is therefore mathematically guaranteed to be blind to word order, by construction, not by accident.

Honest tradeoffs. The independence assumption underlying bag-of-words is provably false as a generative model of language — real text has strong sequential dependencies (that is exactly what n-gram and neural language models exploit) — yet the estimation problem it induces (estimating $P(w \mid c)$ from counts) is extremely well-posed: with $|V|$ parameters per class instead of exponentially many joint parameters, it needs far less data to estimate reliably, which is precisely the classical bias–variance tradeoff of "naive" models: higher bias (wrong independence assumption) for lower variance (few parameters, robust with small data).

Consider a tiny two-document, two-class corpus for a coarse sentiment task, after tokenization and lowercasing (stopword removal applied for brevity):

• $d_1$ (positive): "great acting great story"
• $d_2$ (negative): "boring acting boring plot"

Step 1 — Vocabulary. Distinct tokens across the corpus, in first-seen order:

Step 2 — Count vectors.

Step 3 — A new, unseen test document. "great acting boring story" arrives at inference time.

Notice immediately what has been lost: $d_3$ contains both "great" and "boring" with equal weight, and BoW alone cannot tell that "boring" negates the sentiment of "great" or vice versa — there is no structure connecting them. A downstream classifier trained on $d_1, d_2$ would essentially see $d_3$ as a near-equal mixture of positive and negative evidence (two positive-associated counts, two negative-associated counts), landing close to the decision boundary — which, arguably, is the right answer for a genuinely mixed review, but the model reaches it by accident of counting rather than by understanding contradiction.

Step 4 — Cosine similarity, a typical downstream use. Treating $\vec{d_1}$ and $\vec{d_3}$ as vectors:

and

By this pure count-based similarity, $d_3$ is judged closer to the positive review $d_1$ than to $d_2$ — driven entirely by "great" and "story" contributing weight, and by "acting" appearing in both. This illustrates both the power (a fast, well-defined numeric similarity with no linguistic engineering) and the fragility (the judgment ignores that "boring" is a strong standalone negative signal) of the representation — exactly the gap that motivated reweighting rare, discriminative words more heavily, which is the idea developed next under TF-IDF Weighting.

The term "bag of words" and the underlying independence assumption trace back to the intersection of information retrieval and probabilistic text modeling in the mid-20th century, well before "NLP" was a common phrase. The representation grew out of two converging lines: statistical linguistics' interest in word-frequency distributions, and information retrieval's need for a fast, computable notion of document similarity.

Luhn's work on automatic abstracting and indexing in the 1950s laid the practical groundwork for treating a document as a statistical distribution over its terms — the direct ancestor of the frequency-count vector used in bag-of-words models and, later, TF-IDF weighting.

Bag-of-words representations remain embedded throughout production NLP systems, often invisibly, as the fast first stage before more expensive models are invoked. Spam and abuse filters at email providers still use bag-of-words or bag-of-n-grams features feeding lightweight linear classifiers, because they run in microseconds at the scale of billions of messages per day. Search engines' classical relevance-scoring components (like the BM25 family) are direct descendants of the bag-of-words vector-space model, computing relevance from term frequencies without needing to parse syntax. Document clustering and topic modeling pipelines — including classical Latent Semantic Analysis and Latent Dirichlet Allocation — take a bag-of-words (or TF-IDF-weighted bag-of-words) matrix as their starting input, because topic assignment depends on which words co-occur across documents, not their order within a sentence. Recommendation systems that match user queries to product descriptions frequently use sparse bag-of-words vectors for a cheap, interpretable first-pass filter before a heavier neural re-ranker refines the shortlist. In education and interpretability-sensitive domains (legal discovery, medical record triage), bag-of-words remains attractive precisely because it is fully transparent: every feature is a literal word, every model weight is directly inspectable, unlike the distributed representations inside a transformer. It is also the standard baseline against which every new text representation — word embeddings, contextual embeddings, transformer encodings — is measured, because if a method cannot beat bag-of-words plus a linear classifier on a given task, it has not yet demonstrated its added value.

Ask the tutor: How does TF-IDF weighting change the bag-of-words vectors from the worked example, and would it change which test document is judged most similar?