زنجیره مارکوف مونت کارلو
در علم آمار، روشهای زنجیره مارکف مونت کارلو (MCMC) یک کلاس از الگوریتمها برای نمونهبرداری از یک توزیع احتمالی را تشکیل میدهند. با ساخت یک زنجیره مارکف که توزیع مطلوب را به عنوان توزیع تعادل خود دارد، می توان نمونهای از توزیع مطلوب را با مشاهده زنجیره بعد از چند مرحله بدست آورد. هر چه گامهای بیشتری وجود داشته باشد، توزیع نمونه با توزیع مطلوب واقعی مطابقت بیشتری خواهد داشت. معمولاً انتقال از یک گرهي زنجیره به گرهي دیگر با استفاده از روشهای قدم زدن تصادفی صورت میگیرد.
دامنهی کاربردها
[ویرایش]معمولترین کاربرد این الگوریتمها در محاسبهی عددی انتگرالهای چندگانه است. این انتگرالها در آمار بیزی، فیزیک محاسباتی، زیستشناسی محاسباتی[۱] و زبانشناسی محاسباتی به وجود میآیند. بنابراین میتوان گفت زنجیرههای مارکف مونت کارلو کاربرد گستردهای در این زمینهها دارند.[۲]
در آمار بیزی، توسعه اخیر روشهای مونت کارلو یک گام کلیدی در محاسبه مدلهای سلسله مراتبی بزرگی بودهاست که نیازمند ترکیب صدها یا حتی هزاران پارامتر ناشناخته هستند.[۳]
در نمونهگیری پدیدههای نادر، این الگوریتمها با تولید نمونههایی برای پر کردن تدریجی ناحیهای که نمونهگیری از آن شکست میخورد، مورد استفاده قرار میگیرند.[۲]
توضیح کلی
[ویرایش]
روشهای مونت کارلو نمونههایی از یک متغیر تصادفی پیوستهي چند بعدی را با چگالی احتمالِ متناسب با یک تابع شناختهشده ایجاد میکنند. این نمونهها را می توان برای ارزیابی انتگرال بر روی آن متغیر، به عنوان مقدار پیشبینیشده یا واریانس مورد استفاده قرار داد.
در عمل، معمولاً دستهای از زنجیرهها که هر کدام از نقطهای دلخواه (که معمولاً این نقاط از هم به مقدار کافی فاصله دارند) ساخته میشوند. این زنجیرهها فرآیندهای تصادفی «قدمزن» هستند که به طور تصادفی با توجه به الگوریتمی که به دنبال مکانهایی با سهم بالا در انتگرال برای حرکت به سمت نقاط بعدی است و به آنها احتمالات بالاتر اختصاص میدهد، حرکت میکنند.[۲]
روشهای قدمزدن تصادفی مونت کارلو یک نوع شبیهسازی تصادفی یا روش مونت کارلو هستند. با این حال، در حالی که نمونههای تصادفی به کاررفته در روشهای مونت کارلوی معمول به لحاظ آماری مستقل هستند؛ آنهایی که در روشهای زنجیرهی مارکف مونت کارلو مورد استفاده قرار میگیرند، خودهمبستگی دارند.
این الگوریتمها زنجیرههای مارکفی را به وجود میآورند که دارای یک توزیع تعادل متناسب با تابع داده شده هستند.
کاهش همبستگی
[ویرایش]در حالی که روشهای زنجیرهي مارکف مونت کارلو برای حل بهتر مشکلات ابعاد بالاتر نسبت به الگوریتم مونت کارلوی ساده ایجاد شدند، وقتی که تعداد ابعاد بالا میرود آنها نیز دچار مشکل نفرین ابعاد میشوند. در حالتی که تعداد ابعاد بالا میرود، ناحیههایی که احتمال بالاتری دارند، کش آمده و در حجم در حال گسترشی از فضایی که مشارکت زیادی در انتگرال مطلوب نمیکند، گم میشوند. یک راه برای رسیدگی به این مشکل میتواند کوتاهتر کردن گامهای قدمزن باشد، به طوری که به طور مداوم سعی نکند از بالاترین ناحیهی احتمالی خارج شود. هرچند این روش منجر به این خواهد شد که فرآیند، خودهمبستگی بالایی پیدا کند و تاثیر خود را از دست بدهد (به عبارت دیگر به قدمهای زیادی برای رسیدن به یک نتیجهی دقیق نیاز خواهد بود). روشهای پیچیدهتر ضمن مدیریت فرآیند تصادفی مذکور برای ماندن در مناطقی که سهم بیشتری در انتگرال دارد، از راههای مختلفی برای کاهش خودهمبستگی استفاده میکنند. این الگوریتمها معمولا به یک نظریه پیچیدهتر تکیه میکنند، و اجرای آنها سختتر است، اما معمولا همگرایی سریعتری (گامهای مورد نیاز کمتری) را نشان میدهند.[۲]
مثالهای از زنجیرهی مارکف مونت کارلو
[ویرایش]مثالهایی از روشهای مبتنی بر قدمزدن تصادفی مونت کارلو میتواند شامل موارد زیر باشد[۲]:
- الگوریتم متروپلیس هیستینگز (به انگلیسی: Metropolis–Hastings Algorithm)
- نمونهگیری برشی (به انگلیسی: Slice Sampling)
- متروپلیس چندباره (به انگلیسی: Multiple-try Metropolis)
- جهش برگشتپذیر (به انگلیسی: Reversible-jump)
- مونت کارلوی همیلتونی (یا ترکیبی) (به انگلیسی: (Hamiltonian (or Hybrid) Monte Carlo (HMC)
همگرایی
[ویرایش]معمولاً ساخت یک زنجیره مارکف با ویژگیهای مورد نظر دشوار نیست. مشکل دشوارتر این است که مشخص کنیم چند گام لازم است تا به توزیع پایدار با خطای قابلقبولی همگرا شویم.[۴] یک زنجیره خوب زمان ترکیب سریعی دارد. به این معنی که توزیع پایدار آن به سرعت از یک موقعیت دلخواه به دست میآید. یک روش تجربی استاندارد برای ارزیابی همگرایی عبارت است از اجرای چندین زنجیره مارکوف شبیهسازی شدهی مستقل و بررسی اینکه نسبت نرخ واریانسهای پارامترهای نمونهگیری شدهی درون زنجیرهای به برون زنجیرهای به یک نزدیک باشد.[۴][۵]
به طور معمول، نمونهگیری از زنجیره مارکف تنها میتواند توزیع هدف را «تخمین» بزند، چون همیشه یک تاثیر باقی مانده از موقعیت شروع وجود دارد. الگوریتمهای پیشرفتهترِ بر پایهی زنجیرهی مارکف مونت کارلو مانند «تزویج از گذشته (به انگلیسی: Coupling from the Past)» میتوانند نمونههای دقیق را با هزینه محاسبهی اضافی و یک زمان اجرای محدود نشده (هر چند با انتظار این که این زمان اجرا متناهی باشد) تولید کنند.
بسیاری از روشهای قدمزدن تصادفی مونت کارلو در اطراف توزیع تعادل در گامهای نسبتا کوچک حرکت میکنند و هیچ تمایلی برای قدم برداشتن پیاپی در یک مسیر ندارند. پیادهسازی و تجزیه و تحلیل این روشها آسان است، اما متاسفانه زمان زیادی طول میکشد تا قدمزن تمام فضا را کاوش کند. قدمزن معمولاً دوباره بازمیگردد و محلهایی را که قبلاً پوشش دادهبوده را دوباره قدم میزند.[۲]
منابع
[ویرایش]- ↑ Gupta, Ankur; Rawlings, James B. (April 2014). "Comparison of Parameter Estimation Methods in Stochastic Chemical Kinetic Models: Examples in Systems Biology". AIChE Journal. 60 (4): 1253–1268. doi:10.1002/aic.14409. PMC 4946376. PMID 27429455.
- ↑ ۲٫۰ ۲٫۱ ۲٫۲ ۲٫۳ ۲٫۴ ۲٫۵ "Markov chain Monte Carlo". Wikipedia (به انگلیسی). 2019-06-26.
- ↑ Banerjee, Sudipto; Carlin, Bradley P.; Gelfand, Alan P. (2014-09-12). Hierarchical Modeling and Analysis for Spatial Data (Second ed.). CRC Press. p. xix. ISBN 978-1-4398-1917-3.
- ↑ ۴٫۰ ۴٫۱ Gelman, A.; Rubin, D.B. (1992). "Inference from iterative simulation using multiple sequences (with discussion)". Statistical Science. 7 (4): 457–511. Bibcode:1992StaSc...7..457G. doi:10.1214/ss/1177011136.
- ↑ Cowles, M.K.; Carlin, B.P. (1996). "Markov chain Monte Carlo convergence diagnostics: a comparative review". Journal of the American Statistical Association. 91 (434): 883–904. CiteSeerX 10.1.1.53.3445. doi:10.1080/01621459.1996.10476956.