Phase 05 - Lesson 16

Geração de Texto Antes dos Transformers — Modelos de Linguagem N-grama

This lesson includes a graded coding exercise that runs in your browser, unlocked with lifetime access.

Se uma palavra é surpreendente, o modelo é ruim. A perplexidade transforma a surpresa em um número. A suavização a mantém finita.

Tipo: Build Linguagens: Python Pré-requisitos: Fase 5 · 01 (Processamento de Texto), Fase 2 · 14 (Naive Bayes) Tempo: ~45 minutos

O Problema

Antes dos transformers, antes das RNNs, antes dos word embeddings, um modelo de linguagem previa a próxima palavra contando com que frequência ela seguia as n-1 palavras anteriores. Conte "the cat" → "sat" 47 vezes, "the cat" → "jumped" 12 vezes, "the cat" → "refrigerator" 0 vezes. Normalize para obter uma distribuição de probabilidade.

Isso é um modelo de linguagem n-grama. Ele rodou todo reconhecedor de fala, todo corretor ortográfico e todo sistema de tradução automática baseado em frases de 1980 até 2015. Ele ainda roda quando você precisa de modelagem de linguagem barata no próprio dispositivo.

O problema interessante é o que fazer com n-gramas nunca vistos. Um modelo baseado em contagens brutas atribui probabilidade zero a qualquer coisa que não tenha visto, o que é catastrófico porque sentenças são longas e quase toda sentença longa contém pelo menos uma sequência nunca vista. Cinquenta anos de pesquisa em suavização resolveram isso. A suavização de Kneser-Ney é o resultado, e o deep learning moderno herdou sua tradição empírica.

O Conceito

Probabilidade n-grama: P(w_i | w_{i-n+1}, ..., w_{i-1}). Fixe n (tipicamente 3 para trigramas, 4 para 4-gramas). Compute a partir das contagens:

P(w | context) = count(context, w) / count(context)

O problema da contagem zero. Qualquer n-grama não visto no treino recebe probabilidade zero. Um estudo de 2007 sobre o corpus Brown descobriu que mesmo um modelo de 4-gramas tinha 30% dos 4-gramas de validação (held-out) nunca vistos no treino. Você não consegue avaliar nenhum texto real sem suavização.

Abordagens de suavização, em ordem de sofisticação:

1. Laplace (add-one). Adicione 1 a toda contagem. Simples, péssima em eventos raros.
2. Good-Turing. Realoca massa de probabilidade de eventos de maior frequência para eventos nunca vistos com base na frequência das frequências.
3. Interpolação. Combina estimativas de n-grama, (n-1)-grama, etc., com pesos ajustáveis.
4. Backoff. Se o n-grama tem contagem zero, recua para o (n-1)-grama. O backoff de Katz normaliza isso.
5. Desconto absoluto. Subtraia um desconto fixo D de todas as contagens, redistribua para os nunca vistos.
6. Kneser-Ney. Desconto absoluto mais uma escolha inteligente para o modelo de ordem inferior: usar a probabilidade de continuação (em quantos contextos uma palavra aparece) em vez da frequência bruta.

A intuição de Kneser-Ney é profunda. "San Francisco" é um bigrama comum. O unigrama "Francisco" aparece quase sempre depois de "San". O desconto absoluto ingênuo dá a "Francisco" alta probabilidade unigrama (porque a contagem é alta). Kneser-Ney percebe que "Francisco" aparece em apenas um contexto e diminui sua probabilidade de continuação de acordo. Resultado: um bigrama inédito terminando em "Francisco" recebe a probabilidade baixa apropriada.

Avaliação: perplexidade. O expoente da média do log-verossimilhança negativo por palavra em um conjunto de teste de validação (held-out). Menor é melhor. Uma perplexidade de 100 significa que o modelo está tão confuso quanto estaria escolhendo uniformemente entre 100 palavras.

perplexity = exp(- (1/N) * Σ log P(w_i | context_i))

Construa

Passo 1: contagens de trigramas

from collections import Counter, defaultdict


def train_ngram(corpus_tokens, n=3):
    ngrams = Counter()
    contexts = Counter()
    for sentence in corpus_tokens:
        padded = ["<s>"] * (n - 1) + sentence + ["</s>"]
        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]

A entrada é uma lista de sentenças tokenizadas. A saída são contagens de n-gramas e contagens de contexto. <s> e </s> são fronteiras de sentença.

Passo 2: suavização de Laplace

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

Adiciona 1 a toda contagem. Suaviza, mas aloca massa demais para eventos nunca vistos, prejudicando também os eventos raros conhecidos.

Passo 3: Kneser-Ney (bigrama, interpolado)

def kneser_ney_bigram_model(corpus_tokens, discount=0.75):
    unigrams = Counter()
    bigrams = Counter()
    unigram_contexts = defaultdict(set)

    for sentence in corpus_tokens:
        padded = ["<s>"] + sentence + ["</s>"]
        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

Três partes móveis. continuation_prob captura "em quantos contextos diferentes esta palavra aparece?" (a inovação de Kneser-Ney). lambda_prev é a massa liberada pelo desconto, usada para ponderar o backoff. A probabilidade final é o termo principal descontado mais o termo de continuação ponderado.

Passo 4: gerando texto com amostragem

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] == "</s>":
            break
    return tokens

Amostragem proporcional à probabilidade. Sempre dá uma saída diferente por seed. Para uma saída no estilo busca em feixe (beam search), escolha o argmax em cada passo (greedy) e adicione um pequeno ajuste de aleatoriedade (temperatura).

Passo 5: perplexidade

import math


def perplexity(prob_fn, sentences):
    total_log_prob = 0.0
    total_tokens = 0
    for sentence in sentences:
        padded = ["<s>"] + sentence + ["</s>"]
        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)

Menor é melhor. Para o corpus Brown, um modelo KN de 4-gramas bem ajustado atinge perplexidade em torno de 140. Um LM transformer atinge 15-30 no mesmo conjunto de teste. A diferença é de cerca de 10x. Essa diferença é o motivo pelo qual a área seguiu em frente.

Use

• Ensino de NLP clássico. A exposição mais clara a suavização, MLE e perplexidade que você pode obter.
• KenLM. Biblioteca n-grama de produção. Usada como rescorer em sistemas de fala e MT onde a baixa latência importa.
• Autocompletar no dispositivo. Modelos de trigramas em teclados. Ainda hoje.
• Baselines. Sempre compute a perplexidade de um LM n-grama antes de declarar que seu LM neural é bom. Se seu transformer não vence o KN por uma margem larga, algo está errado.

Entregue

Salve como outputs/prompt-lm-baseline.md:

---
name: lm-baseline
description: Build a reproducible n-gram language model baseline before training a neural LM.
phase: 5
lesson: 16
---

Given a corpus and target use (next-word prediction, rescoring, perplexity baseline), output:

1. N-gram order. Trigram for general English, 4-gram if corpus is large, 5-gram for speech rescoring.
2. Smoothing. Modified Kneser-Ney is the default; Laplace only for teaching.
3. Library. `kenlm` for production, `nltk.lm` for teaching, roll your own only to learn.
4. Evaluation. Held-out perplexity with consistent tokenization between train and test sets.

Refuse to report perplexity computed with different tokenization between systems being compared — perplexity numbers are comparable only under identical tokenization. Flag OOV rate in test set; KN handles OOV poorly unless you reserve a special <UNK> token during training.

Exercícios

1. Fácil. Treine um LM de trigramas em um corpus de 1.000 sentenças de Shakespeare. Gere 20 sentenças. Elas serão localmente plausíveis, mas globalmente incoerentes. Esta é a demonstração canônica.
2. Médio. Implemente perplexidade para seu modelo KN em um conjunto de validação (held-out) de Shakespeare. Compare com Laplace. Você deve ver o KN reduzir a perplexidade em 30-50%.
3. Difícil. Construa um corretor ortográfico de trigramas: dada uma palavra com erro de digitação e seu contexto, gere correções e ranqueie pela probabilidade de contexto sob o LM. Avalie no corpus de ortografia Birkbeck (público).

Termos-chave

Leitura adicional

• Jurafsky and Martin — Speech and Language Processing, Chapter 3 (2026 draft) — o tratamento canônico de LMs n-grama e suavização.
• Chen and Goodman (1998). An Empirical Study of Smoothing Techniques for Language Modeling — o artigo que estabeleceu Kneser-Ney como o melhor suavizador de n-gramas.
• Kneser and Ney (1995). Improved Backing-off for M-gram Language Modeling — o artigo original de KN.
• KenLM — LM n-grama de produção rápido, ainda usado em 2026 para aplicações sensíveis à latência.