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

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

شرح الگوریتم

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

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

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

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

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

${\displaystyle {\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 )}$

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

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

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

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

نمونه

مدل مخلوط گوسی

اگر ${\displaystyle \mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})}$ ، ${\displaystyle n}$ داده مستقل از یک توزیع مخلوط گاوسی با بُعد ${\displaystyle d}$ باشد و ${\displaystyle \mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})}$ متغیرهای پنهانِ مسئله باشد که نشان می‌دهد هر بار داده از کدام یک از توزیع‌های گاوسی آمده است، آنگاه رابطه ${\displaystyle \mathbf {x_{i}} }$ با ${\displaystyle \mathbf {z_{i}} }$ به این شکل خواهد بود (برای سادگی کار تعداد توزیع‌های مخلوط گاوسی دو در نظر گرفته شده):^[۲]

${\displaystyle X_{i}|(Z_{i}=1)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1})}$ و ${\displaystyle X_{i}|(Z_{i}=2)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2})}$ و ${\displaystyle \operatorname {P} (Z_{i}=1)=\tau _{1}\,}$ و ${\displaystyle \operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}}$

هدف یادگیری پارامترهای این دو توزیع و نحوه مخلوط کردن آنهاست یعنی ${\displaystyle \theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )}}$، تابع درست نمایی برابر است با ${\displaystyle L(\theta$ ;\mathbf {x} )=\prod _{i=1}^{n}\sum _{j=1}^{2}\tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})} .

حال اگر مقادیر متغیرهای پنهان مشخص بود تابع درست نمایی با عبارت پایین برابر می‌شد:

${\displaystyle L(\theta$ ;\mathbf {x} ,\mathbf {z} )=p(\mathbf {x} ,\mathbf {z} \vert \theta )=\prod _{i=1}^{n}\prod _{j=1}^{2}\ [f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})\tau _{j}]^{\mathbb {I} (z_{i}=j)}}

و اگر این عبارت را بسط دهیم به این معادله می‌رسیم:

${\displaystyle L(\theta$ ;\mathbf {x} ,\mathbf {z} )=\exp \left\{\sum _{i=1}^{n}\sum _{j=1}^{2}\mathbb {I} (z_{i}=j){\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}\right\}}

${\displaystyle f}$ تابع چگالی احتمال توزیع گاوس است و ${\displaystyle \mathbb {I} }$ تابع مشخصه است. در معادله خط قبلی برای هر ${\displaystyle i}$ دقیقا یک تابع مشخصه یک است و دیگری صفر، یعنی دقیقا برای یکی از ${\displaystyle j}$ها ${\displaystyle \mathbb {I} (z_{i}=j)}$ برابر با یک خواهد بود.

مرحله امید ریاضی (E)

طبق قضیه بیز ${\displaystyle \theta ^{(t)}}$ که همان احتمال شرطی ${\displaystyle Z_{i}}$ است به این شکل محاسبه می‌شود: ${\displaystyle T_{j,i}^{(t)}:=\operatorname {P} (Z_{i}=j|X_{i}=\mathbf {x} _{i};\theta ^{(t)})={\frac {\tau _{j}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j}^{(t)},\Sigma _{j}^{(t)})}{\tau _{1}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{1}^{(t)},\Sigma _{1}^{(t)})+\tau _{2}^{(t)}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{2}^{(t)},\Sigma _{2}^{(t)})}}}$

همچنین تابع ${\displaystyle Q}$ الگوریتم به شکل ذیل بدست می‌آید:

${\displaystyle {\begin{aligned}Q(\theta |\theta ^{(t)})&=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,\mathbf {\theta } ^{(t)}}[\log L(\theta$ ;\mathbf {x} ,\mathbf {Z} )]\\&=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,\mathbf {\theta } ^{(t)}}[\log \prod _{i=1}^{n}L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})]\\&=\operatorname {E} _{\mathbf {Z} |\mathbf {X} ,\mathbf {\theta } ^{(t)}}[\sum _{i=1}^{n}\log L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})]\\&=\sum _{i=1}^{n}\operatorname {E} _{\mathbf {Z_{i}} |\mathbf {X} ;\mathbf {\theta } ^{(t)}}[\log L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})]\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}P(Z_{i}=j|X_{i}=\mathbf {x} _{i};\theta ^{(t)})\log L(\theta _{j};\mathbf {x} _{i},\mathbf {z} _{i})\\&=\sum _{i=1}^{n}\sum _{j=1}^{2}T_{j,i}^{(t)}{\big [}\log \tau _{j}-{\tfrac {1}{2}}\log |\Sigma _{j}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})^{\top }\Sigma _{j}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{j})-{\tfrac {d}{2}}\log(2\pi ){\big ]}\end{aligned}}}

امید ریاضی ${\displaystyle \log L(\theta$ ;\mathbf {x} _{i},\mathbf {z} _{i})} در معادله بالا نسبت به توزیع احتمال مشروط ${\displaystyle Z_{i}}$ یعنی ${\displaystyle P(Z_{i}|X_{i}=\mathbf {x} _{i};\theta ^{(t)})}$ گرفته می شود. این احتمال برای هر ${\displaystyle \mathbf {x} _{i}}$ می‌تواند مقداری متفاوت داشته باشد.

مرحله بیشینه‌سازی (M)

${\displaystyle {\begin{aligned}{\boldsymbol {\tau }}^{(t+1)}&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ Q(\theta |\theta ^{(t)})\\&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ \left\{\left[\sum _{i=1}^{n}T_{1,i}^{(t)}\right]\log \tau _{1}+\left[\sum _{i=1}^{n}T_{2,i}^{(t)}\right]\log \tau _{2}\right\}\end{aligned}}}$

${\displaystyle \tau _{j}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{j,i}^{(t)}}{\sum _{i=1}^{n}(T_{1,i}^{(t)}+T_{2,i}^{(t)})}}={\frac {1}{n}}\sum _{i=1}^{n}T_{j,i}^{(t)}}$

${\displaystyle {\begin{aligned}({\boldsymbol {\mu }}_{1}^{(t+1)},\Sigma _{1}^{(t+1)})&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\ Q(\theta |\theta ^{(t)})\\&={\underset {{\boldsymbol {\mu }}_{1},\Sigma _{1}}{\operatorname {arg\,max} }}\ \sum _{i=1}^{n}T_{1,i}^{(t)}\left\{-{\tfrac {1}{2}}\log |\Sigma _{1}|-{\tfrac {1}{2}}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})^{\top }\Sigma _{1}^{-1}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1})\right\}\end{aligned}}}$

بر طبق برآورد درست نمایی بیشنه توزیع گاوسی، مقادیر میانگین و کوواریانس را به این شکل محاسبه می‌کنیم:

${\displaystyle {\boldsymbol {\mu }}_{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}}$ و ${\displaystyle \Sigma _{1}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{1,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{1}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{1,i}^{(t)}}}}$ و ${\displaystyle {\boldsymbol {\mu }}_{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}\mathbf {x} _{i}}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}}$ و ${\displaystyle \Sigma _{2}^{(t+1)}={\frac {\sum _{i=1}^{n}T_{2,i}^{(t)}(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})(\mathbf {x} _{i}-{\boldsymbol {\mu }}_{2}^{(t+1)})^{\top }}{\sum _{i=1}^{n}T_{2,i}^{(t)}}}}$

پایان الگوریتم

مراحل E و M را به‌صورت متناوب آنقدر اجرا میکنیم تا جایی که میزان افزایش تابع امید ریاضی مشروط از یک حد از پیش تعیین شده‌ای مانند ${\displaystyle \epsilon }$ بیشتر نشود، به زبان ریاضی یعنی زمانی که نابرابری پایین صدق کند.

${\displaystyle E_{Z|\theta ^{(t)},\mathbf {x} }[\log L(\theta ^{(t)};\mathbf {x} ,\mathbf {Z} )]\leq E_{Z|\theta ^{(t-1)},\mathbf {x} }[\log L(\theta ^{(t-1)};\mathbf {x} ,\mathbf {Z} )]+\epsilon }$

تاریخچه

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