2.2. N-Gram Models

N-Gram Language Models

An $n$-gram model is a language model that estimates the probability of a token based on the previous $n-1$ tokens using frequency statistics from a corpus. It assumes a finite Markov dependency structure over sequences. Formally, for a token sequence $w_1,w_2,\dots ,w_T$,
$\mathbb{P}(w_1,\dots ,w_T)={\prod }_{t=1}^T\mathbb{P}(w_t\mid w_{t-n+1},\dots ,w_{t-1}),$
giving an $n$-step approximation of the full distribution $\mathbb{P}(w_t\mid w_1,\dots ,w_{t-1})$. In turn, this results in loss of long-range dependencies in exchange for reduced complexity.

Parameter estimation in n-gram models is grounded in empirical frequency counts from a corpus. Using maximum likelihood estimation, conditional probabilities are computed as normalized counts, such that
$P(w_t\mid h)=\frac{C(h,w_t)+\alpha }{C(h)+\alpha |V|},$
where $h=\{w_{t-n+1},\dots ,w_{t-1}\}$ denotes the context, $|V|$ is the size of the vocabulary, and $\alpha \ge 0$ is a Laplace smoothing constant that alleviates the sparsity problem, where many plausible $n$-grams receive zero probability as $N\to \infty$, simply because they were not observed in the training data.