אלגוריתם EM (Expectation–Maximization)

הבעיה: איך לומדים פרמטרים כשחלק מהנתונים חסר

במודלים סטטיסטיים רבים, המשתנים שרוצים להעריך כוללים גם משתנים "סמויים" (Latent Variables) — ערכים שלא נצפו ישירות בנתונים, לצד הפרמטרים הלא ידועים עצמם. כשיש משתנים סמויים כאלה, המשוואות למציאת הפרמטר הסביר ביותר (Maximum Likelihood) הן לרוב בלתי פתירות באופן אנליטי: הן תלויות הדדית במשתנה הסמוי ובפרמטר בעת ובעונה אחת, כך שאי-אפשר לבודד אחד מהם כדי לפתור את השני. המשתנה הסמוי יכול להיות מידע שחסר באמת (תוצאת בדיקה שלא בוצעה, תווית שלא נרשמה), או כלי נוח לבניית המודל — למשל קבוצת השתייכות נסתרת, שלפיה רוצים מלכתחילה לפרק את הנתונים, בלי שיש בפועל "תווית אמת" שמישהו שכח לרשום. בעיות מהסוג הזה מופיעות בכל תחומי הסטטיסטיקה ולמידת המכונה: מאבחון רפואי שבו חלק מהבדיקות חסרות, ועד מודלים של טקסט ודיבור שבהם המבנה הפנימי (למשל, לאיזה "נושא" שייכת כל מילה) אינו ידוע מראש ויש להסיק אותו מהנתונים עצמם.

דמפסטר, לרד ורובין, 1977: המאמר שנתן לשיטה שם

האלגוריתם הוסבר וקיבל את שמו במאמר קלאסי מ-1977 מאת ארתור דמפסטר, ננסי לרד ודונלד רובין, "Maximum Likelihood from Incomplete Data via the EM Algorithm", בכתב העת Journal of the Royal Statistical Society, Series B (כרך 39, גיליון 1, עמודים 1–38). המאמר הציג אלגוריתם כללי ורחב היקף לחישוב אומדי סבירות מרבית מנתונים חסרים, על פני כמה רמות של הכללה מתמטית, ולצדו הוכחה פורמלית שהסבירות עולה (או לכל הפחות נשארת כפי שהייתה) בכל איטרציה בודדת של האלגוריתם — הוכחה שמבטיחה שההליך אינו יכול "להתדרדר", גם אם אינה מבטיחה הגעה לפתרון הטוב ביותר בכלל: האלגוריתם עלול להתכנס למקסימום מקומי, בהתאם לנקודת ההתחלה. ניתוח ההתכנסות במאמר עצמו היה פגום, וניתוח נכון פרסם ב-1983 סי. אף. ג'ף וו.

המנגנון: שני שלבים חוזרים — תוחלת, ואז מיקסום

האלגוריתם עובד באיטרציות של שני שלבים. בשלב התוחלת (Expectation, E) מחושבת התוחלת (Expectation) של פונקציית הסבירות הלוגריתמית של הנתונים המלאים, על פני הערכים האפשריים של המשתנים הסמויים, כשההסתברות של כל ערך כזה נקבעת לפי הנתונים הנצפים ולפי ערכי הפרמטרים הנוכחיים. למעשה זהו "ניחוש מושקל" של ערכו הסביר של המשתנה הסמוי, לפי כל מה שידוע עד כה. בשלב המיקסום (Maximization, M) מתעדכנים הפרמטרים לערכים שממקסמים את התוחלת שחושבה בשלב הקודם — כלומר, הפרמטרים מתעדכנים כך שיתאימו בצורה הטובה ביותר ל"ניחוש" הנוכחי של המשתנה הסמוי. האלגוריתם חוזר על שני השלבים לסירוגין, בכל פעם עם ניחוש מעודכן וטוב יותר, עד שהפרמטרים מתכנסים ומפסיקים להשתנות באופן משמעותי בין איטרציה לאיטרציה. מה שהופך את השיטה לשימושית במיוחד הוא שכל שלב בודד — התוחלת או המיקסום — הוא לרוב חישוב פשוט שאפשר לפתור ישירות, גם כשאת הבעיה המשולבת (למצוא גם את הפרמטרים וגם את המשתנה הסמוי בבת אחת) אי-אפשר לפתור ישירות. האלגוריתם "מפרק" בעיה קשה לשני חישובים קלים יותר, שכל אחד מהם מזין את השני.

דוגמה מעשית: תמהיל גאוסיאנים — לפרק נתונים לקבוצות בלי לדעת מראש לאיזו קבוצה כל תצפית שייכת

אחד השימושים הנפוצים ביותר של EM הוא אמידת "תמהיל גאוסיאנים" (Mixture of Gaussians) — הנחה שהנתונים נוצרו משילוב של כמה התפלגויות נורמליות נפרדות, בלי לדעת מראש מאיזו מהן הגיעה כל תצפית בודדת. בתמהיל של שתי התפלגויות, למשל, שלב התוחלת מחשב לכל תצפית הסתברות שייכות לכל אחת משתי הקבוצות (ולא שיוך בינארי חד-משמעי: "שייכת לקבוצה 1" או "שייכת לקבוצה 2"), ושלב המיקסום מעדכן לפי אותן הסתברויות את משקלי התמהיל (כמה גדולה כל קבוצה יחסית לאחרת), ואת הממוצע והשונות של כל קבוצה. אחר כך שלב התוחלת הבא מחשב הסתברויות שייכות מדויקות יותר, לפי הפרמטרים המעודכנים.

ההבדל מאלגוריתם k-ממוצעים: הסתברות רכה מול חלוקה קשה

EM קרוב ברוחו לאלגוריתם k-ממוצעים (k-Means Clustering) — שניהם איטרטיביים, ומתחילים מניחוש ראשוני ומשתפרים בכל סיבוב. אבל כשמשתמשים ב-EM לאמידת תמהיל גאוסיאנים, יש ביניהם הבדל מהותי: "אלגוריתם EM יכול לתאר את ההתפלגויות הנורמליות באופן מדויק, בעוד k-ממוצעים מחלק את הנתונים לתאי וורונוי" (Voronoi-cells). למעשה, k-ממוצעים נחשב מקרה פרטי, "קשה", של EM לתמהיל גאוסיאנים. כלומר, k-ממוצעים משייך כל נקודה לקבוצה אחת בלבד, לפי המרחק הגיאומטרי הקצר ביותר למרכז של קבוצה — שיוך "קשה" וחד-משמעי, שמייצר גבולות ישרים בין קבוצות. EM, לעומת זאת, שומר על שיוך "רך", הסתברותי: כל נקודה מקבלת הסתברות שייכות לכל אחת מהקבוצות, ומתאר כל קבוצה כהתפלגות הסתברות מלאה — לא רק מרכז כובד בודד, אלא גם צורה וכיוון. זה ייצוג עדין ועשיר יותר, אך גם תובעני יותר מבחינה חישובית מהחלוקה הגיאומטרית הפשוטה של k-ממוצעים.

מעבר לאשכולות: שימוש רחב יותר בלמידת מכונה

השימוש של EM אינו מוגבל לחלוקת נתונים לאשכולות: הוא משמש גם לפתרון בעיות רגרסיה ליניארית מרובה ולטיפול בנתונים חסרים, ולאימון מודלים סטטיסטיים אחרים שיש בהם רכיב סמוי, כמו מודל מרקוב חבוי (Hidden Markov Model), שבו רצף ה"מצבים" אינו נצפה ישירות, בדיוק כמו קבוצת ההשתייכות בתמהיל הגאוסיאנים, ומוערך באותה שיטה (אלגוריתם באום-וולש הוא מקרה פרטי של EM). EM נשאר כלי יסוד בסטטיסטיקה ובלמידה לא מפוקחת, ודוגמה מוקדמת וחשובה לרעיון שעדיין מרכזי בלמידת מכונה: שאפשר ללמוד פרמטרים גם כשחלק מהתמונה חסר, איטרציה אחר איטרציה, בלי לדרוש שהנתונים יהיו שלמים ומתויגים במלואם מראש. זו הנחת היסוד שמאפשרת בכלל שיטות רבות של למידה לא מפוקחת: שאפשר להתחיל מניחוש גס, ולתת לנתונים עצמם, בתהליך איטרטיבי מתכנס, לחדד את הניחוש הזה שוב ושוב.