چرا نمونه گیری از توزیع گیبس سخت است؟
2/n

خب تا اینجای قصه رو پیش اومدیم که چطوری میتونیم از یک توزیع یکنواخت نمونه های شبه تصادفی تولید کنیم و بعد با استفاده از دونستن وارون تابع CDF میتونیم از یک توزیع گوسی دلخواه هم نمونه برداری کنیم ولی مشکل اینجا بود که برای بعضی از تابع توزیع ها مثل Gibbs/Boltzmann نمیتونیم این کار رو بکنیم چون خود تابع CDF مشخص نیست که چیه چه برسه به وارونش . سختی کار هم در محاسبه ضریب نرمالیزاسیون هستش که در فیزیک آماری بهش میگن partition function.

در علم آمار، Markov Chain Monte Carlo یا به طور خلاصه MCMC به دسته ای از الگوریتم ها میگن که ما اجازه میده از هر توزیع دلخواهی نمونه برداری کنیم.
اصل کار به این صورت هستش که ما میایم و یک Markov chain درست میکنیم که توزیع تعادلیش توزیع مدنظر ما باشه. بنابراین با جلو رفتن تو Markov chain ما قدم به قدم به یک نمونه از توزیع دلخواه مون آشنا تر میشیم.(اینجا قطعا کلی جزئیات ریاضیاتی هست که تضمین میکنه از هر توزیع اولیه ای برای نقطه اولیه زنجیره مون شروع کنیم با گذشت زمان اطلاعات اولیه رو فراموشش میکنیم یعنی mixing اتفاق میفته و از طرف دیگه چون فرآیندمون ergodic هست میتونیم امید ریاضی و غیره رو به راحتی حساب کنیم. من یکم سعی کرده بودم که تو این پست راجع به مفهوم mixing توضیح بدم و یک گیف هم آوردم در ادامه اش تا شاید کار رو بهتر در بیاره.)

روش های بسیار متنوع و معروفی ذیل روش های MCMC قرار میگیرن که شاید بشه گفت معروف ترینش الگوریتم Metropolis-Hastings باشه که روش بسیار جالب و زیباییه به نظرم چون به شدت وسیعه ولی متاسفانه این روش هم مثل خیلی از روش های دیگه دچار نفرین ابعاد curse of dimensionality هست و در ابعاد بالا خیلی خوب کار نمیکنه.

اما الان میخوام صرفا رو یه دسته ی خاصی از الگوریتم های MCMC هستن که بهشون میگن Langevin-based. در واقع در اینجا اون فرآیند تصادفی اصلی که پشت Markov chain هست میشه Langevin dynamics. چرا این دسته از فرآیندهای تصادفی جالبن؟‌ چون اولا دوباره خود این فرآیند به عنوان یک مدل برای توضیح حرکت ذرات کوچک در یک سیال استفاده شده اما به نظر میرسه باهاش میشه چیزهای مختلفی رو باهاش مدل کرد؛ از مکانیک کوانتوم و دینامیک مولکولی گرفته تا اقتصاد و علوم اعصاب و حتی مدل های مولد مثل diffusion.

برای اینکه بتونی از این روش استفاده بکنی حتی لازم نیست که تابع توزیعی که میخوای ازش نمونه بگیری، p(x)، رو کامل بدونی کافیه فقط گرادیان log p(x) رو بدونی. بنابراین از یک نقطه تصادفی شروع میکنی و براساس فرآیند Langevin تو هر مرحله بردارت رو بروزرسانی میکنی و در نهایت (با فرض کوچیک بودن step size) به یک نمونه از توزیع مدنظر میرسی. حالا این بروزرسانی که در واقع نسخه ی گستته سازی شده فرآیند اصلیه چطوریه؟
x_new = x_old - step_size * grad(log p(x)) + sqrt(step_size)* noise

که نمیدونم بهش دقت کردید یا نه به شدت شبیه Gradient Descent عه فقط یه نویز گوسی استاندارد هم بهش اضافه شده که این نویز قراره کمک کنه و ما رو از گیر
افتادن تو local extermum ها نجات بده.

حالا یه سری مشکلات سر راه این الگوریتم معمولا پیش میاد که یکی از اون ها مسئله ی بعد بالاست باز هم ولی یکی دیگه وقتی که ما فرآیندی داریم که به اصطلاح slowly mixing عه. یعنی نقطه هایی که کنار هم بودن در اول کار همین طوری با جلو رفتن زمان نزدیک به هم باقی میمونه و دیر فراموش میکنن(کینه شتری دارن و حافظه sheldon cooper)برای همین در این جور مواقع ما عملا گیر میکنیم.

چون که حس میکنم تا همینجاش کلی مفاهیم سخت رو به صورت متن دارم منتقل میکنم و عملا از حوصله شاید خارج شده باشم متوقف میشم و بهتون این بلاگ پست جالب رو توصیه میکنم که اگه دوست داشتید بیشتر بخونید میتونید برید و این رو بخونید و از دیدن گیف هاش لذت ببرید:
https://friedmanroy.github.io/blog/2022/Langevin/

@Singularthinker