Metode de eșantionare — lecție practică de AI Engineering

Prin eșantionare, inteligența artificială explorează spațiul posibilităților.

Tip: Construire Limbaj: Python Cerințe preliminare: Faza 1, lecțiile 06-07 (Probabilități, Teorema lui Bayes) Durată: ~120 de minute

Obiective de învățare

Implementarea de la zero a eșantionării prin funcția de repartiție inversă, prin respingere și de importanță, folosind numai numere aleatoare uniforme
Construirea eșantionării cu temperatură, top-k și top-p (nucleu) pentru generarea tokenurilor cu modele lingvistice
Explicarea trucului reparametrizării și a motivului pentru care acesta permite propagarea înapoi prin eșantionare în VAE-uri
Rularea unui algoritm MCMC Metropolis-Hastings pentru eșantionarea dintr-o distribuție țintă nenormalizată

Problema

Un model lingvistic termină de procesat promptul dumneavoastră și produce un vector cu 50.000 de logituri, câte unul pentru fiecare token din vocabular. Acum trebuie să aleagă unul. Cum procedează?

Dacă alege întotdeauna tokenul cu probabilitatea cea mai mare, fiecare răspuns este identic. Determinist. Plictisitor. Dacă alege uniform aleatoriu, rezultatul este lipsit de sens. Răspunsul se află undeva între aceste extreme, iar poziția exactă este controlată prin eșantionare.

Eșantionarea nu se limitează la generarea de text. Învățarea prin întărire estimează gradienții politicii prin eșantionarea traiectoriilor. VAE-urile învață reprezentări latente prin eșantionarea din distribuții învățate și propagarea înapoi prin caracterul aleatoriu. Modelele de difuzie generează imagini eșantionând zgomot și eliminându-l iterativ. Metodele Monte Carlo estimează integrale fără soluție în formă închisă. Algoritmii MCMC explorează distribuții a posteriori cu multe dimensiuni, imposibil de enumerat.

Fiecare sistem de IA generativă este un sistem de eșantionare. Strategia de eșantionare determină calitatea, diversitatea și controlabilitatea rezultatului. În această lecție veți construi de la zero principalele metode de eșantionare, pornind de la numere aleatoare uniforme și ajungând la tehnicile care stau la baza LLM-urilor și a modelelor generative moderne.

Conceptul

De ce contează eșantionarea

Eșantionarea apare în patru roluri fundamentale în IA și învățarea automată:

Generare. Modelele lingvistice, modelele de difuzie și GAN-urile produc rezultate prin eșantionare. Algoritmul de eșantionare controlează direct creativitatea, coerența și diversitatea. Temperatura, top-k și eșantionarea de tip nucleu sunt reglajele pe care inginerii le folosesc zilnic.

Antrenare. Coborârea stochastică pe gradient eșantionează miniloturi. Dropout eșantionează neuronii care urmează să fie dezactivați. Augmentarea datelor eșantionează transformări aleatoare. Eșantionarea de importanță reponderează eșantioanele pentru a reduce varianța gradientului în învățarea prin întărire (PPO, TRPO).

Estimare. Multe mărimi din învățarea automată nu au o soluție în formă închisă: pierderea așteptată pentru o distribuție a datelor, funcția de partiție a unui model bazat pe energie sau evidența din inferența bayesiană. Estimarea Monte Carlo le aproximează pe toate prin medierea eșantioanelor.

Explorare. Algoritmii MCMC explorează distribuții a posteriori în inferența bayesiană. Strategiile evolutive eșantionează perturbații ale parametrilor. Eșantionarea Thompson echilibrează explorarea și exploatarea în problemele de tip bandit.

Provocarea esențială: puteți eșantiona direct numai din distribuții simple (uniformă, normală). Pentru toate celelalte aveți nevoie de o metodă care să transforme eșantioanele simple în eșantioane din distribuția țintă.

Eșantionarea aleatoare uniformă

Orice metodă de eșantionare începe de aici. Un generator uniform de numere aleatoare produce valori în [0, 1), astfel încât orice subintervale de lungime egală au probabilități egale.

U ~ Uniform(0, 1)

P(a <= U <= b) = b - a    pentru 0 <= a <= b <= 1

Proprietăți:
  E[U] = 0.5
  Var(U) = 1/12

Pentru a eșantiona uniform dintr-o mulțime discretă cu n elemente, generați U și returnați floor(n * U). Pentru un interval continuu [a, b], calculați a + (b - a) * U.

Ideea-cheie: o variabilă aleatoare uniformă poate fi transformată pentru a produce un eșantion dintr-o distribuție țintă. Trucul constă în găsirea transformării potrivite.

Metoda funcției de repartiție inverse (eșantionare prin transformare inversă)

Funcția de repartiție (CDF) asociază valorilor probabilități:

F(x) = P(X <= x)

Proprietăți:
  F este nedescrescătoare
  F(-inf) = 0
  F(+inf) = 1
  F asociază dreapta reală intervalului [0, 1]

Inversa generalizată a funcției de repartiție asociază probabilităților valori: F_inverse(u) = inf{x : F(x) >= u}. Dacă U ~ Uniform(0, 1), atunci X = F_inverse(U) urmează distribuția țintă, inclusiv atunci când F are salturi sau porțiuni plate.

Algoritm:
  1. Generați u ~ Uniformă(0, 1)
  2. Returnați F_inverse(u)

De ce funcționează:
  P(X <= x) = P(F_inverse(U) <= x) = P(U <= F(x)) = F(x)

Exemplu pentru distribuția exponențială:

Densitate: f(x) = lambda * exp(-lambda * x),   x >= 0
CDF: F(x) = 1 - exp(-lambda * x)

Rezolvați F(x) = u în raport cu x:
  u = 1 - exp(-lambda * x)
  exp(-lambda * x) = 1 - u
  x = -ln(1 - u) / lambda

Deoarece (1 - U) și U au aceeași distribuție:
  x = -ln(u) / lambda

Metoda este directă atunci când puteți scrie sau calcula eficient F_inverse. Distribuția normală nu are o funcție de repartiție inversă elementară în formă închisă, așa că folosim alte metode, precum Box–Muller, sau o aproximație numerică a cuantilei.

Notă tehnică a traducerii: Pentru o CDF care nu este strict crescătoare, „inversa” obișnuită poate să nu existe sau să nu fie unică. Formula corectă, aplicabilă și distribuțiilor discrete, folosește inversa generalizată definită mai sus.

Versiunea discretă: pentru distribuțiile discrete, construiți funcția de repartiție ca sumă cumulată, generați U și găsiți primul indice la care suma cumulată depășește U. Așa funcționează sample_categorical din lecția 06.

Eșantionarea prin respingere

Când nu puteți inversa funcția de repartiție, dar puteți evalua densitatea țintă până la o constantă, puteți folosi eșantionarea prin respingere.

Distribuție țintă: p(x)  (poate fi evaluată, eventual nenormalizată)
Distribuție de propunere: q(x)  (din care se poate eșantiona)
Limită: M astfel încât p(x) <= M * q(x) pentru orice x

Algoritm:
  1. Eșantionați x ~ q(x)
  2. Eșantionați u ~ Uniformă(0, 1)
  3. Dacă u < p(x) / (M * q(x)), acceptați x
  4. În caz contrar, respingeți și reveniți la pasul 1

Rata de acceptare = 1/M

Cu cât limita M este mai strânsă, cu atât rata de acceptare este mai mare. În puține dimensiuni (1-3), eșantionarea prin respingere funcționează bine. În multe dimensiuni, rata de acceptare scade exponențial, deoarece cea mai mare parte a volumului distribuției de propunere este respinsă. Acesta este blestemul dimensionalității pentru eșantionarea prin respingere.

Notă tehnică a traducerii: egalitatea „Acceptance rate = 1/M” presupune că p și q sunt densități normalizate. Dacă p este nenormalizată, rata este Z_p/M, unde Z_p este integrala lui p, cu condiția ca q să fie normalizată și limita să fie validă.

Exemplu: eșantionarea dintr-o distribuție normală trunchiată. Folosiți o distribuție de propunere uniformă pe intervalul trunchiat. Anvelopa M este maximul densității normale pe acel interval.

Exemplu: eșantionarea dintr-un semicerc. Propuneți uniform puncte din dreptunghiul circumscris. Acceptați un punct dacă se află în semicerc. Astfel calculează Monte Carlo valoarea lui pi: rata de acceptare este egală cu raportul ariilor pi/4.

Eșantionarea de importanță

Uneori nu aveți nevoie de eșantioane din distribuția țintă p(x). Trebuie să estimați o valoare așteptată sub p(x), dar dispuneți de eșantioane dintr-o altă distribuție q(x).

Obiectiv: estimați E_p[f(x)] = integrala din f(x) * p(x) dx

Rescriere:
  E_p[f(x)] = integrala din f(x) * (p(x)/q(x)) * q(x) dx
            = E_q[f(x) * w(x)]

unde w(x) = p(x) / q(x) sunt ponderile de importanță.

Estimator:
  E_p[f(x)] ~ (1/N) * sum(f(x_i) * w(x_i))    unde x_i ~ q(x)

Această metodă este esențială în învățarea prin întărire. În PPO (Proximal Policy Optimization), colectați traiectorii sub o politică veche pi_old, dar doriți să optimizați o politică nouă pi_new. Ponderea de importanță este pi_new(a|s) / pi_old(a|s). PPO trunchiază aceste ponderi pentru a împiedica noua politică să se îndepărteze prea mult de cea veche.

Varianța estimatorului prin eșantionare de importanță depinde de cât de apropiată este q de p. Dacă q diferă mult de p, câteva eșantioane primesc ponderi enorme și domină estimarea. Eșantionarea de importanță autonormalizată împarte la suma ponderilor pentru a reduce această problemă:

E_p[f(x)] ~ sum(w_i * f(x_i)) / sum(w_i)

Notă tehnică a traducerii: aceste formule presupun că q(x) este pozitivă oriunde integrandul f(x)p(x) poate contribui. În caz contrar, eșantionarea de importanță nu poate recupera masa de probabilitate din afara suportului lui q.

Estimarea Monte Carlo

Estimarea Monte Carlo aproximează integrale prin medierea eșantioanelor aleatoare. Pentru eșantioane independente și identic distribuite și un integrand cu valoare așteptată finită, legea numerelor mari garantează convergența mediei eșantionului.

Obiectiv: estimați I = integrala din g(x) dx pe domeniul D

Metodă:
  1. Eșantionați uniform x_1, ..., x_N din D
  2. I ~ (Volumul lui D / N) * sum(g(x_i))

Eroare: O(1 / sqrt(N))   indiferent de dimensiune

Exponentul ratei erorii nu depinde direct de dimensiune. Din acest motiv, metodele Monte Carlo sunt adesea atractive în dimensiuni mari, unde integrarea pe grilă devine impracticabilă.

Notă tehnică a traducerii: rata asimptotică O(1/sqrt(N)) presupune, în forma uzuală, o varianță finită. Exponentul nu depinde de dimensiune, însă constanta erorii poate crește considerabil odată cu aceasta.

Estimarea lui pi:

Eșantionați uniform (x, y) din [-1, 1] x [-1, 1]
Numărați câte puncte se află în cercul unitate: x^2 + y^2 <= 1
pi ~ 4 * (numărul din interior) / (numărul total)

Estimarea valorilor așteptate:

E[f(X)] ~ (1/N) * sum(f(x_i))    unde x_i ~ p(x)

Media eșantionului converge către valoarea așteptată adevărată.
Varianța estimatorului = Var(f(X)) / N

Monte Carlo cu lanțuri Markov (MCMC): Metropolis-Hastings

MCMC construiește un lanț Markov a cărui distribuție staționară este distribuția țintă p(x). Dacă lanțul îndeplinește condițiile de ergodicitate necesare, după suficienți pași distribuția stării se apropie de p(x), iar eșantioanele pot fi folosite pentru estimare.

Țintă: p(x)  (cunoscută până la o constantă de normalizare)
Propunere: q(x'|x)  (modul de propunere a stării următoare din starea curentă)

Algoritmul Metropolis–Hastings:
  1. Porniți de la un x_0
  2. Pentru t = 1, 2, ..., T:
     a. Propuneți x' ~ q(x'|x_t)
     b. Calculați raportul de acceptare:
        alpha = [p(x') * q(x_t|x')] / [p(x_t) * q(x'|x_t)]
     c. Acceptați cu probabilitatea min(1, alpha):
        - Dacă u < alpha (u ~ Uniformă(0,1)): x_{t+1} = x'
        - În caz contrar: x_{t+1} = x_t
  3. Eliminați primele B eșantioane (încălzire)
  4. Returnați eșantioanele rămase

Notă tehnică a traducerii: pseudocodul original are un decalaj de indice: după inițializarea lui x_0, prima propunere ar trebui făcută din starea curentă x_0. O scriere coerentă folosește t = 0, …, T-1 și produce x_{t+1}, ori folosește x_{t-1} în iterația care începe la t = 1.

Pentru propuneri simetrice (q(x’|x) = q(x|x’)), raportul se simplifică la p(x’)/p(x). Acesta este algoritmul Metropolis original.

De ce funcționează. Regula de acceptare asigură balanța detaliată: probabilitatea de a vă afla în x și de a trece în x’ este egală cu probabilitatea de a vă afla în x’ și de a trece în x. Balanța detaliată implică faptul că p(x) este o distribuție staționară a lanțului; convergența către ea mai cere condiții precum ireductibilitatea și aperiodicitatea.

Notă tehnică a traducerii: Staționaritatea singură nu garantează convergența dintr-o stare inițială arbitrară. Condițiile exacte depind de spațiul stărilor, dar un lanț trebuie să poată explora suportul țintei și să nu rămână blocat într-un ciclu periodic.

Considerații practice:

Perioada de încălzire (burn-in): eliminați eșantioanele inițiale, de dinainte ca lanțul să ajungă la echilibru
Subeșantionare (thinning): păstrați fiecare al k-lea eșantion pentru a reduce autocorelația dintre eșantioanele reținute
Scara propunerii: dacă este prea mică, lanțul se deplasează lent (acceptare ridicată, explorare lentă); dacă este prea mare, majoritatea propunerilor sunt respinse (acceptare scăzută, lanț blocat)
Rata optimă de acceptare pentru o propunere gaussiană în dimensiuni mari este aproximativ 0,234

Notă tehnică a traducerii: subeșantionarea reduce autocorelația dintre valorile păstrate, dar de regulă irosește eșantioane și nu mărește dimensiunea efectivă a eșantionului raportată la costul de calcul. Valoarea 0,234 este un rezultat asimptotic pentru anumite scheme Metropolis cu mers aleatoriu, nu o țintă universală pentru orice algoritm MCMC.

Eșantionarea Gibbs

Eșantionarea Gibbs este un caz particular de MCMC pentru distribuții multivariate. În loc să propună simultan o deplasare în toate dimensiunile, actualizează câte o variabilă din distribuția ei condiționată.

Țintă: p(x_1, x_2, ..., x_d)

Algoritm:
  Pentru fiecare iterație t:
    Eșantionați x_1^{t+1} ~ p(x_1 | x_2^t, x_3^t, ..., x_d^t)
    Eșantionați x_2^{t+1} ~ p(x_2 | x_1^{t+1}, x_3^t, ..., x_d^t)
    ...
    Eșantionați x_d^{t+1} ~ p(x_d | x_1^{t+1}, x_2^{t+1}, ..., x_{d-1}^{t+1})

Eșantionarea Gibbs necesită posibilitatea de a eșantiona din fiecare distribuție condiționată p(x_i | x_{-i}). Pentru numeroase modele, acest lucru este direct:

Rețele bayesiene: distribuțiile condiționate rezultă din structura grafului
Amestecuri gaussiene: distribuțiile condiționate sunt gaussiene
Modele Ising: distribuția condiționată a fiecărui spin depinde numai de vecinii săi

În eșantionarea Gibbs exactă nu există un pas separat de acceptare sau respingere, astfel încât fiecare actualizare condiționată este păstrată. O actualizare aleatoare a unei coordonate este reversibilă față de distribuția țintă, iar o succesiune corectă de actualizări condiționate păstrează distribuția țintă staționară.

Limitare. Când variabilele sunt puternic corelate, eșantionarea Gibbs se amestecă lent, deoarece actualizarea câte unei variabile nu poate realiza deplasări diagonale mari prin distribuție.

Eșantionarea cu temperatură (utilizată în LLM-uri)

Modelele lingvistice produc logiturile z_1, …, z_V pentru fiecare token din vocabular. Softmax le transformă în probabilități. Temperatura rescalează logiturile înainte de softmax:

p_i = exp(z_i / T) / sum(exp(z_j / T))

T = 1.0: softmax standard (distribuția originală)
T -> 0:  argmax (determinist, alege logitul maxim)
T -> inf: uniformă (toate tokenurile sunt la fel de probabile)
T < 1.0: ascute distribuția (mai multă încredere, diversitate mai mică)
T > 1.0: aplatizează distribuția (mai puțină încredere, diversitate mai mare)

De ce funcționează. Împărțirea logiturilor la T < 1 amplifică diferențele dintre ele. Dacă z_1 = 2 și z_2 = 1, împărțirea la T = 0,5 produce z_1/T = 4 și z_2/T = 2, mărind diferența. După softmax, tokenul cu logitul maxim primește o parte mult mai mare din masa de probabilitate.

În practică:

T = 0,0: decodare greedy, cea mai potrivită pentru întrebări și răspunsuri factuale
T = 0,3-0,7: ușor creativă, potrivită pentru generarea de cod
T = 0,7-1,0: echilibrată, potrivită pentru conversații generale
T = 1,0-1,5: scriere creativă, brainstorming
T > 1,5: din ce în ce mai aleatorie, rareori utilă

Temperatura nu schimbă ce tokenuri sunt posibile, ci masa de probabilitate atribuită fiecăruia.

Notă tehnică a traducerii: T = 0 trebuie tratată ca un caz special care alege argmax sau ca limita T -> 0. Formula și implementarea de mai jos împart la temperatură și nu pot fi evaluate direct cu valoarea zero.

Eșantionarea top-k

Eșantionarea top-k restrânge mulțimea de candidați la cele k tokenuri cu probabilitățile cele mai mari, apoi renormalizează probabilitățile și eșantionează din mulțimea restrânsă.

Algoritm:
  1. Calculați probabilitățile softmax pentru toate cele V tokenuri
  2. Sortați tokenurile descrescător după probabilitate
  3. Păstrați numai primele k tokenuri
  4. Renormalizați: p_i' = p_i / sum(p_j pentru j din top-k)
  5. Eșantionați din distribuția renormalizată

k = 1:  decodare greedy
k = V:  fără filtrare (eșantionare standard)
k = 40: valoare uzuală, elimină coada lungă a tokenurilor improbabile

Top-k împiedică modelul să aleagă tokenuri extrem de improbabile (greșeli de tastare, fragmente fără sens) din coada lungă a distribuției vocabularului. Problema este că k rămâne fix indiferent de context. Când modelul este sigur (un token are probabilitate de 95%), k = 40 permite încă 39 de alternative. Când modelul este nesigur (probabilitatea este distribuită între 1.000 de tokenuri), k = 40 elimină opțiuni plauzibile.

Eșantionarea top-p (de tip nucleu)

Eșantionarea top-p ajustează dinamic dimensiunea mulțimii de candidați. În loc să păstreze un număr fix de tokenuri, păstrează cea mai mică mulțime a cărei probabilitate cumulată depășește p.

Algoritm:
  1. Calculați probabilitățile softmax pentru toate cele V tokenuri
  2. Sortați tokenurile descrescător după probabilitate
  3. Găsiți cel mai mic k pentru care suma probabilităților top-k >= p
  4. Păstrați numai acele k tokenuri
  5. Renormalizați și eșantionați

p = 0.9:  păstrează tokenurile care acoperă 90% din masa de probabilitate
p = 1.0:  fără filtrare
p = 0.1:  foarte restrictiv, aproape greedy

Când modelul este sigur, eșantionarea de tip nucleu păstrează puține tokenuri (poate 2-3). Când modelul este nesigur, păstrează multe (poate 200). Acest comportament adaptiv explică de ce eșantionarea de tip nucleu produce, în general, text mai bun decât top-k.

Combinații uzuale:

Temperatură 0,7 + top-p 0,9: configurație generală bună
Temperatură 0,0 (greedy): cea mai potrivită pentru sarcini deterministe
Temperatură 1,0 + top-k 50: configurația din articolul original Fan et al. (2018)

Top-k și top-p pot fi combinate. Aplicați întâi top-k, apoi top-p pe mulțimea rămasă.

Trucul reparametrizării (utilizat în VAE-uri)

Autoencoderele variaționale (VAE) învață codificând intrările într-o distribuție din spațiul latent, eșantionând din acea distribuție și decodificând eșantionul înapoi. Problema: nu puteți propaga înapoi printr-o operație de eșantionare.

Eșantionare standard (nediferențiabilă):
  z ~ N(mu, sigma^2)

  Aleatorietatea blochează curgerea gradientului.
  d/d_mu [eșantion din N(mu, sigma^2)] = ???

Trucul reparametrizării separă caracterul aleatoriu de parametri:

Eșantionare reparametrizată:
  epsilon ~ N(0, 1)          (zgomot aleatoriu fix, fără parametri)
  z = mu + sigma * epsilon   (funcție deterministă a parametrilor)

  Acum z este o funcție deterministă și diferențiabilă de mu și sigma.
  d(z)/d(mu) = 1
  d(z)/d(sigma) = epsilon

  Gradienții se propagă prin mu și sigma.

Metoda funcționează deoarece N(mu, sigma^2) are aceeași distribuție ca mu + sigma * N(0, 1). Ideea-cheie: mutați caracterul aleatoriu într-o sursă fără parametri (epsilon), apoi exprimați eșantionul ca transformare diferențiabilă a parametrilor.

În bucla de antrenare a VAE-ului:

Codificatorul produce mu și log(sigma^2) pentru fiecare intrare
Eșantionați epsilon ~ N(0, 1)
Calculați z = mu + sigma * epsilon
Decodificați z pentru a reconstrui intrarea
Propagați înapoi prin pașii 4, 3, 2 și 1 (posibil deoarece pasul 3 este diferențiabil)

Fără trucul reparametrizării, VAE-urile nu pot fi antrenate prin propagarea înapoi standard. Această singură idee a făcut VAE-urile practice.

Notă tehnică a traducerii: gradientul nu este propagat „prin” operația aleatoare din pasul 2 și nici nu este necesar să fie. epsilon este tratat ca intrare aleatoare fixă pentru eșantionul curent, iar gradientul ajunge la parametrii codificatorului prin transformarea diferențiabilă din pasul 3.

Gumbel-Softmax (eșantionare categorială diferențiabilă)

Trucul reparametrizării funcționează pentru distribuții continue (gaussiană). Pentru distribuții categoriale discrete avem nevoie de o altă abordare. Gumbel-Softmax oferă o aproximare diferențiabilă a eșantionării categoriale.

Trucul Gumbel-Max (nediferențiabil):

Pentru a eșantiona dintr-o distribuție categorială cu log-probabilitățile log(p_1), ..., log(p_k):
  1. Eșantionați g_i ~ Gumbel(0, 1) pentru fiecare categorie
     (g = -log(-log(u)), unde u ~ Uniformă(0, 1))
  2. Returnați argmax(log(p_i) + g_i)

Aceasta produce eșantioane categoriale exacte.

Gumbel-Softmax (aproximare diferențiabilă):

Înlocuiți argmax-ul discret cu un softmax neted:
  y_i = exp((log(p_i) + g_i) / tau) / sum(exp((log(p_j) + g_j) / tau))

tau (temperatura) controlează aproximarea:
  tau -> 0:  se apropie de un vector one-hot (categorial discret)
  tau -> inf: se apropie de uniformă (1/k, 1/k, ..., 1/k)
  tau = 1.0: aproximare netedă

Gumbel-Softmax produce o relaxare continuă a unui eșantion discret. Rezultatul este un vector de probabilități (one-hot relaxat), nu un vector one-hot strict. Gradienții trec prin softmax. În propagarea înainte din timpul antrenării puteți folosi estimatorul „straight-through”: utilizați argmax strict la propagarea înainte, dar gradienții Gumbel-Softmax relaxați la propagarea înapoi.

Aplicații:

Variabile latente discrete în VAE-uri
Căutarea arhitecturilor neuronale (alegerea operațiilor discrete)
Mecanisme de atenție strictă
Învățarea prin întărire cu acțiuni discrete

Eșantionarea stratificată

Eșantionarea Monte Carlo standard poate lăsa întâmplător goluri în spațiul de eșantionare. Eșantionarea stratificată impune o acoperire uniformă împărțind spațiul în strate și eșantionând din fiecare.

Monte Carlo standard:
  Eșantionați uniform N puncte din [0, 1]
  Unele regiuni pot avea aglomerări, iar altele goluri

Eșantionare stratificată:
  Împărțiți [0, 1] în N strate egale: [0, 1/N), [1/N, 2/N), ..., [(N-1)/N, 1)
  Eșantionați uniform câte un punct din fiecare strat
  x_i = (i + u_i) / N   unde u_i ~ Uniformă(0, 1),  i = 0, ..., N-1

Pentru schema descrisă mai sus — strate cu probabilități egale, câte un eșantion independent în fiecare strat și ponderare corectă — eșantionarea stratificată are o varianță mai mică sau egală cu cea a estimatorului Monte Carlo standard bazat pe același număr de eșantioane:

Var(stratificată) <= Var(Monte Carlo standard)

Îmbunătățirea este maximă când f(x) variază neted.
Pentru funcții constante pe fiecare strat, eșantionarea stratificată este exactă.

Aplicații:

Integrare numerică (cvasi-Monte Carlo)
Împărțirea datelor de antrenare (asigurarea echilibrului claselor în fiecare fold)
Eșantionarea de importanță cu stratificare (combinarea ambelor tehnici)
NeRF (Neural Radiance Fields) folosește eșantionare stratificată de-a lungul razelor camerei

Notă tehnică a traducerii: cvasi-Monte Carlo este o familie distinctă, bazată de regulă pe secvențe deterministe cu discrepanță redusă; nu este sinonimă cu eșantionarea stratificată aleatoare, deși ambele urmăresc o acoperire mai uniformă.

Legătura cu modelele de difuzie

Modelele de difuzie generează imagini printr-un proces de eșantionare. Procesul direct adaugă treptat zgomot gaussian unei imagini în T pași, până când distribuția rezultatului se apropie de una gaussiană simplă. Procesul invers învață tranziții de denoising care transformă un eșantion de zgomot într-un eșantion din distribuția datelor; în generarea necondiționată, acesta nu recuperează în general imaginea originală asociată unui zgomot dat.

Notă tehnică a traducerii: La un număr finit de pași, x_T este de regulă doar aproximativ gaussian, în funcție de programul de zgomot. Iar procesul invers învățat reproduce distribuția datelor, nu o inversare deterministă care identifică imaginea inițială exactă.

Proces direct (cunoscut):
  x_t = sqrt(alpha_t) * x_{t-1} + sqrt(1 - alpha_t) * epsilon
  unde epsilon ~ N(0, I)

  După T pași: x_T ~ N(0, I)  (zgomot pur)

Proces invers (învățat):
  x_{t-1} = (1/sqrt(alpha_t)) * (x_t - (1 - alpha_t)/sqrt(1 - alpha_bar_t) * epsilon_theta(x_t, t)) + sigma_t * z
  unde z ~ N(0, I)

  Fiecare pas de denoising este un pas de eșantionare.

Legătura cu metodele din această lecție:

Fiecare pas de eliminare a zgomotului folosește trucul reparametrizării (eșantionați zgomot, aplicați o transformare deterministă)
Programul de zgomot {alpha_t} controlează o formă de scădere treptată a temperaturii
Antrenarea folosește estimarea Monte Carlo pentru a aproxima limita inferioară a evidenței (ELBO)
Eșantionarea ancestrală din modelele de difuzie este un lanț Markov (fiecare pas depinde numai de starea curentă)

Întregul proces de generare a imaginii este o eșantionare iterativă: porniți de la zgomot și, la fiecare pas, eșantionați o versiune puțin mai puțin zgomotoasă, condiționată de modelul învățat de eliminare a zgomotului.

monte-carlo-pi

Construiți

Pasul 1: eșantionarea uniformă și prin funcția de repartiție inversă

import math
import random

def sample_uniform(a, b):
    return a + (b - a) * random.random()

def sample_exponential_inverse_cdf(lam):
    u = random.random()
    return -math.log(u) / lam

Generați 10.000 de eșantioane exponențiale și verificați dacă media este 1/lambda.

Pasul 2: eșantionarea prin respingere

def rejection_sample(target_pdf, proposal_sample, proposal_pdf, M):
    while True:
        x = proposal_sample()
        u = random.random()
        if u < target_pdf(x) / (M * proposal_pdf(x)):
            return x

Folosiți eșantionarea prin respingere pentru a extrage valori dintr-o distribuție normală trunchiată. Verificați forma construind histograma eșantioanelor.

Pasul 3: eșantionarea de importanță

def importance_sampling_estimate(f, target_pdf, proposal_pdf, proposal_sample, n):
    total = 0
    for _ in range(n):
        x = proposal_sample()
        w = target_pdf(x) / proposal_pdf(x)
        total += f(x) * w
    return total / n

Estimați E[X^2] pentru o distribuție normală folosind o distribuție de propunere uniformă. Comparați cu rezultatul cunoscut (mu^2 + sigma^2).

Notă tehnică a traducerii: o distribuție uniformă proprie pe un interval finit nu acoperă întregul suport al distribuției normale. Pentru o estimare corectă a așteptării normale trebuie aleasă o distribuție de propunere cu suport pe întreaga dreaptă reală sau trebuie reformulată explicit problema pentru o distribuție normală trunchiată.

Pasul 4: estimarea Monte Carlo a lui pi

def monte_carlo_pi(n):
    inside = 0
    for _ in range(n):
        x = random.uniform(-1, 1)
        y = random.uniform(-1, 1)
        if x*x + y*y <= 1:
            inside += 1
    return 4 * inside / n

Pasul 5: MCMC Metropolis-Hastings

def metropolis_hastings(target_log_pdf, proposal_sample, proposal_log_pdf, x0, n_samples, burn_in):
    samples = []
    x = x0
    for i in range(n_samples + burn_in):
        x_new = proposal_sample(x)
        log_alpha = (target_log_pdf(x_new) + proposal_log_pdf(x, x_new)
                     - target_log_pdf(x) - proposal_log_pdf(x_new, x))
        if math.log(random.random()) < log_alpha:
            x = x_new
        if i >= burn_in:
            samples.append(x)
    return samples

Eșantionați dintr-o distribuție bimodală (un amestec de două distribuții gaussiene). Vizualizați traiectoria lanțului.

Pasul 6: eșantionarea Gibbs

def gibbs_sampling_2d(conditional_x_given_y, conditional_y_given_x, x0, y0, n_samples, burn_in):
    x, y = x0, y0
    samples = []
    for i in range(n_samples + burn_in):
        x = conditional_x_given_y(y)
        y = conditional_y_given_x(x)
        if i >= burn_in:
            samples.append((x, y))
    return samples

Pasul 7: eșantionarea cu temperatură

def softmax(logits):
    max_l = max(logits)
    exps = [math.exp(z - max_l) for z in logits]
    total = sum(exps)
    return [e / total for e in exps]

def temperature_sample(logits, temperature):
    scaled = [z / temperature for z in logits]
    probs = softmax(scaled)
    return sample_from_probs(probs)

Arătați cum modifică temperatura distribuția rezultată pentru un set de logituri ale tokenurilor.

Pasul 8: eșantionarea top-k și top-p

def top_k_sample(logits, k):
    indexed = sorted(enumerate(logits), key=lambda x: -x[1])
    top = indexed[:k]
    top_logits = [l for _, l in top]
    probs = softmax(top_logits)
    idx = sample_from_probs(probs)
    return top[idx][0]

def top_p_sample(logits, p):
    probs = softmax(logits)
    indexed = sorted(enumerate(probs), key=lambda x: -x[1])
    cumsum = 0
    selected = []
    for token_idx, prob in indexed:
        cumsum += prob
        selected.append((token_idx, prob))
        if cumsum >= p:
            break
    sel_probs = [pr for _, pr in selected]
    total = sum(sel_probs)
    sel_probs = [pr / total for pr in sel_probs]
    idx = sample_from_probs(sel_probs)
    return selected[idx][0]

Pasul 9: trucul reparametrizării

def reparam_sample(mu, sigma):
    epsilon = random.gauss(0, 1)
    return mu + sigma * epsilon

def reparam_gradient(mu, sigma, epsilon):
    dz_dmu = 1.0
    dz_dsigma = epsilon
    return dz_dmu, dz_dsigma

Demonstrați că gradienții trec prin eșantionul reparametrizat, dar nu și prin eșantionarea directă.

Pasul 10: Gumbel-Softmax

def gumbel_sample():
    u = random.random()
    return -math.log(-math.log(u))

def gumbel_softmax(logits, temperature):
    gumbels = [math.log(p) + gumbel_sample() for p in logits]
    return softmax([g / temperature for g in gumbels])

Arătați cum scăderea temperaturii face ca rezultatul să se apropie de un vector one-hot.

Notă tehnică a traducerii: implementarea originală numește argumentul logits, dar aplică math.log(p) fiecărui element. Aceasta este corectă numai dacă elementele sunt probabilități strict pozitive; dacă intrarea conține logituri, zgomotul Gumbel trebuie adăugat direct acestora. Blocul executabil a fost păstrat neschimbat.

Implementările complete, împreună cu toate vizualizările, se află în code/sampling.py.

Folosiți

Versiunile pentru producție, cu NumPy și SciPy:

import numpy as np

rng = np.random.default_rng(42)

exponential_samples = rng.exponential(scale=2.0, size=10000)
print(f"Exponential mean: {exponential_samples.mean():.4f} (expected 2.0)")

from scipy import stats
normal = stats.norm(loc=0, scale=1)
print(f"CDF at 1.96: {normal.cdf(1.96):.4f}")
print(f"Inverse CDF at 0.975: {normal.ppf(0.975):.4f}")

logits = np.array([2.0, 1.0, 0.5, 0.1, -1.0])
temperature = 0.7
scaled = logits / temperature
probs = np.exp(scaled - scaled.max()) / np.exp(scaled - scaled.max()).sum()
token = rng.choice(len(logits), p=probs)
print(f"Sampled token index: {token}")

Pentru MCMC la scară mare, folosiți biblioteci dedicate:

PyMC: modelare bayesiană completă cu NUTS (HMC adaptiv)
emcee: eșantionator MCMC de ansamblu
NumPyro/JAX: MCMC accelerat pe GPU

Le-ați construit de la zero. Acum știți ce fac apelurile bibliotecilor.

Exerciții

Implementați eșantionarea prin funcția de repartiție inversă pentru distribuția Cauchy. Funcția de repartiție este F(x) = 0.5 + arctan(x)/pi. Generați 10.000 de eșantioane și reprezentați histograma lor împreună cu densitatea adevărată. Observați cozile grele (valorile extreme, foarte îndepărtate de centru).
Folosiți eșantionarea prin respingere pentru a genera eșantioane dintr-o distribuție Beta(2, 5), cu o distribuție de propunere Uniform(0, 1). Reprezentați eșantioanele acceptate împreună cu densitatea Beta adevărată. Care este rata teoretică de acceptare?
Estimați prin Monte Carlo integrala lui sin(x) de la 0 la pi, folosind 1.000, 10.000 și 100.000 de eșantioane. Comparați eroarea la fiecare nivel. Verificați dacă eroarea scalează ca O(1/sqrt(N)).
Implementați Metropolis-Hastings pentru a eșantiona dintr-o distribuție bidimensională p(x, y) proporțională cu exp(-(x^2 * y^2 + x^2 + y^2 - 8x - 8y) / 2). Reprezentați eșantioanele și traiectoria lanțului. Experimentați cu diferite abateri standard ale propunerii.
Construiți o demonstrație completă de generare a textului: pentru un vocabular de 10 cuvinte și logiturile lor, generați secvențe de câte 20 de tokenuri folosind (a) greedy, (b) temperature=0.7, (c) top-k=3 și (d) top-p=0.9. Comparați diversitatea rezultatelor în 5 rulări.

Termeni-cheie

Termen	Ce spun oamenii	Ce înseamnă de fapt
Eșantionare	„Extragerea unor valori aleatoare”	Generarea valorilor conform unei distribuții de probabilitate. Mecanismul din spatele întregii IA generative
Distribuție uniformă	„Toate sunt la fel de probabile”	Fiecare valoare din [a, b] are aceeași densitate de probabilitate 1/(b-a). Punctul de plecare al tuturor metodelor de eșantionare
Funcție de repartiție inversă	„Transformarea probabilității”	Inversa generalizată F_inverse(U) transformă un eșantion uniform într-un eșantion din distribuția țintă. Metoda este exactă matematic; eficiența depinde de posibilitatea calculării cuantilei.
Eșantionare prin respingere	„Propuneți și acceptați/respingeți”	Generați dintr-o distribuție de propunere simplă și acceptați cu o probabilitate proporțională cu raportul țintă/propunere. Exactă, dar irosește eșantioane
Eșantionare de importanță	„Reponderați eșantioanele”	Estimați valori așteptate sub p(x) folosind eșantioane din q(x), ponderând fiecare eșantion cu p(x)/q(x). Esențială pentru PPO în învățarea prin întărire
Monte Carlo	„Media eșantioanelor aleatoare”	Aproximați integrale prin medii ale eșantioanelor. Sub ipoteze uzuale, inclusiv varianță finită pentru rata RMS, eroarea este O(1/sqrt(N)); constanta poate depinde puternic de dimensiune.
MCMC	„Un mers aleatoriu care converge”	Construiți un lanț Markov a cărui distribuție staționară este ținta. Metropolis-Hastings este algoritmul fundamental
Metropolis-Hastings	„Acceptați urcarea, uneori și coborârea”	Propuneți deplasări și le acceptați pe baza raportului densităților. Balanța detaliată face distribuția țintă staționară; convergența mai cere condiții de ergodicitate.
Eșantionare Gibbs	„Câte o variabilă”	Actualizați fiecare variabilă din distribuția ei condiționată, menținându-le fixe pe celelalte. Rată de acceptare 100%
Temperatură	„Reglajul încrederii”	Împarte logiturile la T înainte de softmax. T<1 ascute distribuția (mai multă încredere), T>1 o aplatizează (mai multă diversitate)
Eșantionare top-k	„Păstrați cele mai bune k”	Anulați toate probabilitățile în afară de cele ale primelor k tokenuri, renormalizați și eșantionați. Mulțime de candidați cu dimensiune fixă
Eșantionare de tip nucleu (top-p)	„Păstrați-le pe cele probabile”	Păstrați cea mai mică mulțime de tokenuri a căror probabilitate cumulată depășește p. Dimensiune adaptivă a mulțimii de candidați
Trucul reparametrizării	„Mutați caracterul aleatoriu în exterior”	Scrieți z = mu + sigma * epsilon, unde epsilon ~ N(0,1). Face eșantionarea diferențiabilă. Esențial pentru antrenarea VAE-urilor
Gumbel-Softmax	„Eșantionare categorială relaxată”	Aproximare diferențiabilă a eșantionării categoriale, folosind zgomot Gumbel și softmax cu temperatură
Eșantionare stratificată	„Acoperire impusă”	Împărțiți spațiul de eșantionare în strate și eșantionați din fiecare. Varianță mai mică decât Monte Carlo naiv în condițiile estimatorului stratificat
Perioadă de încălzire	„Perioadă de acomodare”	Eșantioanele MCMC inițiale eliminate înainte ca lanțul să ajungă la distribuția staționară
Balanță detaliată	„Condiție de reversibilitate”	p(x) * T(x->y) = p(y) * T(y->x). Condiție suficientă pentru ca p să fie distribuția staționară a unui lanț Markov
Eșantionare prin difuzie	„Eliminare iterativă a zgomotului”	Generați date pornind de la zgomot și aplicând pași învățați de eliminare a acestuia. Fiecare pas este o operație de eșantionare condiționată

Lecturi suplimentare

Holbrook (2023): The Metropolis-Hastings Algorithm — tutorial detaliat despre fundamentele MCMC
Jang, Gu, Poole (2017): Categorical Reparameterization with Gumbel-Softmax — articolul original despre Gumbel-Softmax
Holtzman et al. (2020): The Curious Case of Neural Text Degeneration — articolul despre eșantionarea de tip nucleu (top-p)
Kingma & Welling (2014): Auto-Encoding Variational Bayes — articolul despre VAE care introduce trucul reparametrizării
Ho, Jain, Abbeel (2020): Denoising Diffusion Probabilistic Models — DDPM leagă eșantionarea de generarea imaginilor

Sursă: Sampling Methods — original

Navigare: înapoi: 01.15 — Statistică pentru învățarea automată · Faza 1 — Fundamente matematice · Catalog complet · în continuare: 01.17 — Sisteme liniare.