Markov Assumptions and Sparse Counts

An n-gram model makes a Markov assumption: only a fixed amount of recent context is used.

A bigram model uses one previous token. A trigram model uses two previous tokens. A 5-gram model uses four previous tokens.

Longer context can be more informative, but it creates a sparse-count problem. Many long contexts appear rarely or never, even in a large corpus.

Example

The context:

the model learned

may appear often. The longer context:

after three small updates the model learned

may appear once or not at all.

If the model has never seen a context, a plain count estimate has no reliable next-token distribution.

Exercise

In a trigram model, how many previous tokens are used as context?