Phase 01 - Lesson 16

Métodos de Amostragem

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

A amostragem é como a IA explora o espaço de possibilidades.

Tipo: Construir Linguagem: Python Pré-requisitos: Fase 1, Lições 06-07 (Probabilidade, Teorema de Bayes) Tempo: ~120 minutos

Objetivos de Aprendizagem

• Implementar amostragem por CDF inversa, por rejeição e por importância do zero usando apenas números aleatórios uniformes
• Construir amostragem por temperatura, top-k e top-p (núcleo) para a geração de tokens de modelos de linguagem
• Explicar o truque da reparametrização e por que ele viabiliza a retropropagação através da amostragem em VAEs
• Rodar MCMC de Metropolis-Hastings para amostrar de uma distribuição alvo não normalizada

O Problema

Um modelo de linguagem termina de processar seu prompt e produz um vetor de 50.000 logits. Um para cada token em seu vocabulário. Agora ele tem que escolher um. Como?

Se ele sempre escolhe o token de maior probabilidade, toda resposta é idêntica. Determinística. Entediante. Se ele escolhe uniformemente ao acaso, a saída é sem sentido. A resposta vive em algum lugar entre esses extremos, e esse algum lugar é controlado pela amostragem.

A amostragem não se limita à geração de texto. O aprendizado por reforço estima gradientes de política amostrando trajetórias. VAEs aprendem representações latentes amostrando de distribuições aprendidas e retropropagando através da aleatoriedade. Modelos de difusão geram imagens amostrando ruído e removendo o ruído iterativamente. Métodos de Monte Carlo estimam integrais que não têm solução fechada. Algoritmos de MCMC exploram distribuições posteriores de alta dimensão impossíveis de enumerar.

Todo sistema de IA generativa é um sistema de amostragem. A estratégia de amostragem determina a qualidade, a diversidade e a controlabilidade da saída. Esta lição constrói todo método de amostragem importante do zero, começando por números aleatórios uniformes e terminando com as técnicas que dão energia aos LLMs e modelos generativos modernos.

O Conceito

Por que a Amostragem Importa

A amostragem aparece em quatro papéis fundamentais ao longo da IA e do aprendizado de máquina:

Geração. Modelos de linguagem, modelos de difusão e GANs produzem saída por amostragem. O algoritmo de amostragem controla diretamente a criatividade, a coerência e a diversidade. Temperatura, top-k e amostragem por núcleo são os botões que os engenheiros giram diariamente.

Treinamento. O gradiente descendente estocástico amostra mini-batches. O dropout amostra neurônios para desativar. A ampliação de dados (data augmentation) amostra transformações aleatórias. A amostragem por importância repondera amostras para reduzir a variância do gradiente no aprendizado por reforço (PPO, TRPO).

Estimação. Muitas quantidades em ML não têm solução fechada. A loss esperada sobre uma distribuição de dados, a função de partição de um modelo baseado em energia, a evidência na inferência bayesiana. A estimação de Monte Carlo aproxima todas elas por meio da média sobre amostras.

Exploração. Algoritmos de MCMC exploram distribuições posteriores na inferência bayesiana. Estratégias evolutivas amostram perturbações de parâmetros. A amostragem de Thompson equilibra exploração e explotação em bandits.

O desafio central: você só consegue amostrar diretamente de distribuições simples (uniforme, normal). Para todo o resto, você precisa de um método para converter amostras simples em amostras da sua distribuição alvo.

Amostragem Aleatória Uniforme

Todo método de amostragem começa aqui. Um gerador de números aleatórios uniformes produz valores em [0, 1) onde todo subintervalo de mesmo comprimento tem igual probabilidade.

U ~ Uniform(0, 1)

P(a <= U <= b) = b - a    for 0 <= a <= b <= 1

Properties:
  E[U] = 0.5
  Var(U) = 1/12

Para amostrar uniformemente de um conjunto discreto de n itens, gere U e retorne floor(n * U). Para amostrar de uma faixa contínua [a, b], calcule a + (b - a) * U.

A percepção-chave: um único número aleatório uniforme contém exatamente a quantidade certa de aleatoriedade para produzir uma amostra de qualquer distribuição. O truque é encontrar a transformação certa.

Método da CDF Inversa (Amostragem por Transformação Inversa)

A função de distribuição acumulada (CDF) mapeia valores para probabilidades:

F(x) = P(X <= x)

Properties:
  F is non-decreasing
  F(-inf) = 0
  F(+inf) = 1
  F maps the real line to [0, 1]

A CDF inversa mapeia probabilidades de volta para valores. Se U ~ Uniform(0, 1), então X = F_inverse(U) segue a distribuição alvo.

Algorithm:
  1. Generate u ~ Uniform(0, 1)
  2. Return F_inverse(u)

Why it works:
  P(X <= x) = P(F_inverse(U) <= x) = P(U <= F(x)) = F(x)

Exemplo da distribuição exponencial:

PDF: f(x) = lambda * exp(-lambda * x),   x >= 0
CDF: F(x) = 1 - exp(-lambda * x)

Solve F(x) = u for x:
  u = 1 - exp(-lambda * x)
  exp(-lambda * x) = 1 - u
  x = -ln(1 - u) / lambda

Since (1 - U) and U have the same distribution:
  x = -ln(u) / lambda

Isso funciona perfeitamente quando você consegue escrever F_inverse em forma fechada. Para a distribuição normal, não há CDF inversa em forma fechada, então usamos outros métodos (Box-Muller, ou aproximação numérica).

Versão discreta: Para distribuições discretas, construa a CDF como uma soma acumulada, gere U e encontre o primeiro índice onde a soma acumulada ultrapassa U. É assim que sample_categorical funciona na Lição 06.

Amostragem por Rejeição

Quando você não consegue inverter a CDF mas consegue avaliar a PDF alvo a menos de uma constante, a amostragem por rejeição funciona.

Target distribution: p(x)  (can evaluate, possibly unnormalized)
Proposal distribution: q(x)  (can sample from)
Bound: M such that p(x) <= M * q(x) for all x

Algorithm:
  1. Sample x ~ q(x)
  2. Sample u ~ Uniform(0, 1)
  3. If u < p(x) / (M * q(x)), accept x
  4. Otherwise, reject and go to step 1

Acceptance rate = 1/M

Quanto mais justo o limite M, maior a taxa de aceitação. Em baixas dimensões (1-3), a amostragem por rejeição funciona bem. Em altas dimensões, a taxa de aceitação cai exponencialmente porque a maior parte do volume da proposta é rejeitada. Essa é a maldição da dimensionalidade para a amostragem por rejeição.

Exemplo: amostrar de uma normal truncada. Use uma proposta uniforme sobre a faixa truncada. O envelope M é o máximo da PDF normal nessa faixa.

Exemplo: amostrar de um semicírculo. Proponha uniformemente no retângulo delimitador. Aceite se o ponto cair dentro do semicírculo. É assim que o Monte Carlo calcula pi: a taxa de aceitação é igual à razão de áreas pi/4.

Amostragem por Importância

Às vezes você não precisa de amostras da distribuição alvo p(x). Você precisa estimar uma esperança sob p(x), e você tem amostras de uma distribuição diferente q(x).

Goal: estimate E_p[f(x)] = integral of f(x) * p(x) dx

Rewrite:
  E_p[f(x)] = integral of f(x) * (p(x)/q(x)) * q(x) dx
            = E_q[f(x) * w(x)]

where w(x) = p(x) / q(x)  are the importance weights.

Estimator:
  E_p[f(x)] ~ (1/N) * sum(f(x_i) * w(x_i))    where x_i ~ q(x)

Isso é crítico no aprendizado por reforço. No PPO (Proximal Policy Optimization), você coleta trajetórias sob uma política antiga pi_old mas quer otimizar uma política nova pi_new. O peso de importância é pi_new(a|s) / pi_old(a|s). O PPO recorta esses pesos para evitar que a nova política divirja demais da antiga.

A variância do estimador de amostragem por importância depende de quão similar q é de p. Se q é muito diferente de p, algumas amostras recebem pesos enormes e dominam a estimativa. A amostragem por importância autonormalizada divide pela soma dos pesos para reduzir esse problema:

E_p[f(x)] ~ sum(w_i * f(x_i)) / sum(w_i)

Estimação de Monte Carlo

A estimação de Monte Carlo aproxima integrais por meio da média de amostras aleatórias. A lei dos grandes números garante a convergência.

Goal: estimate I = integral of g(x) dx over domain D

Method:
  1. Sample x_1, ..., x_N uniformly from D
  2. I ~ (Volume of D / N) * sum(g(x_i))

Error: O(1 / sqrt(N))   regardless of dimension

A taxa de erro é independente da dimensão. É por isso que os métodos de Monte Carlo dominam em altas dimensões, onde a integração baseada em grade é impossível.

Estimando pi:

Sample (x, y) uniformly from [-1, 1] x [-1, 1]
Count how many fall inside the unit circle: x^2 + y^2 <= 1
pi ~ 4 * (count inside) / (total count)

Estimando esperanças:

E[f(X)] ~ (1/N) * sum(f(x_i))    where x_i ~ p(x)

The sample mean converges to the true expectation.
Variance of the estimator = Var(f(X)) / N

Markov Chain Monte Carlo (MCMC): Metropolis-Hastings

O MCMC constrói uma cadeia de Markov cuja distribuição estacionária é a distribuição alvo p(x). Após passos suficientes, as amostras da cadeia são (aproximadamente) amostras de p(x).

Target: p(x)  (known up to a normalizing constant)
Proposal: q(x'|x)  (how to propose the next state given the current state)

Metropolis-Hastings algorithm:
  1. Start at some x_0
  2. For t = 1, 2, ..., T:
     a. Propose x' ~ q(x'|x_t)
     b. Compute acceptance ratio:
        alpha = [p(x') * q(x_t|x')] / [p(x_t) * q(x'|x_t)]
     c. Accept with probability min(1, alpha):
        - If u < alpha (u ~ Uniform(0,1)): x_{t+1} = x'
        - Otherwise: x_{t+1} = x_t
  3. Discard first B samples (burn-in)
  4. Return remaining samples

Para propostas simétricas (q(x'|x) = q(x|x')), a razão se simplifica para p(x')/p(x). Esse é o algoritmo de Metropolis original.

Por que funciona. A regra de aceitação garante o balanço detalhado: a probabilidade de estar em x e se mover para x' é igual à probabilidade de estar em x' e se mover para x. O balanço detalhado implica que p(x) é a distribuição estacionária da cadeia.

Considerações práticas:

• Burn-in: descarte as amostras iniciais antes de a cadeia atingir o equilíbrio
• Afinamento (thinning): mantenha a cada k-ésima amostra para reduzir a autocorrelação
• Escala da proposta: pequena demais e a cadeia se move devagar (alta aceitação, exploração lenta); grande demais e a maioria das propostas é rejeitada (baixa aceitação, presa no lugar)
• A taxa de aceitação ótima para uma proposta gaussiana em altas dimensões é aproximadamente 0.234

Amostragem de Gibbs

A amostragem de Gibbs é um caso especial de MCMC para distribuições multivariadas. Em vez de propor um movimento em todas as dimensões de uma vez, ela atualiza uma variável por vez a partir de sua distribuição condicional.

Target: p(x_1, x_2, ..., x_d)

Algorithm:
  For each iteration t:
    Sample x_1^{t+1} ~ p(x_1 | x_2^t, x_3^t, ..., x_d^t)
    Sample x_2^{t+1} ~ p(x_2 | x_1^{t+1}, x_3^t, ..., x_d^t)
    ...
    Sample x_d^{t+1} ~ p(x_d | x_1^{t+1}, x_2^{t+1}, ..., x_{d-1}^{t+1})

A amostragem de Gibbs exige que você consiga amostrar de cada distribuição condicional p(x_i | x_{-i}). Isso é direto para muitos modelos:

• Redes bayesianas: as condicionais seguem da estrutura do grafo
• Misturas gaussianas: as condicionais são gaussianas
• Modelos de Ising: a condicional de cada spin depende apenas de seus vizinhos

A taxa de aceitação é sempre 1 (toda proposta é aceita) porque amostrar da condicional exata satisfaz automaticamente o balanço detalhado.

Limitação. Quando as variáveis são altamente correlacionadas, a amostragem de Gibbs mistura devagar porque atualizar uma variável por vez não consegue fazer grandes movimentos diagonais pela distribuição.

Amostragem por Temperatura (Usada em LLMs)

Modelos de linguagem produzem logits z_1, ..., z_V para cada token no vocabulário. O softmax os converte em probabilidades. A temperatura reescala os logits antes do softmax:

p_i = exp(z_i / T) / sum(exp(z_j / T))

T = 1.0: standard softmax (original distribution)
T -> 0:  argmax (deterministic, always picks highest logit)
T -> inf: uniform (all tokens equally likely)
T < 1.0: sharpens the distribution (more confident, less diverse)
T > 1.0: flattens the distribution (less confident, more diverse)

Por que funciona. Dividir os logits por T < 1 amplifica as diferenças entre os logits. Se z_1 = 2 e z_2 = 1, dividir por T = 0.5 dá z_1/T = 4 e z_2/T = 2, tornando a diferença maior. Após o softmax, o token de maior logit recebe uma parcela muito maior.

Na prática:

• T = 0.0: decodificação gulosa, melhor para perguntas e respostas factuais
• T = 0.3-0.7: levemente criativa, boa para geração de código
• T = 0.7-1.0: equilibrada, boa para conversa geral
• T = 1.0-1.5: escrita criativa, brainstorming
• T > 1.5: cada vez mais aleatória, raramente útil

A temperatura não muda quais tokens são possíveis. Ela muda a massa de probabilidade alocada a cada token.

Amostragem Top-k

A amostragem top-k restringe o conjunto de candidatos aos k tokens com as maiores probabilidades, depois renormaliza e amostra desse conjunto restrito.

Algorithm:
  1. Compute softmax probabilities for all V tokens
  2. Sort tokens by probability (descending)
  3. Keep only the top k tokens
  4. Renormalize: p_i' = p_i / sum(p_j for j in top-k)
  5. Sample from the renormalized distribution

k = 1:  greedy decoding
k = V:  no filtering (standard sampling)
k = 40: typical setting, removes long tail of unlikely tokens

A top-k impede que o modelo selecione tokens extremamente improváveis (erros de digitação, bobagens) que existem na cauda longa da distribuição do vocabulário. O problema: k é fixo independentemente do contexto. Quando o modelo está confiante (um token tem 95% de probabilidade), k = 40 ainda permite 39 alternativas. Quando o modelo está incerto (a probabilidade está espalhada por 1000 tokens), k = 40 corta opções plausíveis.

Amostragem Top-p (Núcleo)

A amostragem top-p ajusta dinamicamente o tamanho do conjunto de candidatos. Em vez de manter um número fixo de tokens, ela mantém o menor conjunto de tokens cuja probabilidade acumulada ultrapassa p.

Algorithm:
  1. Compute softmax probabilities for all V tokens
  2. Sort tokens by probability (descending)
  3. Find smallest k such that sum of top-k probabilities >= p
  4. Keep only those k tokens
  5. Renormalize and sample

p = 0.9:  keeps tokens covering 90% of probability mass
p = 1.0:  no filtering
p = 0.1:  very restrictive, nearly greedy

Quando o modelo está confiante, a amostragem por núcleo mantém poucos tokens (talvez 2-3). Quando o modelo está incerto, ela mantém muitos (talvez 200). Esse comportamento adaptativo é por que a amostragem por núcleo geralmente produz melhor texto que a top-k.

Combinações comuns:

• Temperatura 0.7 + top-p 0.9: boa configuração de propósito geral
• Temperatura 0.0 (gulosa): melhor para tarefas determinísticas
• Temperatura 1.0 + top-k 50: a configuração do paper original de Fan et al. (2018)

A top-k e a top-p podem ser combinadas. Aplique a top-k primeiro, depois a top-p no conjunto restante.

Truque da Reparametrização (Usado em VAEs)

Autoencoders variacionais (VAEs) aprendem codificando entradas em uma distribuição no espaço latente, amostrando dessa distribuição e decodificando a amostra de volta. O problema: você não consegue retropropagar através de uma operação de amostragem.

Standard sampling (not differentiable):
  z ~ N(mu, sigma^2)

  The randomness blocks gradient flow.
  d/d_mu [sample from N(mu, sigma^2)] = ???

O truque da reparametrização separa a aleatoriedade dos parâmetros:

Reparameterized sampling:
  epsilon ~ N(0, 1)          (fixed random noise, no parameters)
  z = mu + sigma * epsilon   (deterministic function of parameters)

  Now z is a deterministic, differentiable function of mu and sigma.
  d(z)/d(mu) = 1
  d(z)/d(sigma) = epsilon

  Gradients flow through mu and sigma.

Isso funciona porque N(mu, sigma^2) tem a mesma distribuição que mu + sigma * N(0, 1). A percepção-chave: mova a aleatoriedade para uma fonte sem parâmetros (epsilon), depois expresse a amostra como uma transformação diferenciável dos parâmetros.

No loop de treinamento do VAE:

1. O encoder produz mu e log(sigma^2) para cada entrada
2. Amostre epsilon ~ N(0, 1)
3. Calcule z = mu + sigma * epsilon
4. Decodifique z para reconstruir a entrada
5. Retropropague pelos passos 4, 3, 2, 1 (possível porque o passo 3 é diferenciável)

Sem o truque da reparametrização, VAEs não podem ser treinados com retropropagação padrão. Essa única percepção tornou os VAEs práticos.

Gumbel-Softmax (Amostragem Categórica Diferenciável)

O truque da reparametrização funciona para distribuições contínuas (gaussiana). Para distribuições categóricas discretas, precisamos de uma abordagem diferente. O Gumbel-Softmax fornece uma aproximação diferenciável da amostragem categórica.

O truque Gumbel-Max (não diferenciável):

To sample from a categorical distribution with log-probabilities log(p_1), ..., log(p_k):
  1. Sample g_i ~ Gumbel(0, 1) for each category
     (g = -log(-log(u)), where u ~ Uniform(0, 1))
  2. Return argmax(log(p_i) + g_i)

This produces exact categorical samples.

Gumbel-Softmax (aproximação diferenciável):

Replace the hard argmax with a soft softmax:
  y_i = exp((log(p_i) + g_i) / tau) / sum(exp((log(p_j) + g_j) / tau))

tau (temperature) controls the approximation:
  tau -> 0:  approaches a one-hot vector (hard categorical)
  tau -> inf: approaches uniform (1/k, 1/k, ..., 1/k)
  tau = 1.0: soft approximation

O Gumbel-Softmax produz um relaxamento contínuo de uma amostra discreta. A saída é um vetor de probabilidade (one-hot suave) em vez de um one-hot rígido. Os gradientes fluem pelo softmax. Durante o forward pass no treinamento, você pode usar o estimador "straight-through": use o argmax rígido para o forward pass mas os gradientes suaves do Gumbel-Softmax para o backward pass.

Aplicações:

• Variáveis latentes discretas em VAEs
• Busca de arquitetura neural (escolha de operações discretas)
• Mecanismos de atenção rígida (hard attention)
• Aprendizado por reforco com ações discretas

Amostragem Estratificada

A amostragem padrão de Monte Carlo pode deixar lacunas no espaço amostral por acaso. A amostragem estratificada força uma cobertura uniforme dividindo o espaço em estratos e amostrando de cada um.

Standard Monte Carlo:
  Sample N points uniformly from [0, 1]
  Some regions may have clusters, others gaps

Stratified sampling:
  Divide [0, 1] into N equal strata: [0, 1/N), [1/N, 2/N), ..., [(N-1)/N, 1)
  Sample one point uniformly within each stratum
  x_i = (i + u_i) / N   where u_i ~ Uniform(0, 1),  i = 0, ..., N-1

A amostragem estratificada sempre tem variância menor ou igual comparada a Monte Carlo padrão:

Var(stratified) <= Var(standard Monte Carlo)

The improvement is largest when f(x) varies smoothly.
For piecewise-constant functions, stratified sampling is exact.

Aplicações:

• Integração numérica (quasi-Monte Carlo)
• Splits de dados de treinamento (garantindo o balanço de classes em cada fold)
• Amostragem por importância com estratificação (combinando ambas as técnicas)
• NeRF (Neural Radiance Fields) usa amostragem estratificada ao longo dos raios da câmera

Conexão com Modelos de Difusão

Modelos de difusão geram imagens por meio de um processo de amostragem. O processo direto adiciona ruído gaussiano a uma imagem ao longo de T passos até ela se tornar ruído puro. O processo reverso aprende a remover o ruído, recuperando a imagem original passo a passo.

Forward process (known):
  x_t = sqrt(alpha_t) * x_{t-1} + sqrt(1 - alpha_t) * epsilon
  where epsilon ~ N(0, I)

  After T steps: x_T ~ N(0, I)  (pure noise)

Reverse process (learned):
  x_{t-1} = (1/sqrt(alpha_t)) * (x_t - (1 - alpha_t)/sqrt(1 - alpha_bar_t) * epsilon_theta(x_t, t)) + sigma_t * z
  where z ~ N(0, I)

  Each denoising step is a sampling step.

A conexão com os métodos desta lição:

• Cada passo de remoção de ruído usa o truque da reparametrização (amostre ruído, aplique transformação determinística)
• O cronograma de ruído {alpha_t} controla uma forma de recozimento de temperatura (temperature annealing)
• O treinamento usa a estimação de Monte Carlo para aproximar o ELBO (limite inferior da evidência)
• A amostragem ancestral em modelos de difusão é uma cadeia de Markov (cada passo depende apenas do estado atual)

Todo o processo de geração de imagens é amostragem iterativa: comece a partir do ruído e, a cada passo, amostre uma versão um pouco menos ruidosa condicionada ao modelo aprendido de remoção de ruído.

Construa

Passo 1: Amostragem uniforme e por CDF inversa

import math
import random

def sample_uniform(a, b):
    return a + (b - a) * random.random()

def sample_exponential_inverse_cdf(lam):
    u = random.random()
    return -math.log(u) / lam

Gere 10.000 amostras exponenciais e verifique se a média é 1/lambda.

Passo 2: Amostragem por rejeição

def rejection_sample(target_pdf, proposal_sample, proposal_pdf, M):
    while True:
        x = proposal_sample()
        u = random.random()
        if u < target_pdf(x) / (M * proposal_pdf(x)):
            return x

Use a amostragem por rejeição para extrair de uma distribuição normal truncada. Verifique o formato fazendo o histograma das amostras.

Passo 3: Amostragem por importância

def importance_sampling_estimate(f, target_pdf, proposal_pdf, proposal_sample, n):
    total = 0
    for _ in range(n):
        x = proposal_sample()
        w = target_pdf(x) / proposal_pdf(x)
        total += f(x) * w
    return total / n

Estime E[X^2] sob uma distribuição normal usando uma proposta uniforme. Compare com a resposta conhecida (mu^2 + sigma^2).

Passo 4: Estimação de pi por Monte Carlo

def monte_carlo_pi(n):
    inside = 0
    for _ in range(n):
        x = random.uniform(-1, 1)
        y = random.uniform(-1, 1)
        if x*x + y*y <= 1:
            inside += 1
    return 4 * inside / n

Passo 5: MCMC de Metropolis-Hastings

def metropolis_hastings(target_log_pdf, proposal_sample, proposal_log_pdf, x0, n_samples, burn_in):
    samples = []
    x = x0
    for i in range(n_samples + burn_in):
        x_new = proposal_sample(x)
        log_alpha = (target_log_pdf(x_new) + proposal_log_pdf(x, x_new)
                     - target_log_pdf(x) - proposal_log_pdf(x_new, x))
        if math.log(random.random()) < log_alpha:
            x = x_new
        if i >= burn_in:
            samples.append(x)
    return samples

Amostre de uma distribuição bimodal (mistura de duas gaussianas). Visualize a trajetória da cadeia.

Passo 6: Amostragem de Gibbs

def gibbs_sampling_2d(conditional_x_given_y, conditional_y_given_x, x0, y0, n_samples, burn_in):
    x, y = x0, y0
    samples = []
    for i in range(n_samples + burn_in):
        x = conditional_x_given_y(y)
        y = conditional_y_given_x(x)
        if i >= burn_in:
            samples.append((x, y))
    return samples

Passo 7: Amostragem por temperatura

def softmax(logits):
    max_l = max(logits)
    exps = [math.exp(z - max_l) for z in logits]
    total = sum(exps)
    return [e / total for e in exps]

def temperature_sample(logits, temperature):
    scaled = [z / temperature for z in logits]
    probs = softmax(scaled)
    return sample_from_probs(probs)

Mostre como a temperatura muda a distribuição de saída para um conjunto de logits de token.

Passo 8: Amostragem top-k e top-p

def top_k_sample(logits, k):
    indexed = sorted(enumerate(logits), key=lambda x: -x[1])
    top = indexed[:k]
    top_logits = [l for _, l in top]
    probs = softmax(top_logits)
    idx = sample_from_probs(probs)
    return top[idx][0]

def top_p_sample(logits, p):
    probs = softmax(logits)
    indexed = sorted(enumerate(probs), key=lambda x: -x[1])
    cumsum = 0
    selected = []
    for token_idx, prob in indexed:
        cumsum += prob
        selected.append((token_idx, prob))
        if cumsum >= p:
            break
    sel_probs = [pr for _, pr in selected]
    total = sum(sel_probs)
    sel_probs = [pr / total for pr in sel_probs]
    idx = sample_from_probs(sel_probs)
    return selected[idx][0]

Passo 9: Truque da reparametrização

def reparam_sample(mu, sigma):
    epsilon = random.gauss(0, 1)
    return mu + sigma * epsilon

def reparam_gradient(mu, sigma, epsilon):
    dz_dmu = 1.0
    dz_dsigma = epsilon
    return dz_dmu, dz_dsigma

Demonstre que os gradientes fluem através da amostra reparametrizada mas não através da amostragem direta.

Passo 10: Gumbel-Softmax

def gumbel_sample():
    u = random.random()
    return -math.log(-math.log(u))

def gumbel_softmax(logits, temperature):
    gumbels = [math.log(p) + gumbel_sample() for p in logits]
    return softmax([g / temperature for g in gumbels])

Mostre como diminuir a temperatura faz a saída se aproximar de um vetor one-hot.

Implementações completas com todas as visualizações estão em code/sampling.py.

Use

Com NumPy e SciPy, as versões de produção:

import numpy as np

rng = np.random.default_rng(42)

exponential_samples = rng.exponential(scale=2.0, size=10000)
print(f"Exponential mean: {exponential_samples.mean():.4f} (expected 2.0)")

from scipy import stats
normal = stats.norm(loc=0, scale=1)
print(f"CDF at 1.96: {normal.cdf(1.96):.4f}")
print(f"Inverse CDF at 0.975: {normal.ppf(0.975):.4f}")

logits = np.array([2.0, 1.0, 0.5, 0.1, -1.0])
temperature = 0.7
scaled = logits / temperature
probs = np.exp(scaled - scaled.max()) / np.exp(scaled - scaled.max()).sum()
token = rng.choice(len(logits), p=probs)
print(f"Sampled token index: {token}")

Para MCMC em escala, use bibliotecas dedicadas:

• PyMC: modelagem bayesiana completa com NUTS (HMC adaptativo)
• emcee: amostrador MCMC de ensemble
• NumPyro/JAX: MCMC acelerado por GPU

Você construiu isso do zero. Agora você sabe o que as chamadas de biblioteca estão fazendo.

Exercícios

1. Implemente a amostragem por CDF inversa para a distribuição de Cauchy. A CDF é F(x) = 0.5 + arctan(x)/pi. Gere 10.000 amostras e plote o histograma contra a PDF verdadeira. Note as caudas pesadas (valores extremos longe do centro).

2. Use a amostragem por rejeição para gerar amostras de uma distribuição Beta(2, 5) usando uma proposta Uniform(0, 1). Plote as amostras aceitas contra a PDF Beta verdadeira. Qual é a taxa de aceitação teórica?

3. Estime a integral de sin(x) de 0 a pi usando Monte Carlo com 1.000, 10.000 e 100.000 amostras. Compare o erro em cada nível. Verifique que o erro escala como O(1/sqrt(N)).

4. Implemente o Metropolis-Hastings para amostrar de uma distribuição 2D p(x, y) proporcional a exp(-(x^2 * y^2 + x^2 + y^2 - 8x - 8y) / 2). Plote as amostras e a trajetória da cadeia. Experimente diferentes desvios padrão de proposta.

5. Construa uma demo completa de geração de texto: dado um vocabulário de 10 palavras com logits, gere sequências de 20 tokens usando (a) gulosa, (b) temperatura=0.7, (c) top-k=3, (d) top-p=0.9. Compare a diversidade das saídas ao longo de 5 rodadas.

Termos-Chave

Leitura Complementar

• Holbrook (2023): The Metropolis-Hastings Algorithm - tutorial detalhado sobre os fundamentos do MCMC
• Jang, Gu, Poole (2017): Categorical Reparameterization with Gumbel-Softmax - o paper original do Gumbel-Softmax
• Holtzman et al. (2020): The Curious Case of Neural Text Degeneration - o paper da amostragem por núcleo (top-p)
• Kingma & Welling (2014): Auto-Encoding Variational Bayes - o paper do VAE que introduziu o truque da reparametrização
• Ho, Jain, Abbeel (2020): Denoising Diffusion Probabilistic Models - o DDPM conecta a amostragem à geração de imagens