N-grams and Their Variations
On this page
N-grams and Their Variations
Recall first
Why can a language model assign a probability to a whole sentence by multiplying local probabilities? What information does a bigram discard compared with the full history?
First principles
A language model assigns a probability to a token sequence. By the chain rule,
P(w₁…w_T) = ∏ₜ P(wₜ | w₁…wₜ₋₁).
An n-gram model approximates the history with the previous n−1 tokens: a bigram uses P(wᵢ | wᵢ₋₁) and a trigram uses P(wᵢ | wᵢ₋₂,wᵢ₋₁). With start/end markers, the unsmoothed maximum-likelihood estimate is
P_MLE(wᵢ | h) = count(h,wᵢ) / count(h).
This is a Markov assumption: the recent window is enough. It makes estimation simple and fast, but loses long context and produces zero probabilities for unseen n-grams.
Worked example. Corpus sentences <s> I like NLP </s> and <s> I like tea </s> give count(I like)=2, count(like NLP)=1, and count(like)=2. Thus the trigram estimate P(NLP | I, like)=1/2, while bigram P(NLP | like)=1/2. For <s> I like NLP </s>, multiply every conditional, including boundary transitions; if any factor is zero, the unsmoothed sentence probability is zero.
Variations include unigram, bigram, trigram and higher order; interpolation combines orders, e.g. λ₃P₃ + λ₂P₂ + λ₁P₁ with nonnegative weights summing to one; backoff uses a lower-order model when a higher-order count is unavailable. Character and subword n-grams help with morphology and unknown words. Smoothing is not optional decoration—it changes how unseen events receive probability.
Exercise — reveal after answering
If count(the cat)=4 and count(the)=10, what is the unsmoothed bigram estimate P(cat|the)? What hidden assumption makes this estimate fragile?
Answer: 4/10 = 0.4. It treats the empirical context distribution as sufficient and assigns zero to every unseen continuation; sparse or shifted corpora make that unreliable.
Exam lens
Always write the chain rule, then the Markov approximation, then the count ratio. State why <s> and </s> matter and why unsmoothed models fail.
Rapid revision checklist
- Define n-gram and history length.
- Derive MLE from counts.
- Contrast interpolation and backoff.
- Explain zero probabilities and boundary markers.
Key takeaways
- N-grams replace unlimited history with a fixed window.
- Bigram/trigram probabilities come from normalized counts.
- Higher order gives context but increases sparsity; smoothing/backoff trade precision for coverage.