الگوریتم متروپلیس‌هستینگز

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

در آمار و فیزیک آماری، الگوریتم متروپلیس-هستینگز (به انگلیسی: Metropolis–Hastings algorithm) یک متد زنجیره مارکوف مونت کارلو است که برای به دست آوردن ترتیبی از نمونه‌های تصادفی از یک توزیع احتمالی به کار می‌رود. این متد خاصا در مواردی به کار می‌رود که نمونه گیری مستقیم دشوار است. ترتیب به دست آمده را می‌توان برای تقریب گیری توزیع (تولید یک هیستوگرام) یا برای محاسبه یک انتگرال استفاده کرد. متروپلیس-هستینگز و سایر الگوریتم‌های زنجیره ماکو منتوکارلو معمولاً برای نمونه گیری از توزیع‌های چند بعدی در ابعاد زیاد، استفاده می‌شوند.[۱]

تاریخچه[ویرایش]

الگوریتم به افتخار نیکولاس متروپلیس نام گذاری شد کسی که به همراه آریانا روزنبلوث (به انگلیسی: Arianna W. Rosenbluthمارشال روزنبلوث (به انگلیسی: Marshall N. Rosenbluthاگوستا تلر (به انگلیسی: Augusta H. Teller) و ادوارد تلر {{به انگلیسی| Edward Teller) نویسنده‌ی مقاله‌ی معادله‌ی محاسبه‌ی حالت به وسیله‌ی ماشین های محاسبه گر سریع بودند.[۱]

متروپولیس و اولام در سال 1949 برای تولید نمونه ای از یک تابع چگالی استفاده از الگوریتم متروپولیس را توسط یک تابع چگالی پیشنهادی q متقارن معرفی نمودند. متقارن بودن به این معنی است که به ازای هر x و y داشته باشیم: (q(x,y) = q(y,x. در سال 1953 متروپولیس و همکاران به مطالعه بیشتر این الگوریتم پرداختند. بعدها در سال 1970 هستینگس شرط متقارن بودن را حذف نمود و اگوریتم متروپولیس- هستینگس نامیده شد. انواع دیگر این الگوریتم بر اساس ویژگی‌های تابع تولید کنندهٔ نمونه در سال‌های بعد معرفی شدند.[۲]

معرفی[۳][ویرایش]

هنگام انجام استنتاج بیزی، هدف ما محاسبه و استفاده از توزیع مشترک خلفی کامل مجموعه ای از متغیرهای تصادفی است. متأسفانه، این اغلب نیاز به محاسبه انتگرال غیرقابل حل دارد. در چنین مواردی ممکن است ما در برابر حل معادلات تحلیلی تسلیم شویم و روش نمونه گیری مبتنی بر روش زنجیره مارکوف مونت کارلو ادامه دهیم. وقتی از زنجیره مارکوف مونت کارلو استفاده می‌کنیم با استفاده از نمونه شبیه‌سازی شده از توزیع خلفی، توزیع خلفی و انتگرال‌های رام نشدنی را تخمین می‌زنیم.

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

منابع[ویرایش]

  1. ۱٫۰ ۱٫۱ *مشارکت‌کنندگان ویکی‌پدیا. «Metropolis–Hastings algorithm». در دانشنامهٔ ویکی‌پدیای انگلیسی ، بازبینی‌شده در ۵ دسامبر ۲۰۱۲.
  2. «روش پیش فرض رائو-بلکولیزه کردن الگوریتم‌های متروپلیس- هستینگز». 
  3. Yildirim، Ilker. Bayesian Inference: Metropolis-Hastings Sampling. Department of Brain and Cognitive Sciences University of Rochester، August 2012.