7.3.2 N-grams

Why n-grams?

In Bag of Words, we described each SMS message by its word counts, and our first spam filter caught 117 of the 131 spam messages in the test set. Not bad for such a simple idea! But if you looked closely at the ones it missed, you may have noticed that the bag has two blind spots. It forgets word order, so "not good" and "good, not" look exactly the same to it. And it only knows whole words, so a spammer who writes cal;l instead of call, or glues words together as in ringtoneking, gives the model a word it has never seen before.

In this module we will patch both blind spots with one idea. An n-gram is simply a sequence of n neighbouring units. If we count pairs of words (bigrams) such as "not good" or "call now", we keep a little of the word order. If we count short runs of characters, such as cal or all, we get features that survive typos and odd spellings, because a misspelt word still shares most of its pieces with the correct one. The nice part is that both are just one setting away in CountVectorizer. There is a catch, though: the vocabulary gets much bigger. So we will also learn how to keep it under control, and then, on the same split as before, we will check honestly whether n-grams actually help.

What you need to know

Here is what I would like you to take away from this module. Each of these comes up again below, with code:

Learn it properly

There is very little theory in this module, and a lot of measuring. So read the short section below first, and then let us run the comparisons together.

Pick one main course

Our pick: scikit-learn, Limitations of the Bag of Words representation

Read Limitations of the Bag of Words representation in the scikit-learn user guide. It is only about one screen long. It explains why a bag of single words misses phrases and misspellings, introduces word bigrams, and then shows character n-grams on the misspelt pair words and wprds, including the difference between the char and char_wb analyzers. That is exactly the toolkit we will use on this page.

If you prefer something else

• If you are curious about the other use of n-grams: Chapter 3 of Speech and Language Processing, N-gram Language Models, uses n-gram counts to predict the next word. Section 3.1 defines n-grams and the Markov assumption. It is a different task from ours, but the counts are the same. You do not need it for this page.
• The reference: the CountVectorizer page documents ngram_range, analyzer, min_df, max_df and max_features.

A quick tour

The rest of this page builds word and character n-grams, first by hand and then with CountVectorizer. We will watch the vocabulary grow, and then compare the results on the same SMS split as in Bag of Words. Go through your chosen course first, then open a notebook and run each cell as you read.

Word n-grams

Let us start with the word-order problem. Here are two made-up film reviews with opposite meanings. We write a tiny function that lists the n-grams of a text, and compare the two reviews word by word and pair by pair:

review_a = "the film was not good it was bad"
review_b = "the film was not bad it was good"

def word_ngrams(text, n):
    words = text.split()
    grams = []
    for start in range(len(words) - n + 1):
        grams.append(" ".join(words[start:start + n]))
    return grams

same_words = sorted(review_a.split()) == sorted(review_b.split())
print(same_words)
print(word_ngrams(review_a, 2))
print(word_ngrams(review_b, 2))

True
['the film', 'film was', 'was not', 'not good', 'good it', 'it was', 'was bad']
['the film', 'film was', 'was not', 'not bad', 'bad it', 'it was', 'was good']

Look at the first line: True. As single words (unigrams), the two reviews are identical, so a bag of words could never tell them apart. As bigrams, though, they differ: not good and not bad are now features of their own, so a model can learn that not good is negative even though good on its own is positive. (In case you are wondering how many n-grams there are: a text of $k$ words has $k - n + 1$, one for each starting position that leaves room for $n$ words.)

We do not have to write this function ourselves, of course. In CountVectorizer, ngram_range=(min_n, max_n) counts every n-gram from length min_n to max_n. With (1, 2), the three sentences from Bag of Words give 22 features instead of 10:

from sklearn.feature_extraction.text import CountVectorizer

sentences = ["Call now to win a free prize",
             "Call me when you are free",
             "Free prize! Call now, call now"]
bigram_vectorizer = CountVectorizer(ngram_range=(1, 2))
bigram_vectorizer.fit(sentences)
print(len(bigram_vectorizer.vocabulary_))
print(bigram_vectorizer.get_feature_names_out()[:8])

22
['are' 'are free' 'call' 'call me' 'call now' 'free' 'free prize' 'me']

Two small details are worth noticing here. The bigrams are made after tokenization, so the one-letter word a has already been dropped, and "win a free prize" produces the bigram win free. And bigrams happily cross punctuation: prize call comes from "prize! Call".

Character n-grams

Now for the second blind spot, misspelt words. A character n-gram is a run of n characters. With analyzer="char_wb", CountVectorizer takes them inside each word only ("wb" stands for word boundaries). It first pads each word with a space at both ends, so that the pieces at the start and end of a word can be recognised. To see what it produces, we can ask for the analyzer itself: build_analyzer() returns the function that turns one text into features.

char_analyzer = CountVectorizer(analyzer="char_wb",
                                ngram_range=(3, 3)).build_analyzer()
print(char_analyzer("call"))
print(char_analyzer("cal;l"))

[' ca', 'cal', 'all', 'll ']
[' ca', 'cal', 'al;', 'l;l', ';l ']

This is the whole trick. As whole words, call and cal;l have nothing in common, and cal;l is a word the model has never seen. As character trigrams, though, they share ca and cal, so a model that has learned "cal at the start of a word suggests spam" still gets a hint. That is why character n-grams cope with typos, missing letters, and the deliberate misspellings spammers use to dodge filters. (char_wb splits words at whitespace only, which is why the ; stays inside the word.)

There is also a second character analyzer, analyzer="char". It ignores word boundaries, so it also produces n-grams that span a space, such as l n from "call now". For most tasks, char_wb gives fewer and cleaner features, so that is the one we will use.

In practice, you usually count several lengths at once. With ngram_range=(2, 5), even the short word call gives 14 features:

range_analyzer = CountVectorizer(analyzer="char_wb",
                                 ngram_range=(2, 5)).build_analyzer()
print(range_analyzer("call"))

[' c', 'ca', 'al', 'll', 'l ', ' ca', 'cal', 'all', 'll ', ' cal', 'call', 'all ', ' call', 'call ']

The vocabulary grows fast

14 features from one short word! You can probably guess what happens on a whole dataset. Let us load the SMS messages (download sms.csv; SMS Spam Collection, CC BY 4.0) with the same split as in Bag of Words: stratified, 20% test, random_state=0. Using the same split matters, because it is the only way to compare this page's models fairly with the previous one.

import pandas as pd
from sklearn.model_selection import train_test_split

sms = pd.read_csv("sms.csv")
train, test = train_test_split(sms, test_size=0.2,
                               stratify=sms["label"],
                               random_state=0)
X_train = train["text"]
X_test = test["text"]
y_train = (train["label"] == "spam").astype(int)
y_test = (test["label"] == "spam").astype(int)

Now we fit each setting on the 4,136 training messages and count the features it creates. To keep the results easy to read, each setting gets a plain name, and the comment says what it counts:

settings = {
    # single words, as in Bag of Words
    "words": CountVectorizer(),
    # single words and pairs of words
    "words + pairs": CountVectorizer(ngram_range=(1, 2)),
    # single words, pairs and triples
    "words + pairs + triples": CountVectorizer(ngram_range=(1, 3)),
    # pieces of 2 to 5 characters, inside each word
    "chars 2-5, in words": CountVectorizer(
        analyzer="char_wb", ngram_range=(2, 5)),
    # pieces of 2 to 5 characters, also across spaces
    "chars 2-5, across words": CountVectorizer(
        analyzer="char", ngram_range=(2, 5)),
}
sizes = {}
for name, vectorizer in settings.items():
    vectorizer.fit(X_train)
    sizes[name] = len(vectorizer.vocabulary_)
pd.Series(sizes, name="features").to_frame()

That grows fast. Adding bigrams multiplies the vocabulary by more than five, and trigrams double it again, even though we still only have 4,136 messages. Most of the new features are pairs that occur in one message only, such as a particular name followed by a particular word. Features like that cannot help on new messages. All they do is give the model more ways to memorise the training set, which is our old friend overfitting in a new form.

Keeping the vocabulary under control

So how do we keep the useful n-grams and throw away the one-off ones? CountVectorizer has two settings that trim the vocabulary while fit builds it:

• min_df ("minimum document frequency") drops every feature that appears in fewer than this many training documents. min_df=2 removes everything seen in only one message.
• max_features keeps only the given number of most frequent features.

(There is also max_df, which drops features that appear in too many documents. You can think of it as a list of stop words that the data picks for you.)

Let us see how much each one removes:

trimmed = {
    "words + pairs, min_df=2": CountVectorizer(
        ngram_range=(1, 2), min_df=2),
    "words + pairs, max_features=5000": CountVectorizer(
        ngram_range=(1, 2), max_features=5000),
    "chars 2-5, in words, min_df=2": CountVectorizer(
        analyzer="char_wb", ngram_range=(2, 5), min_df=2),
}
for name, vectorizer in trimmed.items():
    vectorizer.fit(X_train)
    print(f"{name:<32}", len(vectorizer.vocabulary_))

words + pairs, min_df=2          9959
words + pairs, max_features=5000 5000
chars 2-5, in words, min_df=2    32725

min_df=2 shrinks the words-and-pairs vocabulary from 42,547 to 9,959. In other words, more than three quarters of all unigrams and bigrams appear in just one training message.

Do n-grams help? An honest comparison

Now for the question we actually care about: do any of these features make a better spam filter? To find out fairly, we keep everything else fixed. We train the same classifier as in Bag of Words (logistic regression with max_iter=1000) and only change the vectorizer. For each one, we record two things:

• the mean F1 of 5-fold cross-validation on the training messages, which is what we would use to choose a setting;
• the precision, recall and F1 on the 1,035 test messages, which we only look at to report the result.

Here is a small function that does both for any vectorizer:

from sklearn.linear_model import LogisticRegression
from sklearn.pipeline import make_pipeline
from sklearn.model_selection import StratifiedKFold, cross_val_score
from sklearn.metrics import precision_score, recall_score, f1_score

folds = StratifiedKFold(n_splits=5, shuffle=True, random_state=0)

def evaluate(vectorizer):
    pipeline = make_pipeline(vectorizer,
                             LogisticRegression(max_iter=1000))
    cv_f1 = cross_val_score(pipeline, X_train, y_train,
                            cv=folds, scoring="f1")
    pipeline.fit(X_train, y_train)
    predictions = pipeline.predict(X_test)
    precision = precision_score(y_test, predictions)
    recall = recall_score(y_test, predictions)
    scores = {
        "features": len(pipeline[0].vocabulary_),
        "CV F1": round(float(cv_f1.mean()), 3),
        "CV std": round(float(cv_f1.std()), 3),
        "test precision": round(precision, 3),
        "test recall": round(recall, 3),
        "test F1": round(f1_score(y_test, predictions), 3),
    }
    return pipeline, scores

pipeline[0] is the first step of the pipeline, which is the fitted vectorizer.

Next, the five settings we want to compare. Two of them are the trimmed versions from the previous section:

candidates = {
    "words": CountVectorizer(),
    "words + pairs": CountVectorizer(ngram_range=(1, 2)),
    "words + pairs, min_df=2": CountVectorizer(
        ngram_range=(1, 2), min_df=2),
    "chars 2-5, in words": CountVectorizer(
        analyzer="char_wb", ngram_range=(2, 5)),
    "chars 2-5, in words, min_df=2": CountVectorizer(
        analyzer="char_wb", ngram_range=(2, 5), min_df=2),
}

Now we evaluate each one, keeping its fitted pipeline (we will use two of them in a moment) and its scores. The character settings take a few seconds each, so don't worry if this cell is slow:

fitted = {}
results = {}
for name, vectorizer in candidates.items():
    pipeline, scores = evaluate(vectorizer)
    fitted[name] = pipeline
    results[name] = scores

table = pd.DataFrame(results).T
table.astype({"features": int})

.T transposes the table so that each setting is a row, and astype shows the feature counts as whole numbers. Here is how to read the columns:

• features: how many columns the vectorizer creates.
• CV F1 and CV std: the mean F1 over the 5 cross-validation folds, and how much it varies between folds. This is what we would use to pick a setting.
• test precision, test recall and test F1: the scores on the 1,035 test messages, which we only use to report the result.

The first row is our bag of words from the previous module, with the same test scores as there. Now let us read the rest honestly, including the part that did not go the way we might have hoped:

• Word bigrams do not help here. Cross-validated F1 is 0.900 against 0.906, and on the test set the model with bigrams catches fewer spam messages (recall 0.840 against 0.893), although it raises fewer false alarms. Trimmed with min_df=2, bigrams land within noise of plain words. When you think about it, this makes sense: SMS messages are short, and spam is recognised by its words rather than their order, so the extra 35,000 features mostly add ways to overfit.
• Character n-grams do help. Both character settings score about 0.94 in cross-validation. That is above the word models by more than the spread between folds, so it is not just luck. On the test set they catch more spam with fewer false alarms: F1 0.941 and 0.949 against 0.929. And with min_df=2, the model needs only half the features for the same quality.

In actual messages, the difference on the test set is small: the best model catches 120 of the 131 spam messages, against 117 for plain words. What makes the improvement believable is the cross-validation scores, which are averaged over five different splits. I would not trust a three-message difference on one test set by itself.

What the character n-grams caught

Remember the two spam messages that the word model missed in Bag of Words? Let us see whether the character model does any better on them. We ask each model for its spam probability:

missed = ["100 dating service cal;l 09064012103 box334sk38ch",
          "ringtoneking 84484"]
for name in ["words", "chars 2-5, in words"]:
    spam_probability = fitted[name].predict_proba(missed)[:, 1]
    print(f"{name:<20}", spam_probability.round(3))

words                [0.074 0.009]
chars 2-5, in words  [0.776 0.041]

predict_proba returns one column per class, and [:, 1] takes the probability of spam. The character model now flags the cal;l message with a probability of 0.776, because pieces such as cal, 0906 and box are familiar from other spam. ringtoneking 84484 is still missed, though. With only two words of context, there is not much for any model to go on. No feature trick catches everything, and I think it is important to report the misses too: they are part of an honest result.

Common mistakes

How to practise

The best way to get a feel for n-grams is to experiment with them yourself. Keep the same SMS split as on this page, so your results stay comparable, and try these:

• Combine words and characters: sklearn.pipeline.make_union(CountVectorizer(), CountVectorizer(analyzer="char_wb", ngram_range=(2, 5))) stacks both feature sets side by side. Does it beat characters alone in cross-validation?
• Try analyzer="char_wb" with ngram_range of (1, 3), (3, 5) and (2, 6). Plot cross-validated F1 against the number of features.
• Write word_ngrams from this page so that it also works for n larger than the number of words. What should it return?
• Find the 10 character n-grams with the largest logistic regression weights for spam. Which ones would you have guessed?

Check yourself

What comes next

You can now go beyond single words: pairs of words keep a little order, and pieces of characters see through typos. Just as importantly, you have seen that more features are not automatically better, and that the only way to know is to measure. Next, we keep the features and change how much each one counts:

• TF-IDF: keep the same features, but weight each count by how informative the word is.
• Vector Embeddings of Simple Text Features: replace thousands of sparse counts with short dense vectors.