Skip to content
بازگشت به نتایج جست‌وجو

زنجیره مارکوف مونت کارلو (MCMC) — متروپولیس-هاستینگز و نمونه‌گیری گیبس

معرفی‌شده توسط
Metropolis et al. (1953); Gibbs sampler formalised by Geman & Geman (1984)
سال
1953 (Metropolis-Hastings); 1984 (Gibbs)
نوع
Simulation-based Bayesian inference / numerical integration

این متن ترجمه ماشینی است و هنوز بازبینی نشده است. متن اصلی را به انگلیسی بخوانید

اندازه قلم

چه کاری انجام می‌دهد؟

زنجیره مارکوف مونت کارلو (MCMC) خانواده‌ای از الگوریتم‌های شبیه‌سازی است که یک زنجیره مارکوف می‌سازد که توزیع پایای آن، توزیع پسین هدف است و امکان استنتاج بیزی و محاسبه انتگرال‌های با ابعاد بالا را فراهم می‌کند که در غیر این صورت از نظر تحلیلی غیرقابل حل بودند.

MCMC که توسط متروپولیس و همکارانش در سال ۱۹۵۳ پیشگام شد و توسط هاستینگز در سال ۱۹۷۰ گسترش یافت، اساس آمار بیزی مدرن را تشکیل می‌دهد. دو متداول‌ترین انواع آن عبارتند از: متروپولیس-هاستینگز، که حرکات را از یک توزیع پیشنهادی عمومی پیشنهاد می‌کند، و نمونه‌گیری گیبس، که هر پارامتر را به نوبه خود از توزیع شرطی کامل آن می‌گیرد.

شهود پشت روش

تصور کنید می‌خواهید شکل رشته کوهی را که زیر مه پنهان شده است بدانید. شما نمی‌توانید آن را یکباره ببینید، اما می‌توانید در یک جهت تصادفی قدم بردارید و بر اساس اینکه زمین بالاتر است یا پایین‌تر، تصمیم بگیرید که حرکت کنید یا نه. با راه رفتن به اندازه کافی طولانی و ثبت مکان‌هایی که بوده‌اید، مکان‌هایی که بیشتر از همه از آن‌ها بازدید کرده‌اید، قله‌ها را ترسیم می‌کنند — این همان توزیع پسین است. MCMC همین کار را در فضای پارامتر با ابعاد بالا انجام می‌دهد: زنجیره‌ای از نمونه‌ها می‌سازد که به تدریج به مناطق با احتمال بالا سرگردان می‌شود، به طوری که هیستوگرام مقادیر بازدید شده، توزیع هدف را بدون نیاز به فرمول بسته برای آن، تقریب می‌زند.

تاریخ

الگوریتم بنیادی متروپولیس در سال ۱۹۵۳ توسط متروپولیس، روزنبلوث، روزنبلوث، تلر و تلر برای شبیه‌سازی مولکولی منتشر شد. هاستینگز (۱۹۷۰) آن را به توزیع‌های پیشنهادی نامتقارن تعمیم داد و الگوریتم متروپولیس-هاستینگز را ایجاد کرد. گمن و گمن (۱۹۸۴) نمونه‌گیری گیبس را در زمینه بازیابی تصویر معرفی کردند. این الگوریتم پس از آنکه گلفاند و اسمیت (۱۹۹۰) کاربرد گسترده آن را برای محاسبات بیزی نشان دادند، و گلمن و روبین (۱۹۹۲) تشخیص همگرایی R̂ را ارائه کردند، در اوایل دهه ۱۹۹۰ به یک ابزار آماری رایج تبدیل شد. توسعه بعدی مونت کارلو هامیلتونی توسط Duane و همکاران (۱۹۸۷) و نوع خودکار آن NUTS توسط هافمن و گلمن (۲۰۱۴) MCMC را به مسائل با ابعاد بالا گسترش داد. کتاب تحلیل داده‌های بیزی اثر گلمن و همکاران (۲۰۱۳) و راهنمای زنجیره مارکوف مونت کارلو (Brooks et al., 2011) مراجع جامع استاندارد هستند.

چه زمانی استفاده شود

MCMC ابزار مناسبی است زمانی که یک مدل بیزی مشخص شده است و توزیع پسین را نمی‌توان به صورت تحلیلی محاسبه کرد — که مورد رایج برای مدل‌های با بیش از چند پارامتر یا با توزیع‌های پیشین غیرهم‌جوش است. همچنین رویکرد استاندارد برای مدل‌های متغیر پنهان، مدل‌های سلسله مراتبی، و هر موقعیتی است که عدم قطعیت باید به طور کامل از طریق یک خط لوله پیچیده منتشر شود. هیچ فرض توزیعی در مورد داده‌ها فراتر از مشخصات درست‌نمایی مورد نیاز نیست. نیاز اصلی عملی، تعداد کافی تکرار برای همگرایی زنجیره است: کمتر از حدود ۱۰۰۰ نمونه پس از دوره گرم کردن معمولاً توصیف قابل اعتمادی از توزیع پسین ارائه نمی‌دهد، و در تنظیمات با ابعاد بالا، بسیار بیشتر لازم است. هنگامی که فضای پارامتر بسیار با ابعاد بالا است، مونت کارلو هامیلتونی (HMC) یا نمونه‌گیر بدون چرخش (NUTS) — افزونه‌های خودکار ایده MCMC — به طور قابل توجهی کارآمدتر از متروپولیس-هاستینگز پایه هستند.

محدودیت‌ها و ملاحظات

  • همگرایی در زمان محدود تضمین نمی‌شود؛ زنجیره‌ای که به نظر می‌رسد همگرا شده است ممکن است همچنان در یک منطقه محلی از توزیع پسین گیر کرده باشد.
  • همبستگی خودکار بین نمونه‌های متوالی به این معنی است که اندازه نمونه مؤثر کوچکتر از تعداد خام تکرارها است و به اجرای طولانی‌تری نسبت به نمونه مستقل معادل نیاز دارد.
  • در فضاهای پارامتر با ابعاد بالا، متروپولیس-هاستینگز با گام تصادفی به خوبی مخلوط نمی‌شود؛ مونت کارلو هامیلتونی یا NUTS برای کاوش کارآمد لازم است.
  • مشخصات مدل مستلزم آن است که تحلیلگر توزیع‌های پیشین را با دقت انتخاب کند، و توزیع‌های پیشین ضعیف انتخاب شده یا درست‌نمایی‌های نادرست مشخص شده می‌توانند توزیع پسین را به روش‌هایی که تشخیص آن‌ها دشوار است، سوگیری کنند.

شرایط منبع جایگزین بررسی علمی مستقل یا اعتبارسنجی توسط موتور تحلیل نیست.

نقاط قوت

  • امکان استنتاج بیزی دقیق (مجازی) را برای مدل‌هایی که توزیع پسین آن‌ها فرم بسته ندارد، فراهم می‌کند و مدل‌های سلسله مراتبی، مسائل داده‌های گمشده، و درست‌نمایی‌های پیچیده را پوشش می‌دهد.
  • نمونه توزیع پسین مشترک کامل را تولید می‌کند، بنابراین هر کمیت مشتق شده، پیش‌بینی، یا تصمیمی را می‌توان با عدم قطعیت منتشر شده به درستی محاسبه کرد.
  • برای نتایج پیوسته، دودویی، و شمارشی کاربرد دارد و هیچ فرض توزیعی بر داده‌ها فراتر از درست‌نمایی مشخص شده توسط مدل‌ساز اعمال نمی‌کند.
  • اجرای چندین زنجیره موازی، تأیید همگرایی را از طریق تشخیص Gelman-Rubin R̂ سیستماتیک می‌کند.

کاربردها

  • برازش مدل‌های بیزی سلسله مراتبی در روانشناسی، آموزش، و پزشکی که در آن داده‌ها گروه‌بندی شده‌اند و تجمیع جزئی مطلوب است.
  • تخمین پارامترهای مدل‌های اپیدمیولوژیکی جدولی (SIR, SEIR) از تعداد موارد مشاهده شده، از جمله کمی‌سازی عدم قطعیت.
  • مدل‌سازی معادلات ساختاری بیزی و مدل‌های متغیر پنهان در تحقیقات علوم اجتماعی.
  • استنتاج پسین برای مدل‌های نظریه پاسخ به آیتم (IRT) در اندازه‌گیری آموزشی.
  • کالیبراسیون مدل‌های شبیه‌سازی پیچیده در برابر داده‌های مشاهده شده زمانی که درست‌نمایی در دسترس است اما غیرهم‌جوش است.
  • مدل‌سازی ریسک مالی و قیمت‌گذاری اختیار معامله تحت عدم قطعیت پارامتر بیزی.

چگونه کار می‌کند

چگونه کار می‌کند

1

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

2

مقادیر اولیه برای همه پارامترها انتخاب می‌شوند و تعداد زنجیره‌ها، طول دوره گرم کردن (burn-in)، و تعداد کل تکرارهای پس از دوره گرم کردن تعیین می‌شوند. اجرای چندین زنجیره مستقل — معمولاً چهار تا — از نقاط شروع متفاوت، یک عمل استاندارد است، زیرا امکان ارزیابی همگرایی را با مقایسه زنجیره‌ها به جای تکیه بر یک مسیر واحد فراهم می‌کند.

3

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

4

پس از دور ریختن دوره گرم کردن، همگرایی ارزیابی می‌شود. آماره Gelman-Rubin R̂ واریانس درون زنجیره‌ای را به واریانس بین زنجیره‌ای در زنجیره‌های متعدد مقایسه می‌کند؛ مقادیر کمتر از ۱.۰۵ نشان می‌دهد که زنجیره‌ها مخلوط شده و به یک توزیع همگرا شده‌اند. نمودارهای ردیابی (دنباله مقادیر نمونه‌برداری شده در طول تکرارها) و اندازه نمونه مؤثر نیز بررسی می‌شوند. اگر R̂ بزرگ باشد یا نمودارهای ردیابی اختلاط ضعیفی را نشان دهند، مدل، توزیع‌های پیشین، یا تنظیمات نمونه‌گیر باید قبل از ادامه استنتاج اصلاح شوند.

5

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

دام‌های رایج

  • نادیده گرفتن یا کوتاه کردن دوره گرم کردن به این معنی است که بخش اولیه غیرپایای زنجیره، تخمین‌های پسین را آلوده می‌کند — همیشه یک دوره گرم کردن سخاوتمندانه را دور بریزید.
  • اجرای تنها یک زنجیره، تشخیص اینکه آیا نمونه‌گیر همگرا شده است یا در یک منطقه گیر کرده است را غیرممکن می‌سازد؛ همیشه حداقل چهار زنجیره مستقل اجرا کنید.
  • در نظر گرفتن تعداد زیادی تکرار خام به عنوان اثبات همگرایی بدون محاسبه R̂ یا بررسی نمودارهای ردیابی می‌تواند اطمینان کاذب ایجاد کند — R̂ < ۱.۰۵ لازم است، نه فقط تکرارهای زیاد.
  • نادیده گرفتن همبستگی خودکار و گزارش اندازه نمونه مؤثر به گونه‌ای که گویی تعداد خام است، دقت را بیش از حد تخمین می‌زند؛ اندازه نمونه مؤثر را در کنار تعداد خام گزارش دهید.
  • اعمال MCMC به مدلی با کمتر از حدود ۱۰۰۰ تکرار پس از دوره گرم کردن، به طور کلی یک توزیع پسین قابل اعتماد ارائه نمی‌دهد؛ اگر بودجه محاسباتی اینقدر محدود است، روش‌های بیزی تحلیلی یا مدل هم‌جوش را در نظر بگیرید.

پرسش‌های متداول

چگونه بدانم زنجیره MCMC من همگرا شده است؟

تشخیص اصلی، آماره Gelman-Rubin R̂ است که با اجرای حداقل چهار زنجیره مستقل از نقاط شروع متفاوت و مقایسه واریانس درون زنجیره‌ای با واریانس بین زنجیره‌ای محاسبه می‌شود. مقادیر R̂ کمتر از ۱.۰۵ برای همه پارامترها آستانه متعارف است. نمودارهای ردیابی باید نشان دهند که زنجیره‌ها همپوشانی دارند و همان منطقه را کاوش می‌کنند؛ نمودارهای قیفی شکل یا در حال حرکت، اختلاط ضعیف را نشان می‌دهند. اندازه نمونه مؤثر نیز باید بررسی شود — اندازه نمونه مؤثر بسیار کوچک نسبت به تعداد خام، همبستگی خودکار بالا را نشان می‌دهد و نیاز به تکرارهای بیشتر یا نمونه‌گیر بهتر دارد.

تفاوت بین متروپولیس-هاستینگز و نمونه‌گیری گیبس چیست؟

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

چه زمانی باید از مونت کارلو هامیلتونی به جای متروپولیس-هاستینگز استفاده کنم؟

مونت کارلو هامیلتونی (HMC) و نوع خودکار آن NUTS از اطلاعات گرادیان لگاریتم توزیع پسین برای پیشنهاد حرکات بزرگ و آگاهانه استفاده می‌کنند که با این حال با احتمال بالا پذیرفته می‌شوند. این امر آن‌ها را در فضاهای پارامتر با ابعاد بالا، که در آن پیشنهادات تصادفی تقریباً همیشه رد می‌شوند، بسیار کارآمدتر از متروپولیس-هاستینگز با گام تصادفی می‌کند. به عنوان یک قاعده عملی، اگر مدل شما بیش از ده پارامتر دارد یا اگر زنجیره‌های متروپولیس-هاستینگز اختلاط ضعیف و اندازه‌های نمونه مؤثر بسیار پایینی را نشان می‌دهند، توصیه می‌شود به HMC یا NUTS روی بیاورید.

به چند تکرار نیاز دارم؟

پاسخ جهانی وجود ندارد، اما یک نقطه شروع رایج ۱۰۰۰ تکرار گرم کردن (burn-in) به علاوه ۲۰۰۰ تکرار نمونه‌برداری در هر زنجیره، در چهار زنجیره، که در مجموع ۸۰۰۰ نمونه پس از دوره گرم کردن می‌دهد، است. کفایت این مقدار به همبستگی خودکار زنجیره و پیچیدگی توزیع پسین بستگی دارد. زنجیره زمانی کافی است که R̂ < ۱.۰۵ برای همه پارامترها و اندازه نمونه مؤثر به اندازه کافی بزرگ باشد تا ویژگی‌های پسین مورد علاقه را توصیف کند — معمولاً حداقل چند صد نمونه مؤثر برای میانگین‌ها و چند هزار برای چارک‌های دم.

روش‌های مرتبط

منابع

  1. Gelman, A., Carlin, J.B., Stern, H.S., Dunson, D.B., Vehtari, A. & Rubin, D.B. (2013). Bayesian Data Analysis (3rd ed.). Chapman & Hall/CRC.

    باز کردن مرجع DOI
    کپی شد.
  2. Brooks, S., Gelman, A., Jones, G.L. & Meng, X.-L. (Eds.) (2011). Handbook of Markov Chain Monte Carlo. Chapman & Hall/CRC.

    باز کردن مرجع DOI
    کپی شد.