Skip to content
Tutorials Center
My learning

Topics

Lesson 13 of 63 ยท Counting and Classic Representations

N-grams

Learn what n-grams are, build word and character n-grams in Python, and use pointwise mutual information (PMI) to find collocations like New York.

A single word often says too little. "York" alone is a place, a surname or a verb-like fragment; "New York" is clearly a city. "Not" and "good" are ordinary words, but "not good" flips the meaning of "good". To keep a little of this context without parsing grammar, we look at n-grams: runs of n consecutive items taken from a sequence.

Items are usually words, but they can also be characters. An n-gram of size 1 is a unigram, size 2 a bigram, size 3 a trigram. N-grams are the oldest trick in the NLP box and still power spelling checkers, language identification, search and the n-gram language models you will meet later. Here you will build them by hand, use them on characters, and score word pairs to find phrases that belong together. You should know how to split text into tokens and count with word frequencies.

What an n-gram is

Slide a window of width n across the tokens, one position at a time. Every window is one n-gram. A text with L tokens gives L - n + 1 n-grams, so longer windows give slightly fewer of them.

The same sentence, three window sizes

Unigrams the, cat, sat
Bigrams the cat, cat sat
Trigrams the cat sat

Bigger n keeps more context but sees each pattern less often.

1 / 2

The function below is all you need. It works on any list, so it serves words and characters alike.

Python A tiny n-gram function

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Ten tokens produce nine bigrams and eight trigrams. Notice that ('the', 'cat') appears twice. Counting such repeats is the next step, and it is exactly what makes n-grams useful: the counts tell you which combinations are common.

Counting n-grams

Python's Counter and zip give a compact bigram counter. zip(tokens, tokens[1:]) pairs every token with its successor, and Counter tallies the pairs.

Python
from collections import Counter

bigrams = Counter(zip(tokens, tokens[1:]))
bigrams.most_common(3)

A few practical points before you build on this:

  • Split into sentences first. If you count bigrams over a whole document, the last word of one sentence pairs with the first word of the next, which is not a real phrase. Segment sentences, then count within each one.
  • Add boundary markers when order matters. Padding with <s> and </s> lets you count "starts a sentence" and "ends a sentence" as ordinary events. Language models rely on this.
  • Mind the growth. With a vocabulary of V words there are V^2 possible bigrams and V^3 possible trigrams, but a real corpus uses only a tiny share of them. Most higher-order n-grams occur once, which is the sparsity problem.

Choose n by data size. Unigrams and bigrams are safe on small data sets. Trigrams and beyond need a lot of text, or most of your counts will be one and tell you nothing.

Character n-grams

Words break easily. "colour" and "color", "recieve" and "receive", or a rare word the system has never seen would all look unrelated to a word-level model. Splitting a word into character n-grams gives overlapping fragments, and similar spellings share many of them.

A common trick is to wrap the word in boundary symbols such as < and >, so that a prefix or a suffix becomes distinguishable from the same letters in the middle of a word. In the example, we compare spellings by how many trigrams they share, using the Jaccard score: the size of the shared set divided by the size of the combined set.

Python Character trigrams and spelling variants

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

color and colour score 0.38, the swapped-letters pair receive/recieve scores 0.27, and receive/believe (which only share an ending) falls to 0.08. The unrelated pair cat/dog scores 0.00. Search engines, spelling correction and language identification all use this idea: a language's most frequent character trigrams are a surprisingly good fingerprint.

Collocations and PMI

A collocation is a pair of words that go together more than chance predicts: "New York", "strong tea", "make a decision". You might try to find them by counting bigrams, but raw counts favor pairs made of very common words such as "of the" or "is a". Those are frequent because both words are frequent, not because they stick together.

Pointwise mutual information (PMI) fixes this by comparing how often two words occur together with how often you would expect them together if they were independent:

TEXT
PMI(a, b) = log2( P(a, b) / (P(a) * P(b)) )

If the pair appears exactly as often as chance predicts, the ratio is 1 and PMI is 0. If it appears four times as often, PMI is 2. A large positive score means "these words attract each other". A negative score means they avoid each other.

flowchart LR
    A["Count words<br/>and word pairs"] --> B["Estimate P(a), P(b), P(a,b)"]
    B --> C["PMI = log2 of P(a,b) over P(a)P(b)"]
    C --> D["Filter by minimum count"]
    D --> E["Rank: collocations on top"]

The minimum-count filter matters: PMI is unreliable for pairs seen once or twice.

That filter is not decoration. A word pair that appears once, where both words appear once, gets a huge PMI by accident. Always require a minimum count before you trust the ranking. The example runs on a tiny made-up corpus of short sentences.

Python Frequent pairs versus PMI

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

"new york" tops both lists, which is what we want. Further down, the lists diverge: PMI pushes pairs such as "weather is" above "is nice" even though the second is more frequent, because "is" is a very common word and so occurs next to many neighbors by chance. On a corpus this small the lower ranks are noisy. With real text, the effect is large: PMI lifts "machine learning" and "ice cream" over "of the".

PMI has its own weakness. It overrates rare pairs, since a small probability in the denominator inflates the ratio. Common fixes are the minimum-count filter used above, a count-weighted variant such as normalized PMI, or a statistical test. NLTK ships ready-made collocation finders for this; the idea is the same as the code above.

N-grams as features

Once you can count n-grams, you can use them as features for a classifier. Adding bigrams to a bag of words lets a model see "not good" as its own feature, not just "not" and "good" separately. You will see this with ngram_range=(1, 2) in Bag of Words. The price is a much larger vocabulary, which is why feature hashing and minimum-frequency cut-offs exist.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How many bigrams does a sentence of 8 tokens contain?

    A window of size n over L tokens gives L - n + 1 windows, so 8 - 2 + 1 = 7 bigrams.
  2. 2. Why can character n-grams help with misspelled words?

    The words colour and color share most of their trigrams, so a character-level model still sees them as close, unlike a word-level model that treats them as unrelated tokens.
  3. 3. What does a PMI score of 0 for a word pair mean?

    PMI compares the observed joint probability with the product of the separate probabilities. A ratio of 1 gives log2(1) = 0, meaning the words look independent.
  4. 4. Why should you set a minimum count before ranking pairs by PMI?

    A rare pair has a tiny expected probability, so even a single co-occurrence produces a very large ratio. The filter removes this noise.

Summary

  • An n-gram is a window of n consecutive items; a sequence of length L has L - n + 1 of them.
  • Unigrams, bigrams and trigrams trade context against sparsity: larger n means more context but rarer patterns.
  • Count n-grams inside sentences with Counter(zip(tokens, tokens[1:])).
  • Character n-grams with boundary markers capture spelling similarity and are robust to typos and unseen words.
  • PMI scores how strongly two words attract each other; it finds collocations that raw counts miss, but needs a minimum-count filter.

Next, turn whole documents into numbers with Bag of Words.