Bag of words and n-grams

Intermediate

Introduction

Models work with numbers, not words. The simplest way to turn a document into numbers is to count its words. Pick a vocabulary, the list of all distinct words in your documents, and describe each document by how often each vocabulary word occurs in it. This is the bag-of-words model: the document is treated like a bag of word tiles shaken up so that the order is lost, but the counts remain. It is old and simple, yet it still powers spam filters, topic classifiers and search engines, and it is the starting point for TF-IDF and Naive Bayes in the next lessons.

How it works

  1. Tokenize every document (and normalize it, if you want "The" and "the" to be one word).
  2. Build the vocabulary: the distinct tokens over all documents, sorted so that every run uses the same order.
  3. Vectorize: for each document, the count vector has one entry per vocabulary word.

For the documents "the cat sat" and "the dog ate the cat", the vocabulary is ate, cat, dog, sat, the, and the vectors are [0, 1, 0, 1, 1] and [1, 1, 1, 0, 2]. Every document, short or long, becomes a vector of the same length, which is exactly what classifiers and similarity measures need.

What a bag throws away is order. "Dog bites man" and "man bites dog" have identical bags. N-grams bring back local order: the bigrams (2-grams) of "dog bites man" are "dog bites" and "bites man", which differ from those of "man bites dog". Using bigrams as extra vocabulary entries lets a model see phrases such as "not good" or "New York". Character n-grams, such as the 3-grams "cat", "at_" of a word, help with spelling mistakes and with languages that do not put spaces between words.

The price is size. A vocabulary of 50,000 words allows 2.5 billion possible bigrams, and each document uses only a handful, so the vectors are sparse: almost every entry is zero. Practical systems store only the non-zero counts, and drop words that appear in too few documents (minimum document frequency) or in nearly all of them.

Example

docs = ["the cat sat", "the cat sat on the mat", "the dog ate the cat"]
tokenized = [d.split() for d in docs]
vocab = sorted(set(w for doc in tokenized for w in doc))
print("vocabulary:", vocab)
for doc in tokenized:
    print([doc.count(w) for w in vocab], " ".join(doc))


def ngrams(tokens, n):
    return [tuple(tokens[i:i + n]) for i in range(len(tokens) - n + 1)]


print("bigrams of doc 3:", ngrams(tokenized[2], 2))
counts = {}
for doc in tokenized:
    for gram in ngrams(doc, 2):
        counts[gram] = counts.get(gram, 0) + 1
print("most common bigrams:", sorted(counts.items(), key=lambda kv: -kv[1])[:2])

a, b = "dog bites man".split(), "man bites dog".split()
print("same bag of words:", sorted(a) == sorted(b))
print("same bigrams:", ngrams(a, 2) == ngrams(b, 2))
Open in compiler

Line by line

  1. The vocabulary is the sorted set of every word in every document: 7 words.
  2. Each count vector lists how often each vocabulary word occurs. "the" occurs twice in the last two documents.
  3. ngrams slides a window of n tokens along the list; a document of 5 tokens has 4 bigrams.
  4. Counting bigrams over all documents shows the phrase "the cat" in every one of them.
  5. "dog bites man" and "man bites dog" have the same sorted words, so the same bag of words, but different bigrams.

Expected result

vocabulary: ['ate', 'cat', 'dog', 'mat', 'on', 'sat', 'the']
[0, 1, 0, 0, 0, 1, 1] the cat sat
[0, 1, 0, 1, 1, 1, 2] the cat sat on the mat
[1, 1, 1, 0, 0, 0, 2] the dog ate the cat
bigrams of doc 3: [('the', 'dog'), ('dog', 'ate'), ('ate', 'the'), ('the', 'cat')]
most common bigrams: [(('the', 'cat'), 3), (('cat', 'sat'), 2)]
same bag of words: True
same bigrams: False

In the real world

scikit-learn's CountVectorizer builds exactly these vectors, with options such as ngram_range=(1, 2) for words and bigrams and min_df to drop rare words; it stores them as sparse matrices. Search engines index n-grams for phrase queries, and character n-grams are behind fastText's ability to handle words it never saw in training. Even large language models are trained on text whose statistics, word and n-gram counts, are studied first to clean and filter the data.

Common mistakes

  • Building the vocabulary from the test data too, which leaks information about the test set into training.
  • Using an unsorted set as the vocabulary, so the vector positions change from run to run.
  • Adding trigrams and 4-grams without limits, which explodes the vocabulary and memory use.
  • Forgetting that unknown words exist: a word that is not in the vocabulary must be ignored or mapped to a special token.

Best practices

  • Fit the vocabulary on the training documents only, then reuse it for new documents.
  • Start with unigrams, add bigrams if word order matters, and measure whether it helps.
  • Use a minimum document frequency to remove typos and very rare words.
  • Store vectors sparsely (only non-zero counts) for real data.

Summary

The bag-of-words model describes a document by its word counts over a fixed vocabulary, which gives every document a vector of the same length but forgets word order. N-grams keep local order by counting sequences of n tokens, at the cost of a much larger and sparser vocabulary, which frequency limits keep under control.

Quick check

1. What does the bag-of-words model ignore?
2. How many bigrams does a sentence of 6 tokens have?
3. Why are count vectors over a real vocabulary called sparse?
4. What does a minimum document frequency do?

Key takeaways

  • A bag of words turns any document into a fixed-length vector, so classic models can use it.
  • Bags ignore order; n-grams keep local order at the cost of a much larger vocabulary.
  • Real vocabularies are huge and vectors are sparse, so frequency limits and sparse storage matter.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.