ConceptDBISAI-written · not yet proofread

N-Gram Model

Also N-gram Model · Unigram Model · Bigram Model · Trigram Model

An n-gram model is a count-based language model that gives, for each sequence of n − 1 previous tokens, a probability distribution over the next token, estimated by counting n-grams in a training text and normalizing.

Know these firstLanguage Model

Definition

Let $V$ be the vocabulary (set of distinct tokens) and $n \in \mathbb{N}$ . An n-gram is a sequence of $n$ tokens. An n-gram model is a language model that gives, for each sequence $v_1 \dots v_{n-1} \in V^{n-1}$ of previous tokens (the context), a probability distribution $\Pr(\cdot \mid v_1 \dots v_{n-1})$ over the next token $v \in V$ .

$n = 1$ , unigram model: a single distribution $\Pr(v)$ over $V$ , independent of the context.
$n = 2$ , bigram model: one distribution $\Pr(\cdot \mid v_1)$ per previous token $v_1$ .
$n = 3$ , trigram model: one distribution $\Pr(\cdot \mid v_1 v_2)$ per pair of previous tokens.

Formula#

Learning from a text (counting). Let $\#s$ be the number of occurrences of the token sequence $s$ in the training text. Then

\Pr(v) = \frac{\#v}{|\text{text}|}, \qquad \Pr(v \mid v_1 \dots v_{n-1}) = \frac{\#v_1 \dots v_{n-1} v}{\sum_{u \in V} \#v_1 \dots v_{n-1} u}.

Generating text (sampling via cumulative counts). Let $V = (v_1, \dots, v_m)$ with counts $\#v_1, \dots, \#v_m$ (for $n \ge 2$ : the counts of the current context, i.e. the last $n - 1$ generated tokens).

Compute the cumulative counts $c_j = \sum_{i \le j} \#v_i$ , $j = 1, \dots, m$ .
Pick a random integer $r \in \{1, \dots, c_m\}$ .
Find the smallest $j$ with $r \le c_j$ .
Output $v_j$ .

Exactly $\#v_j$ values of $r$ map to $v_j$ , so $v_j$ is generated with probability $\#v_j / c_m$ . A unigram model picks each token independently of the previous ones.

def make_counts_cumulative(counts: list[int]):
    for i in range(1, len(counts)):
        counts[i] += counts[i - 1]

def random_char(cumulative_counts: list[int]) -> str:
    r = random.randint(1, cumulative_counts[-1])
    for i, ci in enumerate(cumulative_counts):
        if r <= cumulative_counts[i]:
            return chr(i + ord(" "))

(Lecture code: character tokens, vocabulary = printable ASCII from " " to "~", trained on the ES11 movie plots.)

Properties#

Model	$n$	Conditions on	Probability	# distributions	# possible n-grams ( $\lvert V \rvert = 100$ )
Unigram	1	nothing	$\Pr(v)$	$1$	$100$
Bigram	2	previous token $v_1$	$\Pr(v \mid v_1)$	$\lvert V \rvert$	$10\,000$
Trigram	3	previous two tokens $v_1 v_2$	$\Pr(v \mid v_1 v_2)$	$\lvert V \rvert^2$	$10^6$

Size: there are $|V|^n$ possible n-grams ( $|V|^{n-1}$ contexts), exponential in $n$ , so large $n$ is infeasible. Solution: neural language models.
Unseen contexts and smoothing: many $(n-1)$ -token contexts never occur in the training text, so the model has no distribution for them. Remedy: pick the next token at random (uniformly). This is called smoothing, because it changes the probability distribution.
Tokens: the lecture’s n-gram models use characters as tokens; modern language models use subwords.

Example#

Sources#

Slides 12, p. 5 (unigram), Slides 12, p. 6 (generating text), Slides 12, p. 7 (bigram), Slides 12, p. 8 (trigram), Slides 12, p. 9 (n-gram, size, smoothing)
DBIS_VL12 > Count-based n-gram models, DBIS_VL12 > Generating text with a unigram model, DBIS_VL12 > Bigram model, DBIS_VL12 > Trigram model, DBIS_VL12 > General n-gram models
Exam: DBIS Exam WS2324-2 (not published) Task 5.3 (top- $k$ sampling from a next-token distribution)

Connections

Prerequisites know first1

Language Model

Mentioned in inline links7

Hidden Markov Model
Markov property: $h_i$ depends only on $h_{i-1}$ , not on earlier states or observations. The hidden states form a bigram model (N-Gram Model with $n = 2$ ) over $H$ . §
Language Model
| | Count-based (N-Gram Model) | Neural language model | §
Generating text: repeatedly pick a next token from the distribution (e.g. via cumulative counts, N-Gram Model), append it to the prompt, repeat. LLM services return the next $k$ tokens at once. §
Large Language Model
In the live demo, this instruct model got the system prompt “Act like a character-based language model and predict the next characters” and was compared with the unigram, bigram and trigram models (N-Gram Model) on the same prompt. §
Softmax
Neural language models (see N-Gram Model for the count-based variant) turn their output scores over the vocabulary into a next-token distribution with softmax. §
VL12 – N-gram Models, LLMs, RAG
The N-Gram Model generalizes this to arbitrary $n \in \mathbb{N}$ : for each sequence of $n - 1$ previous tokens, a distribution over the next token. Two problems arise (Slide 9): §
N-Gram Model — unigram, bigram, trigram models learned from counts; $|V|^n$ blow-up and smoothing §
POS-Tagging
Mapping: tags $\to$ hidden states $H$ ; words $\to$ observables $O$ . Transition probabilities $\Pr(t' \mid t)$ are a bigram model over tags (N-Gram Model), emission probabilities $\Pr(w \mid t)$ say which words a tag produces. All parameter… §
Word Embeddings and Language Models — N-Gram Model as the model for the tag transitions §
Word Embeddings and Language Models
N-Gram Model — count-based language model (unigram, bigram, trigram), sampling via cumulative counts §
Unigram → bigram → trigram: condition on $0$ , $1$ , $2$ previous tokens; learn by counting and normalizing; generate by sampling via cumulative counts. §

Search in these mentions →

context	$\Pr(a \mid \cdot)$	$\Pr(b \mid \cdot)$
$aa$	$3/4$	$1/4$
$ab$	$1/2$	$1/2$
$ba$	$1$	$0$
$bb$	$1/2$	$1/2$