در علم آمار و فیزیک آماری، الگوریتم متروپلیس - هیستینگز ( به انگلیسی: Metropolis–Hastings algorithm ) یک روش زنجیره مارکوف مونت کارلو ( به انگلیسی: Markov chain Monte Carlo ) برای بدست آوردن ترتیبی از نمونه های تصادفی از یک توزیع احتمالی است که نمونه برداری مستقیم از آن دشوار می باشد. این ترتیب را می توان برای برآورد یک توزیع ( به عنوان مثال تولید یک هیستوگرام ) یا برای محاسبهٔ برخی انتگرال ها ( به طور مثال یک امید ریاضی ) استفاده کرد. متروپلیس - هیستینگز و دیگر الگوریتم های MCMC عموماً برای نمونه برداری از توزیع های چند بعدی استفاده می شوند، به خصوص زمانی که تعداد ابعاد بالا باشد. برای توزیع های تک بعدی معمولاً روش های دیگری وجود دارند ( به عنوان مثال نمونه گیری عدم پذیرش تطبیقی ) که می توانند به طور مستقیم نمونه های مستقل را از توزیع بازگردانند؛ معمولاً این روش ها با مشکل خودهمبستگی که در روش های MCMC به صورت ذاتی وجود دارند، رو به رو نیستند.
... [مشاهده متن کامل]
این الگوریتم به افتخار نیکلاس متروپلیس ( به انگلیسی: Nicholas Metropolis ) که در سال ۱۹۵۳ در مقاله ای با عنوان «معادلهٔ محاسبهٔ حالت به وسیلهٔ ماشین های رایانش سریع» به همراه همکارانش ( آریانا روزنبلوث ( به انگلیسی: Arianna W. Rosenbluth ) ، مارشال روزنبلوث ( به انگلیسی: Marshall N. Rosenbluth ) ، اگوستا تلر ( به انگلیسی: Augusta H. Teller ) و ادوارد تلر ( به انگلیسی: Edward Teller ) منتشر کرده است، نام گذاری شده. این مقاله الگوریتمی برای توزیع های پیشنهادی متقارن ارائه می دهد و سپس هیستینگز در سال ۱۹۷۰ الگوریتم را برای حالت های عمومی تر توسعه می دهد.
متروپولیس و اولام در سال ۱۹۴۹ برای تولید نمونه ای از یک تابع چگالی استفاده از الگوریتم متروپولیس را توسط یک تابع چگالی پیشنهادی q متقارن معرفی نمودند. متقارن بودن به این معنی است که به ازای هر x و y داشته باشیم: ( q ( x, y ) = q ( y, x. در سال ۱۹۵۳ متروپولیس و همکارانش به مطالعه بیشتر این الگوریتم پرداختند. بعدها در سال ۱۹۷۰ هیستینگز شرط متقارن بودن را حذف نمود و الگوریتم متروپلیس - هیستینگز نامیده شد. انواع دیگر این الگوریتم بر اساس ویژگی های تابع تولید کنندهٔ نمونه در سال های بعد معرفی شدند.
در مورد این که توسعهٔ این الگوریتم دقیقاً به چه کسی نسبت داده شود بحث هایی وجود دارد. متروپلیس عبارت «مونت کارلو» در این زمینه را قبل تر در مقاله ای به همراه استانیسلاو اولام استفاده کرده بوده، همچنین با بحث های محاسباتی این روش آشنا بود و گروهی را در بحث های نظری مربوط به طراحی و ساخت کامپیوتر مانیاک۱ که برای آزمایش های این روش در سال ۱۹۵۲ استفاده می شد، رهبری می کرد. هرچند تا قبل از سال ۲۰۰۳ هیچ شرح دقیقی از فرایند توسعهٔ الگوریتم وجود نداشت. در آن زمان مارشال روزنبلات، کمی قبل تر از مرگش، در کنفرانسی در سال ۲۰۰۳ در آزمایشگاه ملی لوس آلموس که برای پاس داشت پنجاهمین سالگرد انتشار مقاله برگزار شده بود، شرکت کرد و الگوریتم و فرایند توسعهٔ آن را در ارائه ای با عنوان «پیدایش الگوریتم مونت کارلو برای مکانیک آماری» شرح داد. شفاف سازی های تاریخی بعدی به وسیلهٔ گوبرناتیس در مقاله ای در سال ۲۰۰۵ انجام شد. روزنبلات به صورت شفافی بیان می کند که او و همسرش آریانا توسعهٔ الگوریتم را انجام داده اند و متروپلیس نقشی در توسعهٔ آن به جز فراهم کردن زمان کامپیوتر نداشته است.
... [مشاهده متن کامل]
این الگوریتم به افتخار نیکلاس متروپلیس ( به انگلیسی: Nicholas Metropolis ) که در سال ۱۹۵۳ در مقاله ای با عنوان «معادلهٔ محاسبهٔ حالت به وسیلهٔ ماشین های رایانش سریع» به همراه همکارانش ( آریانا روزنبلوث ( به انگلیسی: Arianna W. Rosenbluth ) ، مارشال روزنبلوث ( به انگلیسی: Marshall N. Rosenbluth ) ، اگوستا تلر ( به انگلیسی: Augusta H. Teller ) و ادوارد تلر ( به انگلیسی: Edward Teller ) منتشر کرده است، نام گذاری شده. این مقاله الگوریتمی برای توزیع های پیشنهادی متقارن ارائه می دهد و سپس هیستینگز در سال ۱۹۷۰ الگوریتم را برای حالت های عمومی تر توسعه می دهد.
متروپولیس و اولام در سال ۱۹۴۹ برای تولید نمونه ای از یک تابع چگالی استفاده از الگوریتم متروپولیس را توسط یک تابع چگالی پیشنهادی q متقارن معرفی نمودند. متقارن بودن به این معنی است که به ازای هر x و y داشته باشیم: ( q ( x, y ) = q ( y, x. در سال ۱۹۵۳ متروپولیس و همکارانش به مطالعه بیشتر این الگوریتم پرداختند. بعدها در سال ۱۹۷۰ هیستینگز شرط متقارن بودن را حذف نمود و الگوریتم متروپلیس - هیستینگز نامیده شد. انواع دیگر این الگوریتم بر اساس ویژگی های تابع تولید کنندهٔ نمونه در سال های بعد معرفی شدند.
در مورد این که توسعهٔ این الگوریتم دقیقاً به چه کسی نسبت داده شود بحث هایی وجود دارد. متروپلیس عبارت «مونت کارلو» در این زمینه را قبل تر در مقاله ای به همراه استانیسلاو اولام استفاده کرده بوده، همچنین با بحث های محاسباتی این روش آشنا بود و گروهی را در بحث های نظری مربوط به طراحی و ساخت کامپیوتر مانیاک۱ که برای آزمایش های این روش در سال ۱۹۵۲ استفاده می شد، رهبری می کرد. هرچند تا قبل از سال ۲۰۰۳ هیچ شرح دقیقی از فرایند توسعهٔ الگوریتم وجود نداشت. در آن زمان مارشال روزنبلات، کمی قبل تر از مرگش، در کنفرانسی در سال ۲۰۰۳ در آزمایشگاه ملی لوس آلموس که برای پاس داشت پنجاهمین سالگرد انتشار مقاله برگزار شده بود، شرکت کرد و الگوریتم و فرایند توسعهٔ آن را در ارائه ای با عنوان «پیدایش الگوریتم مونت کارلو برای مکانیک آماری» شرح داد. شفاف سازی های تاریخی بعدی به وسیلهٔ گوبرناتیس در مقاله ای در سال ۲۰۰۵ انجام شد. روزنبلات به صورت شفافی بیان می کند که او و همسرش آریانا توسعهٔ الگوریتم را انجام داده اند و متروپلیس نقشی در توسعهٔ آن به جز فراهم کردن زمان کامپیوتر نداشته است.
