الگوریتم امید ریاضی–بیشینه کردن
الگوریتم امید ریاضی-بیشینهسازی (EM) یک روش تکرارشونده (iterative) است که به دنبال یافتن برآوردی با بیشترین درست نمایی برای پارامترهای یک توزیع پارامتری است. این الگوریتم روش متداول برای زمانهایی است که برخی از متغیرهای تصادفی پنهان هستند.
شرح الگوریتم[ویرایش]
فرض کنید که مشاهدات را با نمایش دهیم، متغیرهای پنهان را با و همهٔ پارامترهای توزیع را نیز با . در این صورت لگاریتم درست نمایی کل دادهها (پنهان و نمایان=مشاهدات) برابر خواهد بود با:
از آنجا که لگاریتم تابع اکیداً صعودی است، میتوان لگاریتم درست نمایی کل دادهها را نسبت به بیشینه کرد. هرچند، آرگومان لگاریتم یک مجموع است و نمیتوان به سادگی پاسخ تحلیلی برای یافت. از این رو، الگوریتم ب-ا ترفندی را برای بیشینه کردن حد پایین لگاریتم درست نمایی بکار میبرد. این حد پایین از نابرابری جنسن بدست میآید. بر اساس نابرابری جنسن که از کوژ بودن تابع لگاریتم استفاده میکند برای هر دسته تایی از ها و ها اگر و ، خواهیم داشت:
اکنون را به صورت زیر باز مینویسیم
با گزینش نابرابری بالا تنگ میشود. این به معنای آن است که نابرابری به برابری تبدیل میشود. این گام الگوریتم همانند بیشینه کردن حدپایین درست نمایی () نسبت به است. در نتیجه روش کار الگوریتم امید ریاضی-بیشینه کردن به صورت زیر است:
- پارامترها را مقدار آغازین میدهیم.
- تا زمان همگرایی به بیشینه محلی ادامه میدهیم:
- گام-ا (مید ریاضی):
- گام-ب (یشینه کردن):
- مقادیر نهایی و را باز گردان
این دیدگاه نسبت به الگوریتم امید ریاضی-بیشینه کردن متعلق به نیل و هینتون است.[۱]
بدین ترتیب در هر گام الگوریتم، حد پایین درست نمایی کل دادهها افزایش مییابد تا آنجا که در یک بیشینه محلی همگرا شود. برای رهایی از بیشینههای محلی، این الگوریتم را معمولاً چندین بار با شرایط آغازین متفاوت اجرا میکنند.
نمونه[ویرایش]
تاریخچه[ویرایش]
این الگوریتم چندین بار به صورت جداگانه توسط افراد مختلف ابداع شدهاست. برای نمونه پیش از اینکه نام آن بیشنه کردن-امید ریاضی باشد، به نام الگوریتم باوم-ولچ شناخته میشد. نمونه امروزی آن را عموماً مربوط به مقاله ای در سال ۱۹۷۷ توسط دمپستر، لرد و روبین میدانند[۲].
منابع[ویرایش]
- ↑ Neal, Radford; Hinton, Geoffrey (1999). Michael I. Jordan, ed. "A view of the EM algorithm that justifies incremental, sparse, and other variants" (PDF). Learning in Graphical Models. Cambridge, MA: MIT Press: 355–368. ISBN 0-262-60032-3. Retrieved 2009-03-22.
- ↑ 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. JSTOR 2984875. MR 0501537.
پیوند به بیرون[ویرایش]
![]() |
این یک مقالهٔ خرد آمار است. با گسترش آن به ویکیپدیا کمک کنید. |