N-Gram Language Models - A Beginner's Guide
Tags: machinelearning, nlp, python, beginners
Published: 2021-02-28 13:16:29

> Have you ever guessed what the next sentence in the paragraph you’re reading would likely talk about? Have you ever noticed that while reading, you almost always know the next word in the sentence?

Well, the answer to these questions is definitely **Yes**! 

As humans, we’re bestowed with the ability to read, understand languages and **interpret contexts**, and can almost always predict the next word in a text, based on what we’ve read so far.

Can we make a machine learning model do the same? 

Oh yeah! We very well can! And we already use such models everyday, such as the *autocomplete* feature in search engines and messaging apps.

> In the context of Natural Language Processing, the task of predicting which word comes next is called **Language Modeling**.

Let’s take a simple example,
> The students opened their _______.

What are the possible words that we can fill the blank with?
Books📗 📒📚
Notes📖
Laptops👩🏽‍💻
Minds💡🙂
Exams📑❔

Well, the list goes on. Wait…why did we think of these words as the best choices, rather than ‘opened their **doors** or **windows’**? 

It’s because we had the word students, and given the context **‘students’**, the words such as books, notes and laptops seem more likely and therefore have a higher probability of occurrence than the words doors and windows.

Typically, this **probability** is what a language model aims at computing. Over the next few minutes, we’ll see the notion of n-grams, a very effective and popular traditional NLP technique, widely used before deep learning models became popular.
****

## What Does a Language Model Do?

Describing in formal terms,
- Given a text corpus with vocabulary `V` ,
- Given a sequence of words, `x(1),x(2),…,x(t)` ,
A language model essentially computes the **probability distribution of the next word** `x(t+1)` .

![Probability distribution of the next word x(t+1) given x(1)…x(t)](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v0izfsfunm1qgzdb9394.jpeg)


A language model, thus, assigns a probability to a piece of text. The probability can be expressed using chain rule as the product of the following probabilities.
- Probability of the first word being `x(1)`
- Probability of the second word being `x(2)` given that the first word is `x(1)`
- Probability of the third word being `x(3)` given that the first two words are `x(1)` and `x(2)`
- In general, the conditional probability that `x(i)` is word i, given that the first (i-1) words are `x(1),x(2),…,x(i-1)`.

The probability of the text according to the language model is:


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/pukyi64wx92ndnw34gis.jpeg)

****

## To Learn a Language Model, Learn N-Grams!
> An n-gram is a **chunk of n consecutive words**.

For our example, The students opened their _______, the following are the n-grams for n=1,2,3 and 4.

**uni**grams: “the”, “students”, “opened”, ”their”
**bi**grams: “the students”, “students opened”, “opened their”
**tri**grams: “the students opened”, “students opened their”
**4**- grams: “the students opened their”

In an n-gram language model, we make an assumption that the word `x(t+1)` depends only on the previous (n-1) words. The idea is to collect how frequently the n-grams occur in our corpus and use it to predict the next word.


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/h0yx9v1zfdohketcswss.jpg)


This equation, on applying the definition of conditional probability yields,

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/tozjnkv2rgesat94eftt.jpeg)
***
## How Do We Compute These Probabilities?
To compute the probabilities of these n-grams and n-1 grams, we just go ahead and start counting them in a large text corpus! 
The Probability of n-gram/Probability of (n-1) gram is given by:

![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kdh8zmbpmei96xpqg7ra.jpeg)

Let’s learn a 4-gram language model for the example,
> As the proctor started the clock, the students opened their _____


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/iqnm0obhwerc2gl2k1jh.jpg)
In learning a 4-gram language model, the next word (the word that fills up the blank) depends only on the previous 3 words. If `w` is the word that goes into the blank, then we compute the conditional probability of the word `w` as follows:


![Alt Text](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/j59b03uks0rs6nbeo4n8.jpeg)

In the above example, let us say we have the following:
```Python
"students opened their" occurred 1000 times
"students opened their books" occurred 400 times
-> P(books/students opened their) = 0.4
"students opened their exams" occurred 200 times
-> P(exams/students opened their) = 0.2
```

The language model would predict the word **books**; But given the context, is **books** really the right choice? Wouldn’t the word **exams** be a better fit? Recall that we have,
As the proctor started the clock, the students opened their _____
Should we really have discarded the context ‘**proctor**’?
Looks like we shouldn’t have. This leads us to understand some of the problems associated with n-grams.
****
## Disadvantages of N-gram Language Models

### Problem of Sparsity
What if “students opened their” never occurred in the corpus?
>The count term in the denominator would go to zero!

If the (n-1) gram never occurred in the corpus, then we cannot compute the probabilities. In that case, we may have to revert to using “opened their” instead of “students opened their”, and this strategy is called **back-off**.

What if “students opened their w” never occurred in the corpus?
>The count term in the numerator would go to zero!

If word `w` never appeared after the n-1 gram, then we may have to add a small factor `delta` to the count, that accounts for all words in the vocabulary `V` .This is called **‘smoothing’**. Sparsity problem increases with increasing `n`. In practice, `n` cannot be greater than 5.

### Problem of Storage
As we need to store count for all possible n-grams in the corpus, increasing n or increasing the size of the corpus, both tend to become storage-inefficient.

However, n-gram language models can also be used for text generation; a tutorial on generating text using such n-grams can be found in reference[2] given below. 

****
## References
[1] [CS224n: Natural Language Processing with Deep Learning](https://web.stanford.edu/class/archive/cs/cs224n/cs224n.1194/)
[2] [NLP for Hackers](https://nlpforhackers.io/language-models/)
[3] All equations are from the [lecture slides of CS224n](https://web.stanford.edu/class/archive/cs/cs224n/cs224n.1194/slides/cs224n-2019-lecture06-rnnlm.pdf)

Cover Image: <span>Photo by <a href="https://unsplash.com/@brett_jordan?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Brett Jordan</a> on <a href="https://unsplash.com/s/photos/words?utm_source=unsplash&amp;utm_medium=referral&amp;utm_content=creditCopyText">Unsplash</a></span>