N-Gram Smoothing

Add-One Smoothing

𝐏(𝑤₂|𝑤₁) = [𝐶(𝑤₁𝑤₂)+1] / [𝐶(𝑤₁)+𝑉]

where:

• 𝐶(𝑤₁𝑤₂) - counts of 𝑤₁𝑤₂ occuring in corpus
• 𝐶(𝑤₁) - counts of 𝑤₁occuring in corpus
• 𝑉 - vocabulary size

Add-𝑎 Smoothing

𝐏(𝑤₂|𝑤₁) = [𝐶(𝑤₁𝑤₂)+𝑎] / [𝐶(𝑤₁)+𝑎𝑉]

Good-Turing Discounting

𝐏(𝑤₂|𝑤₁) = 𝐏*(𝑤₁𝑤₂) / 𝐏*(𝑤₁)

where:

• 𝐏*(𝑤₁𝑤₂) = ((𝑐₁₂+1)·𝑁_𝑐12+1) / (𝑁_𝑐12·𝑁)
• 𝐏*(𝑤₁) = ((𝑐₁+1)·𝑁_𝑐1+1) / (𝑁_𝑐1·𝑁)

where:

• 𝑐₁₂ = 𝐶(𝑤₁𝑤₂) - counts of 𝑤₁𝑤₂ occuring in corpus
• 𝑐₁ = 𝐶(𝑤₁) - counts of 𝑤₁occuring in corpus
• 𝑁_𝑐 = the number of N-Grams that occur 𝑐 times
• 𝑁 = total number of N-Gram𝑠

Backoff