Natural Language Processing · M2 · formulas

Bigram counts: build the table before multiplying

N-grams & probability

Formulas explained through full worked examples

A bigram probability table uses the previous word as its row and the next word as its column. Divide each cell count by its row's total outgoing count. With one end marker on every sentence, each ordinary training word has a continuation, so its outgoing count equals its token frequency. Do not create a bigram that crosses from one sentence into the next.

P(w\mid h)=\frac{C(h,w)}{\sum_{v\in V}C(h,v)}=\frac{C(h,w)}{C(h)}LaTeX: P(w\mid h)=\frac{C(h,w)}{\sum_{v\in V}C(h,v)}=\frac{C(h,w)}{C(h)}
Add boundaries to each sentence separately
List adjacent pairs
Count repeated pairs
Divide each row by its total
Follow the test sentence through the table

Question. Train a bigram model on “I like tea”, “I like coffee” and “you like tea”. Use one start and one end marker. Find the probability of “I like tea”.

Given

Corpus: <s> I like tea </s>; <s> I like coffee </s>; <s> you like tea </s>. Preserve these tokens.

To find

All nonzero bigram estimates and the test probability.

Formula and why it applies

P(w\mid h)=C(h,w)/C(h)LaTeX: P(w\mid h)=C(h,w)/C(h)

Every sentence starts and ends independently. Four probability factors are required for the three test words plus end.

Solution

Step 1. List the training pairs

Sentence 1: (<s>,I), (I,like), (like,tea), (tea,</s>).
Sentence 2: (<s>,I), (I,like), (like,coffee), (coffee,</s>).
Sentence 3: (<s>,you), (you,like), (like,tea), (tea,</s>).

Step 2. Create the nonzero count table
History → nextPair countHistory countProbability
<s> → I232/3
<s> → you131/3
I → like221
you → like111
like → tea232/3
like → coffee131/3
tea → </s>221
coffee → </s>111
Step 3. Write the test path
P=P(I\mid\langle s\rangle)P(like\mid I)P(tea\mid like)P(\langle/s\rangle\mid tea)LaTeX: P=P(I\mid\langle s\rangle)P(like\mid I)P(tea\mid like)P(\langle/s\rangle\mid tea)
Step 4. Substitute each matching row
P=\frac23\times1\times\frac23\times1LaTeX: P=\frac23\times1\times\frac23\times1
Step 5. Multiply
P=\frac49\approx0.444444LaTeX: P=\frac49\approx0.444444
Final answer. P(I like tea) = 4/9 ≈ 0.444444.

Question. Using the same three-sentence corpus given here—“I like tea”, “I like coffee”, “you like tea”—find the bigram probabilities of “you like coffee” and “tea like I”. Include boundaries.

Given

Corpus with one start/end marker per sentence. Counts: start→you=1/3; you→like=1; like→coffee=1/3; coffee→end=1. No training sentence starts with tea.

To find

The two test probabilities.

Formula and why it applies

P(\text{sentence})=\prod P(\text{next token}\mid\text{previous token})LaTeX: P(\text{sentence})=\prod P(\text{next token}\mid\text{previous token})

A model can assign a nonzero probability to a sentence it never saw if all of its local bigrams were seen.

Solution

Step 1. Score you like coffee
P=\frac13\times1\times\frac13\times1=\frac19\approx0.111111LaTeX: P=\frac13\times1\times\frac13\times1=\frac19\approx0.111111
Step 2. Inspect tea like I
P(tea\mid\langle s\rangle)=0/3=0LaTeX: P(tea\mid\langle s\rangle)=0/3=0
Step 3. Apply the zero factor

The full product is zero, regardless of the remaining factors.

Final answer. P(you like coffee) = 1/9; P(tea like I) = 0. A new sentence is not necessarily a zero-probability sentence.

Question. Obtain the unsmoothed bigram probability of “students are from Vellore” from this corpus: “I am from Vellore”; “I am a teacher”; “students are good and are from various cities”; “students from Vellore do engineering”. Use sentence boundaries.

Given

Four training sentences, each padded with one <s> and </s>. Test sequence: <s> students are from Vellore </s>.

To find

The five required conditional probabilities and their product.

Formula and why it applies

P(w\mid h)=C(h,w)/C(h)LaTeX: P(w\mid h)=C(h,w)/C(h)

Count all occurrences in the entire corpus. In particular, are occurs twice inside the third sentence, and Vellore is followed by end once and do once.

Solution

Step 1. Count the histories
HistoryOccurrences with continuation
<s>4
students2
are2
from3
Vellore2
Step 2. Count the required pairs
Required pairCountProbability
<s> students22/4
students are11/2
are from11/2
from Vellore22/3
Vellore </s>11/2
Step 3. Write the complete product
P=\frac24\times\frac12\times\frac12\times\frac23\times\frac12LaTeX: P=\frac24\times\frac12\times\frac12\times\frac23\times\frac12
Step 4. Multiply progressively
\frac24\times\frac12=\frac14,\quad \frac14\times\frac12=\frac18LaTeX: \frac24\times\frac12=\frac14,\quad \frac14\times\frac12=\frac18
\frac18\times\frac23=\frac1{12},\quad \frac1{12}\times\frac12=\frac1{24}LaTeX: \frac18\times\frac23=\frac1{12},\quad \frac1{12}\times\frac12=\frac1{24}
Final answer. P = 1/24 ≈ 0.0416667.

Yaad rakho: Same sentence mein word do baar aaye toh count bhi do.