الگوریتم امید ریاضی–بیشینه کردن

الگوریتم امید ریاضی-بیشینه‌سازی (EM) یک روش تکرارشونده (iterative) است که به دنبال یافتن برآوردی با بیشترین درست نمایی برای پارامترهای یک توزیع پارامتری است. این الگوریتم روش متداول برای زمانهایی است که برخی از متغیرهای تصادفی پنهان هستند.

شرح الگوریتم

فرض کنید که مشاهدات $x_{1},x_{2},...,x_{n}$ را با $d$ نمایش دهیم، متغیرهای پنهان $h_{1},h_{2},...,h_{n}$ را با $h$ و همهٔ پارامترهای توزیع را نیز با $\theta$. در این صورت لگاریتم درست نمایی کل داده‌ها (پنهان و نمایان=مشاهدات) برابر خواهد بود با:

${\mathcal {L}}(\theta )=\log {p(d;\theta )}=\log {\sum _{h}{p(d,h;\theta )}}$

از آنجا که لگاریتم تابع اکیداً صعودی است، می‌توان لگاریتم درست نمایی کل داده‌ها را نسبت به $\theta$ بیشینه کرد. هرچند، آرگومان لگاریتم یک مجموع است و نمی‌توان به سادگی پاسخ تحلیلی برای $\theta$ یافت. از این رو، الگوریتم ب-ا ترفندی را برای بیشینه کردن حد پایین لگاریتم درست نمایی بکار می‌برد. این حد پایین از نابرابری جنسن بدست می‌آید. بر اساس نابرابری جنسن که از کوژ بودن تابع لگاریتم استفاده می‌کند برای هر دسته $k$تایی از $t_{i}$ها و $w_{i}$ها اگر $t_{i}>0$ و $\sum {w_{i}}=1$، خواهیم داشت:

$\sum _{i=1}^{k}{w_{i}\log {t_{i}}}\leq \log {\sum _{i=1}^{k}{w_{i}t_{i}}}$

اکنون ${\mathcal {L}}$ را به صورت زیر باز می‌نویسیم

${\mathcal {L}}(\theta )=\log {\sum _{h}{q(h){\frac {p(d,h;\theta )}{q(h)}}}}\geq \sum _{h}{q(h)\log {\frac {p(d,h;\theta )}{q(h)}}}={\mathcal {J}}(q,\theta )$

با گزینش $q(h)=p(h;d,\theta )$ نابرابری بالا تنگ می‌شود. این به معنای آن است که نابرابری به برابری تبدیل می‌شود. این گام الگوریتم همانند بیشینه کردن حدپایین درست نمایی (${\mathcal {J}}$) نسبت به $q$ است. در نتیجه روش کار الگوریتم امید ریاضی-بیشینه کردن به صورت زیر است:

1. پارامترها را مقدار آغازین $\theta ^{(0)}$ می‌دهیم.
2. تا زمان همگرایی به بیشینه محلی ادامه می‌دهیم:
   1. گام-ا (مید ریاضی): $q^{(t)}=\arg \max _{q}{{\mathcal {J}}(q,\theta ^{(t)})}$
   2. گام-ب (یشینه کردن): $\theta ^{(t+1)}=\arg \max _{\theta }{{\mathcal {J}}(q^{(t)},\theta )}$
3. مقادیر نهایی $\theta$ و $q$ را باز گردان

این دیدگاه نسبت به الگوریتم امید ریاضی-بیشینه کردن متعلق به نیل و هینتون است.

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

تاریخچه

این الگوریتم چندین بار به صورت جداگانه توسط افراد مختلف ابداع شده‌است. برای نمونه پیش از اینکه نام آن بیشنه کردن-امید ریاضی باشد، به نام الگوریتم باوم-ولچ شناخته می‌شد. نمونه امروزی آن را عموماً مربوط به مقاله ای در سال ۱۹۷۷ توسط دمپستر، لرد و روبین می‌دانند.

پیوند به بیرون

• کتاب ویکی انگلیسی در این رابطه