روش‌های نمونه‌برداری در یادگیری ماشین و مدل‌های زبانی

در سیستم‌های هوش مصنوعی مولد، از چت‌بات‌های مبتنی بر مدل‌های زبانی بزرگ گرفته تا تولیدکننده‌های تصویر، خروجی نهایی همیشه حاصل یک فرایند نمونه‌برداری (Sampling) است. اگر یک مدل زبانی صرفاً توکنی را انتخاب کند که بالاترین احتمال را دارد، پاسخ‌ها یکنواخت، تکراری و غیرطبیعی می‌شوند. برعکس، انتخاب کاملاً تصادفی نیز به خروجی‌های بی‌معنی می‌انجامد. تسلط بر استراتژی‌های نمونه‌برداری به شما امکان می‌دهد تعادل میان دقت، انسجام و خلاقیت را در مدل‌ها برقرار کنید.

علاوه بر کنترل متن تولیدی، تکنیک‌های نمونه‌برداری ستون فقرات آموزش و استنتاج در مدل‌های پیشرفته هستند؛ از ترفند بازپارامتری‌سازی در VAEها که امکان پس‌انتشار را فراهم می‌سازد تا الگوریتم‌های MCMC و روش‌های مونت‌کارلو برای تقریب انتگرال‌های پیچیده و برآورد گرادیان‌ها در یادگیری تقویتی. این درس منطق ریاضی و پیاده‌سازی گام‌به‌گام این الگوریتم‌ها را از صفر بررسی می‌کند تا مکانیزم درونی کتابخانه‌ها و پارامترهای LLMها را دقیق بشناسید.

نمونه‌برداری (Sampling) شیوه‌ی هوش مصنوعی برای کاوش در فضای احتمالات است.

اهداف یادگیری

• پیاده‌سازی نمونه‌برداری معکوس CDF، نمونه‌برداری طردی (rejection sampling) و نمونه‌برداری اهمیتی (importance sampling) از صفر، فقط با استفاده از اعداد تصادفی یکنواخت
• ساخت نمونه‌برداری با دما (temperature)، نمونه‌برداری top-k و نمونه‌برداری top-p (هسته‌ای یا nucleus) برای تولید توکن در مدل‌های زبانی
• توضیح ترفند بازپارامتری‌سازی (reparameterization trick) و چگونگی فراهم‌کردن امکان پس‌انتشار (backpropagation) از میان عمل نمونه‌برداری در VAEها
• اجرای الگوریتم Metropolis-Hastings MCMC برای نمونه‌برداری از یک توزیع هدف نرمال‌نشده

صورت مسئله

یک مدل زبانی پردازش پرامپت شما را تمام می‌کند و برداری از 50,000 لوجیت (logit) تحویل می‌دهد؛ یک مقدار برای هر توکن در واژگانش. حالا باید یکی را انتخاب کند. اما چطور؟

اگر همیشه توکنی را انتخاب کند که بیشترین احتمال را دارد، همه‌ی پاسخ‌ها یکسان خواهند بود: قطعی، پیش‌پاافتاده و خسته‌کننده. اگر کاملاً تصادفی و با احتمال یکنواخت انتخاب کند، خروجی چرت‌وپرت خواهد بود. پاسخ مطلوب جایی میان این دو سر طیف قرار دارد؛ و آن نقطه دقیقاً با نمونه‌برداری کنترل می‌شود.

نمونه‌برداری محدود به تولید متن نیست. در یادگیری تقویتی (reinforcement learning)، گرادیان‌های خط‌مشی با نمونه‌برداری از مسیرها تخمین زده می‌شوند. VAEها بازنمایی‌های نهفته را با نمونه‌برداری از توزیع‌های آموخته‌شده و پس‌انتشار از دل تصادفی‌بودن یاد می‌گیرند. مدل‌های انتشار (diffusion models) با نمونه‌برداری از نویز و نویززدایی گام‌به‌گام تصویر تولید می‌کنند. روش‌های مونت‌کارلو (Monte Carlo) انتگرال‌هایی را تخمین می‌زنند که راه‌حل تحلیلی و فرمول بسته ندارند. الگوریتم‌های MCMC توزیع‌های پسین چندبعدی را کاوش می‌کنند که فهرست‌کردن تمام مقادیر آن‌ها غیرممکن است.

هر سیستم هوش مصنوعی مولد در واقع یک سیستم نمونه‌برداری است. استراتژی نمونه‌برداری، کیفیت، تنوع و مهارپذیری خروجی را تعیین می‌کند. در این درس، تک‌تک روش‌های اصلی نمونه‌برداری را از صفر می‌سازیم؛ از اعداد تصادفی یکنواخت شروع می‌کنیم و به تکنیک‌هایی می‌رسیم که موتور محرک LLMها و مدل‌های مولد امروزی هستند.

مفاهیم پایه

چرا نمونه‌برداری اهمیت دارد؟

نمونه‌برداری چهار نقش بنیادین در هوش مصنوعی و یادگیری ماشین ایفا می‌کند:

تولید (Generation). مدل‌های زبانی، مدل‌های انتشار و GANها همگی با نمونه‌برداری خروجی تولید می‌کنند. الگوریتم نمونه‌برداری مستقیماً خلاقیت، انسجام و تنوع را کنترل می‌کند. پارامترهای Temperature، top-k و nucleus پیچ‌های تنظیمی هستند که مهندسان هر روز با آن‌ها سروکار دارند.

آموزش (Training). روش گرادیان کاهشی تصادفی (SGD) مینی‌بچ‌ها را نمونه‌برداری می‌کند. دراپ‌اوت (Dropout) نورون‌هایی را برای غیرفعال‌شدن برمی‌گزیند. داده‌افزایی (Data augmentation) تبدیل‌های تصادفی را نمونه می‌گیرد. نمونه‌برداری اهمیتی با وزن‌دهی دوباره به نمونه‌ها، واریانس گرادیان را در یادگیری تقویتی (مثل PPO و TRPO) کاهش می‌دهد.

تخمین (Estimation). بسیاری از کمیت‌ها در یادگیری ماشین فرمول بسته‌ای ندارند: امید ریاضی تابع زیان روی توزیع داده، تابع افراز (partition function) در مدل‌های مبتنی بر انرژی، و شواهد (evidence) در استنتاج بیزی. روش مونت‌کارلو همه‌ی این مقادیر را با میانگین‌گیری روی نمونه‌ها تقریب می‌زند.

کاوش (Exploration). الگوریتم‌های MCMC توزیع‌های پسین را در استنتاج بیزی بررسی می‌کنند. راهبردهای تکاملی، اغتشاش‌های پارامتری را نمونه‌برداری می‌کنند. روش تامپسون (Thompson sampling) تعادل میان کاوش و بهره‌برداری را در مسائل راهزن چنددست بر قرار می‌کند.

چالش اصلی اینجاست: شما فقط می‌توانید مستقیماً از توزیع‌های ساده (مثل یکنواخت و نرمال) نمونه‌برداری کنید. برای هر توزیع دیگری، نیازمند روشی هستید که نمونه‌های ساده را به نمونه‌هایی از توزیع هدف تبدیل کند.

نمونه‌برداری تصادفی یکنواخت

همه‌ی روش‌های نمونه‌برداری از این نقطه شروع می‌شوند. یک مولد اعداد تصادفی یکنواخت، مقادیری در بازه‌ی $[0, 1)$ تولید می‌کند که در آن هر زیربازه‌ای با طول یکسان، شانس برابری دارد.

U ~ Uniform(0, 1)

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

Properties:
  E[U] = 0.5
  Var(U) = 1/12

برای نمونه‌برداری یکنواخت از یک مجموعه‌ی گسسته با $n$ عضو، مقدار $U$ را تولید کنید و $\lfloor n U \rfloor$ را برگردانید. برای نمونه‌برداری از یک بازه‌ی پیوسته $[a, b]$، عبارت $a + (b - a) U$ را حساب کنید.

نکته‌ی کلیدی: یک عدد تصادفی یکنواخت دقیقاً حاوی همان اندازه‌ای از تصادفی‌بودن است که برای تولید یک نمونه از هر توزیعی نیاز دارید. چالش اصلی پیدا کردن تبدیل مناسب است.

روش معکوس تابع توزیع تجمعی (Inverse Transform Sampling)

تابع توزیع تجمعی (CDF) مقادیر را به احتمال‌ها نگاشت می‌کند:

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

Properties:
  F is non-decreasing
  F(-inf) = 0
  F(+inf) = 1
  F maps the real line to [0, 1]

معکوس CDF احتمال‌ها را دوباره به مقادیر برمی‌گرداند. اگر $U \sim \text{Uniform}(0, 1)$ باشد، آنگاه $X = F^{-1}(U)$ از توزیع هدف پیروی می‌کند.

Algorithm:
  1. Generate u ~ Uniform(0, 1)
  2. Return F_inverse(u)

Why it works:
  P(X <= x) = P(F_inverse(U) <= x) = P(U <= F(x)) = F(x)

مثال توزیع نمایی:

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

Solve F(x) = u for x:
  u = 1 - exp(-lambda * x)
  exp(-lambda * x) = 1 - u
  x = -ln(1 - u) / lambda

Since (1 - U) and U have the same distribution:
  x = -ln(u) / lambda

این روش زمانی عالی کار می‌کند که بتوانید $F^{-1}$ را به صورت یک فرمول بسته بنویسید. برای توزیع نرمال، معکوس CDF فرمول بسته ندارد؛ بنابراین از روش‌های دیگر (مثل Box-Muller یا تقریب‌های عددی) استفاده می‌کنیم.

نسخه‌ی گسسته: برای توزیع‌های گسسته، CDF را با جمع تجمعی (cumulative sum) می‌سازید، عدد $U$ را تولید می‌کنید و اولین اندیسی را پیدا می‌کنید که جمع تجمعی در آن از $U$ بیشتر می‌شود. تابع sample_categorical در درس 06 دقیقاً به همین شیوه کار می‌کند.

نمونه‌برداری طردی (Rejection Sampling)

وقتی نمی‌توانید CDF را معکوس کنید اما امکان محاسبه‌ی تابع چگالی احتمال هدف (PDF) تا حد یک ضریب ثابت را دارید، نمونه‌برداری طردی گره‌گشاست.

Target distribution: p(x)  (can evaluate, possibly unnormalized)
Proposal distribution: q(x)  (can sample from)
Bound: M such that p(x) <= M * q(x) for all x

Algorithm:
  1. Sample x ~ q(x)
  2. Sample u ~ Uniform(0, 1)
  3. If u < p(x) / (M * q(x)), accept x
  4. Otherwise, reject and go to step 1

Acceptance rate = Z/M, where Z is the integral of p(x)
                (Z = 1, so the rate is 1/M, when p is normalized)

هر چه کران $M$ تنگ‌تر باشد، نرخ پذیرش (acceptance rate) بالاتر خواهد بود. در ابعاد پایین (1 تا 3)، نمونه‌برداری طردی عملکرد خوبی دارد. در ابعاد بالا، نرخ پذیرش به‌شکل نمایی سقوط می‌کند، چرا که بیشتر حجم توزیع پیشنهادی طرد می‌شود. این پدیده، همان نفرین ابعاد (curse of dimensionality) در نمونه‌برداری طردی است.

مثال: نمونه‌برداری از توزیع نرمال بریده‌شده (truncated normal). از یک توزیع پیشنهادی یکنواخت روی بازه‌ی بریده‌شده استفاده کنید. پوشش $M$ بیشینه‌ی PDF توزیع نرمال در آن بازه است.

مثال: نمونه‌برداری از یک نیم‌دایره. نقاط را به‌صورت یکنواخت در مستطیل محیطی پیشنهاد دهید. اگر نقطه درون نیم‌دایره افتاد، آن را بپذیرید. روش مونت‌کارلو به همین ترتیب عدد $\pi$ را تخمین می‌زند: نرخ پذیرش برابر با نسبت مساحت‌ها یعنی $\pi/4$ است.

نمونه‌برداری اهمیتی (Importance Sampling)

گاهی اوقات به نمونه‌هایی از توزیع هدف $p(x)$ نیازی ندارید. شما می‌خواهید امید ریاضی را تحت توزیع $p(x)$ تخمین بزنید، و نمونه‌هایی از توزیع متفاوتی مانند $q(x)$ در دست دارید.

Goal: estimate E_p[f(x)] = integral of f(x) * p(x) dx

Rewrite:
  E_p[f(x)] = integral of f(x) * (p(x)/q(x)) * q(x) dx
            = E_q[f(x) * w(x)]

where w(x) = p(x) / q(x)  are the importance weights.

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

این تکنیک نقشی حیاتی در یادگیری تقویتی دارد. در الگوریتم PPO (بهینه‌سازی خط‌مشی نزدیک)، شما مسیرها را بر اساس خط‌مشی قدیمی $\pi_{\text{old}}$ جمع‌آوری می‌کنید اما قصد دارید خط‌مشی جدید $\pi_{\text{new}}$ را بهینه‌سازی کنید. وزن اهمیت برابر با $\pi_{\text{new}}(a \mid s) / \pi_{\text{old}}(a \mid s)$ است. PPO این وزن‌ها را برش می‌زند (clip می‌کند) تا مانع از فاصله‌گرفتن بیش از حد خط‌مشی جدید از خط‌مشی قبلی شود.

واریانس برآوردگر نمونه‌برداری اهمیتی به شباهت بین $q$ و $p$ بستگی دارد. اگر $q$ فاصله‌ی زیادی با $p$ داشته باشد، تعداد اندکی از نمونه‌ها وزن‌های فوق‌العاده بزرگی پیدا می‌کنند و کل تخمین را تحت‌الشعاع قرار می‌دهند. نمونه‌برداری اهمیتی خودنرمال‌ساز (self-normalized) با تقسیم بر مجموع وزن‌ها این مشکل را تخفیف می‌دهد:

$$\mathbb{E}_p[f(x)] \approx \frac{\sum_i w_i \, f(x_i)}{\sum_i w_i}$$

تخمین مونت‌کارلو (Monte Carlo Estimation)

تخمین مونت‌کارلو با میانگین‌گیری از نمونه‌های تصادفی، انتگرال‌ها را تقریب می‌زند. قانون اعداد بزرگ، همگرایی این تقریب را تضمین می‌کند.

Goal: estimate I = integral of g(x) dx over domain D

Method:
  1. Sample x_1, ..., x_N uniformly from D
  2. I ~ (Volume of D / N) * sum(g(x_i))

Error: O(1 / sqrt(N))   regardless of dimension

نرخ خطای این روش ربطی به ابعاد مسئله ندارد. درست به همین دلیل است که روش‌های مونت‌کارلو در ابعاد بالا، جایی که انتگرال‌گیری شبکه‌محور ناممکن می‌شود، دست بالا را دارند.

تخمین عدد پی:

Sample (x, y) uniformly from [-1, 1] x [-1, 1]
Count how many fall inside the unit circle: x^2 + y^2 <= 1
pi ~ 4 * (count inside) / (total count)

تخمین امید ریاضی:

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

The sample mean converges to the true expectation.
Variance of the estimator = Var(f(X)) / N

روش‌های زنجیره‌ی مارکوفی مونت‌کارلو (MCMC): متروپولیس-هیستینگز

روش MCMC زنجیره‌ای مارکوفی می‌سازد که توزیع پایای آن توزیع هدف $p(x)$ است. پس از گذشت گام‌های کافی، نمونه‌های به‌دست‌آمده از زنجیره (تقریباً) همان نمونه‌های توزیع $p(x)$ خواهند بود.

Target: p(x)  (known up to a normalizing constant)
Proposal: q(x'|x)  (how to propose the next state given the current state)

Metropolis-Hastings algorithm:
  1. Start at some x_0
  2. For t = 1, 2, ..., T:
     a. Propose x' ~ q(x'|x_t)
     b. Compute acceptance ratio:
        alpha = [p(x') * q(x_t|x')] / [p(x_t) * q(x'|x_t)]
     c. Accept with probability min(1, alpha):
        - If u < alpha (u ~ Uniform(0,1)): x_{t+1} = x'
        - Otherwise: x_{t+1} = x_t
  3. Discard first B samples (burn-in)
  4. Return remaining samples

برای پیشنهادهای متقارن $(q(x' \mid x) = q(x \mid x'))$، این نسبت ساده‌تر شده و به صورت $p(x')/p(x)$ درمی‌آید. این حالت، همان الگوریتم اولیه‌ی متروپولیس است.

دلیل درستی الگوریتم. قاعده‌ی پذیرش متضمن برقراری تعادل جزئی (detailed balance) است: احتمال حضور در $x$ و رفتن به $x'$ با احتمال حضور در $x'$ و رفتن به $x$ برابر می‌شود. برقراری تعادل جزئی نشان می‌دهد که $p(x)$ توزیع پایای زنجیره است.

نکات کاربردی:

• دوره‌ی گرم‌شدن (Burn-in): دور ریختن نمونه‌های اولیه پیش از رسیدن زنجیره به تعادل
• رقیق‌سازی (Thinning): نگه‌داشتن هر $k$اُمین نمونه برای کاهش خودهمبستگی
• مقیاس توزیع پیشنهادی: اگر بیش از حد کوچک باشد زنجیره کُند حرکت می‌کند (پذیرش بالا، اما کاوش بسیار کُند)؛ اگر زیادی بزرگ باشد اغلب پیشنهادها رد می‌شوند (پذیرش پایین و درجا زدن زنجیره)
• نرخ پذیرش بهینه برای یک پیشنهاد گاوسی در ابعاد بالا تقریباً 0.234 است

نمونه‌برداری گیبز (Gibbs Sampling)

نمونه‌برداری گیبز حالت خاصی از MCMC برای توزیع‌های چندمتغیره است. به جای پیشنهاد حرکت هم‌زمان در همه‌ی ابعاد، در هر گام یک متغیر را با استفاده از توزیع شرطی آن به‌روزرسانی می‌کند.

Target: p(x_1, x_2, ..., x_d)

Algorithm:
  For each iteration t:
    Sample x_1^{t+1} ~ p(x_1 | x_2^t, x_3^t, ..., x_d^t)
    Sample x_2^{t+1} ~ p(x_2 | x_1^{t+1}, x_3^t, ..., x_d^t)
    ...
    Sample x_d^{t+1} ~ p(x_d | x_1^{t+1}, x_2^{t+1}, ..., x_{d-1}^{t+1})

نمونه‌برداری گیبز مستلزم توانایی نمونه‌برداری از تک‌تک توزیع‌های شرطی $p(x_i \mid x_{-i})$ است. این کار در بسیاری از مدل‌ها ساده است:

• شبکه‌های بیزی: توزیع‌های شرطی مستقیماً از ساختار گراف به دست می‌آیند
• مخلوط‌های گاوسی: توزیع‌های شرطی از جنس گاوسی هستند
• مدل‌های آیزینگ: توزیع شرطی هر اسپین فقط به همسایه‌های آن وابسته است

نرخ پذیرش در این روش همیشه 1 است (هر پیشنهادی پذیرفته می‌شود)، زیرا نمونه‌برداری مستقیم از توزیع شرطی دقیق، خودبه‌خود شرط تعادل جزئی را برآورده می‌کند.

محدودیت. وقتی متغیرها همبستگی شدیدی داشته باشند، سرعت آمیختگی (mixing) نمونه‌برداری گیبز بسیار افت می‌کند؛ زیرا به‌روزرسانی تک‌تک متغیرها نمی‌تواند گام‌های قطری بزرگی در فضای توزیع بردارد.

نمونه‌برداری با دما (Temperature Sampling در مدل‌های زبانی)

مدل‌های زبانی برای هر توکن از واژگان خود، لوجیت‌هایی $z_1, \ldots, z_V$ تولید می‌کنند. تابع Softmax این مقادیر را به احتمال تبدیل می‌کند. دما مقیاس لوجیت‌ها را پیش از اِعمال Softmax تغییر می‌دهد:

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

T = 1.0: standard softmax (original distribution)
T -> 0:  argmax (deterministic, always picks highest logit)
T -> inf: uniform (all tokens equally likely)
T < 1.0: sharpens the distribution (more confident, less diverse)
T > 1.0: flattens the distribution (less confident, more diverse)

نحوه‌ی کار. تقسیم لوجیت‌ها بر $T < 1$ اختلاف بین آن‌ها را پررنگ‌تر می‌کند. اگر $z_1 = 2$ و $z_2 = 1$ باشند، تقسیم آن‌ها بر $T = 0.5$ مقادیر $z_1/T = 4$ و $z_2/T = 2$ را می‌دهد که اختلاف بیشتری از هم دارند. پس از اِعمال Softmax، توکنی که بیشترین لوجیت را دارد سهم بسیار بزرگ‌تری از احتمال را به خود اختصاص می‌دهد.

در عمل:

• $T = 0.0$: رمزگشایی حریصانه (greedy)، ایدئال برای پرسش‌وپاسخ‌های مبتنی بر واقعیت
• $T = 0.3\text{-}0.7$: خلاقیت اندک، مناسب برای تولید کد
• $T = 0.7\text{-}1.0$: متعادل، خوب برای گفت‌وگوهای عمومی
• $T = 1.0\text{-}1.5$: داستان‌نویسی و ایده‌پردازی خلاقانه
• $T > 1.5$: به‌شدت تصادفی، به‌ندرت کاربردی دارد

دما فهرست توکن‌های ممکن را تغییر نمی‌دهد؛ بلکه توزیع جرم احتمال میان این توکن‌ها را دگرگون می‌کند.

نمونه‌برداری Top-k

نمونه‌برداری top-k مجموعه‌ی کاندیداها را تنها به $k$ توکنی که بالاترین احتمال را دارند محدود می‌کند، سپس احتمال‌ها را دوباره نرمال کرده و از آن مجموعه‌ی محدود نمونه برمی‌دارد.

Algorithm:
  1. Compute softmax probabilities for all V tokens
  2. Sort tokens by probability (descending)
  3. Keep only the top k tokens
  4. Renormalize: p_i' = p_i / sum(p_j for j in top-k)
  5. Sample from the renormalized distribution

k = 1:  greedy decoding
k = V:  no filtering (standard sampling)
k = 40: typical setting, removes long tail of unlikely tokens

روش top-k مانع از آن می‌شود که مدل، توکن‌های به‌شدت نامحتمل (مثل غلط‌های املایی یا کلمات بی‌ربط) موجود در دم طولانی واژگان را انتخاب کند. مشکل اینجاست: مقدار $k$ صرف‌نظر از بافت متن ثابت می‌ماند. وقتی مدل به پاسخ خود کاملاً مطمئن است (یک توکن احتمال 95% دارد)، $k = 40$ همچنان اجازه می‌دهد 39 گزینه‌ی دیگر بررسی شوند. برعکس، وقتی مدل دچار تردید است (احتمال بین 1000 توکن پخش شده)، $k = 40$ گزینه‌های معقول را حذف می‌کند.

نمونه‌برداری Top-p (هسته‌ای یا Nucleus)

نمونه‌برداری top-p اندازه‌ی مجموعه‌ی کاندیداها را پویا نگه می‌دارد. به جای حفظ تعداد ثابتی از توکن‌ها، کوچک‌ترین مجموعه‌ای از توکن‌ها را برمی‌گزیند که مجموع احتمال تجمعی آن‌ها از مقدار $p$ بگذرد.

Algorithm:
  1. Compute softmax probabilities for all V tokens
  2. Sort tokens by probability (descending)
  3. Find smallest k such that sum of top-k probabilities >= p
  4. Keep only those k tokens
  5. Renormalize and sample

p = 0.9:  keeps tokens covering 90% of probability mass
p = 1.0:  no filtering
p = 0.1:  very restrictive, nearly greedy

هنگامی که مدل اطمینان بالایی دارد، نمونه‌برداری هسته‌ای توکن‌های انگشت‌شماری (شاید 2 یا 3 تا) را نگه می‌دارد. وقتی دچار تردید است، توکن‌های زیادی (شاید 200 تا) در دایره‌ی انتخاب می‌مانند. این رفتار تطبیقی دلیلی است بر این که چرا نمونه‌برداری هسته‌ای عموماً متنی بهتر از top-k تولید می‌کند.

ترکیب‌های رایج:

• دمای 0.7 به همراه top-p با مقدار 0.9: تنظیمی عالی برای کاربردهای عمومی
• دمای 0.0 (حریصانه): بهترین انتخاب برای کارهای قطعی
• دمای 1.0 به همراه top-k با مقدار 50: تنظیمات مقاله‌ی اصلی Fan et al. (2018)

امکان ترکیب top-k و top-p هم وجود دارد: ابتدا فیلتر top-k را اِعمال کنید و سپس top-p را روی مجموعه‌ی باقی‌مانده پیاده سازید.

ترفند بازپارامتری‌سازی (Reparameterization Trick در VAEها)

خودرمزگذارهای متغیر (VAEs) ورودی را به یک توزیع در فضای نهفته کدگذاری کرده، از آن توزیع نمونه‌برداری می‌کنند و در نهایت با رمزگشایی نمونه، ورودی را بازسازی می‌کنند. مشکل اینجاست: پس‌انتشار گرادیان از میان یک عملیات نمونه‌برداری ناممکن است.

Standard sampling (not differentiable):
  z ~ N(mu, sigma^2)

  The randomness blocks gradient flow.
  d/d_mu [sample from N(mu, sigma^2)] = ???

ترفند بازپارامتری‌سازی بخش تصادفی را از پارامترها جدا می‌کند:

Reparameterized sampling:
  epsilon ~ N(0, 1)          (fixed random noise, no parameters)
  z = mu + sigma * epsilon   (deterministic function of parameters)

  Now z is a deterministic, differentiable function of mu and sigma.
  d(z)/d(mu) = 1
  d(z)/d(sigma) = epsilon

  Gradients flow through mu and sigma.

این فرمولاسیون به‌درستی عمل می‌کند؛ زیرا توزیع $\mathcal{N}(\mu, \sigma^2)$ عیناً مشابه $\mu + \sigma \cdot \mathcal{N}(0, 1)$ است. ایده‌ی کلیدی: مؤلفه‌ی تصادفی را به منبعی بدون پارامتر ($\epsilon$) منتقل کنید و سپس نمونه را به شکل تبدیلی مشتق‌پذیر از پارامترها بنویسید.

در حلقه‌ی آموزش VAE:

1. انکودر برای هر ورودی مقادیر $\mu$ و $\log(\sigma^2)$ را تولید می‌کند
2. بردار نویز $\epsilon \sim \mathcal{N}(0, 1)$ نمونه‌برداری می‌شود
3. مقدار $z = \mu + \sigma \epsilon$ محاسبه می‌شود
4. دکودر با دریافت $z$ ورودی را بازسازی می‌کند
5. پس‌انتشار به ترتیب در مراحل 4، 3، 2 و 1 جریان می‌یابد (این کار ممکن است چون مرحله‌ی 3 مشتق‌پذیر است)

بدون ترفند بازپارامتری‌سازی، امکان آموزش VAEها با پس‌انتشار استاندارد وجود نداشت. همین یک نوآوری بود که VAEها را به ابزارهایی کاربردی تبدیل کرد.

روش Gumbel-Softmax (نمونه‌برداری دسته‌ای مشتق‌پذیر)

ترفند بازپارامتری‌سازی مخصوص توزیع‌های پیوسته (مانند گاوسی) است. برای توزیع‌های دسته‌ای گسسته (categorical) نیازمند راهکار دیگری هستیم. ترفند Gumbel-Softmax تقریبی مشتق‌پذیر از نمونه‌برداری دسته‌ای ارائه می‌دهد.

ترفند Gumbel-Max (غیرمشتق‌پذیر):

To sample from a categorical distribution with log-probabilities log(p_1), ..., log(p_k):
  1. Sample g_i ~ Gumbel(0, 1) for each category
     (g = -log(-log(u)), where u ~ Uniform(0, 1))
  2. Return argmax(log(p_i) + g_i)

This produces exact categorical samples.

روش Gumbel-Softmax (تقریب مشتق‌پذیر):

Replace the hard argmax with a soft softmax:
  y_i = exp((log(p_i) + g_i) / tau) / sum(exp((log(p_j) + g_j) / tau))

tau (temperature) controls the approximation:
  tau -> 0:  approaches a one-hot vector (hard categorical)
  tau -> inf: approaches uniform (1/k, 1/k, ..., 1/k)
  tau = 1.0: soft approximation

روش Gumbel-Softmax نسخه‌ای پیوسته و ملایم از یک نمونه‌ی گسسته می‌سازد. خروجی به جای یک بردار one-hot سخت، یک بردار احتمالاتی (soft one-hot) است. گرادیان‌ها به‌راحتی از تابع Softmax عبور می‌کنند. در طول مرحله‌ی رفت (forward pass) آموزش، می‌توانید از برآوردگر «مستقیم» (straight-through) کمک بگیرید: در رفت از argmax سخت استفاده کنید اما در مرحله‌ی برگشت، گرادیان‌های نرم Gumbel-Softmax را عبور دهید.

کاربردها:

• متغیرهای نهفته‌ی گسسته در VAEها
• جست‌وجوی معماری شبکه عصبی (انتخاب عملیات گسسته)
• سازوکارهای اتنشن سخت (hard attention)
• یادگیری تقویتی با اکشن‌های گسسته

نمونه‌برداری طبقه‌بندی‌شده (Stratified Sampling)

نمونه‌برداری مونت‌کارلوی استاندارد ممکن است بر حسب اتفاق، بخش‌هایی از فضای نمونه را خالی بگذارد. نمونه‌برداری طبقه‌بندی‌شده فضا را به چند طبقه (strata) تقسیم کرده و از تک‌تک آن‌ها نمونه برمی‌دارد تا پوشش یکنواختی تضمین شود.

Standard Monte Carlo:
  Sample N points uniformly from [0, 1]
  Some regions may have clusters, others gaps

Stratified sampling:
  Divide [0, 1] into N equal strata: [0, 1/N), [1/N, 2/N), ..., [(N-1)/N, 1)
  Sample one point uniformly within each stratum
  x_i = (i + u_i) / N   where u_i ~ Uniform(0, 1),  i = 0, ..., N-1

واریانس نمونه‌برداری طبقه‌بندی‌شده همواره کمتر یا مساوی مونت‌کارلوی استاندارد است:

Var(stratified) <= Var(standard Monte Carlo)

The improvement is largest when f(x) varies smoothly.
For piecewise-constant functions, stratified sampling is exact.

کاربردها:

• انتگرال‌گیری عددی (روش‌های شبه‌مونت‌کارلو)
• تقسیم‌بندی داده‌های آموزشی (تضمین تعادل کلاس‌ها در هر فولد)
• نمونه‌برداری اهمیتی همراه با طبقه‌بندی (ترکیب هر دو تکنیک)
• مدل‌های NeRF که در امتداد پرتوهای دوربین از نمونه‌برداری طبقه‌بندی‌شده بهره می‌برند

ارتباط با مدل‌های انتشار (Diffusion Models)

مدل‌های انتشار تصاویر را از طریق فرایندی مبتنی بر نمونه‌برداری خلق می‌کنند. در فرایند رفت، طی $T$ مرحله نویز گاوسی به تصویر اضافه می‌شود تا جایی که تصویر به نویز خالص بدل شود. در فرایند برگشت، شبکه یاد می‌گیرد نویز را گام‌به‌گام حذف کند تا تصویر اولیه بازیابی شود.

Forward process (known):
  x_t = sqrt(alpha_t) * x_{t-1} + sqrt(1 - alpha_t) * epsilon
  where epsilon ~ N(0, I)

  After T steps: x_T ~ N(0, I)  (pure noise)

Reverse process (learned):
  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
  where z ~ N(0, I)

  Each denoising step is a sampling step.

پیوند میان این مدل‌ها و روش‌های این درس:

• هر مرحله‌ی نویززدایی از ترفند بازپارامتری‌سازی استفاده می‌کند (نمونه‌برداری نویز و اِعمال تبدیل معین)
• زمان‌بندی نویز $\lbrace \alpha_t \rbrace$ نقشی مشابه با کاهش تدریجی دما (annealing) دارد
• فرایند آموزش از تخمین مونت‌کارلو برای تقریب زدن حد پایین شواهد (ELBO) بهره می‌برد
• نمونه‌برداری نیاکانی (ancestral sampling) در مدل‌های انتشار یک زنجیره‌ی مارکوفی است (هر مرحله فقط به حالت فعلی بستگی دارد)

کل فرایند تولید تصویر، یک نمونه‌برداری تکرارشونده است: از نویز شروع می‌کنید و در هر گام، نسخه‌ای اندکی کم‌نویزتر را با شرط‌کردن روی مدل نویززدای آموزش‌دیده نمونه برمی‌دارید.

پیاده‌سازی از صفر

گام 1: نمونه‌برداری یکنواخت و معکوس CDF

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

تعداد 10,000 نمونه‌ی نمایی تولید کنید و بررسی کنید که میانگین آن‌ها برابر با $1/\lambda$ باشد.

گام 2: نمونه‌برداری طردی

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

با استفاده از نمونه‌برداری طردی، از یک توزیع نرمال بریده‌شده نمونه بگیرید. صحت شکل توزیع را با رسم هیستوگرام نمونه‌ها بررسی کنید.

گام 3: نمونه‌برداری اهمیتی

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

مقدار $\mathbb{E}[X^2]$ را تحت توزیع نرمال با کمک یک توزیع پیشنهادی یکنواخت تخمین بزنید. نتیجه را با پاسخ معلوم یعنی $\mu^2 + \sigma^2$ مقایسه کنید.

گام 4: تخمین عدد پی به روش مونت‌کارلو

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

گام 5: روش MCMC متروپولیس-هیستینگز

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

از یک توزیع دوقله‌ای (مخلوط دو گاوسی) نمونه‌برداری کنید و مسیر زنجیره را به تصویر بکشید.

گام 6: نمونه‌برداری گیبز

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

گام 7: نمونه‌برداری با دما

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)

نشان دهید که تغییر دما چگونه توزیع خروجی یک بردار لوجیت را تغییر می‌دهد.

گام 8: نمونه‌برداری Top-k و 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]

گام 9: ترفند بازپارامتری‌سازی

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

نشان دهید که گرادیان‌ها از نمونه‌ی بازپارامتری‌شده عبور می‌کنند اما امکان عبور از نمونه‌برداری مستقیم را ندارند.

گام 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])

نشان دهید که با کاهش دما چگونه بردار خروجی به یک بردار one-hot نزدیک می‌شود.

پیاده‌سازی‌های کامل به همراه تمام نمودارها در فایل code/sampling.py در دسترس است.

استفاده از ابزارهای واقعی

پیاده‌سازی‌های سطح تولید با NumPy و 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}")

برای مقیاس‌های بزرگ MCMC، کتابخانه‌های تخصصی زیر را به کار بگیرید:

• PyMC: مدل‌سازی کامل بیزی با NUTS (روش HMC تطبیقی)
• emcee: نمونه‌بردار گروهی MCMC
• NumPyro/JAX: اجرای MCMC با شتاب‌دهنده‌ی GPU

شما این مفاهیم را از پایه ساخته‌اید؛ حالا دقیقاً می‌دانید فراخوانی‌های کتابخانه در پس‌زمینه چه می‌کنند.

تمرین‌ها

1. نمونه‌برداری معکوس CDF را برای توزیع کوشی (Cauchy) پیاده کنید. تابع CDF این توزیع $F(x) = 0.5 + \arctan(x)/\pi$ است. تعداد 10,000 نمونه بسازید و هیستوگرام آن را با PDF واقعی مقایسه کنید. به دم‌های سنگین توزیع (مقادیر دورافتاده از مرکز) دقت کنید.

2. با استفاده از یک توزیع پیشنهادی Uniform(0, 1) و روش نمونه‌برداری طردی، از توزیع Beta(2, 5) نمونه تولید کنید. هیستوگرام نمونه‌های پذیرفته‌شده را در برابر PDF دقیق بتا رسم کنید. نرخ پذیرش نظری چقدر است؟

3. انتگرال تابع $\sin(x)$ را از 0 تا $\pi$ با روش مونت‌کارلو و به ازای 1,000، 10,000 و 100,000 نمونه تقریب بزنید. خطای تخمین را در هر سطح مقایسه کنید. نشان دهید که خطا متناسب با $O(1/\sqrt{N})$ مقیاس می‌گیرد.

4. الگوریتم متروپولیس-هیستینگز را برای نمونه‌برداری از توزیع دوبعدی $p(x, y)$ متناسب با $\exp(-(x^2 y^2 + x^2 + y^2 - 8x - 8y) / 2)$ پیاده‌سازی کنید. نمونه‌ها و مسیر حرکت زنجیره را رسم کنید. آزمایش را با انحراف معیارهای متفاوتی برای توزیع پیشنهادی بیازمایید.

5. یک دمو کامل تولید متن بسازید: با داشتن واژگانی 10 کلمه‌ای همراه با لوجیت‌ها، توالی‌هایی از 20 توکن را با روش‌های (الف) حریصانه، (ب) دما=0.7، (ج) top-k=3 و (د) top-p=0.9 تولید کنید. تنوع کلمات خروجی را در 5 بار اجرای مختلف مقایسه کنید.

راهنمایی‌ها

تمرین 1. معادله‌ی $u = F(x)$ را بر حسب $x$ حل کنید که نتیجه‌ی آن $x = \tan(\pi(u - 0.5))$ خواهد بود. دقت کنید که میانه‌ی نمونه‌ها به 0 نزدیک باشد و حدود 6% نمونه‌ها مقادیری با $\lvert x \rvert > 10$ داشته باشند، یعنی $1 - (2/\pi)\arctan(10)$.

تمرین 2. چگالی توزیع Beta(2, 5) برابر با $30x(1-x)^4$ است. بیشینه‌ی این تابع را در نقطه‌ی مُد آن یعنی $x = 1/5$ پیدا کنید و از این مقدار به عنوان $M$ در rejection_sample بهره بگیرید. نرخ پذیرش نظری $1/M$ است؛ پس آن را با نسبت پیشنهادهای پذیرفته‌شده مقایسه کنید.

تمرین 3. پاسخ دقیق انتگرال 2 است. تابع monte_carlo_integral(math.sin, 0, math.pi, n) را به ازای مقادیر مختلف $n$ فراخوانی کنید و اجراها را با چندین سید (seed) تصادفی تکرار کنید. هر بار که $n$ به اندازه‌ی 10 برابر زیاد می‌شود، میانگین خطا باید تقریباً به ضریب $\sqrt{10} \approx 3.2$ کاهش یابد.

تمرین 4. لگاریتم تابع هدف یعنی $-(x^2 y^2 + x^2 + y^2 - 8x - 8y)/2$ را بنویسید و آن را به تابع metropolis_hastings_2d بفرستید. نرخ پذیرش را به ازای هر انحراف معیار در توزیع پیشنهادی ثبت کنید: مقادیر خیلی کوچک تقریباً همه‌ی گام‌ها را می‌پذیرند اما حرکت بسیار کُندی دارند، و مقادیر خیلی بزرگ بیشتر گام‌ها را رد می‌کنند.

تمرین 5. در رمزگشایی حریصانه، در هر گام اندیس بزرگ‌ترین لوجیت را انتخاب کنید. برای سه روش دیگر از توابع temperature_sample، top_k_sample و top_p_sample کمک بگیرید. روش حریصانه در تمام 5 اجرا پاسخی کاملاً یکسان تولید می‌کند؛ بنابراین برای سنجش تنوع، تعداد توالی‌های یکتا را برای هر روش بشمارید.

اصطلاحات کلیدی

برای مطالعه‌ی بیشتر

• مقاله‌ی Holbrook (2023): The Metropolis-Hastings Algorithm - راهنمای جامع و دقیق اصول بنیادین MCMC
• مقاله‌ی Jang, Gu, Poole (2017): Categorical Reparameterization with Gumbel-Softmax - مقاله‌ی اصلی ترفند Gumbel-Softmax
• مقاله‌ی Holtzman et al. (2020): The Curious Case of Neural Text Degeneration - مقاله‌ی معرفی نمونه‌برداری هسته‌ای (top-p)
• مقاله‌ی Kingma & Welling (2014): Auto-Encoding Variational Bayes - مقاله‌ی کلاسیک VAE و معرفی ترفند بازپارامتری‌سازی
• مقاله‌ی Ho, Jain, Abbeel (2020): Denoising Diffusion Probabilistic Models - مقاله‌ی مدل‌های DDPM و پیوند عمیق میان نمونه‌برداری و تولید تصویر