Amostragem por Importância

Visão geral

Amostragem por importância (importance sampling, IS) é uma técnica central de Monte Carlo (Monte Carlo) para estimar uma expectativa sob uma distribuição-alvo (target distribution) (p(x)) quando é mais fácil extrair amostras de uma distribuição de proposta (proposal distribution) (q(x)). A ideia-chave é corrigir o desalinhamento entre (p) e (q) usando pesos de razão de verossimilhança (likelihood-ratio weights):

[ w(x) = \frac{p(x)}{q(x)}. ]

A amostragem por importância aparece em toda a IA/ML moderna: avaliar sistemas a partir de dados registrados (logged data) (avaliação fora da política (off-policy evaluation) em Aprendizado por Reforço (Reinforcement Learning)), estimar probabilidades de eventos raros, corrigir mudança de distribuição do conjunto de dados (dataset shift) e reduzir variância em estimadores de Monte Carlo.

Este artigo foca em:

  • a intuição central e a derivação
  • comportamento de não viés e variância
  • tamanho efetivo da amostra (effective sample size, ESS)
  • armadilhas comuns como degenerescência de pesos (weight degeneracy)
  • usos práticos em avaliação fora da política e outros cenários de redução de variância

(Para um contexto mais amplo, veja Métodos de Monte Carlo.)

O problema básico: estimar uma expectativa

Suponha que queremos:

[ \mu ;=; \mathbb{E}_{x \sim p}[f(x)] ;=; \int f(x),p(x),dx ]

mas amostrar de (p(x)) é difícil (ou impossível), enquanto amostrar de uma (q(x)) mais simples é fácil.

Um estimador ingênuo de Monte Carlo exigiria (x_i \sim p). A amostragem por importância, em vez disso, extrai (x_i \sim q) e repondera cada amostra para considerar quão mais (ou menos) provável aquela amostra seria sob (p).

Derivação e intuição central

Comece com a identidade:

[ \mathbb{E}{p}[f(x)] = \int f(x),p(x),dx = \int f(x),\frac{p(x)}{q(x)},q(x),dx = \mathbb{E}{q}\left[f(x),\frac{p(x)}{q(x)}\right] ]

Isso exige uma condição crucial:

Condição de suporte (support condition): se (p(x) > 0), então (q(x) > 0).
Caso contrário, (p(x)/q(x)) pode ser indefinido/infinito e o estimador pode falhar de forma catastrófica.

O estimador de amostragem por importância

Dadas amostras i.i.d. (x_1,\dots,x_N \sim q), o estimador padrão (não normalizado) de amostragem por importância é:

[ \hat{\mu}{\text{IS}} = \frac{1}{N}\sum{i=1}^N w(x_i) f(x_i), \quad \text{onde } w(x)=\frac{p(x)}{q(x)}. ]

Por que os pesos fazem sentido

Cada amostra “vale mais” quando é comum sob a distribuição-alvo (p), mas rara sob a proposta (q). O peso (p(x)/q(x)) é exatamente esse fator de correção.

Essa perspectiva é especialmente útil para:

  • estimação de eventos raros (rare-event estimation): escolher (q) para amostrar regiões raras com mais frequência e, em seguida, reduzir o peso de forma correspondente
  • avaliação fora da política: dados registrados vêm de uma política de comportamento (q), mas queremos o desempenho sob uma política-alvo (p)

Não viés (e quando isso quebra)

Não viés da amostragem por importância padrão

Assumindo que a condição de suporte e a integrabilidade valem:

[ \mathbb{E}q[\hat{\mu}{\text{IS}}] = \mathbb{E}q\left[\frac{1}{N}\sum{i=1}^N w(x_i)f(x_i)\right] = \mathbb{E}_q[w(x)f(x)] = \mathbb{E}_p[f(x)] ]

Logo, a amostragem por importância padrão não é viesada.

Amostragem por importância auto-normalizada (SNIS)

Frequentemente (p(x)) é conhecida apenas até uma constante: [ p(x) = \frac{\tilde{p}(x)}{Z} ] como em muitos contextos bayesianos. Nesse caso, (w(x)=p(x)/q(x)) não está diretamente disponível.

Uma solução alternativa comum é a amostragem por importância auto-normalizada (self-normalized importance sampling, SNIS), que usa pesos não normalizados (\tilde{w}(x)=\tilde{p}(x)/q(x)):

[ \hat{\mu}{\text{SNIS}} = \frac{\sum{i=1}^N \tilde{w}(x_i) f(x_i)}{\sum_{i=1}^N \tilde{w}(x_i)}. ]

Propriedades importantes:

  • viesado para (N) finito (estimador por razão)
  • consistente quando (N \to \infty) sob condições brandas
  • muitas vezes muito mais prático quando (Z) é desconhecido

Variância: o verdadeiro desafio

A amostragem por importância é conceitualmente simples, mas seu sucesso prático depende da variância.

Variância do estimador de amostragem por importância

Como (\hat{\mu}_{\text{IS}}) é uma média de termos i.i.d. sob (q),

[ \mathrm{Var}(\hat{\mu}_{\text{IS}}) = \frac{1}{N}\mathrm{Var}_q\left(w(x)f(x)\right). ]

Se (w(x)f(x)) tiver alta variância sob (q), o estimador fica ruidoso; em casos extremos, a variância pode ser infinita, fazendo o erro de Monte Carlo se comportar mal ou não convergir na prática.

O que faz a variância explodir?

A variância tende a explodir quando:

  • (q(x)) é pequena demais em regiões onde (p(x)|f(x)|) é grande
  • o alvo tem caudas mais pesadas do que a proposta
  • (p/q) tem valores raros, porém enormes (poucas amostras dominam)

Isso leva à degenerescência de pesos: a maioria dos pesos fica próxima de zero, e um número minúsculo carrega quase toda a massa.

A proposta “ótima” (e por que é difícil)

Para estimar (\mathbb{E}_p[f(x)]), a proposta de variância mínima (em um sentido idealizado) é:

[ q^*(x) \propto |f(x)|,p(x). ]

Intuição: amostrar mais onde a magnitude do integrando (|f(x)|p(x)) mais contribui para a integral.

Na prática, (q^*) geralmente não está disponível (ela depende da integral desconhecida), mas isso motiva:

  • amostragem por importância adaptativa (adaptive importance sampling)
  • famílias de propostas ajustadas para aproximar (|f|p)
  • propostas de mistura (mixture proposals) que cobrem múltiplas regiões importantes

Tamanho efetivo da amostra (ESS)

Um diagnóstico popular para degenerescência de pesos é o tamanho efetivo da amostra. Dados pesos (possivelmente não normalizados) (w_i), defina pesos normalizados:

[ \bar{w}i = \frac{w_i}{\sum{j=1}^N w_j}. ]

Então, uma estimativa comum de ESS é:

[ \mathrm{ESS} = \frac{1}{\sum_{i=1}^N \bar{w}i^2} ;=; \frac{\left(\sum{i=1}^N w_i\right)^2}{\sum_{i=1}^N w_i^2}. ]

Propriedades:

  • (1 \le \mathrm{ESS} \le N)
  • (\mathrm{ESS}\approx N): pesos relativamente uniformes (bom)
  • (\mathrm{ESS}\ll N): apenas algumas amostras importam (ruim)

O ESS não é uma medida perfeita, mas é simples e amplamente usada, especialmente em Monte Carlo Sequencial (Sequential Monte Carlo)/Filtros de Partículas (Particle Filters).

Cálculo prático do ESS (Python)

import numpy as np

def effective_sample_size(w):
    w = np.asarray(w, dtype=float)
    w_sum = w.sum()
    if w_sum == 0:
        return 0.0
    w_norm = w / w_sum
    return 1.0 / np.sum(w_norm ** 2)

Exemplo prático 1: estimar uma probabilidade de evento raro

Seja (X \sim \mathcal{N}(0,1)). Queremos a pequena probabilidade:

[ \mathbb{P}(X > 5) = \mathbb{E}_p[\mathbf{1}{X>5}] ]

O Monte Carlo direto a partir de (p) quase nunca observa (X>5), então o estimador tem enorme erro relativo.

Escolha uma proposta (q = \mathcal{N}(5,1)), que amostra a região rara com frequência. Então:

[ \hat{p} = \frac{1}{N}\sum_{i=1}^N \mathbf{1}{x_i>5}\frac{p(x_i)}{q(x_i)}, \quad x_i \sim q. ]

Isso frequentemente fornece redução de variância de várias ordens de magnitude — se (q) cobrir suficientemente onde o evento ocorre.

Esboço mínimo de implementação

import numpy as np
from math import sqrt, pi, exp

def normal_pdf(x, mu=0.0, sigma=1.0):
    z = (x - mu) / sigma
    return (1.0 / (sigma * sqrt(2*pi))) * exp(-0.5 * z*z)

def estimate_tail_prob(N=10000, mu_q=5.0, sigma=1.0):
    x = np.random.normal(loc=mu_q, scale=sigma, size=N)

    p = np.array([normal_pdf(xi, 0.0, sigma) for xi in x])
    q = np.array([normal_pdf(xi, mu_q, sigma) for xi in x])

    w = p / q
    f = (x > 5.0).astype(float)
    return np.mean(w * f), effective_sample_size(w)

est, ess = estimate_tail_prob()
print("estimate:", est, "ESS:", ess)

Exemplo prático 2: mudança de covariáveis / reponderação do conjunto de dados

Em aprendizado supervisionado, você pode treinar com dados de uma distribuição fonte (q(x,y)), mas se importar com o desempenho em uma distribuição-alvo (p(x,y)). Sob a suposição de mudança de covariáveis (covariate shift), (p(y\mid x)=q(y\mid x)) mas (p(x)\neq q(x)), um risco-alvo pode ser escrito como:

\[ \mathbb{E}_{p(x,y)}[\ell(h(x),y)]

\mathbb{E}_{q(x,y)}\left[\frac{p(x)}{q(x)}\ell(h(x),y)\right]. ]

Isso é amostragem por importância, em que o peso corrige o desalinhamento da distribuição de atributos. Na prática, estimar (p(x)/q(x)) pode ser feito via estimação da razão de densidades (density ratio estimation) (por exemplo, classificadores que distinguem fonte vs. alvo), mas os pesos podem se tornar instáveis — novamente levantando preocupações de degenerescência.

(Ideias intimamente relacionadas aparecem em adaptação de domínio (domain adaptation) e métodos de reponderação.)

Armadilhas comuns e modos de falha

1) Incompatibilidade de suporte (a armadilha de “probabilidade zero”)

Se existir algum (x) com (p(x)>0) mas (q(x)=0), então (p(x)/q(x)) é infinito e o estimador de amostragem por importância é inválido.

Em avaliação fora da política, isso corresponde a uma política de comportamento que nunca toma alguma ação que a política-alvo poderia tomar. Então você não consegue avaliar de forma confiável a política-alvo apenas com aqueles dados registrados.

2) Degenerescência de pesos

Mesmo quando os suportes se sobrepõem, os pesos podem se concentrar fortemente:

  • A maioria dos (\bar{w}_i\approx 0)
  • Alguns poucos (\bar{w}_i) dominam
  • O ESS fica minúsculo

Isso leva a alta variância e estimativas instáveis.

3) Caudas pesadas e variância infinita

Se (p/q) tiver caudas pesadas sob (q), (\mathrm{Var}_q(wf)) pode ser infinita mesmo que a expectativa exista. Esse é um motivo sutil, mas importante, pelo qual a amostragem por importância pode “parecer que deveria funcionar”, mas falha empiricamente.

4) Estabilidade numérica

Pesos podem sofrer underflow/overflow quando calculados no espaço de probabilidades. Uma correção padrão é calcular pesos em log e normalizar usando o truque de log-sum-exp (log-sum-exp trick):

import numpy as np

def normalize_log_weights(logw):
    m = np.max(logw)
    w = np.exp(logw - m)
    return w / np.sum(w)

5) “Consertos” viesados e o compromisso viés–variância

Profissionais comumente aplicam:

  • corte/truncamento de pesos (weight clipping/truncation): (w_i \leftarrow \min(w_i, c))
  • normalização de pesos (SNIS)
  • propostas de mistura para ampliar o suporte

Isso pode reduzir a variância substancialmente, mas pode introduzir viés (corte) ou viés em amostras finitas (SNIS). Em muitos cenários aplicados de ML, um viés controlado é aceitável se ele estabiliza o aprendizado ou a avaliação.

Amostragem por importância em avaliação fora da política (OPE)

Um caso de uso particularmente importante em ML é avaliar uma política-alvo (\pi) usando trajetórias coletadas por uma política de comportamento diferente (\mu). Isso é central em RL, sistemas de recomendação e anúncios, onde implantar diretamente uma nova política é arriscado.

Considere trajetórias (\tau = (s_0,a_0,r_0,s_1,a_1,r_1,\dots)) de (\mu). O retorno esperado sob (\pi) é:

[ J(\pi) = \mathbb{E}_{\tau \sim p(\tau \mid \pi)}[G(\tau)] ]

Usando amostragem por importância:

[ J(\pi) = \mathbb{E}_{\tau \sim p(\tau \mid \mu)}\left[ \rho(\tau), G(\tau) \right] ]

onde a razão de verossimilhança da trajetória é:

[ \rho(\tau) = \prod_{t=0}^{T-1}\frac{\pi(a_t\mid s_t)}{\mu(a_t\mid s_t)}. ]

Isso é amostragem por importância com:

  • distribuição-alvo sobre trajetórias: induzida por (\pi)
  • distribuição de proposta sobre trajetórias: induzida por (\mu)

Por que OPE é difícil: pesos multiplicativos

O produto ao longo do tempo pode explodir ou desaparecer exponencialmente com o horizonte (T), causando degenerescência extrema de pesos. Esse é um dos motivos pelos quais OPE é estatisticamente desafiador.

Variantes comuns de OPE

  • amostragem por importância por decisão (per-decision importance sampling, PDIS): usa produtos parciais até o tempo (t) ao ponderar a recompensa no tempo (t), frequentemente reduzindo variância.
  • amostragem por importância ponderada (weighted importance sampling, WIS): um estimador auto-normalizado sobre trajetórias (menor variância, viesado mas consistente).
  • estimadores duplamente robustos (doubly robust estimators): combinam amostragem por importância com um modelo de valor aprendido para reduzir variância e permanecer robustos a parte do erro do modelo (veja Avaliação Fora da Política).

Assim, a amostragem por importância é um bloco fundamental para métodos práticos de OPE no Aprendizado por Reforço moderno.

Amostragem por importância como uma ferramenta geral de redução de variância

Mesmo quando você consegue amostrar de (p), você ainda pode usar amostragem por importância para reduzir variância ao amostrar de uma (q) mais inteligente. Isso se conecta a ideias mais amplas de redução de variância, como:

  • Variáveis de Controle (Control Variates)
  • amostragem estratificada (stratified sampling) e variáveis antitéticas (antithetic variates) (técnicas comuns de Monte Carlo)
  • propostas adaptativas, incluindo misturas e refinamento iterativo

Propostas adaptativas e de mistura

Uma abordagem prática padrão é escolher:

[ q(x) = \sum_{k=1}^K \alpha_k q_k(x) ]

para que múltiplas regiões de alta contribuição sejam cobertas. Misturas também reduzem a chance de incompatibilidade de suporte catastrófica (desde que cada região importante tenha alguma massa na mistura).

Orientação prática: escolhendo e usando uma distribuição de proposta

  1. Garanta cobertura de suporte

    • Certifique-se de que (q(x)) atribui probabilidade não trivial onde quer que (p(x)|f(x)|) seja grande.

  2. Combine as caudas

    • Se (p) tem caudas mais pesadas, escolha (q) com caudas pelo menos tão pesadas para evitar pesos enormes.

  3. Monitore ESS e histogramas de pesos

    • Um ESS muito baixo é um alerta precoce de que sua estimativa pode estar sendo dominada por poucas amostras.

  4. Use pesos em log

    • Para estabilidade numérica em alta dimensionalidade.

  5. Considere auto-normalização

    • Especialmente quando (p) é não normalizada (comum em inferência bayesiana), mas lembre-se de que ela é viesada para (N) finito.

  6. Use corte/truncamento quando necessário

    • Particularmente em avaliação fora da política e em loops de treinamento de RL, onde estabilidade importa. Trate isso como um compromisso viés–variância.

Resumo

A amostragem por importância estima expectativas sob uma distribuição-alvo (p) usando amostras de uma proposta (q) ao reponderar amostras com a razão de verossimilhança (p/q). Ela é:

  • não viesada em sua forma padrão (dada cobertura de suporte e variância finita),
  • frequentemente de alta variância na prática quando os pesos degeneram,
  • diagnosticável via tamanho efetivo da amostra (ESS),
  • central para avaliação fora da política em Aprendizado por Reforço e amplamente usada para redução de variância em estimação por Monte Carlo.

Em ML aplicado, o principal desafio raramente é a álgebra — é escolher (ou aprender) uma distribuição de proposta que mantenha os pesos bem-comportados, enquanto ainda concentra a computação nas partes do espaço que importam.