مدل آمیخته‌ی گاوسی و الگوریتم EM

مسئولیت‌ها و به‌روزرسانی پارامترهای یک مدل آمیخته‌ی گاوسی را دستی حساب کنی و بدانی EM چه چیزی را تضمین می‌کند و چه چیزی را نه.

15 دقیقه مطالعه · 5 سؤال تمرینی · یادگیری ماشین میانی و پیشرفته

مدل آمیخته‌ی گاوسی

فرض کنید داده‌ها از چند خوشه‌ی گاوسی آمده‌اند، ولی نمی‌دانیم هر نقطه مال کدام خوشه است. مدل آمیخته‌ی گاوسی (GMM) این را با یک متغیر پنهان $z \in \{1, \dots, K\}$ مدل می‌کند:

p(z = k) = \pi_k, \qquad p(x \mid z = k) = \mathcal N(x \mid \mu_k, \Sigma_k)

p(x) = \sum_{k=1}^K \pi_k\, \mathcal N(x \mid \mu_k, \Sigma_k)

لگ‌درست‌نمایی $\sum_i \log \sum_k \pi_k \mathcal N(x_i \mid \mu_k, \Sigma_k)$ شامل لگاریتمِ یک جمع است. برای همین جواب بسته ندارد.

یک مشکل دیگر: اگر یک مؤلفه روی یک نقطه‌ی داده بنشیند ( $\mu_k = x_i$ ) و واریانسش به صفر برود، چگالی آن نقطه و در نتیجه درست‌نمایی به بی‌نهایت می‌رود. پس بیشینه‌ی سراسری MLE معنادار نیست و در عمل به بیشینه‌های محلی خوب یا منظم‌سازی کوواریانس تکیه می‌کنیم.

الگوریتم EM برای GMM

ایده: اگر برچسب خوشه‌ها را می‌دانستیم، برآورد پارامترها ساده بود. EM به‌طور متناوب برچسب‌ها را به‌صورت «نرم» حدس می‌زند و پارامترها را به‌روز می‌کند.

گام E: مسئولیت (Responsibility) هر مؤلفه برای هر نقطه، یعنی احتمال پسین $z_i = k$ :

\gamma_{ik} = \frac{\pi_k\,\mathcal N(x_i \mid \mu_k, \Sigma_k)}{\sum_j \pi_j\,\mathcal N(x_i \mid \mu_j, \Sigma_j)}

گام M: با $N_k = \sum_i \gamma_{ik}$ ، برآورد وزن‌دار پارامترها:

\pi_k = \frac{N_k}{n}, \qquad \mu_k = \frac{1}{N_k}\sum_i \gamma_{ik}\,x_i, \qquad \Sigma_k = \frac{1}{N_k}\sum_i \gamma_{ik}(x_i - \mu_k)(x_i - \mu_k)^\top

این دو گام را تا همگرایی لگ‌درست‌نمایی تکرار می‌کنیم.

چرا EM کار می‌کند؟

برای هر توزیع دلخواه $q(z)$ روی متغیرهای پنهان، این اتحاد برقرار است:

\log p(x \mid \theta) = \underbrace{\mathbb E_{q}\!\left[\log \frac{p(x, z \mid \theta)}{q(z)}\right]}_{\text{ELBO}:\ \mathcal L(q, \theta)} + \operatorname{KL}\big(q(z)\,\|\,p(z \mid x, \theta)\big)

چون $\operatorname{KL} \ge 0$ ، ELBO یک کران پایین برای لگ‌درست‌نمایی است.

گام E: $q = p(z \mid x, \theta^{\text{old}})$ قرار می‌دهیم. KL صفر می‌شود و کران دقیقاً به لگ‌درست‌نمایی می‌رسد.
گام M: $\mathcal L$ را نسبت به $\theta$ بیشینه می‌کنیم.

نتیجه: لگ‌درست‌نمایی در هیچ دوری کم نمی‌شود. ولی EM فقط به یک نقطه‌ی ایستا (معمولاً بیشینه‌ی محلی) همگرا می‌شود و به مقداردهی اولیه حساس است.

k-means حالت حدی EM برای GMM است: کوواریانس‌ها $\epsilon I$ ثابت و مشترک باشند و $\epsilon \to 0$ . آن‌وقت مسئولیت‌ها سخت (۰ یا ۱) می‌شوند.

تمرین‌های این درس را حل کن (رایگان)