Monte Carlo Sequencial

Visão geral

Monte Carlo Sequencial (Sequential Monte Carlo, SMC) é uma família de métodos de Monte Carlo para aproximar uma sequência de distribuições de probabilidade que evoluem ao longo do tempo ou ao longo de um caminho artificial. Em vez de extrair amostras independentes diretamente da distribuição-alvo (o que muitas vezes é impossível), o SMC mantém um conjunto de amostras ponderadas — chamadas partículas (particles) — que são propagadas e reponderadas conforme o alvo muda.

O SMC é mais conhecido por filtros de partículas (particle filters) em modelos de espaço de estados (rastreamento e séries temporais), mas as mesmas ideias também sustentam métodos mais gerais, como amostradores SMC (SMC samplers), que fazem uma ponte entre uma distribuição fácil e uma difícil (por exemplo, via têmpera/recozimento (tempering/annealing)).

O SMC se apoia conceitualmente em Amostragem por Importância (Importance Sampling): cada etapa usa ponderação por importância, e o SMC adiciona mecanismos para manter a aproximação saudável ao longo do tempo — especialmente a reamostragem (resampling) para combater a degenerescência dos pesos (weight degeneracy).

Quando e por que o SMC é útil

O SMC é útil quando:

  • A distribuição-alvo muda sequencialmente, por exemplo, (p(x_t \mid y_{1:t})) à medida que novos dados chegam.
  • O estado é latente e as dinâmicas são markovianas (comum em séries temporais bayesianas e rastreamento).
  • Você quer um algoritmo online que consiga atualizar estimativas sem re-treinar do zero.
  • Você quer um estimador da constante de normalização (normalizing constant) (verossimilhança marginal) ao longo do processo (importante para comparação de modelos).
  • Você quer uma alternativa baseada em população ao Monte Carlo via Cadeias de Markov (Markov Chain Monte Carlo, MCMC) para pós-teriores difíceis.

Áreas comuns de aplicação incluem:

  • Rastreamento de objetos (visão computacional), fusão de sensores (sensor fusion)
  • Localização em robótica/SLAM
  • Finanças (volatilidade estocástica), econometria
  • Epidemiologia e inferência bayesiana em fluxo (streaming)
  • Programação probabilística e estimação de evidência de modelos bayesianos

Ideia central: aproximar distribuições com partículas ponderadas

Suponha que queremos aproximar uma sequência de distribuições ({\pi_t(x_t)}_{t=0}^T). O SMC representa cada (\pi_t) com partículas e pesos:

[ \pi_t(x) \approx \sum_{i=1}^N w_t^{(i)} , \delta(x - x_t^{(i)}), \quad \text{with } w_t^{(i)} \ge 0,\ \sum_{i=1}^N w_t^{(i)} = 1. ]

Então, esperanças sob (\pi_t) são aproximadas por somas ponderadas:

[ \mathbb{E}{\pi_t}[f(X)] \approx \sum{i=1}^N w_t^{(i)} f(x_t^{(i)}). ]

Isso é simples — mas o desafio é evitar que os pesos colapsem sobre poucas partículas ao longo do tempo.

Um cenário canônico: modelos de espaço de estados (state-space models) — filtragem de partículas (particle filtering)

Um caso de uso padrão é um modelo oculto de Markov (hidden Markov model) / modelo de espaço de estados (veja também Modelos Ocultos de Markov):

  • Dinâmica do estado latente: (x_t \sim p(x_t \mid x_{t-1}))
  • Observações: (y_t \sim p(y_t \mid x_t))

O alvo de filtragem é o posterior:

[ \pi_t(x_t) = p(x_t \mid y_{1:t}). ]

O SMC (filtragem de partículas) mantém partículas aproximando esse posterior conforme cada nova observação chega.

Amostragem sequencial por importância (sequential importance sampling, SIS): amostragem por importância ao longo do tempo

O SMC pode ser derivado aplicando amostragem por importância à distribuição do caminho (path distribution) (x_{0:t}), e não apenas ao estado atual.

Seja o alvo no tempo (t) (\gamma_t(x_{0:t})) (possivelmente não normalizado), com versão normalizada (\pi_t(x_{0:t})). Escolhemos uma proposta (proposal) (q_t(x_{0:t})) que fatoriza sequencialmente:

[ q_t(x_{0:t}) = q_0(x_0)\prod_{s=1}^t q_s(x_s \mid x_{0:s-1}). ]

As partículas são amostradas de (q_t) e recebem pesos de importância (importance weights):

[ \tilde{w}t^{(i)} = \frac{\gamma_t(x{0:t}^{(i)})}{q_t(x_{0:t}^{(i)})}. ]

Por causa da fatorização, os pesos podem ser atualizados incrementalmente:

[ \tilde{w}t^{(i)} = \tilde{w}{t-1}^{(i)} \cdot \frac{\gamma_t(x_{0:t}^{(i)})}{\gamma_{t-1}(x_{0:t-1}^{(i)}), q_t(x_t^{(i)} \mid x_{0:t-1}^{(i)})}. ]

No modelo de espaço de estados, um alvo comum é:

[ \gamma_t(x_{0:t}) = p(x_0)\prod_{s=1}^t p(x_s\mid x_{s-1}) \prod_{s=1}^t p(y_s \mid x_s). ]

Então o peso incremental frequentemente se simplifica para algo proporcional ao termo de verossimilhança e à correção da proposta.

O problema: degenerescência dos pesos

Com o tempo, a maioria das partículas recebe peso desprezível, e o tamanho efetivo da amostra colapsa. Isso é um problema bem conhecido: no SIS puro, a variância cresce com o tempo, especialmente em altas dimensões ou com observações informativas.

Um diagnóstico padrão é o tamanho efetivo da amostra (effective sample size, ESS):

[ \text{ESS} = \frac{1}{\sum_{i=1}^N (w_t^{(i)})^2}. ]

  • ESS (\approx N): pesos razoavelmente uniformes (bom).
  • ESS (\ll N): apenas poucas partículas importam (ruim).

É aqui que a reamostragem entra.

Reamostragem: combater a degenerescência (a um custo)

Reamostragem substitui o conjunto de partículas ponderadas por um conjunto não ponderado ao amostrar partículas proporcionalmente aos seus pesos. Intuitivamente: “mata” partículas de baixo peso e “clona” partículas de alto peso.

Após reamostrar, os pesos tipicamente são redefinidos para (1/N).

A reamostragem reduz a degenerescência dos pesos, mas introduz:

  • Ruído de amostragem (sampling noise) (variância extra)
  • Perda de diversidade (loss of diversity) (muitos duplicados)
  • Degenerescência de trajetória (path degeneracy) em suavização (linhagens ancestrais colapsam)

Quando reamostrar

Uma estratégia comum é a reamostragem adaptativa (adaptive resampling):

  • Calcular o ESS
  • Reamostrar apenas se (\text{ESS} < \tau N) (por exemplo, (\tau = 0.5))

Esquemas comuns de reamostragem

  • Reamostragem multinomial (multinomial resampling): mais simples, maior variância
  • Reamostragem sistemática (systematic resampling): baixa variância, muito comum na prática
  • Reamostragem estratificada (stratified resampling): também baixa variância
  • Reamostragem residual (residual resampling): parte determinística + restante aleatório

A reamostragem sistemática e a estratificada costumam ser preferidas devido à menor variância.

Filtros de partículas: a variante de SMC mais comum

Um filtro de partículas básico (filtro bootstrap) usa a transição como proposta:

  • Propagar: (x_t^{(i)} \sim p(x_t \mid x_{t-1}^{(a_i)}))
  • Ponderar: (w_t^{(i)} \propto p(y_t \mid x_t^{(i)}))

Isso é simples e muitas vezes eficaz, mas pode falhar quando a verossimilhança é muito “aguda” em relação às dinâmicas. Nesse caso, propostas melhores ajudam.

Propostas melhores (distribuições de importância)

Um filtro de partículas mais geral propõe a partir de (q(x_t \mid x_{t-1}, y_t)), idealmente próximo da proposta ótima:

[ q^*(x_t \mid x_{t-1}, y_t) = p(x_t \mid x_{t-1}, y_t). ]

Isso minimiza a variância dos pesos localmente, mas pode ser intratável. Aproximações práticas incluem:

  • Linearização (propostas no estilo EKF)
  • Propostas unscented
  • Aproximações locais de Laplace
  • Propostas aprendidas (inferência amortizada), comuns em ML moderno

Essas escolhas conectam filtros de partículas a práticas mais amplas de Inferência Bayesiana (Bayesian Inference) e de inferência aproximada.

Amostradores SMC: SMC além de séries temporais

Nem toda sequência é “tempo”. Amostradores SMC miram uma sequência de distribuições em um espaço fixo (x):

[ \pi_0(x) \rightarrow \pi_1(x) \rightarrow \cdots \rightarrow \pi_T(x), ]

onde (\pi_0) é fácil de amostrar e (\pi_T) é a distribuição de interesse (por exemplo, um posterior).

Uma construção comum é a têmpera/recozimento:

[ \pi_t(x) \propto p(x), p(y \mid x)^{\beta_t}, \quad 0 = \beta_0 < \beta_1 < \cdots < \beta_T = 1. ]

À medida que (\beta_t) aumenta, a distribuição muda gradualmente do prior para o posterior.

Reponderação e rejuvenescimento (movimentos de MCMC)

Amostradores SMC tipicamente alternam:

  1. Reponderar partículas ao mover (\pi_{t-1}\to\pi_t)
  2. Reamostrar se o ESS cair
  3. Mover partículas via transições de MCMC que deixam (\pi_t) invariante (uma etapa de “rejuvenescimento”)

Esse padrão reamostrar-mover (resample-move) ajuda a manter diversidade e torna amostradores SMC competitivos com MCMC, especialmente para alvos multimodais.

Fundamentos teóricos (intuições que importam na prática)

Ponto de vista de Feynman–Kac (alto nível)

Muitos algoritmos de SMC podem ser descritos por:

  • Um operador de mutação/propagação (proposta/dinâmica)
  • Uma função potencial ou de ponderação (incremento de verossimilhança)
  • Seleção opcional (reamostragem)

Essa abstração (frequentemente chamada de modelo de Feynman–Kac) é útil porque fornece:

  • Consistência quando (N \to \infty)
  • Teoremas do limite central (central limit theorems) para estimativas por partículas
  • Estimadores não viesados (unbiased estimators) de constantes de normalização sob condições padrão

Você não precisa de todo o ferramental de teoria da medida para usar SMC, mas a mensagem-chave é: SMC não é um truque ad hoc; é uma aproximação de Monte Carlo, com princípios, para medidas em evolução.

Estimando constantes de normalização (verossimilhança marginal)

O SMC pode fornecer uma estimativa da constante de normalização (Z_T) (por exemplo, verossimilhança marginal (p(y_{1:T}))):

[ \hat{Z}T = \prod{t=1}^T \left(\sum_{i=1}^N w_{t-1}^{(i)} , \tilde{w}_t^{(i)}\right) ]

(A forma exata depende de convenções; a ideia central é que médias de pesos incrementais se multiplicam.)

Isso é valioso para:

  • Comparação de modelos bayesianos
  • Seleção de hiperparâmetros
  • Fluxos de trabalho em programação probabilística

Redução de variância e Rao–Blackwellização

Se parte do modelo é condicionalmente tratável, você pode integrá-la e reduzir a variância — isso é Rao–Blackwellização (Rao–Blackwellization) (Rao–Blackwellização (Rao–Blackwellization)). Na filtragem de partículas, isso produz filtros de partículas Rao–Blackwellizados (Rao–Blackwellized particle filters, RBPF), comuns em rastreamento e SLAM:

  • Usar partículas para componentes não lineares
  • Usar filtros analíticos (por exemplo, filtro de Kalman) para subestrutura linear-gaussiana

Variáveis de controle (control variates) (Variáveis de Controle (Control Variates)) também às vezes são usadas para reduzir a variância de Monte Carlo, especialmente em amostradores SMC, embora sejam mais comuns em Monte Carlo offline do que na filtragem de partículas clássica.

Exemplo prático 1: rastreamento 1D com um filtro de partículas

Considere um modelo simples de rastreamento não linear:

  • Dinâmica: (x_t = x_{t-1} + \epsilon_t), (\epsilon_t \sim \mathcal{N}(0, \sigma^2))
  • Observação: (y_t = \sin(x_t) + \eta_t), (\eta_t \sim \mathcal{N}(0, \tau^2))

O posterior (p(x_t \mid y_{1:t})) é não linear devido a (\sin(x_t)). Um filtro de partículas lida com isso facilmente.

Pseudocódigo (filtro de partículas bootstrap (bootstrap particle filter))

Initialize particles: x0^(i) ~ p(x0), weights w0^(i) = 1/N

For t = 1..T:
  # Propagate
  for i = 1..N:
    x_t^(i) ~ p(x_t | x_{t-1}^(i))

  # Weight by likelihood
  for i = 1..N:
    w_t^(i) ∝ p(y_t | x_t^(i))
  normalize weights

  # Resample if ESS low
  if ESS(w_t) < threshold:
    resample particles according to w_t
    set w_t^(i) = 1/N

Esboço mínimo em estilo Python

import numpy as np

def systematic_resample(w):
    N = len(w)
    u0 = np.random.rand() / N
    cdf = np.cumsum(w)
    idx = np.searchsorted(cdf, u0 + np.arange(N)/N)
    return idx

def particle_filter(y, N=2000, sigma=1.0, tau=0.3):
    T = len(y)
    x = np.zeros((T, N))
    w = np.ones(N) / N

    # prior
    x[0] = np.random.normal(0.0, 2.0, size=N)

    for t in range(1, T):
        # propagate
        x[t] = x[t-1] + np.random.normal(0.0, sigma, size=N)

        # weight
        ll = -0.5*((y[t] - np.sin(x[t]))/tau)**2
        ll -= np.max(ll)  # stabilize
        w = np.exp(ll)
        w /= np.sum(w)

        ess = 1.0 / np.sum(w**2)
        if ess < 0.5 * N:
            idx = systematic_resample(w)
            x[t] = x[t, idx]
            w[:] = 1.0 / N

    return x, w

Mesmo neste exemplo simples, a reamostragem adaptativa e a estabilização numérica (deslocamento do log da verossimilhança) são detalhes importantes para implementações robustas.

Exemplo prático 2: SMC recozido para inferência de posterior bayesiano

Suponha que você queira amostras de um posterior bayesiano (p(\theta \mid y)) que é multimodal. Você pode definir um cronograma de temperatura (\beta_t) e executar um amostrador SMC:

  1. Começar com partículas do prior (p(\theta)) ((\beta_0=0))
  2. Incrementar (\beta_t), reponderar por (p(y\mid\theta)^{\Delta \beta})
  3. Reamostrar se o ESS cair
  4. Aplicar vários passos de MCMC mirando (\pi_t(\theta))

Isso se assemelha a um “MCMC de população”, mas a ponderação do SMC fornece uma ponte direta entre distribuições e uma estimativa de evidência do modelo.

Armadilhas comuns e melhores práticas de engenharia

Escolhendo o número de partículas \(N\)

  • Um (N) maior melhora a acurácia, mas custa mais computação.
  • Em estados de alta dimensão, (N) precisa crescer rapidamente para evitar colapso — este é um desafio fundamental.

Regras práticas:

  • Comece com (N) na casa das centenas/milhares para rastreamento de baixa dimensão.
  • Monitore o ESS e o desempenho do filtro em vez de depender apenas de (N).

O desenho da proposta importa mais do que a reamostragem

A reamostragem corrige sintomas de degenerescência dos pesos, mas uma proposta ruim ainda pode falhar:

  • Se as observações são muito informativas, propor a partir das dinâmicas pode colocar a maioria das partículas em regiões de baixa verossimilhança.
  • Propostas melhores (usando (y_t)) podem melhorar dramaticamente o ESS.

Trate a estabilidade numérica com cuidado

Trabalhe no espaço log ao computar pesos:

  • Acumule log-pesos
  • Subtraia o máximo log-peso antes de exponenciar
  • Normalize com segurança

Empobrecimento de partículas e rejuvenescimento

Reamostrar com frequência pode levar a muitas partículas duplicadas (“empobrecimento”). Mitigações:

  • Reamostrar apenas quando o ESS estiver baixo
  • Adicionar passos de movimento (rejuvenescimento via MCMC) após reamostrar
  • Adicionar pequeno ruído (com cuidado, respeitando o alvo)

Suavização vs filtragem

Filtragem estima (p(x_t \mid y_{1:t})). Suavização estima (p(x_{0:T} \mid y_{1:T})) ou (p(x_t \mid y_{1:T})).

Armazenar trajetórias completas de forma ingênua leva à degenerescência de trajetória (estados iniciais colapsam para poucos ancestrais). A suavização via SMC usa algoritmos especializados (ideias forward-backward, amostragem de ancestrais, particle Gibbs, etc.), especialmente em métodos conectados a Monte Carlo via Cadeias de Markov, como particle MCMC.

Onde o SMC se encaixa entre métodos de inferência

  • Versus filtros de Kalman (Kalman filters): SMC lida com modelos não lineares/não gaussianos, a um custo computacional maior. (Veja Filtro de Kalman (Kalman Filter).)
  • Versus MCMC: SMC pode ser mais paralelizável (muitas partículas), lida naturalmente com sequências/atualizações online e produz estimativas de evidência; MCMC pode ser mais eficiente para pós-teriores estáticos em dimensões moderadas quando a mistura é boa.
  • Versus inferência variacional (variational inference, VI): VI costuma ser mais rápida e escalável, mas introduz viés de otimização; SMC é baseado em Monte Carlo e pode ser assintoticamente exato quando (N\to\infty). (Veja Inferência Variacional (Variational Inference).)

Resumo

Métodos de Monte Carlo sequencial aproximam distribuições de probabilidade em evolução usando uma população de partículas ponderadas. Os mecanismos-chave são:

  • Amostragem sequencial por importância: propagar partículas ao longo do tempo (ou ao longo de um caminho de distribuições) e atualizar pesos incrementalmente.
  • Reamostragem: evitar degenerescência dos pesos ao concentrar computação em partículas de alto peso, tipicamente acionada por baixo ESS.
  • Variantes:
    • Filtros de partículas para modelos de espaço de estados e rastreamento bayesiano online
    • Amostradores SMC para alvos estáticos via têmpera/recozimento, frequentemente com rejuvenescimento via MCMC

O SMC é um pilar da inferência probabilística moderna: prático, conceitualmente claro e flexível — especialmente quando as distribuições evoluem ou quando filtragem/amostragem exata é intratável.