الگوریتم امید ریاضی–بیشینه کردن
الگوریتم امید ریاضی-بیشینه‌سازی (EM) یک روش تکرارشونده (iterative) است که به دنبال یافتن برآوردی با بیشترین درست نمایی برای پارامترهای یک توزیع پارامتری است. این الگوریتم روش متداول برای زمانهایی است که برخی از متغیرهای تصادفی پنهان هستند.
فرض کنید که مشاهدات formula_1 را با formula_2 نمایش دهیم، متغیرهای پنهان formula_3 را با formula_4 و همهٔ پارامترهای توزیع را نیز با formula_5. در این صورت لگاریتم درست نمایی کل داده‌ها (پنهان و نمایان=مشاهدات) برابر خواهد بود با:
از آنجا که لگاریتم تابع اکیداً صعودی است، می‌توان لگاریتم درست نمایی کل داده‌ها را نسبت به formula_5 بیشینه کرد. هرچند، آرگومان لگاریتم یک مجموع است و نمی‌توان به سادگی پاسخ تحلیلی برای formula_5 یافت. از این رو، الگوریتم ب-ا ترفندی را برای بیشینه کردن "حد پایین" لگاریتم درست نمایی بکار می‌برد. این حد پایین از نابرابری ینسن بدست می‌آید. بر اساس نابرابری ینسن که از کوژ بودن تابع لگاریتم استفاده می‌کند برای هر دسته formula_9تایی از formula_10ها و formula_11ها اگر formula_12 و formula_13، خواهیم داشت:
اکنون formula_15 را به صورت زیر باز می‌نویسیم
با گزینش formula_17 نابرابری بالا تنگ می‌شود. این به معنای آن است که نابرابری به برابری تبدیل می‌شود. این گام الگوریتم همانند بیشینه کردن حدپایین درست نمایی (formula_18) نسبت به formula_19 است. در نتیجه روش کار الگوریتم امید ریاضی-بیشینه کردن به صورت زیر است:
این دیدگاه نسبت به الگوریتم امید ریاضی-بیشینه کردن متعلق به نیل و هینتون است.
بدین ترتیب در هر گام الگوریتم، حد پایین درست نمایی کل داده‌ها افزایش می‌یابد تا آنجا که در یک بیشینه محلی همگرا شود. برای رهایی از بیشینه‌های محلی، این الگوریتم را معمولاً چندین بار با شرایط آغازین متفاوت اجرا می‌کنند.
اگر formula_25 ، formula_26 داده مستقل از یک توزیع مخلوط گاوسی با بُعد formula_2 باشد و formula_28 متغیرهای پنهانِ مسئله باشد که نشان می‌دهد هر بار داده از کدام یک از توزیع‌های گاوسی آمده است، آنگاه رابطه formula_29 با formula_30 به این شکل خواهد بود (برای سادگی کار تعداد توزیع‌های مخلوط گاوسی دو در نظر گرفته شده):
formula_31 و formula_32 و formula_33 و formula_34
هدف یادگیری پارامترهای این دو توزیع و نحوه مخلوط کردن آنهاست یعنی formula_35، تابع درست نمایی برابر است با formula_36.
حال اگر مقادیر متغیرهای پنهان مشخص بود تابع درست نمایی با عبارت پایین برابر می‌شد:
formula_37
و اگر این عبارت را بسط دهیم به این معادله می‌رسیم:
formula_38
formula_39 تابع چگالی احتمال توزیع گاوس است و formula_40 تابع مشخصه است. در معادله خط قبلی برای هر formula_41 دقیقا یک تابع مشخصه یک است و دیگری صفر، یعنی دقیقا برای یکی از formula_42ها formula_43 برابر با یک خواهد بود. طبق قضیه بیز formula_44 که همان احتمال شرطی formula_45 است به این شکل محاسبه می‌شود: formula_46
همچنین تابع formula_47 الگوریتم به شکل ذیل بدست می‌آید:
formula_48
امید ریاضی formula_49 در معادله بالا نسبت به توزیع احتمال مشروط formula_50 یعنی formula_51 گرفته می شود. این احتمال برای هر formula_52 می‌تواند مقداری متفاوت داشته باشد.
formula_53
formula_54
بر طبق برآورد درست نمایی بیشنه توزیع گاوسی، مقادیر میانگین و کوواریانس را به این شکل محاسبه می‌کنیم:
formula_56 و formula_57 و formula_58 و formula_59
مراحل E و M را به‌صورت متناوب آنقدر اجرا میکنیم تا جایی که میزان افزایش تابع امید ریاضی مشروط از یک حد از پیش تعیین شده‌ای مانند formula_60 بیشتر نشود، به زبان ریاضی یعنی زمانی که نابرابری پایین صدق کند.
formula_61
این الگوریتم چندین بار به صورت جداگانه توسط افراد مختلف ابداع شده‌است. برای نمونه پیش از اینکه نام آن بیشنه کردن-امید ریاضی باشد، به نام الگوریتم باوم-ولچ شناخته می‌شد. نمونه امروزی آن را عموماً مربوط به مقاله ای در سال ۱۹۷۷ توسط دمپستر، لرد و روبین می‌دانند.