n-Gram Language Models

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Context Sensitive Spelling Correction

The office is about fifteen minuets from my house

Week 2: Lecture 4

2 / 24

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Context Sensitive Spelling Correction

The office is about fifteen minuets from my house

Week 2: Lecture 4

2 / 24

Context Sensitive Spelling Correction

Use a Language Model

P(about fifteen minutes from) > P(about fifteen minuets from)

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

The office is about fifteen minuets from my house

Week 2: Lecture 4

2 / 24

Probablilistic Language Models: Applications

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Speech Recognition

P(I saw a van) >> P(eyes awe of an)

Week 2: Lecture 4

3 / 24

Probablilistic Language Models: Applications

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Speech Recognition

P(I saw a van) >> P(eyes awe of an)

​

Machine Translation

Which sentence is more plausible in the target language?

P(high winds) > P(large winds)

Week 2: Lecture 4

3 / 24

Probablilistic Language Models: Applications

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Speech Recognition

P(I saw a van) >> P(eyes awe of an)

​

Machine Translation

Which sentence is more plausible in the target language?

P(high winds) > P(large winds)

​

Other Applications

Context Sensitive Spelling Correction Natural Language Generation

...

Week 2: Lecture 4

3 / 24

Completion Prediction

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Language model also supports predicting the completion of a sentence.

• Please turn off your cell ...
• Your program does not ...

Week 2: Lecture 4

4 / 24

Completion Prediction

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Language model also supports predicting the completion of a sentence.

• Please turn off your cell ...
• Your program does not ...

Predictive text input systems can guess what you are typing and give choices on how to complete it.

Week 2: Lecture 4

4 / 24

Probabilistic Language Modeling

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Goal: Compute the probability of a sentence or sequence of words:

​

P(W)= P(w₁, w₂, w₃,..., w_n)

Week 2: Lecture 4

5 / 24

Probabilistic Language Modeling

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Goal: Compute the probability of a sentence or sequence of words:

​

P(W)= P(w₁, w₂, w₃,..., w_n)

​

​

Related Task: probability of an upcoming word:

​

P(w₄|w₁, w₂, w₃)

Week 2: Lecture 4

5 / 24

Probabilistic Language Modeling

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Goal: Compute the probability of a sentence or sequence of words:

​

P(W)= P(w₁, w₂, w₃,..., w_n)

​

​

Related Task: probability of an upcoming word:

​

P(w₄|w₁, w₂, w₃)

​

​

A model that computes either of these is called a language model

Week 2: Lecture 4

5 / 24

Computing P(W)

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

How to compute the joint probability

P(about, fifteen, minutes, from)

​

Basic Idea

Rely on the Chain Rule of Probability

Week 2: Lecture 4

6 / 24

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

The Chain Rule

​

Conditional Probabilities

P(B|A)= ^{P(A, B)}

P(A)

Week 2: Lecture 4

7 / 24

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

The Chain Rule

​

Conditional Probabilities

P(B|A)= ^{P(A, B)}

P(A)

P(A, B)= P(A)P(B|A)

Week 2: Lecture 4

7 / 24

The Chain Rule

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Conditional Probabilities

P(B|A)= ^{P(A, B)}

P(A)

P(A, B)= P(A)P(B|A)

​

More Variables

P(A, B, C, D)= P(A)P(B|A)P(C|A, B)P(D|A, B, C)

Week 2: Lecture 4

7 / 24

The Chain Rule

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Conditional Probabilities

P(B|A)= ^{P(A, B)}

P(A)

P(A, B)= P(A)P(B|A)

​

More Variables

P(A, B, C, D)= P(A)P(B|A)P(C|A, B)P(D|A, B, C)

​

The Chain Rule in General

P(x₁, x₂,..., x_n)= P(x₁)P(x₂|x₁)P(x₃|x₁, x₂) .. . P(x_n|x₁,..., x_n—1)

Week 2: Lecture 4

7 / 24

Probability of words in sentences

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Week 2: Lecture 4

8 / 24

Probability of words in sentences

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

P(“about fifteen minutes from”) =

P(about) x P(fifteen | about) x P(minutes | about fifteen) x P(from | about fifteen minutes)

Week 2: Lecture 4

8 / 24

Estimating These Probability Values

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Count and divide

_{P(office | about fifteen minutes from) =} Count (about fifteen minutes from office)

Count (about fifteen minutes from)

The counts can be estimated from a large corpus of text.

Week 2: Lecture 4

9 / 24

Estimating These Probability Values

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Count and divide

_{P(office | about fifteen minutes from) =} Count (about fifteen minutes from office)

Count (about fifteen minutes from)

​

What is the problem

We may never see enough data for estimating these

Week 2: Lecture 4

9 / 24

Circa 2026:

We have seen “enough” English data

• lexicon, syntax, frequent usage, popular usage, correct usage

… but not enough for

• - reasoning
• - neutral > hateful
• - Unbiased > biased (this is worse)
• - Other languages

Markov Assumption

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Simplifying Assumption: Use only the previous word

P(office | about fifteen minutes from) ≈ P(office | from)

Week 2: Lecture 4

10 / 24

Markov Assumption

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Simplifying Assumption: Use only the previous word

P(office | about fifteen minutes from) ≈ P(office | from)

​

Or the couple previous words

P(office | about fifteen minutes from) ≈ P(office | minutes from)

We can hope to get many more occurrences of these shorter phrases in a large corpus, which will help us better estimate the probabilities.

Week 2: Lecture 4

10 / 24

Markov Assumption

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

More Formally: kth order Markov Model

Chain Rule:

Week 2: Lecture 4

11 / 24

Markov Assumption

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

More Formally: kth order Markov Model

Chain Rule:

​

We approximate each component in the product

Week 2: Lecture 4

11 / 24

N-Gram Models

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

P(office | about fifteen minutes from)

An N-gram model uses only N — 1 words of prior context.

Week 2: Lecture 4

12 / 24

N-Gram Models

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

P(office | about fifteen minutes from)

An N-gram model uses only N — 1 words of prior context.

Unigram: P(office) Bigram: P(office | from)

Trigram: P(office | minutes from)

Unigram model: no context is used

Week 2: Lecture 4

12 / 24

N-Gram Models

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

P(office | about fifteen minutes from)

An N-gram model uses only N — 1 words of prior context.

Unigram: P(office) Bigram: P(office | from)

Trigram: P(office | minutes from)

​

Markov model and Language Model

Week 2: Lecture 4

12 / 24

N-Gram Models

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

P(office | about fifteen minutes from)

An N-gram model uses only N — 1 words of prior context.

Unigram: P(office) Bigram: P(office | from)

Trigram: P(office | minutes from)

​

Markov model and Language Model

An N-gram model is an N — 1-order Markov Model

Week 2: Lecture 4

12 / 24

N-Gram Models

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

We can extend to trigrams, 4-grams, 5-grams In general, an insufficient model of language:

Week 2: Lecture 4

13 / 24

N-Gram Models

We can extend to trigrams, 4-grams, 5-grams In general, an insufficient model of language:

language has long-distance dependencies:

“The computer which I had just put into the machine room on the fifth floor crashed.”

​

​

For any reasonable value of n, a n-gram language model cannot completely model a natural language.

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Week 2: Lecture 4

13 / 24

Theoretically, true..

But, LLMs are also statistical..

Approximate (1000-gram model)

+ IF

+RLHF

N-Gram Models

We can extend to trigrams, 4-grams, 5-grams In general, an insufficient model of language:

language has long-distance dependencies:

“The computer which I had just put into the machine room on the fifth floor crashed.”

In most of the applications, we can get away with N-gram models

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Week 2: Lecture 4

13 / 24

Estimating N-grams probabilities

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

How to estimate the n-gram probabilities from a large text corpus?

Week 2: Lecture 4

14 / 24

Estimating N-grams probabilities

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Maximum Likelihood Estimate

Value that makes the observed data the “most probable”

Week 2: Lecture 4

14 / 24

An Example

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

<s>I am here </s>

<s>who am I </s>

<s>I would like to know </s>

Week 2: Lecture 4

15 / 24

An Example

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

<s>I am here </s>

<s>who am I </s>

<s>I would like to know </s>

Estimating bigrams

P(I|<s>) =

P(</s>|here) = P(would | I) = P(here | am) = P(know | like) =

Week 2: Lecture 4

15 / 24

An Example

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

<s>I am here </s>

<s>who am I </s>

<s>I would like to know </s>

Estimating bigrams

P(I|<s>) = 2/3

P(</s>|here) =1 P(would | I) = 1/3 P(here | am) = 1/2 P(know | like) = 0

​

So, given a corpus, we can easily estimate such probabilities.

The larger the corpus, the better will be the probability estimates.

Week 2: Lecture 4

15 / 24

Bigram counts from 9222 Restaurant Sentences

N-gram Language Models

16 / 24

Pawan Goyal (IIT Kharagpur)

Some frequent bigrams:

I want want to to eat

eat lunch to spend

Week 2: Lecture 4

Computing bigram probabilities

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Normlize by unigrams

To compute the bigram probabilities, we also need the frequencies of each unigram.

​

​

P( want | i ) = c( i want ) / c( i ) = 827 / 2533 = 0.33

Week 2: Lecture 4

17 / 24

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Computing bigram probabilities

​

Normlize by unigrams

Bigram Probabilities

Week 2: Lecture 4

17 / 24

Computing Sentence Probabilities

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

Now, we know how to estimate bigram probabilities from a given text corpus.

​

Next, how to estimate the probability of a sentence / phrase?

​

P(<s> I want english food </s>)

= P(I | <s>) x P(want | I) x P(english | want) x P(food | english ) x P(</s> | food)

Week 2: Lecture 4

18 / 24

Computing Sentence Probabilities

N-gram Language Models

Pawan Goyal (IIT Kharagpur)

P(<s> I want english food </s>)

= P(I | <s>) x P(want | I) x P(english | want) x P(food | english ) x P(</s> | food)

= 0.000031

Using the chain rule of probabilities, with a first order Markov assumption.

Week 2: Lecture 4

18 / 24

Now that we know how to compute the probability of a sentence / phrase, we can do many practical tasks:

​

Query completion

Predicting the next word as one types Deciding which translation is more ‘natural’ Context-sensitive spelling correction

What knowledge does n-gram represent?

N-gram Language Models

19 / 24

Pawan Goyal (IIT Kharagpur)

P(english|want) = .0011

P(chinese|want) = .0065

P(to|want) = .66 P(eat | to) = .28 P(food | to) = 0 P(want | spend) = 0 P (i | <s>) = .25

For the given corpus (food), Chinese is more desirable then English

Week 2: Lecture 4

Usually, a verb comes after ‘to’, not a noun

Many sentences start with ‘I’

Two verbs, e.g., ‘want’ and ‘spend’ do not come consecutively

Next word prediction ideally requires reasoning?

Example by Ilya Sutskever!

Practical Issues

N-gram Language Models

20 / 24

Pawan Goyal (IIT Kharagpur)

Adding is faster than multiplying

log(p₁ ⇥ p₂ ⇥ p₃ ⇥ p₄)= logp₁ + logp₂ + logp₃ + logp₄

Everything in log space

Avoids underflow

Handling zeros

Use smoothing

Suppose a sentence contains a bigram that never occurs in

Week 2: Lecture 4

the corpus (from which the language model is learned)

Multiplication of many probability values can lead to underflow (can lead to zero values for small probabilities)

N-gram Language Models

21 / 24

Pawan Goyal (IIT Kharagpur)

Language Modeling Toolkit

SRILM

http://www.speech.sri.com/projects/srilm/

Week 2: Lecture 4

Google N-grams

N-gram Language Models

22 / 24

Pawan Goyal (IIT Kharagpur)

Number of tokens: 1,024,908,267,229 Number of sentences: 95,119,665,584 Number of unigrams: 13,588,391 Number of bigrams: 314,843,401 Number of trigrams: 977,069,902 Number of fourgrams: 1,313,818,354 Number of fivegrams: 1,176,470,663

http://googleresearch.blogspot.in/2006/08/ all-our-n-gram-are-belong-to-you.html

Week 2: Lecture 4

Example from the 4-gram data

N-gram Language Models

23 / 24

Pawan Goyal (IIT Kharagpur)

serve as the inspector 66 serve as the inspiration 1390 serve as the installation 136 serve as the institute 187 serve as the institution 279 serve as the institutional 461

Week 2: Lecture 4

N-gram Language Models

24 / 24

Pawan Goyal (IIT Kharagpur)

Google books Ngram Data

Week 2: Lecture 4