EM ExpectationMaximization Part4

الگوریتم EM: پلی میان مشاهده و واقعیت پنهان در دنیای داده‌کاوی و یادگیری ماشین، اغلب با موقعیتی شبیه به یک معمای کارآگاهی روبرو هستیم: ما نتایج نهایی را می‌بینیم، اما نمی‌دانیم کدام علت پنهان کدام نتیجه را تولید کرده است. الگوریتم «امیدریاضی-بیشینه» یا EM دقیقاً برای حل چنین مسائلی طراحی شده است؛ جایی که بخشی از اطلاعات مربوط به نحوه تولید داده‌ها برای ما پنهان است. برای درک نیاز به EM، ابتدا باید با مفهوم «تخمین چگالی» آشنا شویم. فرض کنید تعدادی داده دارید، مثلاً قد یک گروه از افراد. هدف شما یافتن «قانون» یا الگویی است که این داده‌ها را تولید کرده است. یک روش ساده، روش «پارامتریک» نام دارد. در این روش، شما از قبل شکل قانون را حدس می‌زنید (مثلاً منحنی زنگوله‌شکل نرمال) و سپس سعی می‌کنید پارامترهای آن (مثل میانگین و انحراف معیار) را طوری تنظیم کنید که با داده‌ها سازگار باشد. بهترین روش برای یافتن این پارامترها، «بیشینه‌سازی درست‌نمایی» یا MLE است. ایدۀ MLE ساده است: پارامتری را پیدا کن که احتمال مشاهده داده‌هایی که در اختیار داری را به حداکثر برساند. این روش برای داده‌های ساده عالی کار می‌کند. اما دنیای واقعی به ندرت به این سادگی است. اغلب، داده‌ها از ترکیبی از چندین گروه مختلف تولید می‌شوند. مثلاً قد افراد می‌تواند ترکیبی از قد زنان و مردان باشد که هرکدام میانگین خاص خود را دارند. در اینجا، یک منحنی نرمال ساده به هیچ وجه نمی‌تواند این داده‌ها را به خوبی توصیف کند. ما به «مدل مخلوط» نیاز داریم. در این مدل، فرض می‌کنیم هر داده از یکی از K گروه (مؤلفه) با یک احتمال مشخص (وزن) تولید شده است. مشکل اصلی اینجاست: ما نمی‌دانیم هر داده متعلق به کدام گروه است. این «متغیر پنهان» است. اگر تعلق داده‌ها را می‌دانستیم، کار ساده بود و می‌توانستیم میانگین هر گروه را جداگانه محاسبه کنیم. اما برعکس، اگر میانگین گروه‌ها را می‌دانستیم، می‌توانستیم به راحتی بگوییم هر داده به کدام گروه تعلق دارد. این یک دور باطل است و روش مستقیم MLE در اینجا به دلیل پیچیدگی محاسباتی عملاً شکست می‌خورد. اینجاست که الگوریتم EM پا به میان می‌گذارد و این چرخه معیوب را به یک فرآیند ایده‌آل و تکراری تبدیل می‌کند. EM به جای حل یک مسئله بسیار دشوار، آن را به دو گام ساده که مدام تکرار می‌شوند، تجزیه می‌کند: گام امیدریاضی (E): در این مرحله، الگوریتم با استفاده از حدس‌های اولیه برای پارامترها (میانگین و وزن هر گروه)، «مسئولیت» هر داده را برای هر گروه محاسبه می‌کند. به زبان ساده، الگوریتم حدس می‌زند که هر مشاهده با چه احتمالی به هر یک از گروه‌های مخفی تعلق دارد. این یک «تعلق نرم» است، نه یک بله یا خیر قطعی. در این مرحله، الگوریتم به طور ضمنی داده‌های مفقود شده (برچسب هر داده) را با توجه به بهترین حدس خود «تکمیل» می‌کند. گام بیشینه‌سازی (M): حالا که یک تخمین (هرچند ناقص) از تعلق داده‌ها وجود دارد، الگوریتم می‌تواند پارامترهای مدل را بهبود ببخشد. این مرحله مشابه روش MLE در دنیای داده‌های کامل است؛ با این تفاوت که به هر داده، وزن داریم که همان احتمال تعلق آن به گروه است. الگوریتم میانگین جدید هر گروه را به صورت میانگین وزنی داده‌های متعلق به آن گروه محاسبه می‌کند. این کار، پارامترهای جدید و بهتری را تولید می‌کند. این دو گام بارها و بارها تکرار می‌شوند. در هر تکرار، الگوریتم تضمین می‌کند که میزان «سازگاری مدل با داده» (تابع درست‌نمایی) افزایش می‌یابد یا ثابت می‌ماند. به همین دلیل، EM هرگز بدتر نمی‌شود و در نهایت به یک نقطه مطلوب (معمولاً یک قله محلی) همگرا می‌شود. شاید جذاب‌ترین ویژگی EM این باشد که در عین قدرت و کاربرد گسترده در مسائلی مانند خوشه‌بندی (مدل مخلوط گاوسی) و بینایی کامپیوتر، درک مفهومی آن بسیار شهودی و نزدیک به فرآیند استدلال انسان است: یک حدس اولیه بزن، ببین چقدر خوب است، براساس آن حدس خود را اصلاح کن، و این فرآیند را آنقدر تکرار کن تا به یک جواب خوب برسی. به همین دلیل، EM را پلی میان داده‌های خام مشاهده‌شده و ساختار پنهان واقعیت می‌دانند.