چگونه گام‌های امید ریاضی و بیشینه‌سازی برای یافتن متغیرهای پنهان به برآورد بیشینه درنمایی همگرا می‌شوند

یک فرض رایج در مدل‌سازی آماری این است که داده‌های گمشده یا متغیرهای پنهانِ مشاهده‌ناپذیر، برآورد بیشینه درنمایی (Maximum Likelihood Estimation) را غیرممکن می‌سازند و تحلیلگران را مجبور می‌کنند تا رکوردهای ناقص را دور بریزند یا وضعیت‌های پنهان را حدس بزنند. الگوریتم امید ریاضی-بیشینه‌سازی (EM) نشان می‌دهد که این فرض از نظر ریاضی نادرست است. این الگوریتم با تقسیم مسئله به دو فاز متناوب، ثابت می‌کند که مجموعه‌داده‌های ناقص همچنان می‌توانند بدون نیاز به جایگذاری‌های دلخواه، برآوردهای بهینه‌ای از پارامترها ارائه دهند.[1]

سازوکار این الگوریتم بر یک حلقه بازخورد پیوسته میان «آنچه می‌دانیم» و «آنچه فرض می‌کنیم» استوار است. وقتی یک مجموعه‌داده حاوی متغیرهای پنهان است — مانند تخصیص مشتریان به خوشه‌های جمعیتی مشاهده‌نشده یا ردیابی یک وضعیت پنهان در مدل مارکوف — محاسبه مستقیم بیشینه درنمایی بسیار دشوار و پیچیده می‌شود. تابع درنمایی به داده‌های گمشده نیاز دارد، اما تخمین داده‌های گمشده نیز خود نیازمند تابع درنمایی است.[2]

الگوریتم EM این بن‌بست را از طریق دو فاز همنام خود می‌شکند: گام امید ریاضی (E) و گام بیشینه‌سازی (M). در گام E، الگوریتم از برآوردهای فعلی و احتمالاً ناقصِ پارامترها استفاده می‌کند تا مقدار موردانتظار داده‌های گمشده را محاسبه کند. این گام یک مقدار قطعی به متغیر گمشده اختصاص نمی‌دهد؛ بلکه یک توزیع احتمال را روی تمام مقادیر ممکن محاسبه می‌کند.[1]

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

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

تضمین ریاضیاتی که باعث کارکرد این حلقه می‌شود این است که درنمایی کلی داده‌های مشاهده‌شده پس از یک چرخه EM هرگز کاهش نخواهد یافت. هر ترکیب از گام‌های E و M یا برازش مدل را بهبود می‌بخشد یا آن را بدون تغییر رها می‌کند. این افزایش یکنواخت توسط نابرابری ینسن هدایت می‌شود؛ قضیه‌ای که یک کران پایین برای لگاریتم درنمایی تعیین می‌کند که گام M آن را به سمت بالا می‌راند.

پژوهشگرانی که همگرایی این الگوریتم را در مدل‌های درخت پنهان گاوسی تحلیل کرده‌اند، دریافتند که این بهینه‌سازی کران پایین بسیار قابل‌اعتماد اما از نظر محاسباتی سنگین است. در تحلیلی که در سال ۲۰۲۰ در arXiv منتشر شد، نشان داده شد که رفتار همگرایی به‌شدت به هندسه فضای پارامترها بستگی دارد. وقتی سطح درنمایی هموار باشد، الگوریتم به‌طور پیوسته به سمت قله صعود می‌کند.[3]

با این حال، سرعت دقیق این صعود — یعنی نرخ همگرایی — توسط نسبت اطلاعات گمشده به اطلاعات کامل تعیین می‌شود. اگر یک مجموعه‌داده شامل ۱۰,۰۰۰ رکورد باشد اما ۴,۵۰۰ مورد از آن‌ها دارای متغیرهای پنهان باشند، الگوریتم برای رسیدن به آستانه همگرایی استاندارد ۰.۰۰۱ به تکرارهای بسیار بیشتری نیاز دارد تا مجموعه‌داده‌ای که تنها ۵۰۰ مقدار گمشده دارد.[2][3]

در کاربردهای عملی، مانند آموزش یک مدل مخلوط گاوسی با ۳ مؤلفه مجزا، تحلیلگران معمولاً الگوریتم را به ۱۰۰ یا ۲۰۰ تکرار محدود می‌کنند. اگر به‌روزرسانی‌های پارامتر در گام M به زیر یک تلورانس ازپیش‌تعیین‌شده — اغلب ۰.۰۰۰۱ — کاهش یابد، الگوریتم اعلام همگرایی کرده و متوقف می‌شود، با این فرض که به قله سطح درنمایی رسیده است.[1][2]

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

برای کاهش این مشکل، دانشمندان داده به‌ندرت الگوریتم EM را فقط یک بار اجرا می‌کنند. یک رویه استاندارد شامل مقداردهی اولیه الگوریتم بین ۱۰ تا ۵۰ بار با پارامترهای شروع تصادفی است که به آن اجازه می‌دهد مناطق مختلف سطح درنمایی را کاوش کند. مدل نهایی از اجرایی انتخاب می‌شود که بالاترین امتیاز کلی لگاریتم درنمایی را به دست آورد.[2]

با وجود معرفی رسمی آن در سال ۱۹۷۷، الگوریتم EM همچنان یکی از ارکان اصلی یادگیری ماشین مدرن است و پایه‌گذار تکنیک‌هایی از مدل‌های پنهان مارکوف در تشخیص گفتار تا الگوریتم‌های خوشه‌بندی مورد استفاده در بخش‌بندی مشتریان محسوب می‌شود. توانایی آن در استخراج قطعیت از اطلاعات ناقص، آن را به ابزاری ضروری در محیط‌هایی تبدیل می‌کند که به‌دست آوردن داده‌های بی‌نقص غیرممکن است.[4]