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

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

شرح الگوریتم

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

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

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

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

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

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

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

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

تاریخچه

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

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

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