موضوع مقاله: زنجیره مارکوف مونت کارلو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # زنجیره مارکوف مونت کارلو | مقدمه: در علم آمار، روش‌های زنجیره مارکف مونت کارلو (MCMC) یک کلاس از الگوریتم‌ها برای نمونه‌برداری از یک توزیع احتمالی را تشکیل می‌دهند. | ## بخش 1: زنجیره مارکوف مونت کارلو | با ساخت یک زنجیره مارکف که توزیع مطلوب را به عنوان توزیع تعادل خود دارد، می توان نمونه‌ای از توزیع مطلوب را با مشاهده زنجیره بعد از چند مرحله بدست آورد. هر چه گام‌های بیشتری وجود داشته باشد، توزیع نمونه با توزیع مطلوب واقعی مطابقت بیشتری خواهد داشت. معمولاً انتقال از یک گره‌ی زنجیره به گره‌ی دیگر با استفاده از روش‌های قدم زدن تصادفی صورت می‌گیرد. دامنه‌ی کاربردها معمول‌ترین کاربرد این الگوریتم‌ها در محاسبه‌ی عددی انتگرال‌های چندگانه است. بنابراین می‌توان گفت زنجیره‌های مارکف مونت کارلو کاربرد گسترده‌ای در این زمینه‌ها دارند. در نمونه‌گیری پدیده‌های نادر، این الگوریتم‌ها با تولید نمونه‌هایی برای پر کردن تدریجی ناحیه‌ای که نمونه‌گیری از آن شکست می‌خورد، مورد استفاده قرار می‌گیرند. زنجیره‌ی مارکف مونت کارلو تلاش می‌کند تا توزیع آبی را با توزیع نارنجی تخمین بزند. روش‌های مونت کارلو نمونه‌هایی از یک متغیر تصادفی پیوسته‌ی چند بعدی را با چگالی احتمالِ متناسب با یک تابع شناخته‌شده ایجاد می‌کنند. این نمونه‌ها را می توان برای ارزیابی انتگرال بر روی آن متغیر، به عنوان مقدار پیش‌بینی‌شده یا واریانس مورد استفاده قرار داد. | ## بخش 2: زنجیره مارکوف مونت کارلو | در عمل، معمولاً دسته‌ای از زنجیره‌ها که هر کدام از نقطه‌ای دلخواه (که معمولاً این نقاط از هم به مقدار کافی فاصله دارند) ساخته می‌شوند. این زنجیره‌ها فرآیندهای تصادفی «قدم‌زن» هستند که به طور تصادفی با توجه به الگوریتمی که به دنبال مکان‌هایی با سهم بالا در انتگرال برای حرکت به سمت نقاط بعدی است و به آن‌ها احتمالات بالاتر اختصاص می‌دهد، حرکت می‌کنند. روش‌های قدم‌زدن تصادفی مونت کارلو یک نوع شبیه‌سازی تصادفی یا روش مونت کارلو هستند. با این حال، در حالی که نمونه‌های تصادفی به کاررفته در روش‌های مونت کارلوی معمول به لحاظ آماری مستقل هستند؛ آن‌هایی که در روش‌های زنجیره‌ی مارکف مونت کارلو مورد استفاده قرار می‌گیرند، خودهمبستگی دارند. این الگوریتم‌ها زنجیره‌های مارکفی را به وجود می‌آورند که دارای یک توزیع تعادل متناسب با تابع داده شده هستند. کاهش همبستگی در حالی که روش‌های زنجیره‌ی مارکف مونت کارلو برای حل بهتر مشکلات ابعاد بالاتر نسبت به الگوریتم مونت کارلوی ساده ایجاد شدند، وقتی که تعداد ابعاد بالا می‌رود آن‌ها نیز دچار مشکل نفرین ابعاد می‌شوند. در حالتی که تعداد ابعاد بالا می‌رود، ناحیه‌‌هایی که احتمال بالاتری دارند، کش آمده و در حجم در حال گسترشی از فضایی که مشارکت زیادی در انتگرال مطلوب نمی‌کند، گم می‌شوند. یک راه برای رسیدگی به این مشکل می‌تواند کوتاه‌تر کردن گام‌های قدم‌زن باشد، به طوری که به طور مداوم سعی نکند از بالاترین ناحیه‌ی احتمالی خارج شود. هرچند این روش منجر به این خواهد شد که فرآیند، خودهمبستگی بالایی پیدا کند و تاثیر خود را از دست بدهد (به عبارت دیگر به قدم‌های زیادی برای رسیدن به یک نتیجه‌ی دقیق نیاز خواهد بود). | ## بخش 3: زنجیره مارکوف مونت کارلو | روش‌های پیچیده‌تر ضمن مدیریت فرآیند تصادفی مذکور برای ماندن در مناطقی که سهم بیشتری در انتگرال دارد، از راه‌های مختلفی برای کاهش خودهمبستگی استفاده می‌کنند. این الگوریتم‌ها معمولا به یک نظریه پیچیده‌تر تکیه می‌کنند، و اجرای آن‌ها سخت‌تر است، اما معمولا هم‌گرایی سریع‌تری (گام‌های مورد نیاز کمتری) را نشان می‌دهند. مثال‌های از زنجیره‌ی مارکف مونت کارلو مثال‌هایی از روش‌های مبتنی بر قدم‌زدن تصادفی مونت کارلو می‌تواند شامل موارد زیر باشد: الگوریتم متروپلیس هیستینگز نمونه‌گیری برشی متروپلیس چندباره جهش برگشت‌پذیر مونت کارلوی همیلتونی (یا ترکیبی) هم‌گرایی معمولاً ساخت یک زنجیره مارکف با ویژگی‌های مورد نظر دشوار نیست. مشکل دشوارتر این است که مشخص کنیم چند گام لازم است تا به توزیع پایدار با خطای قابل‌قبولی همگرا شویم. یک روش تجربی استاندارد برای ارزیابی هم‌گرایی عبارت است از اجرای چندین زنجیره مارکوف شبیه‌سازی شده‌ی مستقل و بررسی اینکه نسبت نرخ واریانس‌های پارامترهای نمونه‌گیری شده‌ی درون زنجیره‌ای به برون زنجیره‌ای به یک نزدیک باشد. به طور معمول، نمونه‌گیری از زنجیره مارکف تنها می‌تواند توزیع هدف را «تخمین» بزند، چون همیشه یک تاثیر باقی مانده از موقعیت شروع وجود دارد. الگوریتم‌های پیشرفته‌ترِ بر پایه‌ی زنجیره‌ی مارکف مونت کارلو مانند «تزویج از گذشته » می‌توانند نمونه‌های دقیق را با هزینه محاسبه‌ی اضافی و یک زمان اجرای محدود نشده (هر چند با انتظار این که این زمان اجرا متناهی باشد) تولید کنند. بسیاری از روش‌های قدم‌زدن تصادفی مونت کارلو در اطراف توزیع تعادل در گام‌های نسبتا کوچک حرکت می‌کنند و هیچ تمایلی برای قدم برداشتن پیاپی در یک مسیر ندارند. پیاده‌سازی و تجزیه و تحلیل این روش‌ها آسان است، اما متاسفانه زمان زیادی طول می‌کشد تا قدم‌زن تمام فضا را کاوش کند. | ## جمع‌بندی | قدم‌زن معمولاً دوباره بازمی‌گردد و محل‌هایی را که قبلاً پوشش داده‌بوده را دوباره قدم می‌زند.