N Gram Model

A Markov Process of order $n-1$.

So for a Bigram model we would have a Markov Chain and for a Trigram model we would have a Markov Process of order $2$.

For Trigram model: $P\left({\mathrm{c}}_i\mid {\mathrm{c}}_{1:i-1}\right)=P\left({\mathrm{c}}_i\mid {\mathrm{c}}_{(i-2)},{\mathrm{c}}_{(i-1)}\right)$ Using the Chain Rule and Markov Property we get for a sequence of characters $P\left({\mathrm{c}}_{1:N}\right)={\prod }_{i=1}^{N}P\left({\mathbf{c}}_i\mid {\mathbf{c}}_{1:i-1}\right)={\prod }_{i=1}^{N}P\left({\mathbf{c}}_i\mid {\mathbf{c}}_{(i-2)},{\mathbf{c}}_{(i-1)}\right)$ Thus, a trigram model for a language with 100 characters, P(c,|ci-2:i-1) has 1.000.000 entries. It can be estimated from a corpus with 107 characters.

Can be used for relatively bad Natural Language Generation or for

• Language Identification
• Spelling Correction
• Genre Classification
• Named Entity Recognition