Procese stocastice

Aleatoriu, dar cu structură. Matematica din spatele mersurilor aleatorii, al lanțurilor Markov și al modelelor de difuzie.

Tip: Învățare Limbaj: Python Cerințe preliminare: Faza 1, lecțiile 06–07 (probabilități, Bayes) Durată: ~75 de minute

Obiective de învățare

• Să simulați mersuri aleatorii 1D și 2D și să verificați scalarea cu sqrt(n) a abaterii
• Să construiți un simulator de lanț Markov și să-i calculați distribuția staționară prin descompunere în valori proprii
• Să implementați MCMC Metropolis–Hastings și dinamica Langevin pentru eșantionarea din distribuții țintă
• Să corelați procesul de difuzie direct cu mișcarea browniană și să explicați cum generează date procesul invers

Problema

Numeroase sisteme de IA includ aleatoriu care evoluează în timp. Nu este vorba despre aleatoriu static, ci despre unul structurat și secvențial, în care fiecare pas depinde de ceea ce l-a precedat.

Modelele lingvistice generează tokenuri pe rând. Fiecare token depinde de contextul precedent. Modelul produce o distribuție de probabilitate, eșantionează din ea și trece mai departe. Acesta este un proces stocastic.

Modelele de difuzie adaugă zgomot unei imagini pas cu pas, până când aceasta devine aproximativ zgomot gaussian. Apoi inversează procesul, eliminând zgomotul treptat până când apare o imagine nouă. Procesul direct este un lanț Markov, iar cel invers este un lanț Markov învățat, parcurs în sens invers.

Agenții de învățare prin întărire efectuează acțiuni într-un mediu. Fiecare acțiune conduce, cu anumite probabilități, la o stare nouă. Agentul urmează o politică stocastică într-o lume stocastică. Întregul sistem este un proces decizional Markov.

Eșantionarea MCMC — un instrument central al inferenței bayesiene — construiește un lanț Markov a cărui distribuție staționară este distribuția a posteriori din care doriți să eșantionați.

Toate acestea se bazează pe patru idei fundamentale:

1. Mersuri aleatorii — cel mai simplu proces stocastic
2. Lanțuri Markov — aleatoriu structurat printr-o matrice de tranziție
3. Dinamică Langevin — coborâre pe gradient cu zgomot
4. Metropolis–Hastings — eșantionare dintr-o distribuție arbitrară

Conceptul

Mersuri aleatorii

Porniți din poziția 0. La fiecare pas, aruncați o monedă echitabilă. Pajură: vă deplasați la dreapta (+1). Cap: vă deplasați la stânga (−1).

După n pași, poziția este suma a n valori aleatoare +/−1. Poziția așteptată este 0, deoarece mersul nu are derivă. Totuși, scara tipică a distanței față de origine crește ca sqrt(n).

Acest fapt poate părea contraintuitiv. Mersul este echitabil — nu există derivă în nicio direcție — dar, cu timpul, se îndepărtează tot mai mult de punctul de pornire. Abaterea standard după n pași este sqrt(n).

Pasul 0:  Poziție = 0
Pasul 1:  Poziție = +1 sau -1
Pasul 2:  Poziție = +2, 0 sau -2
...
Pasul 100: Distanță așteptată față de origine ~ 10 (sqrt(100))
Pasul 10000: Distanță așteptată față de origine ~ 100 (sqrt(10000))

Notă tehnică: Blocul original folosește „expected distance” pentru sqrt(n), însă sqrt(n) este abaterea standard și distanța RMS. În 1D, distanța absolută medie este asimptotic sqrt(2n/pi), nu sqrt(n).

În 2D, mersul se deplasează în sus, în jos, la stânga sau la dreapta cu probabilități egale. Distanța RMS față de origine are aceeași scalare sqrt(n), iar traseul conturează un tipar asemănător unui fractal.

De ce sqrt(n)? Fiecare pas este +1 sau −1 cu probabilități egale. După n pași, poziția este S_n = X_1 + X_2 + … + X_n, unde fiecare X_i este +/−1. Varianța fiecărui pas este 1, iar pașii sunt independenți, deci Var(S_n) = n. Abaterea standard este sqrt(n). Conform teoremei limitei centrale, S_n / sqrt(n) converge în distribuție la o normală standard.

Această scalare cu sqrt(n) apare frecvent în ML. Dacă exemplele au contribuții independente și comparabile, zgomotul estimării gradientului prin minibatch scade ca 1/sqrt(batch_size). De asemenea, factori precum 1/sqrt(d) normalizează produse scalare în mecanismele de atenție. Rădăcina pătrată este semnătura sumelor de contribuții aleatoare independente.

Legătura cu mișcarea browniană. Considerați un mers aleatoriu cu pas de mărime 1/sqrt(n) și n pași pe unitate de timp. Când n tinde la infinit, mersul converge la mișcarea browniană B(t) — un proces în timp continuu în care B(t) are distribuție normală cu medie 0 și varianță t.

Mișcarea browniană este fundamentul matematic al difuziei. Ea modelează agitația aleatoare a particulelor dintr-un fluid, fluctuațiile prețurilor activelor și — aspect esențial aici — procesul de zgomot folosit de modelele de difuzie.

Ruina jucătorului. Un participant la un mers aleatoriu pornește din poziția k, cu bariere absorbante la 0 și N. Care este probabilitatea de a ajunge la N înainte de 0? Pentru un mers echitabil: P(atinge N) = k/N. Este un rezultat surprinzător de simplu și elegant. El se leagă de teoria martingalelor: mersul aleatoriu echitabil este o martingală, adică valoarea sa viitoare așteptată este egală cu valoarea curentă.

Lanțuri Markov

Un lanț Markov este un sistem care trece între stări conform unor probabilități fixe. Proprietatea esențială este că starea următoare depinde numai de starea curentă, nu de întregul istoric.

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

Aceasta este proprietatea Markov. Datorită ei, puteți descrie întreaga dinamică printr-o matrice de tranziție P:

P[i][j] = probabilitatea trecerii din starea i în starea j

Suma fiecărui rând din P este 1, deoarece sistemul trebuie să treacă într-o stare, inclusiv eventual în aceeași stare.

Exemplu — vremea:

Stări: Însorit (0), Ploios (1), Înnorat (2)

P = [[0.7, 0.1, 0.2],    (dacă este însorit: 70% însorit, 10% ploios, 20% înnorat)
     [0.3, 0.4, 0.3],    (dacă este ploios: 30% însorit, 40% ploios, 30% înnorat)
     [0.4, 0.2, 0.4]]    (dacă este înnorat: 40% însorit, 20% ploios, 40% înnorat)

Porniți din orice stare. După numeroase tranziții, distribuția stărilor converge la distribuția staționară pi, pentru care pi * P = pi. Aceasta este vectorul propriu stâng al lui P corespunzător valorii proprii 1.

Pentru lanțul vremii, distribuția staționară exactă este [6/11, 2/11, 3/11], adică aproximativ [0,5455, 0,1818, 0,2727]. Pe termen lung, vremea este însorită în aproximativ 54,55% din timp, indiferent de starea inițială.

Notă tehnică: Sursa indică aproximarea [0,53, 0,18, 0,29], care nu satisface exact ecuația pi * P = pi pentru matricea prezentată; valorile de mai sus sunt soluția normalizată corectă.

Calcularea distribuției staționare. Există două metode:

1. Metoda puterii: înmulțiți în mod repetat orice distribuție inițială cu P. După suficiente iterații, aceasta converge.
2. Metoda valorilor proprii: găsiți vectorul propriu stâng al lui P pentru valoarea proprie 1. Acesta este vectorul propriu al lui P^T corespunzător valorii proprii 1.

Ambele metode necesită îndeplinirea condițiilor de convergență relevante.

Condiții de convergență. Un lanț Markov finit converge la o distribuție staționară unică dacă este:

• Ireductibil: din orice stare se poate ajunge în oricare alta
• Aperiodic: lanțul nu evoluează într-un ciclu cu perioadă fixă

Multe lanțuri proiectate în aplicații ML îndeplinesc ambele condiții, dar acest lucru trebuie verificat, nu presupus.

Stări absorbante. O stare este absorbantă dacă, odată ce intrați în ea, nu o mai părăsiți (P[i][i] = 1). Lanțurile Markov absorbante modelează procese cu stări terminale: un joc care se încheie, un client care renunță la serviciu sau o secvență de tokenuri care ajunge la tokenul de sfârșit de text.

Timp de amestecare. Câți pași sunt necesari până când lanțul ajunge „aproape” de distribuția staționară? Formal, este numărul de pași după care distanța de variație totală față de staționaritate scade sub un prag ales. Amestecarea rapidă înseamnă puțini pași. Pentru lanțurile finite reversibile, decalajul spectral al lui P se leagă de timpul de amestecare: un decalaj mai mare implică, în general, o amestecare mai rapidă. Totuși, timpul exact depinde și de toleranță, distribuția inițială și masa staționară minimă.

Legătura cu modelele lingvistice

Generarea tokenurilor într-un model lingvistic poate fi formulată ca proces Markov dacă starea curentă include întregul context reținut și orice stare internă relevantă a modelului. Dată această stare, modelul produce o distribuție pentru tokenul următor. Temperatura controlează cât de concentrată este distribuția:

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

• Temperatură = 1,0: distribuția standard
• Temperatură < 1,0: mai concentrată, deci mai deterministă
• Temperatură > 1,0: mai uniformă, deci mai aleatorie
• Temperatură -> 0: argmax, adică alegere greedy

Eșantionarea top-k restrânge distribuția la cele k tokenuri cu probabilitatea cea mai mare. Eșantionarea top-p, sau nucleus, o restrânge la cea mai mică mulțime de tokenuri a căror probabilitate cumulată depășește p. Ambele modifică probabilitățile de tranziție condiționate de starea-context.

Mișcarea browniană

Mișcarea browniană este limita în timp continuu a mersului aleatoriu. Poziția B(t) are trei proprietăți:

1. B(0) = 0
2. B(t) - B(s) are distribuție normală cu medie 0 și varianță t - s, pentru t > s
3. Incrementele pe intervale care nu se suprapun sunt independente

Mișcarea browniană este continuă, dar aproape sigur nicăieri derivabilă: oscilează la orice scară. Urma mișcării browniene plane are aproape sigur dimensiune Hausdorff 2; această afirmație se referă la urma din plan, nu la graficul unei mișcări browniene scalare.

Într-o simulare discretă, aproximați mișcarea browniană astfel:

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

Scalarea cu sqrt(dt) este importantă. Ea provine din teorema limitei centrale aplicată mersurilor aleatorii.

Dinamica Langevin

Coborârea pe gradient găsește minimul unei funcții. Dinamica Langevin continuă poate eșantiona, în condiții adecvate, din distribuția proporțională cu exp(-U(x)/T), unde U este o funcție de energie, iar T este temperatura.

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

Asupra particulei acționează două forțe:

1. Forța gradientului (-dt * gradient(U)): împinge către energie scăzută, asemenea coborârii pe gradient
2. Forța aleatoare (sqrt(2Tdt) * z): împinge în direcții aleatoare și favorizează explorarea

La temperatura T = 0, actualizarea devine coborâre pe gradient. La temperatură ridicată, seamănă mai mult cu un mers aleatoriu. La o temperatură aleasă în funcție de distribuția urmărită, particula explorează peisajul energetic și petrece mai mult timp în regiunile cu energie joasă.

Notă tehnică: Ecuația din bloc este o discretizare Euler–Maruyama, numită și algoritmul Langevin neajustat. La un pas dt finit, distribuția sa invariantă poate fi deplasată față de exp(-U/T). Eroarea se reduce cu dt, iar o corecție Metropolis conduce la MALA.

Legătura cu modelele de difuzie. Procesul direct al unui model de difuzie este:

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

Acesta este un lanț Markov care amestecă treptat datele cu zgomot. După suficienți pași și pentru un program de zgomot adecvat, distribuția lui x_T este aproximativ gaussiană standard.

Procesul invers — de la zgomot înapoi la date — este tot un lanț Markov, însă probabilitățile sale de tranziție sunt parametrizate de o rețea neuronală. În parametrizarea uzuală DDPM, rețeaua prezice zgomotul, iar predicția este folosită pentru a calcula media tranziției inverse; pasul poate include și un termen aleatoriu de varianță prescrisă.

MCMC: Monte Carlo cu lanțuri Markov

Uneori trebuie să eșantionați dintr-o distribuție p(x) pe care o puteți evalua până la o constantă, dar din care nu puteți eșantiona direct. Distribuțiile a posteriori bayesiene sunt exemplul clasic: cunoașteți produsul dintre verosimilitate și distribuția a priori, însă constanta de normalizare este imposibil de calculat practic.

Metropolis–Hastings construiește un lanț Markov a cărui distribuție staționară este p(x):

1. Porniți dintr-o poziție x
2. Propuneți o poziție nouă x’ din distribuția de propunere Q(x’|x)
3. Calculați raportul de acceptare: a = p(x’) * Q(x|x’) / (p(x) * Q(x’|x))
4. Acceptați x’ cu probabilitatea min(1, a); în caz contrar, rămâneți în x
5. Repetați

Dacă Q este simetrică, de exemplu Q(x’|x) = Q(x|x’) = N(x, sigma^2), raportul se simplifică la a = p(x’) / p(x). Aveți nevoie numai de raportul probabilităților, deoarece constanta de normalizare se reduce.

Lanțul converge la p(x) dacă sunt îndeplinite condiții precum ireductibilitatea și aperiodicitatea, împreună cu proprietățile de recurență adecvate spațiului de stări. Convergența poate fi însă lentă dacă propunerea este prea mică, caz în care lanțul înaintează ca un mers aleatoriu, sau prea mare, caz în care multe propuneri sunt respinse. Reglarea propunerii este o parte importantă a aplicării MCMC.

De ce funcționează. Raportul de acceptare asigură echilibrul detaliat: fluxul de probabilitate staționar de la x la x’ este egal cu cel de la x’ la x. Echilibrul detaliat este o condiție suficientă, dar nu necesară, pentru ca p(x) să fie distribuția staționară a lanțului. După ce lanțul a ajuns la staționaritate, eșantioanele sale marginale urmează p(x), deși eșantioanele succesive sunt în general corelate.

Aspecte practice:

• Perioada de încălzire (burn-in): eliminați primele N eșantioane. Lanțul are nevoie de timp pentru a ajunge din starea inițială în regiunea staționară.
• Subeșantionarea (thinning): păstrarea fiecărui al k-lea eșantion reduce corelația dintre valorile păstrate, dar adesea irosește calcule și nu îmbunătățește dimensiunea efectivă a eșantionului pentru același buget de calcul.
• Lanțuri multiple: rulați mai multe lanțuri din puncte de pornire diferite. Acordul lor oferă dovezi de convergență, dar nu constituie singur o demonstrație.
• Rata de acceptare: valoarea optimă de aproximativ 23,4% este un rezultat asimptotic pentru algoritmul Metropolis de tip mers aleatoriu în dimensiuni mari, în anumite ipoteze. Alte propuneri, alte dimensiuni și alți algoritmi au ținte diferite; evaluați și deplasarea lanțului, autocorelația și dimensiunea efectivă a eșantionului.

Procese stocastice în IA

Proces	Aplicație în IA
Mers aleatoriu	Explorare în RL, reprezentări vectoriale Node2Vec
Lanț Markov	Generare de text, eșantionare MCMC
Mișcare browniană	Modele de difuzie, procesul direct
Dinamică Langevin	Modele generative bazate pe scor, SGLD
Proces decizional Markov	Învățare prin întărire
Metropolis–Hastings	Inferență bayesiană, eșantionare din distribuția a posteriori

random-walk-diffusion

Construiți

Pasul 1: simulator de mers aleatoriu

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

Mersul 1D stochează sumele cumulative. Fiecare pas este +1 sau −1, iar poziția după n pași este suma lor. Varianța crește liniar cu n, astfel încât abaterea standard crește ca sqrt(n).

Pasul 2: lanț 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)

Distribuția staționară este vectorul propriu stâng al lui P pentru valoarea proprie 1. Îl găsim calculând vectorii proprii ai lui P^T, deoarece transpunerea transformă vectorii proprii stângi în vectori proprii drepți.

Notă tehnică: Implementarea didactică presupune că matricea este stocastică și că distribuția staționară relevantă este unică. Codul nu validează aceste condiții, iar aplicarea np.abs poate ascunde un vector propriu ales sau orientat necorespunzător în cazuri problematice.

Pasul 3: dinamica 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)

Gradientul împinge x către energie joasă, iar zgomotul îl ajută să exploreze. Pentru dinamica continuă, distribuția de echilibru este proporțională cu exp(-U(x)/temperature). Implementarea discretă de mai sus o aproximează și poate avea o eroare dependentă de pasul dt.

Pasul 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

Algoritmul propune un punct nou, verifică dacă are o probabilitate mai mare sau îl acceptă cu probabilitatea dată de raport și repetă. Nu există un interval universal de rată de acceptare care să garanteze o amestecare bună; interpretați rata împreună cu deplasarea, autocorelația și dimensiunea efectivă a eșantionului. Implementarea presupune, de asemenea, n_samples > 1.

Folosiți

În practică, veți utiliza biblioteci consacrate pentru acești algoritmi. Înțelegerea mecanismelor rămâne însă importantă pentru depanare și reglare.

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

Notă tehnică: Eticheta Expected distance din cod este păstrată exact ca în sursă, dar valoarea calculată este abaterea standard și distanța RMS. Distanța absolută medie după 10.000 de pași este aproximativ sqrt(2 * 10000 / pi), adică 79,8.

NumPy pentru matrice de tranziție

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

Înmulțiți în mod repetat distribuția inițială cu P. Pentru acest lanț ireductibil și aperiodic, ea converge după suficiente iterații la distribuția staționară, indiferent de punctul de pornire. Aceasta este metoda puterii pentru găsirea vectorului propriu stâng dominant.

Legături cu framework-uri reale

• Difuzie în PyTorch: DDPMScheduler din Hugging Face diffusers implementează programarea pașilor procesului direct și invers
• NumPyro / PyMC: folosesc MCMC pentru inferență bayesiană, inclusiv eșantionatorul NUTS, care evită reglarea manuală a lungimii traiectoriei și este de regulă mai eficient decât Metropolis–Hastings cu mers aleatoriu
• Gymnasium (RL): funcția de pas a mediului definește dinamica unui proces decizional Markov

Verificarea convergenței unui lanț 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")

Decalajul spectral indică viteza cu care lanțul își pierde memoria stării inițiale. Cantitatea 1/decalaj este timpul de relaxare, nu timpul de amestecare propriu-zis. Timpul de amestecare include de regulă factori logaritmici care depind de toleranță și de distribuția staționară; de aceea, linia Approximate mixing time din exemplu trebuie citită numai ca indicator de scară. Verificați convergența înainte de simulări lungi, deoarece un lanț care se amestecă lent consumă resurse fără a produce multe eșantioane efectiv independente.

Livrați

Această lecție produce:

• outputs/prompt-stochastic-process-advisor.md — un prompt care vă ajută să identificați framework-ul de proces stocastic potrivit unei probleme

Legături

Concept	Unde apare
Mers aleatoriu	Reprezentări vectoriale de graf Node2Vec, explorare în RL
Lanț Markov	Generare de tokenuri în LLM-uri, eșantionare MCMC
Mișcare browniană	Procesul direct de difuzie în DDPM, modele bazate pe SDE
Dinamică Langevin	Modele generative bazate pe scor, dinamică Langevin cu gradient stocastic (SGLD)
Distribuție staționară	Ținta convergenței MCMC, PageRank
Metropolis–Hastings	Eșantionare a distribuției a posteriori bayesiene, recoacere simulată
Temperatură	Eșantionare LLM, explorare Boltzmann în RL, recoacere simulată
Timp de amestecare	Viteza de convergență MCMC, analiza decalajului spectral
Stare absorbantă	Token de sfârșit de secvență, stări terminale în RL
Echilibru detaliat	Condiție suficientă folosită pentru corectitudinea eșantionatoarelor MCMC

Modelele de difuzie merită o atenție specială. DDPM (Ho et al., 2020) definește un lanț Markov direct:

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

unde beta_t este un program de zgomot. După T pași, x_T are aproximativ distribuția N(0, I). Procesul invers este parametrizat de o rețea neuronală care prezice zgomotul:

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

Fiecare pas de generare este un pas într-un lanț Markov învățat. Înțelegerea lanțurilor Markov vă ajută să înțelegeți cum și de ce generează date modelele de difuzie.

SGLD, dinamica Langevin cu gradient stocastic, combină gradientul estimat din minibatch cu zgomot Langevin calibrat. Cu o schemă adecvată de pași descrescători și în ipoteze de regularitate, metoda poate aproxima eșantioane din distribuția a posteriori. La pași fini sau constanți, gradientul stocastic și discretizarea pot introduce deplasare; prin urmare, nu obțineți eșantioane bayesiene „gratuit”, fără controlul pașilor și diagnosticarea convergenței. Cu aceste precauții, SGLD este una dintre metodele simple de estimare a incertitudinii într-o rețea neuronală.

Ideea centrală a tuturor acestor legături este că procesele stocastice nu sunt doar instrumente teoretice. Ele sunt mecanisme computaționale din interiorul sistemelor IA moderne. Când reglați temperatura unui LLM, modificați distribuțiile de tranziție condiționate de context. Când antrenați un model de difuzie, învățați să inversați un proces asemănător mișcării browniene. Când efectuați inferență bayesiană, construiți un lanț care trebuie să convergă la distribuția a posteriori.

Exerciții

1. Simulați 1.000 de mersuri aleatorii cu câte 10.000 de pași. Reprezentați distribuția pozițiilor finale. Verificați că este aproximativ gaussiană, cu medie 0 și abatere standard sqrt(10000) = 100.

2. Construiți un generator de text bazat pe un lanț Markov. Antrenați-l pe un corpus mic: pentru fiecare cuvânt, numărați tranzițiile la cuvântul următor. Construiți matricea de tranziție. Generați propoziții noi eșantionând din lanț.

3. Implementați recoacerea simulată folosind Metropolis–Hastings. Porniți de la o temperatură ridicată, la care acceptați aproape orice, și reduceți-o treptat, până când acceptați aproape numai îmbunătățiri. Folosiți metoda pentru a găsi minimul unei funcții cu multe minime locale.

4. Comparați dinamica Langevin la temperaturi diferite. Eșantionați din potențialul cu două godeuri U(x) = (x^2 - 1)^2. La temperatură joasă, eșantioanele tind să rămână într-un godeu; la temperatură ridicată, trec mai frecvent între ele. Alegeți un orizont de simulare și un criteriu explicit de amestecare, apoi estimați temperatura la care tranzițiile între godeuri devin frecvente pentru acea configurație.

Notă tehnică: Pentru acest sistem finit nu există o singură „temperatură critică” universală de amestecare. Rezultatul depinde de bariera energetică, pasul de discretizare, durata simulării și criteriul ales.

5. Implementați procesul direct de difuzie. Porniți de la un semnal 1D, de exemplu o undă sinusoidală. Adăugați progresiv zgomot în 100 de pași, cu un program liniar. Arătați cum semnalul se degradează până la zgomot aproximativ gaussian. Apoi implementați un denoiser simplu care aproximează procesul invers, folosind estimarea zgomotului în formula corect scalată a mediei pasului invers.

Termeni-cheie

Termen	Cum i se spune	Ce înseamnă de fapt
Mers aleatoriu	„Deplasare prin aruncarea monedei”	Proces în care poziția se schimbă la fiecare pas prin incremente aleatoare
Proprietatea Markov	„Fără memorie”	Viitorul depinde numai de starea prezentă, nu de istoricul anterior acesteia
Matrice de tranziție	„Tabelul probabilităților”	P[i][j] = probabilitatea trecerii din starea i în starea j
Distribuție staționară	„Media pe termen lung”	Distribuția pi pentru care pi*P = pi, adică echilibrul lanțului
Mișcare browniană	„Agitație aleatoare”	Limita în timp continuu a unui mers aleatoriu, B(t) ~ N(0, t)
Dinamică Langevin	„Coborâre pe gradient cu zgomot”	Regulă de actualizare care combină gradientul determinist cu o perturbație aleatoare
MCMC	„Deplasare către țintă”	Construirea unui lanț Markov a cărui distribuție staționară este distribuția dorită
Metropolis–Hastings	„Propune, apoi acceptă sau respinge”	Algoritm MCMC care folosește rapoarte de acceptare pentru a păstra distribuția țintă
Temperatură	„Butonul de aleatoriu”	Parametru care controlează compromisul dintre explorare și exploatare
Proces de difuzie	„Zgomot introdus, zgomot eliminat”	Direct: adăugare treptată de zgomot. Invers: denoising treptat pentru generarea datelor

Lecturi suplimentare

• Ho, Jain, Abbeel (2020) — „Denoising Diffusion Probabilistic Models”. Lucrarea DDPM care a popularizat modelele de difuzie; prezintă derivarea lanțurilor Markov direct și invers.
• Song & Ermon (2019) — „Generative Modeling by Estimating Gradients of the Data Distribution”. Abordare bazată pe scor care folosește dinamica Langevin pentru eșantionare.
• Roberts & Rosenthal (2004) — „General state space Markov chains and MCMC algorithms”. Teoria condițiilor în care funcționează MCMC.
• Norris (1997) — „Markov Chains”. Manual de referință despre convergență, distribuții staționare și timpi de atingere.
• Welling & Teh (2011) — „Bayesian Learning via Stochastic Gradient Langevin Dynamics”. Combină SGD cu dinamica Langevin pentru inferență bayesiană scalabilă.

---

Sursă: Stochastic Processes — original

Navigare: înapoi: 01.21 — Teoria grafurilor pentru învățarea automată · Faza 1 — Fundamente matematice · Catalog complet.