N-gram Language Models

An n-gram is a contiguous sequence of items that are collected from a sequence of text or speech corpus. The n in n-grams specifies the number of tokens considered.

Sliding a window of size n along the text, 1 token at a time, produces every n-gram in it. A text of $L$ tokens gives $L-n+1$ n-grams, and neighbouring n-grams overlap because the window moves by 1 token rather than by n.

This model generate sentences in human language. It uses conditional probabilties where it requires the last $n-1$ words to generate the next word $n$

Probability of a Sentence

N-grams are a probabilistic model that computes the probability of a sentence or a given sequence of words.

$$P(W)=P(w_1,w_2,w_3,w_4,\dots w_n)orP(w_5\mid w_1,w_2,w_3,w_4)$$

To compute this probability, we use the chain rule of probability:

$$P(B\mid A)=\frac{P(A,B)}{P(A)}orP(A,B)=P(A)P(B\mid A)$$

With more variables this becomes:

$$P(A,B,C,D)=P(A)P(B\mid A)P(C\mid A,B)P(D\mid A,B,C)$$

• each new word is conditioned on every word before it, so the chain grows by 1 term per word
• as these sentences get longer, the computation for these probabilities becomes increasingly difficult

Markov Assumption

To simplify these probabilities, the Markov assumption is utilised:

$$P(w_n\mid w_1,w_2,w_3,\dots w_{n-1})\approx P(w_n\mid w_{n-1})Unigram$$ $$P(w_n\mid w_1,w_2,w_3,\dots w_{n-1})\approx P(w_n\mid w_{n-2},w_{n-1})Bigram$$ $$P(w_n\mid w_1,w_2,w_3,\dots w_{n-1})\approx P(w_n\mid w_{n-k}\dots ,w_{n-1})k-gram$$

Intuitively, this means the next word in a sentence can be predicted as a probability based on the n number of words that precedes it.

• the full history before the window is thrown away, so only a fixed number of preceding words is kept
• this is what makes the model computable, since a short history has far fewer combinations to count

Counting the Probabilities

Each probability is obtained by counting over the training corpus, and for the bigram case:

$$P(w_i\mid w_{i-1})=\frac{c(w_{i-1},w_i)}{c(w_{i-1})}$$

• $c()$ is a count of how many times that sequence appears in the corpus
• the numerator counts the pair, and the denominator counts the first word on its own
• <s> and </s> mark the start and end of a sentence, so the first word and the sentence ending can be predicted in the same way
• there is no training loop here, since the model is built entirely by counting

Choosing n

Size of n	Effect
small	fewer combinations to count, so the counts are reliable, and very little context is captured
large	more context is captured, and most sequences are never seen in the corpus, so their counts fall to 0

• a sequence unseen in training gets a probability of 0, which is the same zero probability problem that smoothing fixes

• the tokens counted here come from Tokenization, so the choice of tokenizer decides what an n-gram is made of

• the fix for that zero probability is Smoothing