Phase 01 - Lesson 22

Procesos Estocásticos

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

Aleatoriedad con estructura. La matemática detrás de las caminatas aleatorias, las cadenas de Markov y los modelos de difusión.

Tipo: Learn Lenguaje: Python Prerrequisitos: Fase 1, Lecciones 06-07 (probabilidad, Bayes) Tiempo: ~75 minutos

Objetivos de Aprendizaje

• Simular caminatas aleatorias en 1D y 2D y verificar el escalado sqrt(n) del desplazamiento
• Construir un simulador de cadena de Markov y calcular su distribución estacionaria mediante descomposición en autovalores
• Implementar MCMC con Metropolis-Hastings y dinámica de Langevin para muestrear distribuciones objetivo
• Conectar el proceso de difusión directo con el movimiento browniano y explicar cómo el proceso inverso genera datos

El Problema

Muchos sistemas de IA involucran aleatoriedad que evoluciona con el tiempo. No aleatoriedad estática -- aleatoriedad estructurada y secuencial, donde cada paso depende de lo que vino antes.

Los modelos de lenguaje generan tokens de a uno a la vez. Cada token depende del contexto anterior. El modelo produce una distribución de probabilidad, muestrea de ella y continúa. Eso es un proceso estocástico.

Los modelos de difusión agregan ruido a una imagen paso a paso hasta que se convierte en puro ruido estático. Luego revierten el proceso, eliminando el ruido paso a paso hasta que emerge una nueva imagen. El proceso directo es una cadena de Markov. El proceso inverso es una cadena de Markov aprendida que se ejecuta hacia atrás.

Los agentes de aprendizaje por refuerzo toman acciones en un entorno. Cada acción conduce a un nuevo estado con cierta probabilidad. El agente sigue una política aleatoria en un mundo aleatorio. Todo el conjunto es un proceso de decisión de Markov.

El muestreo MCMC -- la columna vertebral de la inferencia bayesiana -- construye una cadena de Markov cuya distribución estacionaria es la posterior de la que quieres muestrear.

Todo esto se construye sobre cuatro ideas fundamentales:

1. Caminatas aleatorias -- el proceso estocástico más simple
2. Cadenas de Markov -- aleatoriedad estructurada con una matriz de transición
3. Dinámica de Langevin -- descenso de gradiente con ruido
4. Metropolis-Hastings -- muestreo de cualquier distribución

El Concepto

Caminatas Aleatorias

Comienza en la posición 0. En cada paso, lanza una moneda justa. Cara: muévete a la derecha (+1). Cruz: muévete a la izquierda (-1).

Después de n pasos, tu posición es la suma de n valores aleatorios +/-1. La posición esperada es 0 (la caminata no tiene sesgo). Pero la distancia esperada desde el origen crece como sqrt(n).

Esto es contraintuitivo. La caminata es justa -- no hay deriva en ninguna dirección. Pero con el tiempo, se aleja cada vez más de donde comenzó. La desviación estándar después de n pasos es 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))

En 2D, la caminata se mueve hacia arriba, abajo, izquierda o derecha con igual probabilidad. El mismo escalado sqrt(n) se aplica a la distancia desde el origen. El camino traza un patrón similar a un fractal.

¿Por qué sqrt(n)? Cada paso es +1 o -1 con igual probabilidad. Después de n pasos, la posición S_n = X_1 + X_2 + ... + X_n donde cada X_i es +/-1. La varianza de cada paso es 1, y los pasos son independientes, por lo que Var(S_n) = n. Desviación estándar = sqrt(n). Por el teorema central del límite, S_n / sqrt(n) converge a una distribución normal estándar.

Este escalado sqrt(n) aparece en todas partes en ML. El ruido del SGD escala como 1/sqrt(batch_size). Las dimensiones de embedding escalan como sqrt(d). La raíz cuadrada es la firma de las adiciones aleatorias independientes.

Conexión con el movimiento browniano. Toma una caminata aleatoria con tamaño de paso 1/sqrt(n) y n pasos por unidad de tiempo. A medida que n tiende a infinito, la caminata converge al movimiento browniano B(t) -- un proceso de tiempo continuo donde B(t) tiene distribución normal con media 0 y varianza t.

El movimiento browniano es la base matemática de la difusión. Modela el temblor aleatorio de las partículas en un fluido, las fluctuaciones de los precios de las acciones y -- crucialmente -- el proceso de ruido en los modelos de difusión.

Ruina del jugador (Gambler's ruin). Un caminante aleatorio que comienza en la posición k, con barreras absorbentes en 0 y N. ¿Cuál es la probabilidad de alcanzar N antes que 0? Para una caminata justa: P(alcanzar N) = k/N. Esto es sorprendentemente simple y elegante. Se conecta con la teoría de las martingalas -- la caminata aleatoria justa es una martingala (valor futuro esperado = valor actual).

Cadenas de Markov

Una cadena de Markov es un sistema que transiciona entre estados de acuerdo con probabilidades fijas. La propiedad clave: el siguiente estado depende solo del estado actual, no del historial.

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

Esta es la propiedad de Markov. Significa que puedes describir toda la dinámica con una matriz de transición P:

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

Cada fila de P suma 1 (tienes que ir a algún lugar).

Ejemplo -- 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)

Comienza en cualquier estado. Después de muchas transiciones, la distribución de estados converge a la distribución estacionaria pi, donde pi * P = pi. Este es el autovector izquierdo de P con autovalor 1.

Para la cadena del clima, la distribución estacionaria podría ser [0.53, 0.18, 0.29] -- a largo plazo, está soleado el 53% del tiempo, independientemente del 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

Calcular la distribución estacionaria. Hay dos enfoques:

1. Método de la potencia: multiplica cualquier distribución inicial por P repetidamente. Después de suficientes iteraciones, converge.
2. Método de los autovalores: encuentra el autovector izquierdo de P con autovalor 1. Este es el autovector de P^T con autovalor 1.

Ambos enfoques requieren que la cadena satisfaga condiciones de convergencia.

Condiciones de convergencia. Una cadena de Markov converge a una distribución estacionaria única si es:

• Irreducible: todo estado es alcanzable desde cualquier otro estado
• Aperiódica: la cadena no cicla con un periodo fijo

La mayoría de las cadenas que encuentras en ML satisfacen ambas condiciones.

Estados absorbentes. Un estado es absorbente si una vez que entras en él, nunca sales (P[i][i] = 1). Las cadenas de Markov absorbentes modelan procesos con estados terminales -- un juego que termina, un cliente que se da de baja (churn), una secuencia de tokens que alcanza el token de fin de texto.

Tiempo de mezcla. ¿Cuántos pasos hasta que la cadena esté "cerca" de la distribución estacionaria? Formalmente, el número de pasos hasta que la distancia de variación total respecto a la estacionariedad caiga por debajo de algún umbral. Mezcla rápida = pocos pasos necesarios. El gap espectral de P (1 menos el segundo autovalor más grande) controla el tiempo de mezcla. Un gap mayor = mezcla más rápida.

Conexión con los Modelos de Lenguaje

La generación de tokens en un modelo de lenguaje es aproximadamente un proceso de Markov. Dado el contexto actual, el modelo produce una distribución sobre el siguiente token. La temperatura controla la nitidez:

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

• Temperatura = 1.0: distribución estándar
• Temperatura < 1.0: más nítida (más determinista)
• Temperatura > 1.0: más plana (más aleatoria)
• Temperatura -> 0: argmax (voraz)

El muestreo top-k trunca a los k tokens de mayor probabilidad. El muestreo top-p (nucleus) trunca al conjunto más pequeño de tokens cuya probabilidad acumulada excede p. Ambos modifican las probabilidades de transición de Markov.

Movimiento Browniano

El límite de tiempo continuo de la caminata aleatoria. La posición B(t) tiene tres propiedades:

1. B(0) = 0
2. B(t) - B(s) tiene distribución normal con media 0 y varianza t - s (para t > s)
3. Los incrementos en intervalos no superpuestos son independientes

El movimiento browniano es continuo pero en ningún lugar diferenciable -- tiembla a toda escala. El camino tiene dimensión fractal 2 en el plano.

En la simulación discreta, aproximas el movimiento browniano mediante:

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

El escalado sqrt(dt) es importante. Proviene del teorema central del límite aplicado a las caminatas aleatorias.

Dinámica de Langevin

El descenso de gradiente encuentra el mínimo de una función. La dinámica de Langevin encuentra la distribución de probabilidad proporcional a exp(-U(x)/T), donde U es una función de energía y T es la temperatura.

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

Dos fuerzas actúan sobre la partícula:

1. Fuerza del gradiente (-dt * gradient(U)): empuja hacia la energía baja (como el descenso de gradiente)
2. Fuerza aleatoria (sqrt(2Tdt) * z): empuja en direcciones aleatorias (exploración)

A temperatura T = 0, esto es descenso de gradiente puro. A alta temperatura, es casi una caminata aleatoria. A la temperatura correcta, la partícula explora el paisaje de energía y pasa más tiempo en regiones de baja energía.

Conexión con los modelos de difusión. El proceso directo de un modelo de difusión es:

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

Esta es una cadena de Markov que gradualmente mezcla los datos con ruido. Después de suficientes pasos, x_T es ruido gaussiano puro.

El proceso inverso -- yendo del ruido de vuelta a los datos -- también es una cadena de Markov, pero sus probabilidades de transición son aprendidas por una red neuronal. La red aprende a predecir el ruido que se agregó en cada paso y luego lo resta.

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 mediante Cadenas de Markov

A veces necesitas muestrear de una distribución p(x) que puedes evaluar (salvo una constante) pero no puedes muestrear directamente. Las posteriores bayesianas son el ejemplo clásico -- conoces la verosimilitud por la prior, pero la constante de normalización es intratable.

Metropolis-Hastings construye una cadena de Markov cuya distribución estacionaria es p(x):

1. Comienza en alguna posición x
2. Propone una nueva posición x' a partir de una distribución de propuesta Q(x'|x)
3. Calcula la razón de aceptación: a = p(x') * Q(x|x') / (p(x) * Q(x'|x))
4. Acepta x' con probabilidad min(1, a). De lo contrario, permanece en x.
5. Repite.

Si Q es simétrica (por ejemplo, Q(x'|x) = Q(x|x') = N(x, sigma^2)), la razón se simplifica a a = p(x') / p(x). Solo necesitas la razón de probabilidades -- la constante de normalización se cancela.

La cadena tiene convergencia garantizada a p(x) bajo condiciones leves. Pero la convergencia puede ser lenta si la propuesta es demasiado pequeña (caminata aleatoria) o demasiado grande (alto rechazo). Ajustar la propuesta es el arte del MCMC.

Por qué funciona. La razón de aceptación garantiza el balance detallado: la probabilidad de estar en x y moverse a x' es igual a la probabilidad de estar en x' y moverse a x. El balance detallado implica que p(x) es la distribución estacionaria de la cadena. Así que después de suficientes pasos, las muestras provienen de p(x).

Consideraciones prácticas:

• Burn-in: descarta las primeras N muestras. La cadena necesita tiempo para alcanzar la distribución estacionaria desde su punto de partida.
• Adelgazamiento (thinning): conserva cada k-ésima muestra para reducir la autocorrelación.
• Múltiples cadenas: ejecuta varias cadenas desde puntos de partida diferentes. Si convergen a la misma distribución, tienes evidencia de convergencia.
• Tasa de aceptación: para propuestas gaussianas en d dimensiones, la tasa de aceptación óptima es de alrededor del 23% (Roberts & Rosenthal, 2001). Demasiado alta significa que la cadena apenas se mueve. Demasiado baja significa que rechaza todo.

Procesos Estocásticos en IA

Build It

Paso 1: Simulador de caminata aleatoria

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

La caminata en 1D almacena sumas acumuladas. Cada paso es +1 o -1. Después de n pasos, la posición es la suma. La varianza crece linealmente con n, por lo que la desviación estándar crece como sqrt(n).

Paso 2: Cadena 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)

La distribución estacionaria es el autovector izquierdo de P con autovalor 1. La encontramos calculando los autovectores de P^T (transponer convierte los autovectores izquierdos en autovectores derechos).

Paso 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)

El gradiente empuja a x hacia la energía baja. El ruido evita que se quede atascado. En el equilibrio, la distribución de las muestras es proporcional a exp(-U(x)/temperature).

Paso 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

El algoritmo propone un nuevo punto, verifica si tiene mayor probabilidad (o acepta con probabilidad proporcional a la razón) y repite. La tasa de aceptación debería estar alrededor del 23-50% para una buena mezcla.

Use It

En la práctica, usas bibliotecas establecidas para estos algoritmos. Pero entender la mecánica importa para la depuración y el 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 matrices de transición

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)}")

Multiplica la distribución inicial por P repetidamente. Después de suficientes iteraciones, converge a la distribución estacionaria independientemente de dónde comenzaste. Este es el método de la potencia para encontrar el autovector dominante izquierdo.

Conexiones con frameworks reales

• Difusión en PyTorch: El DDPMScheduler en diffusers de Hugging Face implementa las cadenas de Markov directa e inversa
• NumPyro / PyMC: Usan MCMC (muestreador NUTS, que mejora el Metropolis-Hastings) para inferencia bayesiana
• Gymnasium (RL): La función de paso (step) del entorno define un proceso de decisión de Markov

Verificar la convergencia de la cadena 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")

El gap espectral te dice qué tan rápido la cadena olvida su estado inicial. Un gap de 0.2 significa aproximadamente 5 pasos para mezclar. Un gap de 0.01 significa aproximadamente 100 pasos. Siempre verifica esto antes de ejecutar simulaciones largas -- una cadena que mezcla lentamente desperdicia cómputo.

Ship It

Esta lección produce:

• outputs/prompt-stochastic-process-advisor.md -- un prompt que ayuda a identificar qué framework de proceso estocástico se aplica a un problema dado

Conexiones

Los modelos de difusión merecen atención especial. El DDPM (Ho et al., 2020) define una cadena de Markov directa:

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

donde beta_t es un cronograma de ruido. Después de T pasos, x_T es aproximadamente N(0, I). El proceso inverso es parametrizado por una red neuronal que predice el ruido:

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

Cada paso de la generación es un paso en una cadena de Markov aprendida. Entender las cadenas de Markov significa entender cómo y por qué los modelos de difusión generan datos.

La SGLD (Dinámica de Langevin con Gradiente Estocástico) combina el descenso de gradiente en mini-lotes con ruido de Langevin. En lugar de calcular el gradiente completo, usas una estimación estocástica y agregas ruido calibrado. A medida que la tasa de aprendizaje decae, la SGLD transiciona de la optimización al muestreo -- obtienes muestras aproximadas de la posterior bayesiana de forma gratuita. Esta es una de las formas más simples de obtener estimaciones de incertidumbre de una red neuronal.

La idea clave a través de todas estas conexiones: los procesos estocásticos no son solo herramientas teóricas. Son los mecanismos computacionales dentro de los sistemas modernos de IA. Cuando ajustas la temperatura de un LLM, estás ajustando una cadena de Markov. Cuando entrenas un modelo de difusión, estás aprendiendo a revertir un proceso similar al movimiento browniano. Cuando ejecutas inferencia bayesiana, estás construyendo una cadena que converge a la posterior.

Ejercicios

1. Simula 1000 caminatas aleatorias de 10000 pasos. Grafica la distribución de las posiciones finales. Verifica que sea aproximadamente gaussiana con media 0 y desviación estándar sqrt(10000) = 100.

2. Construye un generador de texto usando una cadena de Markov. Entrena en un pequeño corpus: para cada palabra, cuenta las transiciones a la siguiente palabra. Construye la matriz de transición. Genera nuevas oraciones muestreando de la cadena.

3. Implementa el recocido simulado (simulated annealing) usando Metropolis-Hastings. Comienza a alta temperatura (acepta casi todo) y enfría gradualmente (acepta solo mejoras). Úsalo para encontrar el mínimo de una función con muchos mínimos locales.

4. Compara la dinámica de Langevin a diferentes temperaturas. Muestrea de un potencial de doble pozo U(x) = (x^2 - 1)^2. A baja temperatura, las muestras se agrupan en un pozo. A alta temperatura, se dispersan por ambos. Encuentra la temperatura crítica en la que la cadena mezcla entre los pozos.

5. Implementa el proceso de difusión directo. Comienza con una señal 1D (por ejemplo, una onda senoidal). Agrega ruido progresivamente a lo largo de 100 pasos con un cronograma de ruido lineal. Muestra cómo la señal se degrada hasta convertirse en ruido puro. Luego implementa un eliminador de ruido simple que revierta el proceso (incluso uno ingenuo que solo reste el ruido estimado).

Términos Clave

Lectura Adicional

• Ho, Jain, Abbeel (2020) -- "Denoising Diffusion Probabilistic Models." El artículo del DDPM que lanzó la revolución de los modelos de difusión. Derivación clara de las cadenas de Markov directa e inversa.
• Song & Ermon (2019) -- "Generative Modeling by Estimating Gradients of the Data Distribution." Enfoque basado en score usando dinámica de Langevin para el muestreo.
• Roberts & Rosenthal (2004) -- "General state space Markov chains and MCMC algorithms." La teoría detrás de cuándo y por qué funciona el MCMC.
• Norris (1997) -- "Markov Chains." El libro de texto estándar. Cubre convergencia, distribuciones estacionarias y tiempos de llegada (hitting times).
• Welling & Teh (2011) -- "Bayesian Learning via Stochastic Gradient Langevin Dynamics." Combina SGD con dinámica de Langevin para inferencia bayesiana escalable.