### Step 1: trigram counts ```python from collections import Counter, defaultdict def train_ngram(corpus_tokens, n=3): ngrams = Counter() contexts = Counter() for sentence in corpus_tokens: padded = ["~~"] * (n - 1) + sentence + ["~~"] for i in range(len(padded) - n + 1): ctx = tuple(padded[i:i + n - 1]) word = padded[i + n - 1] ngrams[ctx + (word,)] += 1 contexts[ctx] += 1 return ngrams, contexts def raw_probability(ngrams, contexts, context, word): ctx = tuple(context) if contexts.get(ctx, 0) == 0: return 0.0 return ngrams.get(ctx + (word,), 0) / contexts[ctx] ``` Input is a list of tokenized sentences. Output is n-gram counts and context counts. `~~` and `~~` are sentence boundaries. ### Step 2: Laplace smoothing ```python def laplace_probability(ngrams, contexts, vocab_size, context, word): ctx = tuple(context) numerator = ngrams.get(ctx + (word,), 0) + 1 denominator = contexts.get(ctx, 0) + vocab_size return numerator / denominator ``` Add 1 to every count. Smooths but over-allocates mass to unseen events, hurting rare-known events too. ### Step 3: Kneser-Ney (bigram, interpolated) ```python def kneser_ney_bigram_model(corpus_tokens, discount=0.75): unigrams = Counter() bigrams = Counter() unigram_contexts = defaultdict(set) for sentence in corpus_tokens: padded = ["~~"] + sentence + ["~~"] for i, w in enumerate(padded): unigrams[w] += 1 if i > 0: prev = padded[i - 1] bigrams[(prev, w)] += 1 unigram_contexts[w].add(prev) total_unique_bigrams = sum(len(ctx_set) for ctx_set in unigram_contexts.values()) continuation_prob = { w: len(ctx_set) / total_unique_bigrams for w, ctx_set in unigram_contexts.items() } context_totals = Counter() for (prev, w), count in bigrams.items(): context_totals[prev] += count unique_follow = defaultdict(set) for (prev, w) in bigrams: unique_follow[prev].add(w) def prob(prev, w): count = bigrams.get((prev, w), 0) denom = context_totals.get(prev, 0) if denom == 0: return continuation_prob.get(w, 1e-9) first_term = max(count - discount, 0) / denom lambda_prev = discount * len(unique_follow[prev]) / denom return first_term + lambda_prev * continuation_prob.get(w, 1e-9) return prob ``` Three moving parts. `continuation_prob` captures "how many different contexts does this word appear in?" (the Kneser-Ney innovation). `lambda_prev` is the mass freed by the discount, used to weight the backoff. The final probability is the discounted main term plus the weighted continuation term. ### Step 4: generating text with sampling ```python import random def generate(prob_fn, vocab, prefix, max_len=30, seed=0): rng = random.Random(seed) tokens = list(prefix) for _ in range(max_len): candidates = [(w, prob_fn(tokens[-1], w)) for w in vocab] total = sum(p for _, p in candidates) r = rng.random() * total acc = 0.0 for w, p in candidates: acc += p if r <= acc: tokens.append(w) break if tokens[-1] == "": break return tokens ``` Sampling proportional to probability. Always gives different output per seed. For beam-search-like output, pick the argmax at each step (greedy) and add a small randomness knob (temperature). ### Step 5: perplexity ```python import math def perplexity(prob_fn, sentences): total_log_prob = 0.0 total_tokens = 0 for sentence in sentences: padded = ["~~"] + sentence + ["~~"] for i in range(1, len(padded)): p = prob_fn(padded[i - 1], padded[i]) total_log_prob += math.log(max(p, 1e-12)) total_tokens += 1 return math.exp(-total_log_prob / total_tokens) ``` Lower is better. For Brown corpus, a well-tuned 4-gram KN model hits perplexity around 140. A transformer LM hits 15-30 on the same test set. The gap is about 10x. That gap is why the field moved on.