سعی کردم هرچیزی که از جلسات دوره فهمیدم رو به صورت جزوه در بیارم و در این پلت‌فورم با بقیه به اشتراک بذارم. کل جلسات دوره 23 تاست که سعی می‌کنم هفته‌ای دو جلسه رو منتشر کنم. تا جایی که تونستم سعی کردم خوب و کامل بنویسم، اما اگر جایی ایرادی داشت، حتما تو کامنت‌ها بهم بگید تا درستش کنم.
ادامه بحث بررسی کلاسترینگ با دیدگاه احتمالاتی را خواهیم دید. در ابتدا ادامه مثال جلسه قبل رو بررسی خواهیم کرد و سپس با جزییات الگوریتم EM آشنا خواهیم شد.
یک سری داده داریم که از سه تا گاوسی متفاوت اومدن و برچسب‌های اولیه‌شون هم مشخصه. برچسب‌هاشونو بر می‌داریم و به توزیع دوم تو شکل پایین می‌رسیم. روش الگوریتم EM رو مشخص کردیم و در نهایت به شکل c رسیدیم. همونطور که مشخصه نتیجه نهایی با حالت اولیه یکمی فرق میکنه و یک سری داده‌ها رنگ‌های ترکیبی از قرمز و آبی و سبز گرفتن که مشخص میکنه که هر داده با یه احتمالی به بیشتر از یک گاوسی متعلق هست.
مثال پایین الگوریتم EM رو در هر مرحله نشون میده که چطور داده‌ها به گاوسی‌های مختلف اساین میشن در هر مرحله.
مشابه الگوریتم k-means توی این الگوریتم هم مشکل بهینه‌های محلی رو داریم. تو روش maximum likelihood یکی از بهینه‌های سراسری عدد مثبت بی‌نهایت هست که همواره سعی می‌کنیم بهش نرسیم. زمانی که به یک کلاستر فقط یک نقطه اختصاص پیدا کنه این حالت رخ میده.
الگوریتم k-means به صورت احتمالاتی عمل نمی‌کنه و تعداد پارامترهاش کمتره. همچنین شکل کلاسترهارو محدودتر در نظر می‌گرفت. روش EM پارامترهای بیشتری داره و به صورت احتمالاتی عمل میکنه و در کل کندتره. از طرفی شکل توزیع‌هارو فقط کروی در نظر نمی‌گیره و با دیتای بیشتر می‌تونه کلاسترینگ رو بهتر انجام بده.
الگوریتم EM به این صورت عمل میکرد که برای مدلی که تعدادی پارامتر داره یک مقداردهی اولیه براشون انجام میده و بعد در یک حلقه تا رسیدن به یک همگرایی مقدار پارامترها رو آپدیت میکنه. همچنین یک گام دیگه هم داره که میزان ممبرشیپ رو به ازای هر داده برای هر گاوسی مشخص میکنه.
مسئله‌ای که اینجا داریم به کمک maximum likelihood جوابش بسته و محدود به دست نمیاد. مشکلی که داریم اینکه همزمان دو تا متغیر ناشناخته‌شده داریم. برای اینکه بتونیم جواب رو به دست بیاریم می‌تونیم اینجوری در نظر بگیریم که یکی از متغیرهارو جوابش رو داریم و بر اساس اون متغیر دوم رو هم جوابش رو پیدا کنیم.
مثلا اینجا فرض کنید گاوسی رو داشته باشیم، پس می‌تونیم به سادگی میزان پارامترهاشو تخمین بزنیم. (هم گاوسی رو نداریم هم پارامترهاشو، ولی فرض می‌کنیم حالا گاوسی رو داریم تا بتونیم پارامترهاشو تخمین بزنیم. البته میشه برعکس هم در نظر گرفت). این ایده کلی الگوریتم EM هست. گام‌های این الگوریتم در تصویر پایین آورده شده.
وقتی برای داده‌ها یک متغیر ناشناخته داریم که مقدارشو نمی‌دونیم می‌تونیم از ایده الگوریتم EM براش استفاده کنیم به این صورت که تو هر گام دو کار مختلف انجام میده. اولین کار حدس مقادیر برای متغیر ناشناخته هست. این کار مثل این می‌مونه که توزیع داده رو برای اون متغیر در بیاره. یعنی بیاد بگه که متغیر با چه احتمالی به کدوم توزیع‌ها تعلق داره. کار دوم پیدا کردن پارامترها بر اساس اون توزیع‌های به‌دست اومده هست.
گام‌های مختلف الگوریتم EM تو اسلاید زیر آورده شده. تو گام E توزیع روی متغیرهای تصادفی ناشناخته رو پیدا میکنه و تو گام M استفاده از توزیع به‌دست اومده از مرحله قبل استفاده میکنه و یک تابع هدف داره که دنبال ماکسیمم کردن اون هست.
تابع هدفی که در گام M به‌دست میاد به صورت زیر هست که از نظر محاسباتی استفاده ازش برامون راحته. برای جزییات بیشتر در مورد این تابع هدف به دقیقه 33 از ویدیو این جلسه مراجعه بفرمایید.
چرا الگوریتم EM مقدار likelihood رو برامون حداکثر میکنه؟ فرض کنید به ازای هر توزیعی رابطه زیر برقرار باشه. سمت چپ مقدار likelihood رو نشون میده و سمت راست هم برای توزیع مورد نظر برقرار هست. به نامساوی زیر نامساوی Jensen گفته میشه. در ادامه اول می‌بینیم این نامساوی چیه و بعد ادامه بحث رو دنبال خواهیم کرد.
ایده این نامساوی این هست که میگه اگه یک تابع convex داشته باشیم، اکسپکتیشن تابع مقدارش بزرگ‌تر مساوی f(E[x]) میشه. یعنی اگه اکسپکتیشن رو ببریم داخل تابع باعث میشه که مقدارش کوچیکتر مساوی E[f(x)] بشه و برعکس همین برای توابع concave برقرار هست. برای شهود بیشتر در مورد این نامساوی به دقیقه 39 از ویدیو مراجعه بفرمایید.
حالا اگه برگردیم به رابطه بالا، ما به‌جای اینکه بخوایم خود likelihood رو حداکثر کنیم، از این نامساوی استفاده می‌کنیم و حد پایین رو براش ماکسیمم می‌کنیم که با F(theta, Q) نام‌گذاری شده.
گام E معادل با پیدا کردن توزیع Q به صورتی هست که حد پایین براش حداکثر بشه و گام M معادل با این هست که توزیع Q رو جایگذاری کنیم و بعد حد پایین به‌دست اومده رو بر حسب تتا حداکثر کنیم.
تصویر زیر شهود این الگوریتم رو مشخص میکنه. نمودار قرمز رنگ معادل با likelihood هست و نمودار آبی حد پایینی هست که بالاتر معرفی شد. از آنجایی که محاسبات برای حد پایین ساده‌تر از کار کردن با خود likelihood هست به همین دلیل از F(theta, Q) به جای likelihood استفاده می‌شود.
اثبات درستی روابط بالا در اینجا آورده نشده است. در صورت تمایل برای کسب جزییات بیشتر می‌توانید به دقیقه 45 از ویدیو مراجعه بفرمایید.
الگوریتم EM و جزییات آن را بررسی کردیم. از آنجایی که مباحث تئوری و ریاضیات این جلسه به نسبت جلسات قبلی بیشتر بود مباحث تئوری مرتبط با اثبات درستی الگوریتم EM در اینجا آورده نشده است و در صورت تمایل برای جزییات بیشتر از چگونگی اثبات می‌توانید ویدیو این جلسه را ببینید.
اگر جایی ایراد یا مشکلی بود، حتما بهم بگید تا تصحیحش کنم.
