چگونه الگوریتم متروپولیس-هیستینگز با دور زدن ریاضیات پیچیده، احتمالات درهم‌تنیده را ترسیم می‌کند

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

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

در سال ۱۹۵۳، فیزیکدانی به نام نیکلاس متروپولیس یک راه‌حل جایگزین برای توزیع‌های متقارن معرفی کرد که بعدتر در سال ۱۹۷۰ توسط آمارشناسی به نام دبلیو. کی. هیستینگز تعمیم داده شد. آن‌ها ثابت کردند که اگر تنها به احتمال نسبی دو نقطه اهمیت بدهید، این مخرج غیرممکن در واقع بی‌اهمیت است. از آنجا که مخرج در سراسر توزیع یک مقدار ثابت است، هنگام تقسیم احتمال یک حالت بر احتمال حالت دیگر، از معادله حذف می‌شود.[3][8]

همان‌طور که برایان کنگ، دانشمند داده، در تحلیل خود از این روش اشاره می‌کند، متروپولیس-هیستینگز «روشی است که به ما اجازه می‌دهد از هر توزیع احتمالی نمونه‌برداری کنیم، به شرطی که بتوانیم مقدار تابعی را که متناسب با چگالی توزیع هدف است، محاسبه کنیم.»[8]

الگوریتم با انتخاب یک نقطه شروع دلخواه در فضای پارامتر آغاز می‌شود. از آنجا، از یک «توزیع پیشنهادی» – که اغلب یک منحنی زنگوله‌ای استاندارد گاوسی با مرکزیت موقعیت فعلی است – برای پیشنهاد یک گام تصادفی به سمت یک مقدار پارامتر جدید استفاده می‌کند.[1][4]

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

اگر نسبت پذیرش بزرگتر از ۱.۰ باشد، حالت پیشنهادی قطعاً محتمل‌تر از حالت فعلی است. الگوریتم بلافاصله این حرکت را می‌پذیرد و رو به بالا به سمت مناطق متراکم‌تر توزیع هدف گام برمی‌دارد.[6]

نبوغ ریاضی متروپولیس-هیستینگز در نحوه برخورد آن با گام‌های پیشنهادی رو به پایین نهفته است. اگر نسبت پذیرش کمتر از ۱.۰ باشد – مثلاً ۰.۳ – الگوریتم به طور خودکار حرکت را رد نمی‌کند. در عوض، یک عدد تصادفی بین ۰.۰ و ۱.۰ از یک توزیع یکنواخت استخراج می‌کند.[2][6]

اگر عدد تصادفی استخراج‌شده کمتر از نسبت پذیرش (۰.۳) باشد، الگوریتم گام ضعیف‌تر را می‌پذیرد. اگر عدد استخراج‌شده بیشتر باشد، گام را رد می‌کند، در موقعیت فعلی خود باقی می‌ماند و همان موقعیت فعلی را به عنوان نمونه بعدی در زنجیره ثبت می‌کند.[1][4]

این فیلتر احتمالاتی از گیر افتادن دائمی زنجیره مارکوف روی یک قله محلی واحد جلوگیری می‌کند. با پذیرش گهگاه حرکات رو به پایین، الگوریتم کل فضای پارامتر را کاوش می‌کند. در طول ۱۰,۰۰۰ تکرار یا بیشتر، فرکانس بازدید زنجیره از هر منطقه خاص کاملاً متناسب با احتمال واقعی و زیربنایی آن منطقه می‌شود.[5][7]

کارایی این کاوش کاملاً به واریانس توزیع پیشنهادی بستگی دارد. اگر واریانس بسیار کوچک تنظیم شود، گام‌های پیشنهادی ریز خواهند بود. الگوریتم تقریباً ۱۰۰ درصد آن‌ها را می‌پذیرد، اما پیمایش یک توزیع گسترده زمان بسیار طولانی و غیرعملی خواهد برد؛ حالت شکستی که به عنوان خودهمبستگی بالا شناخته می‌شود.[3][8]

برعکس، اگر واریانس پیشنهادی بیش از حد بزرگ باشد، الگوریتم مکرراً جهش‌های وحشیانه‌ای را به سمت مناطق بایر با احتمال کم پیشنهاد می‌دهد. نسبت پذیرش برای این جهش‌ها به صفر نزدیک می‌شود و باعث می‌شود الگوریتم تقریباً همه چیز را رد کند و در جای خود متوقف شود و یک حالت را صدها بار پشت سر هم ثبت کند.[1][7]

یافتن نقطه طلایی ریاضی نیازمند تنظیم نرخ پذیرش است. برای یک توزیع هدف یک‌بعدی، نتایج نظری نشان می‌دهند که واریانس پیشنهادی بهینه به نرخ پذیرشی در حدود ۰.۴۴ دست می‌یابد.[3]

با افزایش تعداد ابعاد، این آستانه ایده‌آل کاهش می‌یابد. برای مدل‌های با ابعاد بالا با ۲۰ پارامتر یا بیشتر، نرخ پذیرش بهینه دقیقاً روی ۰.۲۳۴ همگرا می‌شود. رسیدن به این کسر خاص تضمین می‌کند که زنجیره گام‌هایی به اندازه کافی بزرگ برای کاوش برمی‌دارد، اما به اندازه کافی محتاطانه عمل می‌کند تا از رد شدن مداوم جلوگیری کند.[3][7]

حتی با تنظیم بی‌نقص، نمونه‌های اولیه در زنجیره به شدت تحت تأثیر نقطه شروع دلخواه قرار دارند. متخصصان معمولاً ۱,۰۰۰ تا ۵,۰۰۰ تکرار اول – اغلب تا ۵۰ درصد از کل اجرا – را به عنوان دوره «گرم‌شدن» دور می‌ریزند و تنها از نمونه‌های بعدی برای تحلیل نهایی خود استفاده می‌کنند.[2][4]

محدودیت اصلی متروپولیس-هیستینگز در توزیع‌های به شدت همبسته یا چندنمایی ظاهر می‌شود. اگر یک توزیع هدف دارای دو قله احتمال مجزا باشد که توسط یک دره وسیع با احتمال نزدیک به صفر از هم جدا شده‌اند، الگوریتم برای عبور از این شکاف با مشکل مواجه می‌شود.[2][6]

از آنجا که الگوریتم بر یک قدم‌زدن تصادفی تکیه دارد، احتمال پیشنهاد دنباله‌ای از گام‌ها که با موفقیت از یک دره عمیق عبور کنند، بسیار ناچیز است. زنجیره ممکن است کل اجرای خود را تنها صرف ترسیم یک قله کند و محقق را کاملاً از وجود قله دیگر بی‌خبر بگذارد.[5][8]

در مواجهه با این هندسه‌های بیمارگونه، آمارشناسان مدرن اغلب قدم‌زدن تصادفی را به طور کامل کنار می‌گذارند. در عوض، آن‌ها به سراغ انواع پیشرفته‌تری مانند مونت کارلوی همیلتونی می‌روند که گرادیان فضای احتمال را محاسبه می‌کند تا بدون تکیه بر پیشنهادهای کورکورانه، به طور موثر به سمت مناطق با چگالی بالا بلغزد.[7]