Phase 01 - Lesson 22

Processos Estocásticos

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

Aleatoriedade com estrutura. A matemática por trás dos passeios aleatórios, cadeias de Markov e modelos de difusão.

Tipo: Learn Linguagem: Python Pré-requisitos: Fase 1, Lições 06-07 (probabilidade, Bayes) Tempo: ~75 minutos

Objetivos de Aprendizagem

• Simular passeios aleatórios em 1D e 2D e verificar o escalonamento sqrt(n) do deslocamento
• Construir um simulador de cadeia de Markov e calcular sua distribuição estacionária via autodecomposição
• Implementar MCMC com Metropolis-Hastings e dinâmica de Langevin para amostragem de distribuições-alvo
• Conectar o processo de difusão direto ao movimento Browniano e explicar como o processo reverso gera dados

O Problema

Muitos sistemas de IA envolvem aleatoriedade que evolui ao longo do tempo. Não aleatoriedade estática -- aleatoriedade estruturada e sequencial, em que cada passo depende do que veio antes.

Modelos de linguagem geram tokens um de cada vez. Cada token depende do contexto anterior. O modelo gera uma distribuição de probabilidade, amostra dela e segue em frente. Isso e um processo estocástico.

Modelos de difusão adicionam ruído a uma imagem passo a passo até que ela se torne puro chiado estático. Depois revertem o processo, removendo ruído passo a passo até que uma nova imagem emerja. O processo direto e uma cadeia de Markov. O processo reverso e uma cadeia de Markov aprendida rodando ao contrario.

Agentes de aprendizado por reforco realizam ações em um ambiente. Cada ação leva a um novo estado com alguma probabilidade. O agente segue uma política aleatória em um mundo aleatório. Tudo isso e um processo de decisão de Markov.

A amostragem MCMC -- a espinha dorsal da inferência bayesiana -- constrói uma cadeia de Markov cuja distribuição estacionária e a posteriori da qual você quer amostrar.

Tudo isso se baseia em quatro ideias fundamentais:

1. Passeios aleatórios -- o processo estocástico mais simples
2. Cadeias de Markov -- aleatoriedade estruturada com uma matriz de transição
3. Dinâmica de Langevin -- gradiente descendente com ruído
4. Metropolis-Hastings -- amostragem de qualquer distribuição

O Conceito

Passeios Aleatórios

Comece na posição 0. A cada passo, jogue uma moeda justa. Cara: mova-se para a direita (+1). Coroa: mova-se para a esquerda (-1).

Após n passos, sua posição e a soma de n valores aleatórios +/-1. A posição esperada e 0 (o passeio não tem viés). Mas a distância esperada da origem cresce como sqrt(n).

Isso e contraintuitivo. O passeio e justo -- nenhuma deriva em qualquer direção. Mas ao longo do tempo, ele se afasta cada vez mais de onde começou. O desvio padrão após n passos e sqrt(n).

Step 0:  Position = 0
Step 1:  Position = +1 or -1
Step 2:  Position = +2, 0, or -2
...
Step 100: Expected distance from origin ~ 10 (sqrt(100))
Step 10000: Expected distance from origin ~ 100 (sqrt(10000))

Em 2D, o passeio se move para cima, para baixo, para a esquerda ou para a direita com igual probabilidade. O mesmo escalonamento sqrt(n) se aplica a distância da origem. O caminho traça um padrão parecido com um fractal.

Por que sqrt(n)? Cada passo e +1 ou -1 com igual probabilidade. Após n passos, a posição S_n = X_1 + X_2 + ... + X_n onde cada X_i e +/-1. A variância de cada passo e 1, e os passos são independentes, então Var(S_n) = n. Desvio padrão = sqrt(n). Pelo teorema central do limite, S_n / sqrt(n) converge para uma distribuição normal padrão.

Esse escalonamento sqrt(n) aparece em todo lugar em ML. O ruído do SGD escala como 1/sqrt(batch_size). As dimensões de embedding escalam como sqrt(d). A raiz quadrada e a assinatura de adições aleatórias independentes.

Conexão com o movimento Browniano. Tome um passeio aleatório com tamanho de passo 1/sqrt(n) e n passos por unidade de tempo. A medida que n vai ao infinito, o passeio converge para o movimento Browniano B(t) -- um processo de tempo contínuo onde B(t) tem distribuição normal com média 0 e variância t.

O movimento Browniano e a fundação matemática da difusão. Ele modela o tremor aleatório de partículas em um fluido, as flutuações dos preços de ações e -- crucialmente -- o processo de ruído em modelos de difusão.

Ruina do apostador (Gambler's ruin). Um caminhante aleatório começando na posição k, com barreiras absorventes em 0 e N. Qual e a probabilidade de alcançar N antes de 0? Para um passeio justo: P(alcançar N) = k/N. Isso e surpreendentemente simples e elegante. Conecta-se a teoria dos martingais -- o passeio aleatório justo e um martingal (valor futuro esperado = valor atual).

Cadeias de Markov

Uma cadeia de Markov e um sistema que transiciona entre estados de acordo com probabilidades fixas. A propriedade-chave: o próximo estado depende apenas do estado atual, não do histórico.

P(X_{t+1} = j | X_t = i, X_{t-1} = ...) = P(X_{t+1} = j | X_t = i)

Esta e a propriedade de Markov. Ela significa que você pode descrever toda a dinâmica com uma matriz de transição P:

P[i][j] = probability of going from state i to state j

Cada linha de P soma 1 (você tem que ir para algum lugar).

Exemplo -- Clima:

States: Sunny (0), Rainy (1), Cloudy (2)

P = [[0.7, 0.1, 0.2],    (if sunny: 70% sunny, 10% rainy, 20% cloudy)
     [0.3, 0.4, 0.3],    (if rainy: 30% sunny, 40% rainy, 30% cloudy)
     [0.4, 0.2, 0.4]]    (if cloudy: 40% sunny, 20% rainy, 40% cloudy)

Comece em qualquer estado. Após muitas transições, a distribuição de estados converge para a distribuição estacionária pi, onde pi * P = pi. Este e o autovetor a esquerda de P com autovalor 1.

Para a cadeia do clima, a distribuição estacionária pode ser [0.53, 0.18, 0.29] -- no longo prazo, fica ensolarado 53% do tempo, independentemente do estado inicial.

graph LR
    S["Sunny"] -->|0.7| S
    S -->|0.1| R["Rainy"]
    S -->|0.2| C["Cloudy"]
    R -->|0.3| S
    R -->|0.4| R
    R -->|0.3| C
    C -->|0.4| S
    C -->|0.2| R
    C -->|0.4| C

Calculando a distribuição estacionária. Existem duas abordagens:

1. Método da potência: multiplique qualquer distribuição inicial por P repetidamente. Após iterações suficientes, ela converge.
2. Método dos autovalores: encontre o autovetor a esquerda de P com autovalor 1. Este e o autovetor de P^T com autovalor 1.

Ambas as abordagens exigem que a cadeia satisfaca condições de convergência.

Condições de convergência. Uma cadeia de Markov converge para uma distribuição estacionária única se ela for:

• Irredutível: todo estado e alcançável a partir de qualquer outro estado
• Aperiódica: a cadeia não cicla com um período fixo

A maioria das cadeias que você encontra em ML satisfaz ambas as condições.

Estados absorventes. Um estado e absorvente se, uma vez que você entra nele, nunca sai (P[i][i] = 1). Cadeias de Markov absorventes modelam processos com estados terminais -- um jogo que termina, um cliente que cancela (churn), uma sequência de tokens que atinge o token de fim de texto.

Tempo de mistura. Quantos passos até que a cadeia esteja "próxima" da distribuição estacionária? Formalmente, o número de passos até que a distância de variação total em relação a estacionariedade caia abaixo de algum limiar. Mistura rápida = poucos passos necessários. O gap espectral de P (1 menos o segundo maior autovalor) controla o tempo de mistura. Gap maior = mistura mais rápida.

Conexão com Modelos de Linguagem

A geração de tokens em um modelo de linguagem e aproximadamente um processo de Markov. Dado o contexto atual, o modelo gera uma distribuição sobre o próximo token. A temperatura controla a nitidez:

P(token_i) = exp(logit_i / temperature) / sum(exp(logit_j / temperature))

• Temperatura = 1.0: distribuição padrão
• Temperatura < 1.0: mais nítida (mais determinística)
• Temperatura > 1.0: mais plana (mais aleatória)
• Temperatura -> 0: argmax (guloso)

A amostragem top-k trunca para os k tokens de maior probabilidade. A amostragem top-p (nucleus) trunca para o menor conjunto de tokens cuja probabilidade cumulativa excede p. Ambas modificam as probabilidades de transição de Markov.

Movimento Browniano

O limite de tempo contínuo do passeio aleatório. A posição B(t) tem três propriedades:

1. B(0) = 0
2. B(t) - B(s) tem distribuição normal com média 0 e variância t - s (para t > s)
3. Os incrementos em intervalos não sobrepostos são independentes

O movimento Browniano e contínuo, mas em lugar nenhum diferenciável -- ele treme em toda escala. O caminho tem dimensão fractal 2 no plano.

Na simulação discreta, você aproxima o movimento Browniano por:

B(t + dt) = B(t) + sqrt(dt) * z,    where z ~ N(0, 1)

O escalonamento sqrt(dt) e importante. Ele vem do teorema central do limite aplicado a passeios aleatórios.

Dinâmica de Langevin

O gradiente descendente encontra o mínimo de uma função. A dinâmica de Langevin encontra a distribuição de probabilidade proporcional a exp(-U(x)/T), onde U e uma função de energia e T e a temperatura.

x_{t+1} = x_t - dt * gradient(U(x_t)) + sqrt(2 * T * dt) * z_t

Duas forças atuam sobre a partícula:

1. Força do gradiente (-dt * gradient(U)): empurra em direção a baixa energia (como o gradiente descendente)
2. Força aleatória (sqrt(2Tdt) * z): empurra em direções aleatórias (exploração)

Na temperatura T = 0, isso e gradiente descendente puro. Em alta temperatura, e quase um passeio aleatório. Na temperatura certa, a partícula explora a paisagem de energia e passa mais tempo em regiões de baixa energia.

Conexão com modelos de difusão. O processo direto de um modelo de difusão e:

x_t = sqrt(alpha_t) * x_{t-1} + sqrt(1 - alpha_t) * noise

Esta e uma cadeia de Markov que gradualmente mistura os dados com ruído. Após passos suficientes, x_T e ruído gaussiano puro.

O processo reverso -- indo do ruído de volta aos dados -- também e uma cadeia de Markov, mas suas probabilidades de transição são aprendidas por uma rede neural. A rede aprende a prever o ruído que foi adicionado em cada passo e, então, o subtrai.

graph LR
    subgraph "Forward Process (add noise)"
        X0["x_0 (data)"] -->|"+ noise"| X1["x_1"]
        X1 -->|"+ noise"| X2["x_2"]
        X2 -->|"..."| XT["x_T (pure noise)"]
    end
    subgraph "Reverse Process (denoise)"
        XT2["x_T (noise)"] -->|"neural net"| XR2["x_{T-1}"]
        XR2 -->|"neural net"| XR1["x_{T-2}"]
        XR1 -->|"..."| XR0["x_0 (generated data)"]
    end

MCMC: Monte Carlo via Cadeias de Markov

As vezes você precisa amostrar de uma distribuição p(x) que você consegue avaliar (a menos de uma constante), mas não consegue amostrar diretamente. As posterioris bayesianas são o exemplo clássico -- você conhece a verossimilhança vezes a priori, mas a constante de normalização e intratável.

Metropolis-Hastings constrói uma cadeia de Markov cuja distribuição estacionária e p(x):

1. Comece em alguma posição x
2. Proponha uma nova posição x' a partir de uma distribuição de proposta Q(x'|x)
3. Calcule a razão de aceitação: a = p(x') * Q(x|x') / (p(x) * Q(x'|x))
4. Aceite x' com probabilidade min(1, a). Caso contrario, permaneca em x.
5. Repita.

Se Q for simétrica (por exemplo, Q(x'|x) = Q(x|x') = N(x, sigma^2)), a razão se simplifica para a = p(x') / p(x). Você só precisa da razão de probabilidades -- a constante de normalização se cancela.

A cadeia tem convergência garantida para p(x) sob condições brandas. Mas a convergência pode ser lenta se a proposta for muito pequena (passeio aleatório) ou muito grande (alta rejeição). Ajustar a proposta e a arte do MCMC.

Por que funciona. A razão de aceitação garante o balanço detalhado: a probabilidade de estar em x e mover para x' e igual a probabilidade de estar em x' e mover para x. O balanço detalhado implica que p(x) e a distribuição estacionária da cadeia. Portanto, após passos suficientes, as amostras vem de p(x).

Considerações práticas:

• Burn-in: descarte as primeiras N amostras. A cadeia precisa de tempo para alcançar a distribuição estacionária a partir do seu ponto de partida.
• Afinamento (thinning): mantenha cada k-ésima amostra para reduzir a autocorrelacao.
• Múltiplas cadeias: rode várias cadeias a partir de pontos de partida diferentes. Se elas convergem para a mesma distribuição, você tem evidência de convergência.
• Taxa de aceitação: para propostas gaussianas em d dimensões, a taxa de aceitação ótima e cerca de 23% (Roberts & Rosenthal, 2001). Muito alta significa que a cadeia mal se move. Muito baixa significa que ela rejeita tudo.

Processos Estocásticos em IA

Build It

Passo 1: Simulador de passeio aleatório

import numpy as np

def random_walk_1d(n_steps, seed=None):
    rng = np.random.RandomState(seed)
    steps = rng.choice([-1, 1], size=n_steps)
    positions = np.concatenate([[0], np.cumsum(steps)])
    return positions


def random_walk_2d(n_steps, seed=None):
    rng = np.random.RandomState(seed)
    directions = rng.choice(4, size=n_steps)
    dx = np.zeros(n_steps)
    dy = np.zeros(n_steps)
    dx[directions == 0] = 1   # right
    dx[directions == 1] = -1  # left
    dy[directions == 2] = 1   # up
    dy[directions == 3] = -1  # down
    x = np.concatenate([[0], np.cumsum(dx)])
    y = np.concatenate([[0], np.cumsum(dy)])
    return x, y

O passeio em 1D armazena somas cumulativas. Cada passo e +1 ou -1. Após n passos, a posição e a soma. A variância cresce linearmente com n, então o desvio padrão cresce como sqrt(n).

Passo 2: Cadeia de Markov

class MarkovChain:
    def __init__(self, transition_matrix, state_names=None):
        self.P = np.array(transition_matrix, dtype=float)
        self.n_states = len(self.P)
        self.state_names = state_names or [str(i) for i in range(self.n_states)]

    def step(self, current_state, rng=None):
        if rng is None:
            rng = np.random.RandomState()
        probs = self.P[current_state]
        return rng.choice(self.n_states, p=probs)

    def simulate(self, start_state, n_steps, seed=None):
        rng = np.random.RandomState(seed)
        states = [start_state]
        current = start_state
        for _ in range(n_steps):
            current = self.step(current, rng)
            states.append(current)
        return states

    def stationary_distribution(self):
        eigenvalues, eigenvectors = np.linalg.eig(self.P.T)
        idx = np.argmin(np.abs(eigenvalues - 1.0))
        stationary = np.real(eigenvectors[:, idx])
        stationary = stationary / stationary.sum()
        return np.abs(stationary)

A distribuição estacionária e o autovetor a esquerda de P com autovalor 1. Encontramos isso calculando os autovetores de P^T (transpor transforma autovetores a esquerda em autovetores a direita).

Passo 3: Dinâmica de Langevin

def langevin_dynamics(grad_U, x0, dt, temperature, n_steps, seed=None):
    rng = np.random.RandomState(seed)
    x = np.array(x0, dtype=float)
    trajectory = [x.copy()]
    for _ in range(n_steps):
        noise = rng.randn(*x.shape)
        x = x - dt * grad_U(x) + np.sqrt(2 * temperature * dt) * noise
        trajectory.append(x.copy())
    return np.array(trajectory)

O gradiente empurra x em direção a baixa energia. O ruído impede que ele fique preso. No equilibrio, a distribuição das amostras e proporcional a exp(-U(x)/temperature).

Passo 4: Metropolis-Hastings

def metropolis_hastings(target_log_prob, proposal_std, x0, n_samples, seed=None):
    rng = np.random.RandomState(seed)
    x = np.array(x0, dtype=float)
    samples = [x.copy()]
    accepted = 0
    for _ in range(n_samples - 1):
        x_proposed = x + rng.randn(*x.shape) * proposal_std
        log_ratio = target_log_prob(x_proposed) - target_log_prob(x)
        if np.log(rng.rand()) < log_ratio:
            x = x_proposed
            accepted += 1
        samples.append(x.copy())
    acceptance_rate = accepted / (n_samples - 1)
    return np.array(samples), acceptance_rate

O algoritmo propoe um novo ponto, verifica se ele tem probabilidade maior (ou aceita com probabilidade proporcional a razão) e repete. A taxa de aceitação deve ficar em torno de 23-50% para uma boa mistura.

Use It

Na prática, você usa bibliotecas estabelecidas para esses algoritmos. Mas entender a mecânica importa para depuração e ajuste.

import numpy as np

rng = np.random.RandomState(42)
walk = np.cumsum(rng.choice([-1, 1], size=10000))
print(f"Final position: {walk[-1]}")
print(f"Expected distance: {np.sqrt(10000):.1f}")
print(f"Actual distance: {abs(walk[-1])}")

numpy para matrizes de transição

import numpy as np

P = np.array([[0.7, 0.1, 0.2],
              [0.3, 0.4, 0.3],
              [0.4, 0.2, 0.4]])

distribution = np.array([1.0, 0.0, 0.0])
for _ in range(100):
    distribution = distribution @ P

print(f"Stationary distribution: {np.round(distribution, 4)}")

Multiplique a distribuição inicial por P repetidamente. Após iterações suficientes, ela converge para a distribuição estacionária, independentemente de onde você começou. Este e o método da potência para encontrar o autovetor dominante a esquerda.

Conexões com frameworks reais

• Difusão em PyTorch: O DDPMScheduler no diffusers da Hugging Face implementa as cadeias de Markov direta e reversa
• NumPyro / PyMC: Usam MCMC (amostrador NUTS, que aprimora o Metropolis-Hastings) para inferência bayesiana
• Gymnasium (RL): A função de passo (step) do ambiente define um processo de decisão de Markov

Verificando a convergência da cadeia de Markov

import numpy as np

P = np.array([[0.9, 0.1], [0.3, 0.7]])

eigenvalues = np.linalg.eigvals(P)
spectral_gap = 1 - sorted(np.abs(eigenvalues))[-2]
print(f"Eigenvalues: {eigenvalues}")
print(f"Spectral gap: {spectral_gap:.4f}")
print(f"Approximate mixing time: {1/spectral_gap:.1f} steps")

O gap espectral lhe diz quão rápido a cadeia esquece seu estado inicial. Um gap de 0.2 significa cerca de 5 passos para misturar. Um gap de 0.01 significa cerca de 100 passos. Sempre verifique isso antes de rodar simulações longas -- uma cadeia que mistura lentamente desperdiça computação.

Ship It

Esta lição produz:

• outputs/prompt-stochastic-process-advisor.md -- um prompt que ajuda a identificar qual framework de processo estocástico se aplica a um dado problema

Conexões

Os modelos de difusão merecem atenção especial. O DDPM (Ho et al., 2020) define uma cadeia de Markov direta:

q(x_t | x_{t-1}) = N(x_t; sqrt(1-beta_t) * x_{t-1}, beta_t * I)

onde beta_t e um cronograma de ruído. Após T passos, x_T e aproximadamente N(0, I). O processo reverso e parametrizado por uma rede neural que preve o ruído:

p_theta(x_{t-1} | x_t) = N(x_{t-1}; mu_theta(x_t, t), sigma_t^2 * I)

Cada passo da geração e um passo em uma cadeia de Markov aprendida. Entender as cadeias de Markov significa entender como e por que os modelos de difusão geram dados.

A SGLD (Dinâmica de Langevin com Gradiente Estocástico) combina o gradiente descendente em mini-lotes com ruído de Langevin. Em vez de calcular o gradiente completo, você usa uma estimativa estocástica e adiciona ruído calibrado. A medida que a taxa de aprendizado decai, a SGLD transiciona de otimização para amostragem -- você obtém amostras aproximadas da posteriori bayesiana de graça. Esta e uma das formas mais simples de obter estimativas de incerteza de uma rede neural.

A ideia central em todas essas conexões: processos estocásticos não são apenas ferramentas teóricas. Eles são os mecanismos computacionais dentro dos sistemas modernos de IA. Quando você ajusta a temperatura de um LLM, você esta ajustando uma cadeia de Markov. Quando você treina um modelo de difusão, você esta aprendendo a reverter um processo parecido com o movimento Browniano. Quando você roda inferência bayesiana, você esta construindo uma cadeia que converge para a posteriori.

Exercícios

1. Simule 1000 passeios aleatórios de 10000 passos. Plote a distribuição das posições finais. Verifique se ela e aproximadamente gaussiana com média 0 e desvio padrão sqrt(10000) = 100.

2. Construa um gerador de texto usando uma cadeia de Markov. Treine em um pequeno corpus: para cada palavra, conte as transições para a próxima palavra. Construa a matriz de transição. Gere novas frases amostrando da cadeia.

3. Implemente o recozimento simulado (simulated annealing) usando Metropolis-Hastings. Comece em alta temperatura (aceite quase tudo) e resfrie gradualmente (aceite apenas melhorias). Use-o para encontrar o mínimo de uma função com muitos mínimos locais.

4. Compare a dinâmica de Langevin em diferentes temperaturas. Amostre de um potencial de poço duplo U(x) = (x^2 - 1)^2. Em baixa temperatura, as amostras se agrupam em um poço. Em alta temperatura, elas se espalham por ambos. Encontre a temperatura crítica em que a cadeia mistura entre os poços.

5. Implemente o processo de difusão direto. Comece com um sinal 1D (por exemplo, uma onda senoidal). Adicione ruído progressivamente ao longo de 100 passos com um cronograma de ruído linear. Mostre como o sinal se degrada até virar ruído puro. Depois implemente um removedor de ruído simples que reverte o processo (mesmo um ingênuo que apenas subtrai o ruído estimado).

Termos-Chave

Leitura Adicional

• Ho, Jain, Abbeel (2020) -- "Denoising Diffusion Probabilistic Models." O artigo do DDPM que lancou a revolucao dos modelos de difusão. Derivação clara das cadeias de Markov direta e reversa.
• Song & Ermon (2019) -- "Generative Modeling by Estimating Gradients of the Data Distribution." Abordagem baseada em score usando dinâmica de Langevin para amostragem.
• Roberts & Rosenthal (2004) -- "General state space Markov chains and MCMC algorithms." A teoria por trás de quando e por que o MCMC funciona.
• Norris (1997) -- "Markov Chains." O livro-texto padrão. Cobre convergência, distribuições estacionárias e tempos de chegada (hitting times).
• Welling & Teh (2011) -- "Bayesian Learning via Stochastic Gradient Langevin Dynamics." Combina SGD com dinâmica de Langevin para inferência bayesiana escalável.