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

الگوریتم EM

معرفی‌شده توسط
Dempster, Laird & Rubin
سال
1977
نوع
Iterative optimization algorithm
خانواده
Estimation

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

اندازه قلم

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

الگوریتم امید-بیشینه‌سازی (EM) یک رویه بهینه‌سازی تکراری برای یافتن برآوردهای درست‌نمایی بیشینه یا پسین بیشینه پارامترها در مدل‌های آماری با متغیرهای پنهان یا داده‌های گمشده است. این الگوریتم که توسط دمپستر، لیرد و رابین در مقاله برجسته سال ۱۹۷۷ آنها معرفی شد، بین محاسبه امید ریاضی درست‌نمایی داده‌های کامل (گام E) و بیشینه‌سازی آن نسبت به پارامترها (گام M) متناوب عمل می‌کند و افزایش یکنواخت و غیرکاهشی درست‌نمایی را در هر تکرار تضمین می‌کند.

شهود پشت روش

تصور کنید در حال یادگیری قوانین یک بازی از طریق تماشای بازیکنانی هستید که کارت‌هایشان را نمی‌توانید ببینید. در هر دور، شما حدس می‌زنید که با توجه به آنچه مشاهده می‌کنید، احتمالاً چه کارت‌هایی در دست دارند، سپس مدل خود را از قوانین با فرض صحیح بودن آن حدس‌ها به‌روز می‌کنید. الگوریتم EM دقیقاً همین کار را انجام می‌دهد: گام E اطلاعات گمشده را با استفاده از برآوردهای پارامتر فعلی به صورت احتمالی پر می‌کند، و گام M مدل را دوباره برازش می‌دهد، گویی که آن مقادیر پر شده مشاهدات واقعی هستند.

تاریخ

این الگوریتم به طور رسمی توسط آرتور دمپستر، نان لیرد و دونالد رابین در مقاله JRSS-B سال ۱۹۷۷ آنها یکپارچه و نام‌گذاری شد، که همچنان یکی از پر استنادترین مقالات آماری منتشر شده است. این مقاله رویه‌های خاص موردی قبلی را که به طور مستقل برای مسائل خاص داده‌های گمشده توسعه یافته بودند، تعمیم داد. دهه‌های بعدی شاهد توسعه بی‌شمار افزونه‌ها از جمله الگوریتم‌های ECM، ECME، AECM و SEM بود که کاربرد را گسترش داده و همگرایی را در بسیاری از تنظیمات عملی تسریع کردند.

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

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

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

  • همگرایی به یک حداکثر محلی به جای حداکثر سراسری در مواردی که سطح درست‌نمایی چندوجهی است
  • می‌تواند همگرایی بسیار کند (خطی) را در مواردی که نسبت اطلاعات گمشده زیاد است، نشان دهد
  • نیاز به تحلیلگر برای مشخص کردن مدل داده‌های کامل و توزیع متغیرهای پنهان
  • الگوریتم EM استاندارد مستقیماً ماتریس کوواریانس داده‌های مشاهده‌شده برآوردها را ارائه نمی‌دهد؛ یک گام تکمیلی (مانند روش لویی یا الگوریتم SEM) برای خطاهای استاندارد لازم است

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

نقاط قوت

  • افزایش یکنواخت تضمین شده در درست‌نمایی داده‌های مشاهده‌شده در هر تکرار، تضمین کننده همگرایی پایدار
  • تبدیل یک مسئله دشوار داده‌های گمشده به دنباله‌ای از بهینه‌سازی‌های قابل حل داده‌های کامل
  • کاربرد گسترده در مدل‌های خانواده نمایی، مدل‌های آمیخته، و چارچوب‌های متغیر پنهان
  • به‌روزرسانی‌های گام M با فرم بسته برای بسیاری از مدل‌های استاندارد در دسترس است، که پیاده‌سازی را کارآمد می‌کند

کاربردها

  • برازش مدل‌های آمیخته گوسی برای خوشه‌بندی و برآورد چگالی
  • آموزش مدل‌های پنهان مارکوف برای تشخیص گفتار و تحلیل توالی بیولوژیکی
  • استنتاج چندگانه و تحلیل داده‌های گمشده در تحقیقات علوم بالینی و اجتماعی
  • برآورد پارامتر در تحلیل عاملی و تحلیل کلاس پنهان
  • بخش‌بندی و بازسازی تصویر در تصویربرداری پزشکی

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

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

1

قبل از شروع تکرار، تحلیلگر مقادیر اولیه را برای پارامترهای ناشناخته، که با $\theta_0$ نشان داده می‌شوند، انتخاب می‌کند. این مقادیر می‌توانند به صورت تصادفی، از یک برازش ساده‌شده، یا بر اساس دانش دامنه انتخاب شوند. کیفیت مقداردهی اولیه می‌تواند بر حداکثر محلی که الگوریتم به آن همگرا می‌شود تأثیر بگذارد، بنابراین استفاده از چندین راه‌اندازی تصادفی یک عمل رایج است.

فرمول
\text{Choose initial parameter estimates } \theta^{(0)}
2

با توجه به برآورد پارامتر فعلی $\theta_t$، گام E تابع $Q$ را محاسبه می‌کند، که امید ریاضی درست‌نمایی لگاریتمی داده‌های کامل بر روی توزیع متغیرهای پنهان مشاهده‌نشده $Z$، مشروط بر داده‌های مشاهده‌شده $X$ است. این امید ریاضی به طور مؤثری مقادیر ناشناخته را با برآوردهای احتمالی آنها جایگزین می‌کند، بدون اینکه به یک مقدار واحد تعهد کند.

فرمول
Q(\theta \mid \theta^{(t)}) = \mathbb{E}_{Z \mid X, \theta^{(t)}}[\log p(X, Z \mid \theta)]
3

گام M تابع $Q$ را از گام E نسبت به $\theta$ بیشینه می‌کند و برآورد به‌روز شده $\theta_{t+1}$ را تولید می‌کند. از آنجایی که بیشینه‌سازی درست‌نمایی لگاریتمی داده‌های کامل اغلب ساده‌تر از درست‌نمایی حاشیه‌ای داده‌های مشاهده‌شده است، این گام حتی زمانی که بیشینه‌سازی مستقیم درست‌نمایی امکان‌پذیر نباشد، اغلب قابل حل است.

فرمول
\theta^{(t+1)} = \arg\max_{\theta} \, Q(\theta \mid \theta^{(t)})
4

گام‌های E و M به صورت متناوب تکرار می‌شوند. پس از هر چرخه کامل، درست‌نمایی لگاریتمی داده‌های مشاهده‌شده ارزیابی می‌شود. تکرار زمانی متوقف می‌شود که تغییر در درست‌نمایی لگاریتمی (یا در بردار پارامتر) کمتر از یک تلرانس از پیش تعریف شده توسط کاربر، $\epsilon$، شود. دمپستر و همکاران ثابت کردند که هر چرخه نمی‌تواند درست‌نمایی داده‌های مشاهده‌شده را کاهش دهد و همگرایی پایدار را تضمین می‌کند.

فرمول
\text{Repeat E- and M-steps until } |\ell(\theta^{(t+1)}) - \ell(\theta^{(t)})| < \epsilon

دام‌های رایج

  • استفاده از یک مقداردهی اولیه تصادفی واحد، خطر توقف در یک حداکثر محلی ضعیف را دارد؛ همیشه چندین راه‌اندازی مجدد را اجرا کرده و راه‌حلی را با بالاترین درست‌نمایی نهایی انتخاب کنید
  • اعلام زودهنگام همگرایی با نظارت صرف بر تغییر پارامتر به جای درست‌نمایی داده‌های مشاهده‌شده می‌تواند منجر به برآوردهای نادرست شود
  • اعمال EM زمانی که داده‌ها به صورت غیرتصادفی گمشده (MNAR) هستند بدون تنظیم مدل می‌تواند منجر به سوگیری سیستماتیک در برآوردها شود
  • نادیده گرفتن مشکل تعویض برچسب در مدل‌های آمیخته منجر به تخصیص مولفه‌های غیرقابل تفسیر می‌شود، حتی پس از همگرایی صحیح

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

آیا الگوریتم EM همیشه به حداکثر سراسری همگرا می‌شود؟

خیر. الگوریتم EM تنها تضمین شده است که یک حداکثر محلی (یا نقطه زینی) از درست‌نمایی داده‌های مشاهده‌شده را پیدا کند. هنگامی که سطح درست‌نمایی دارای چندین مُد است، راه‌حل نهایی به مقداردهی اولیه بستگی دارد. اجرای الگوریتم از چندین نقطه شروع مختلف و حفظ راه‌حلی با بالاترین درست‌نمایی لگاریتمی، راه‌حل عملی استاندارد است.

الگوریتم EM چگونه با بهینه‌سازی مستقیم درست‌نمایی تفاوت دارد؟

حداکثر درست‌نمایی (MLE) مستقیم، درست‌نمایی لگاریتمی داده‌های مشاهده‌شده را بیشینه می‌کند، که ممکن است شامل انتگرال‌های غیرقابل حل بر روی متغیرهای پنهان باشد. الگوریتم EM با بیشینه‌سازی تکراری درست‌نمایی لگاریتمی داده‌های کامل مورد انتظار، که اغلب از نظر تحلیلی قابل حل است، از این موضوع اجتناب می‌کند. مبادله این است که الگوریتم EM ممکن است کند همگرا شود، در حالی که روش‌های مبتنی بر گرادیان می‌توانند سریع‌تر باشند، زمانی که گرادیان‌های درست‌نمایی حاشیه‌ای در دسترس باشند.

چه زمانی باید استنتاج MICE را بر الگوریتم EM ترجیح دهم؟

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

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

منابع

  1. Dempster, A. P., Laird, N. M., & Rubin, D. B. (1977). Maximum likelihood from incomplete data via the EM algorithm. Journal of the Royal Statistical Society: Series B, 39(1), 1–38.

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