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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

الگوریتم امید ریاضی-بیشینه‌سازی (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}} \le \log{\sum_{i=1}^k{w_it_i}}

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

\mathcal{L}(\theta) = \log{\sum_h{q(h)\frac{p(d,h;\theta)}{q(h)}}} \ge \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 را باز گردان

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

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

نمونه[ویرایش]

تاریخچه[ویرایش]

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

منابع[ویرایش]

  1. Neal, Radford; Hinton, Geoffrey (1999). Michael I. Jordan. ed. "A view of the EM algorithm that justifies incremental, sparse, and other variants". Learning in Graphical Models (Cambridge, MA: MIT Press): 355–368. ISBN 0-262-60032-3. Retrieved 2009-03-22. 
  2. 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 (Methodological) 39 (1): 1–38. جی‌استور 2984875. MR 0501537. 

پیوند به بیرون[ویرایش]