فرایندهای تصادفی در هوش مصنوعی: از گشت تصادفی تا مدل‌های دیفیوژن

بسیاری از الگوریتم‌های پیشرفته‌ی هوش مصنوعی در محیط‌های قطعی عمل نمی‌کنند؛ تولید گام‌به‌گام متن در مدل‌های زبانی، نویززدایی تدریجی در مدل‌های دیفیوژن، اکتشاف در یادگیری تقویتی و نمونه‌گیری‌های بیزی همگی بر نوعی پویایی تصادفی اما ساختاریافته استوارند. درک این سیستم‌ها بدون تسلط بر نظریه‌ی فرایندهای تصادفی (Stochastic Processes) ناممکن است.

در این درس چهار مفهوم کلیدی را کالبدشکافی می‌کنیم: گشت‌های تصادفی، زنجیره‌های مارکوف و ویژگی بی‌حافظگی، دینامیک لانژون (ترکیب گرادیان با نویز) و الگوریتم‌های MCMC نظیر متروپولیس-هیستینگز. پیوند مستقیم این مفاهیم با سازوکار مدل‌های زبانی بزرگ و مدل‌های دیفیوژن مدرن، تصویر روشنی از چگونگی عملکرد تولید داده در هوش مصنوعی به شما می‌دهد.

تمام کدهای شبیه‌سازی این آموزش با کتابخانه‌های استاندارد محاسباتی نظیر NumPy و بر روی CPU سیستم شخصی قابل پیاده‌سازی و اجرا هستند و برای یادگیری آن‌ها به هیچ سخت‌افزار ابری یا دسترسی خاصی نیاز ندارید.

تصادفی بودنِ ساختاریافته: ریاضیات گشت‌های تصادفی، زنجیره‌های مارکوف و مدل‌های دیفیوژن.

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

• شبیه‌سازی گشت‌های تصادفی 1بعدی و 2بعدی و بررسی رفتار مقیاس‌پذیری جابه‌جایی با $\sqrt{n}$
• ساخت شبیه‌ساز زنجیره مارکوف و محاسبه‌ی توزیع ایستا (stationary distribution) از طریق تجزیه ویژه (eigendecomposition)
• پیاده‌سازی MCMC متروپولیس-هیستینگز (Metropolis-Hastings) و دینامیک لانژون (Langevin dynamics) برای نمونه‌گیری از توزیع‌های هدف
• پیوند دادن فرایند رفتِ دیفیوژن (forward diffusion) به حرکت براونی و تبیین نحوه‌ی تولید داده در فرایند برگشت (reverse process)

صورت مسئله

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

مدل‌های زبانی توکن‌ها را یکی‌یکی تولید می‌کنند. هر توکن به زمینه‌ی قبلی وابسته است. مدل یک توزیع احتمال خروجی می‌دهد، از آن نمونه‌گیری می‌کند و پیش می‌رود. این دقیقاً یک فرایند تصادفی (stochastic process) است.

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

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

نمونه‌گیری MCMC که ستون فقرات استنتاج بیزی (Bayesian inference) به شمار می‌رود، زنجیره مارکوفی می‌سازد که توزیع ایستای آن همان پسینِ (posterior) مورد نظر برای نمونه‌گیری است.

همه‌ی این موارد بر چهار ایده‌ی بنیادین بنا شده‌اند:

1. گشت‌های تصادفی (Random walks) — ساده‌ترین فرایند تصادفی
2. زنجیره‌های مارکوف (Markov chains) — تصادفی بودن ساختاریافته همراه با ماتریس انتقال
3. دینامیک لانژون (Langevin dynamics) — نزول گرادیان به همراه نویز
4. متروپولیس-هیستینگز (Metropolis-Hastings) — نمونه‌گیری از هر توزیع دلخواه

مفاهیم پایه

گشت‌های تصادفی

از موقعیت 0 آغاز کنید. در هر گام، سکه‌ای سالم بیندازید. اگر شیر آمد به راست بروید (+1) و اگر خط آمد به چپ (-1).

پس از $n$ گام، موقعیت شما حاصل جمع $n$ مقدار تصادفیِ $\pm 1$ خواهد بود. امید ریاضیِ موقعیت برابر با 0 است (گشت نااریب است). اما فاصله‌ی مورد انتظار از مبدأ با ضریب $\sqrt{n}$ رشد می‌کند.

این نتیجه خلاف شهود به نظر می‌رسد. گشت کاملاً منصفانه است و هیچ رانشی به هیچ سمتی وجود ندارد. با این حال با گذشت زمان، متحرک دور و دورتر از نقطه‌ی شروع پرسه می‌زند. انحراف معیار پس از $n$ گام برابر با $\sqrt{n}$ است.

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

در فضای 2بعدی، گام‌ها با احتمالی برابر به بالا، پایین، چپ یا راست برداشته می‌شوند. همان نرخ مقیاس‌پذیریِ $\sqrt{n}$ برای فاصله از مبدأ نیز برقرار است. مسیر طی‌شده الگویی شبیه به فرکتال پدید می‌آورد.

چرا $\sqrt{n}$؟ هر گام با احتمال برابر +1 یا -1 است. پس از $n$ گام، موقعیت برابر است با $S_n = X_1 + X_2 + \cdots + X_n$ که در آن هر $X_i$ متغیری با مشخصه‌ی $\pm 1$ است. واریانس هر گام برابر با 1 بوده و گام‌ها مستقل از یکدیگرند؛ در نتیجه $\mathop{\mathrm{Var}}(S_n) = n$. انحراف معیار = $\sqrt{n}$. بر اساس قضیه حد مرکزی، $S_n / \sqrt{n}$ به یک توزیع نرمال استاندارد همگرا می‌شود.

این مقیاس‌پذیریِ $\sqrt{n}$ در سراسر یادگیری ماشین به چشم می‌خورد. نویز SGD با نسبت 1/sqrt(batch_size) مقیاس می‌گیرد. ابعاد امبدینگ با $\sqrt{d}$ مقیاس پیدا می‌کند. جذر گرفتن، امضای جمع زدنِ متغیرهای تصادفی مستقل است.

ارتباط با حرکت براونی. گشت تصادفی‌ای را با اندازه‌ی گام $1/\sqrt{n}$ و تعداد $n$ گام در واحد زمان در نظر بگیرید. وقتی $n$ به سمت بی‌نهایت میل می‌کند، گشت به حرکت براونی (Brownian motion) یا همان $B(t)$ همگرا می‌شود — فرایندی پیوسته در زمان که در آن $B(t)$ توزیع نرمالی با میانگین 0 و واریانس $t$ دارد.

حرکت براونی شالوده‌ی ریاضی پدیده‌ی دیفیوژن است. این مفهوم لرزش تصادفی ذرات در سیال، نوسانات قیمت سهام و — از همه مهم‌تر — فرایند نویز در مدل‌های دیفیوژن را مدل‌سازی می‌کند.

مسئله‌ی ورشکستگی قمارباز (Gambler's ruin). متحرکی با گشت تصادفی را در نظر بگیرید که از موقعیت $k$ شروع می‌کند و مرزهای جذب‌کننده در نقاط 0 و $N$ قرار دارند. احتمال رسیدن به $N$ پیش از رسیدن به 0 چقدر است؟ برای گشتی منصفانه این احتمال برابر است با: $P(\text{reach } N) = k/N$. این رابطه به‌طرز شگفت‌انگیزی ساده و زیباست و به نظریه‌ی مارتینگل‌ها (martingales) پیوند می‌خورد — گشت تصادفیِ منصفانه یک مارتینگل است (امید ریاضی مقدار آینده = مقدار فعلی).

زنجیره‌های مارکوف

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

$$P(X_{t+1} = j \mid X_t = i, X_{t-1} = \ldots) = P(X_{t+1} = j \mid X_t = i)$$

به این ویژگی، خاصیت مارکوف می‌گویند. به این معنی که می‌توانید پویایی کل سیستم را با یک ماتریس انتقال (transition matrix) به نام $P$ توصیف کنید:

$$P[i][j] = \text{probability of going from state } i \text{ to state } j$$

مجموع مقادیر هر سطر از $P$ برابر با 1 است (بالاخره سیستم باید به حالتی برود).

مثال — وضعیت آب‌وهوا:

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

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

از هر حالتی شروع کنید. پس از گذشت چندین انتقال، توزیع حالت‌ها به توزیع ایستا یعنی $\pi$ همگرا می‌شود، جایی که $\pi P = \pi$. این بردار، بردار ویژه چپِ (left eigenvector) ماتریس $P$ با مقدار ویژه 1 است.

در این زنجیره‌ی آب‌وهوا، توزیع ایستا برابر با [0.55, 0.18, 0.27] است؛ یعنی در بلندمدت و فارغ از اینکه کار از چه حالتی آغاز شده باشد، هوا در 55% مواقع آفتابی خواهد بود.

محاسبه‌ی توزیع ایستا. برای این کار دو رویکرد وجود دارد:

1. روش توان (Power method): هر توزیع اولیه‌ای را به‌طور متوالی در $P$ ضرب کنید. پس از تکرارهای کافی، همگرا می‌شود.
2. روش مقدار ویژه (Eigenvalue method): پیدا کردن بردار ویژه چپِ $P$ با مقدار ویژه 1. این معادل با بردار ویژه $P^T$ با مقدار ویژه 1 است.

هر دو رویکرد مستلزم برقراری شرایط همگرایی در زنجیره هستند.

شرایط همگرایی. زنجیره مارکوف به توزیع ایستای یکتایی همگرا می‌شود اگر:

• تحویل‌ناپذیر (Irreducible) باشد: از هر حالتی بتوان به هر حالت دیگری رسید.
• غیردوره‌ای (Aperiodic) باشد: زنجیره در چرخه‌هایی با دوره‌ی زمانی ثابت گرفتار نشود.

بیشتر زنجیره‌هایی که در یادگیری ماشین با آن‌ها روبه‌رو می‌شوید، هر دو شرط را دارند.

حالت‌های جذب‌کننده (Absorbing states). اگر پس از ورود به یک حالت دیگر نتوانید از آن خارج شوید، آن حالت جذب‌کننده است ($P[i][i] = 1$). زنجیره‌های مارکوف جذب‌کننده، فرایندهایی با حالت‌های پایانی را مدل‌سازی می‌کنند؛ مثل بازی‌ای که تمام می‌شود، کاربری که ریزش می‌کند (churn)، یا توالی توکن‌هایی که به توکن پایان متن (end-of-text) می‌رسد.

زمان آمیختگی (Mixing time). چند گام طول می‌کشد تا زنجیره به توزیع ایستا «نزدیک» شود؟ به بیان دقیق‌تر، تعداد گام‌هایی که لازم است تا فاصله‌ی تغییرات کل (total variation distance) از حالت پایا به زیر آستانه‌ای مشخص برسد. آمیختگی سریع یعنی نیاز به گام‌های کمتر. برای زنجیره‌ای برگشت‌پذیر، شکاف طیفی (spectral gap) ماتریس $P$ (که برابر است با 1 منهای بزرگ‌ترین اندازه‌ی مقادیر ویژه، به‌جز مقدار ویژه 1) زمان آمیختگی را کنترل می‌کند. شکاف بزرگ‌تر یعنی آمیختگی سریع‌تر.

ارتباط با مدل‌های زبانی

فرایند تولید توکن در مدل‌های زبانی تقریباً یک فرایند مارکوف است. مدل با در نظر گرفتن زمینه‌ی فعلی، توزیعی روی توکن بعدی خروجی می‌دهد. پارامتر دما (temperature) میزان تیزی و تمرکز این توزیع را تنظیم می‌کند:

$$P(\text{token}_i) = \frac{\exp(\text{logit}_i / \text{temperature})}{\sum_j \exp(\text{logit}_j / \text{temperature})}$$

• دما = 1.0: توزیع استاندارد
• دما < 1.0: تیزتر (بیشتر قطعی)
• دما > 1.0: تخت‌تر (بیشتر تصادفی)
• دما $\to 0$: حالت حریصانه یا argmax

روش نمونه‌گیری Top-k انتخاب را به $k$ توکن با بیشترین احتمال محدود می‌کند. نمونه‌گیری Top-p (یا nucleus) انتخاب را به کوچک‌ترین مجموعه‌ای از توکن‌ها محدود می‌کند که مجموع احتمال آن‌ها از $p$ فراتر رود. هر دو روش احتمال‌های انتقال مارکوف را تغییر می‌دهند.

حرکت براونی

حد پیوسته در زمانِ گشت تصادفی. متغیر مکان $B(t)$ دارای سه ویژگی است:

1. $B(0) = 0$
2. نمو $B(t) - B(s)$ دارای توزیع نرمال با میانگین 0 و واریانس $t - s$ است (به ازای $t > s$)
3. نموها در بازه‌های بدون همپوشانی، مستقل از یکدیگرند

حرکت براونی پیوسته است اما در هیچ نقطه‌ای مشتق‌پذیر نیست؛ یعنی در تمام مقیاس‌ها لرزش و نوسان دارد. این مسیر در صفحه دارای بُعد فرکتالی 2 است.

در شبیه‌سازی گسسته، حرکت براونی را با این رابطه تقریب می‌زنید:

$$B(t + dt) = B(t) + \sqrt{dt} \, z, \quad \text{where } z \sim \mathcal{N}(0, 1)$$

ضریب مقیاس $\sqrt{dt}$ اهمیت بالایی دارد و حاصل اعمال قضیه حد مرکزی بر گشت‌های تصادفی است.

دینامیک لانژون

نزول گرادیان کمینه‌ی یک تابع را می‌یابد. دینامیک لانژون در پی یافتن توزیع احتمال متناسب با $\exp(-U(x)/T)$ است؛ جایی که $U$ تابع انرژی و $T$ دما است.

$$x_{t+1} = x_t - dt \, \nabla U(x_t) + \sqrt{2 T \, dt} \, z_t$$

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

1. نیروی گرادیان ($-dt \cdot \nabla U$): ذره را به سمت انرژی کمتر می‌راند (درست مثل نزول گرادیان)
2. نیروی تصادفی ($\sqrt{2T dt} \cdot z$): ذره را در جهت‌های تصادفی می‌راند (اکتشاف)

در دمای $T = 0$، این فرایند نزول گرادیان خالص است. در دماهای بالا، تقریباً شبیه یک گشت تصادفی عمل می‌کند. در دمای مناسب، ذره چشم‌انداز انرژی را کاوش کرده و بیشتر وقت خود را در نواحی با انرژی پایین سپری می‌کند.

ارتباط با مدل‌های دیفیوژن. فرایند رفت در مدل دیفیوژن به این صورت است:

$$x_t = \sqrt{\alpha_t} \, x_{t-1} + \sqrt{1 - \alpha_t} \cdot \text{noise}$$

این سازوکار یک زنجیره مارکوف است که داده را به‌تدریج با نویز می‌آمیزد. پس از گام‌های کافی، $x_T$ تبدیل به نویز گاوسی خالص می‌شود.

فرایند برگشت — یعنی بازگشت از نویز به داده — نیز یک زنجیره مارکوف است، منتها با این تفاوت که احتمال‌های انتقال آن را یک شبکه عصبی یاد می‌گیرد. شبکه یاد می‌گیرد نویزی را که در هر گام اضافه شده پیش‌بینی کرده و سپس آن را کم کند.

روش MCMC: مونت‌کارلو با زنجیره مارکوف

گاهی اوقات نیاز دارید از توزیعی مثل $p(x)$ نمونه‌گیری کنید که مقدار آن را (تا ضریبی ثابت) می‌توانید محاسبه کنید، اما امکان نمونه‌گیری مستقیم از آن را ندارید. توزیع‌های پسین بیزی نمونه‌ای کلاسیک از این دست هستند؛ حاصل‌ضرب درست‌نمایی در پیشین را در اختیار دارید، اما محاسبه‌ی ثابت نرمال‌سازی عملاً امکان‌پذیر نیست.

الگوریتم متروپولیس-هیستینگز زنجیره مارکوفی می‌سازد که توزیع ایستای آن همان $p(x)$ است:

1. از یک موقعیت اولیه مانند $x$ شروع کنید.
2. موقعیت جدید $x'$ را بر اساس یک توزیع پیشنهادی (proposal distribution) به نام $Q(x' \mid x)$ پیشنهاد دهید.
3. نسبت پذیرش (acceptance ratio) را حساب کنید: $a = p(x') Q(x \mid x') / (p(x) Q(x' \mid x))$
4. موقعیت جدید $x'$ را با احتمال $\min(1, a)$ بپذیرید؛ در غیر این صورت در $x$ باقی بمانید.
5. این فرایند را تکرار کنید.

اگر توزیع $Q$ متقارن باشد (مثلاً $Q(x' \mid x) = Q(x \mid x') = \mathcal{N}(x, \sigma^2){}$)، نسبت مذکور ساده شده و به $a = p(x') / p(x)$ تبدیل می‌شود. شما فقط به نسبت احتمال‌ها نیاز دارید؛ ضریب نرمال‌سازی ساده شده و خط می‌خورد.

تحت شرایطی نه‌چندان سخت‌گیرانه، همگرایی زنجیره به $p(x)$ تضمین می‌شود. اما اگر گام‌های پیشنهادی خیلی کوچک باشد (گشت تصادفی) یا خیلی بزرگ باشد (نرخ رد شدن بالا)، همگرایی می‌تواند بسیار کند شود. تنظیم این توزیع پیشنهادی، هنر اصلی در MCMC است.

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

نکات کاربردی در عمل:

• دوره گرم‌کردن (Burn-in): اولین $N$ نمونه را دور بریزید. زنجیره نیاز به زمان دارد تا از نقطه‌ی شروع خود به توزیع ایستا برسد.
• تُنُک‌سازی (Thinning): برای کاهش خودهمبستگی (autocorrelation)، فقط هر $k$مین نمونه را نگه دارید.
• زنجیره‌های چندگانه: چندین زنجیره را از نقاط شروع گوناگون اجرا کنید. اگر همگی به توزیعی یکسان همگرا شدند، نشانه‌ی خوبی از وقوع همگرایی است.
• نرخ پذیرش: برای توزیع‌های پیشنهادی گاوسی در ابعاد $d$، نرخ پذیرش بهینه حدود 23% است (Roberts & Rosenthal, 2001). نرخ پذیرشِ بسیار بالا یعنی زنجیره تغییر موقعیت چندانی ندارد و نرخ بسیار پایین یعنی مدام در حال رد کردن پیشنهادهاست.

فرایندهای تصادفی در هوش مصنوعی

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

گام 1: شبیه‌ساز گشت تصادفی

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

گشت 1بعدی مجموع‌های تجمعی را ذخیره می‌کند. هر گام یا +1 است یا -1. پس از $n$ گام، موقعیت نهایی حاصل جمع این مقادیر خواهد بود. واریانس به‌صورت خطی با $n$ رشد می‌کند، بنابراین انحراف معیار با $\sqrt{n}$ افزایش می‌یابد.

گام 2: زنجیره مارکوف

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)

توزیع ایستا، بردار ویژه چپِ ماتریس $P$ متناظر با مقدار ویژه 1 است. این بردار را با محاسبه‌ی مقادیر ویژه $P^T$ پیدا می‌کنیم (ترانهادن، بردارهای ویژه چپ را به بردارهای ویژه راست تبدیل می‌کند).

گام 3: دینامیک لانژون

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)

گرادیان، متغیر $x$ را به سمت انرژی پایین می‌راند؛ نویز هم مانع از گیر افتادن آن می‌شود. در حالت تعادل، توزیع نمونه‌ها متناسب با $\exp(-U(x)/\text{temperature})$ خواهد بود.

گام 4: متروپولیس-هیستینگز

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

این الگوریتم نقطه‌ای جدید پیشنهاد می‌دهد، احتمالِ بیشتر آن را بررسی می‌کند (یا با احتمالی متناسب با نسبت، آن را می‌پذیرد) و سپس تکرار می‌شود. برای دستیابی به آمیختگی مطلوب، نرخ پذیرش باید بین 23 تا 50 درصد باشد.

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

در عمل برای اجرای این الگوریتم‌ها از کتابخانه‌های شناخته‌شده استفاده می‌کنید، اما درک سازوکار درونی آن‌ها برای دیباگ و تنظیم دقیق پارامترها حیاتی است.

import numpy as np

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

کتابخانه‌ی numpy برای ماتریس‌های انتقال

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

توزیع اولیه را به‌طور پیاپی در $P$ ضرب کنید. پس از تکرارهای کافی و بدون توجه به اینکه از کجا شروع کرده‌اید، توزیع به حالت ایستا همگرا می‌شود. این همان روش توان برای پیدا کردن بردار ویژه چپِ مسلط است.

ارتباط با فریم‌ورک‌های دنیای واقعی

• دیفیوژن در PyTorch: کلاس DDPMScheduler در کتابخانه‌ی diffusers متعلق به Hugging Face زنجیره‌های مارکوف رفت و برگشت را پیاده‌سازی می‌کند.
• NumPyro / PyMC: استفاده از MCMC (نمونه‌گیر NUTS که نسخه‌ی ارتقایافته‌ی متروپولیس-هیستینگز است) برای استنتاج بیزی.
• Gymnasium (در یادگیری تقویتی): تابع step در محیط، یک فرایند تصمیم‌گیری مارکوف را تعریف می‌کند.

اعتبارسنجی همگرایی در زنجیره مارکوف

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

شکاف طیفی نشان می‌دهد زنجیره با چه سرعتی حالت اولیه‌ی خود را فراموش می‌کند. شکافی معادل 0.2 یعنی تقریباً 5 گام برای آمیختگی کافی است، اما شکاف 0.01 به حدود 100 گام نیاز دارد. پیش از اجرای شبیه‌سازی‌های طولانی حتماً این موضوع را بررسی کنید؛ زنجیره‌ای با آمیختگی کُند منابع پردازشی شما را هدر می‌دهد.

خروجی این درس

از این درس خروجی زیر حاصل می‌شود:

• فایل outputs/prompt-stochastic-process-advisor.md — پرامپتی که در تشخیص چارچوب مناسبِ فرایندهای تصادفی برای مسائل مختلف به شما کمک می‌کند.

پیوندها

مدل‌های دیفیوژن سزاوار توجه ویژه‌ای هستند. مقاله‌ی DDPM (Ho et al., 2020) یک زنجیره مارکوف رفت را تعریف می‌کند:

$$q(x_t \mid x_{t-1}) = \mathcal{N}\left(x_t; \sqrt{1-\beta_t} \, x_{t-1}, \beta_t I\right)$$

که در آن $\beta_t$ همان زمان‌بندی نویز است. پس از $T$ گام، مقدار $x_T$ تقریباً معادل $\mathcal{N}(0, I)$ خواهد بود. فرایند برگشت به‌کمک یک شبکه عصبی پارامتریزه می‌شود که وظیفه‌ی پیش‌بینی نویز را بر عهده دارد:

$$p_\theta(x_{t-1} \mid x_t) = \mathcal{N}\left(x_{t-1}; \mu_\theta(x_t, t), \sigma_t^2 I\right)$$

هر گام از فرایند تولید داده، در واقع گامی در یک زنجیره مارکوف آموزش‌دیده است. درک عمیق زنجیره‌های مارکوف یعنی درک چگونگی و چرایی تولید داده توسط مدل‌های دیفیوژن.

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

بینش کلیدی نهفته در میان تمام این پیوندها این است: فرایندهای تصادفی صرفاً ابزارهایی تئوریک نیستند، بلکه سازوکارهای محاسباتی در بطن سیستم‌های مدرن هوش مصنوعی‌اند. با تنظیم دمای یک مدل زبانی، زنجیره مارکوف را دستکاری می‌کنید. با آموزش یک مدل دیفیوژن، در عمل شیوه‌ی معکوس کردن فرایندی شبهِ حرکت براونی را یاد می‌گیرید. هنگامی هم که دست به استنتاج بیزی می‌زنید، در حال ساخت زنجیره‌ای هستید که به توزیع پسین همگرا می‌شود.

تمرین‌ها

1. شبیه‌سازی 1000 گشت تصادفی با 10000 گام. توزیع موقعیت‌های پایانی را رسم کنید. نشان دهید این توزیع تقریباً گاوسی با میانگین 0 و انحراف معیار $\sqrt{10000} = 100$ است.

2. ساخت تولیدکننده‌ی متن با استفاده از زنجیره مارکوف. مدلی را با یک پیکره متنی کوچک آموزش دهید: برای هر کلمه، تعداد دفعات انتقال به کلمه‌ی بعدی را بشمارید. ماتریس انتقال را بسازید. با نمونه‌گیری از این زنجیره، جملات جدید تولید کنید.

3. پیاده‌سازی تبرید شبیه‌سازی‌شده (Simulated Annealing) با استفاده از متروپولیس-هیستینگز. کار را با دمای بالا آغاز کنید (پذیرش تقریباً تمامی گزینه‌ها) و به‌تدریج سیستم را خنک کنید (پذیرش فقط مواردی که وضعیت را بهبود می‌دهند). از این روش برای یافتن کمینه‌ی تابعی با چندین کمینه محلی استفاده کنید.

4. مقایسه‌ی دینامیک لانژون در دماهای مختلف. از یک پتانسیل دوچاهی $U(x) = (x^2 - 1)^2$ نمونه‌گیری کنید. در دمای پایین، نمونه‌ها درون یکی از چاه‌ها خوشه می‌شوند. در دمای بالا، در میان هر دو چاه پراکنده می‌شوند. دمای بحرانی را که در آن زنجیره میان دو چاه آمیخته می‌شود پیدا کنید.

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

راهنمایی‌ها

تمرین 1. تابع random_walk_1d(10000, seed=i) را برای 1000 سید مختلف فراخوانی کرده و موقعیت نهایی هر اجرا را ثبت کنید. بررسی کنید که میانگین نزدیک به 0، انحراف معیار نزدیک به 100 و حدود 68% از موقعیت‌های پایانی در بازه‌ی بین -100 و 100 باشند.

تمرین 2. هر جفت‌کلمه را بشمارید، سپس مقادیر هر سطر را بر مجموع آن سطر تقسیم کنید تا جمع هر سطر برابر با 1 شود. ماتریس نهایی را به MarkovChain(transition_matrix, state_names) بفرستید و متد simulate را فراخوانی کنید. بررسی کنید که تمام جفت‌کلمات متن خروجی، در پیکره متنی اولیه نیز آمده باشند.

تمرین 3. نقطه‌ای با وضعیت بدتر را با احتمال $\exp(-\Delta / T)$ بپذیرید و پس از هر گام، پارامتر $T$ را در ضریبی مثل 0.99 ضرب کنید. الگوریتم را روی تابعی بیازمایید که کمینه‌ی آن را از پیش می‌دانید و پاسخ خود را با جست‌وجوی شبکه‌ای ریزدانه (fine grid search) مقایسه کنید.

تمرین 4. گرادیان برابر است با $4x(x^2 - 1)$. این مقدار را به تابع langevin_dynamics(grad_U, x0, dt, temperature, n_steps) بدهید. سد پتانسیل در $x = 0$ ارتفاعی برابر با 1 دارد؛ بنابراین بسامد تغییر علامت $x$ را برای دماهایی در بازه‌ی 0.05 تا 1 بشمارید و به دنبال دمایی بگردید که این تعداد شروع به رشد سریع می‌کند.

تمرین 5. تابع diffusion_forward(signal, 100) را فراخوانی کنید و مقدار $\bar{\alpha}$ را در گام آخر به‌صورت حاصل‌ضرب مقادیر $(1 - \beta_t)$ به دست آورید. اگر $\bar{\alpha}$ فاصله‌ی زیادی با 0 دارد یعنی سیگنال هنوز به نویز خالص تبدیل نشده؛ در این حالت مقدار beta_end را افزایش دهید. نویززدای خود را ابتدا با نویز واقعی تست کنید؛ در این حالت مقدار $(x_t - \sqrt{1 - \bar{\alpha}_t} \epsilon)/\sqrt{\bar{\alpha}_t}$ باید دقیقاً سیگنال اولیه را بازسازی کند.

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

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

• Ho, Jain, Abbeel (2020) -- "Denoising Diffusion Probabilistic Models." مقاله‌ی بنیادین DDPM که تحول مدل‌های دیفیوژن را آغاز کرد؛ حاوی محاسبات ریاضیاتی شفاف برای زنجیره‌های مارکوف در فرایندهای رفت و برگشت.
• Song & Ermon (2019) -- "Generative Modeling by Estimating Gradients of the Data Distribution." رویکرد مبتنی بر امتیاز که از دینامیک لانژون برای نمونه‌گیری استفاده می‌کند.
• Roberts & Rosenthal (2004) -- "General state space Markov chains and MCMC algorithms." نظریه‌ای درباره‌ی زمان و چرایی کارکرد الگوریتم‌های MCMC.
• Norris (1997) -- "Markov Chains." کتاب مرجع استاندارد؛ پوشش مباحث همگرایی، توزیع‌های ایستا و زمان‌های برخورد (hitting times).
• Welling & Teh (2011) -- "Bayesian Learning via Stochastic Gradient Langevin Dynamics." ترکیب SGD با دینامیک لانژون برای پیاده‌سازی استنتاج بیزی مقیاس‌پذیر.