אלגוריתם מיקסום התוחלת – הבדלי גרסאות

תוכן שנמחק תוכן שנוסף

בשורה

גרסה מ־17:06, 7 באפריל 2024

דוגמה לשימוש באלגוריתם EM כדי ליצור אשכולות (Clustering). בדוגמה זו מוצג מידע על התפרצויות גייזר אולד פיית'פול. ציר ה-X מבטא את משך ההתפרצות של הגייזר, וציר ה-Y מבטא את הזמן שחלף מההתפרצות הקודמת. האלגוריתם מגיע להתכנסות ולסיווג לשני סוגים של התפרצויות הגייזר אולד פיית'פול.

אלגוריתם מיקסום התוחלת (באנגלית: Expectation–maximization; ובראשי תיבות: EM) הוא שיטה איטרטיבית למציאת אומדי נראות מקסימלית לפרמטרים, במודלים סטטיסטיים התלויים במשתנים סמויים שלא נצפו. מודל איטרציה זה עובר בין שני שלבים:

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

פרמטרי הערכות אלה משמשים לאחר מכן כדי לקבוע את ההתפלגות של המשתנים החבויים בשלב התוחלת הבא.

היסטוריה

אלגוריתם EM קיבל את שמו לראשונה בשנת 1977 במאמר מאת ארתור דמפסטר, נאן ליירד, ודונלד רובין.^[1] במאמר זה ציינו החוקרים כי בעבר השיטה כבר הועלתה על הכתב בידי מחברים אחרים. דמפסטר-ליירד-רובין הגדירו את שיטת מיקסום-התוחלת ככלי חשוב בניתוח סטטיסטי, לפתרון מגוון רחב ביותר של בעיות. עם זאת, ניתוח ההתכנסות של דמפסטר-ליירד-רובין היה פגום, וניתוח התכנסות נכון פורסם על ידי ס.פ ג'ף וו ב-1983.^[2]

מבוא

אלגוריתם EM משמש למציאת משתני הנראות המקסימלית במקרים שבהם לא ניתן לפתור את המשוואה באופן ישיר. בדרך כלל מודל מסוג זה מכיל משתנים סמויים, משתנים לא ידועים ומאגר נתונים ידוע. מציאת פתרון נראות מרבית דורש שימוש בנגזרות של פונקציית הנראות המתייחסת לכל המשתנים הידועים. במודלים סטטיסטיים המכילים משתנים סמויים שיטה זו אינה אפשרית, ולכן במקרים כאלה צריך לבנות קבוצה של משוואות שפתרונן דורש את ערכי המשתנים הסמויים ולהפך. אולם החלפת קבוצת משוואות מסוימת באחרת תיצור משוואה ללא פתרון.

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

תיאור מתמטי

בהינתן מודל סטטיסטי המורכב מסדרת מדידות X, קבוצת נתונים סמויים שאינם נראים או ערכים חסרים Z, ווקטור של פרמטרים לא ידועים θ, ופונקציית נראות $L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )=p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})$ , הערכת הנראות המרבית של הפרמטרים הלא ידועים נקבעת על ידי הנראות השולית של הנתונים הנצפים: $L({\boldsymbol {\theta }};\mathbf {X} )=p(\mathbf {X} \mid {\boldsymbol {\theta }})=\sum _{\mathbf {Z} }p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})$ . אלגוריתם EM מבקש למצוא את הערכת הנראות המרבית של הנראות השולית על ידי יישום איטרטיבי של שני הצעדים הבאים:

שלב התוחלת (שלב ה-E): חישוב תוחלת הלוגריתם של פונקציית הנראות, ביחס להתפלגות המותנית של X ו-Z ותחת האומדן הנוכחי של הפרמטרים ${\boldsymbol {\theta }}^{(t)}$ :

Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)}}\left[\log L({\boldsymbol {\theta }};\mathbf {X} ,\mathbf {Z} )\right]\,

שלב המיקסום (שלב ה-M): מצא וקטור של פרמטרים θ שמגדיל את התוחלת שחושבה בצעד הראשון:

${\boldsymbol {\theta }}^{(t+1)}={\underset {\boldsymbol {\theta }}{\operatorname {arg\,max} }}\ Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\,$

המודלים שבהם אופייני להשתמש באלגוריתם EM:

הערכים שנמדדו X יכולים להיות בדידים או רציפים (בפרט הם יכולים לקבל ערכים מקבוצה אינסופית). למעשה ייתכן שיש וקטור של ערכים בכל אחת מהתצפיות.
הערכים החסרים Z הם בדידים, ונמשכים ממספר קבוע של משתנים, ויש משתנה חבוי אחד לכל קבוצת משתנים שנצפתה.
הפרמטרים הם רציפים, ומשני סוגים: פרמטרים הקשורים לכל נקודות הנתונים ופרמטרים הקשורים עם ערך מסוים של המשתנה הסמוי.

עם זאת, ניתן להחיל את אלגוריתם EM על כל מיני מודלים.

המוטיבציה: אם אנחנו יודעים את הערך של הפרמטר θ, אנחנו בדרך כלל יכולים למצוא את ערכיהם של המשתנים הסמויים Z על ידי מקסימיזציית לוג הנראות על כל הערכים האפשריים של Z, אפשר פשוט על ידי איטרציה על Z או דרך אלגוריתם כגון אלגוריתם ויטרבי עבור מודלי מרקוב חבויים. לעומת זאת, אם אנחנו יודעים את הערך של המשתנים הסמויים Z, נוכל להעריך את הפרמטר θ בקלות יחסית, בדרך כלל על ידי קיבוץ הנתונים שנצפו על פי ערכו של המשתנה הסמוי הקשור, וחישוב הממוצע (או פונקציה כלשהי) של ערכי הנקודות בכל קבוצה. הדבר מצביע על אלגוריתם איטרטיבי, במקרה שבו הן הקבוצה Z והן הווקטור θ לא ידוע:

ראשית, צריך לאתחל את הפרמטרים הלא ידועים של וקטור θ לערכים אקראיים כלשהם.
לחשב את ההסתברות לכל נתון או ערך בקבוצה Z לפי ערכי הפרמטרים של וקטור θ שחושבו בשלב 1.
להשתמש בערכי Z שחושבו בשלב 2 כדי לחשב אומדן טוב יותר לפרמטרים של וקטור θ. פרמטרים הקשורים לנתון או ערך מסוים בקבוצה Z ישמשו רק עם נקודות המידע אשר המשתנים החבויים שמקושרים איתם הם בעלי אותו הערך.
יש לחזור על השלבים 2 ו-3 עד להתכנסות.

הוכחת נכונות

אלגוריתם EM פועל לשפר את הביטוי $Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})$ במקום לשפר ישירות את הביטוי $\log p(\mathbf {X} \mid {\boldsymbol {\theta }})$ . ההוכחה שלהלן תראה כי שיפורים בביטוי הראשון גוררים שיפורים בביטוי האחרון:

מתוך הגדרת ההסתברות המותנית,

p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})=p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})p(\mathbf {X} \mid {\boldsymbol {\theta }})

או באופן שקול, אם ההסתברות ל-Z איננה אפס בהינתן X ו-θ, כלומר:

p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})\neq 0

, אז:

p(\mathbf {X} \mid {\boldsymbol {\theta }})={\frac {p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})}{p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})}}

אם מוציאים לוגריתם לשני הצדדים של המשוואה, מתקבל:

\log p(\mathbf {X} \mid {\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})

לשם ההמשך, ההוכחה תניח ש-Z הוא משתנה מקרי בדיד, אבל ההוכחה תקפה (בשינויים הנדרשים) גם עבור משתנה מקרי רציף.

בשלב הבא, מחשבים את התוחלת על ערכים של Z על ידי הכפלת שני הצדדים ב- $p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})$ וסיכום על Z. ביחס ל-Z, צד שמאל הוא תוחלת של קבוע, כך שמתקבל:

{\begin{aligned}\log p(\mathbf {X} \mid {\boldsymbol {\theta }})&=\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {X} ,\mathbf {Z} \mid {\boldsymbol {\theta }})-\sum _{\mathbf {Z} }p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }}^{(t)})\log p(\mathbf {Z} \mid \mathbf {X} ,{\boldsymbol {\theta }})\\&=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})\,\end{aligned}}

$H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})$ מוגדר בתור הנגדי לסכום שאותו מחליף, והוא אינו אלא האנטרופיה הצולבת בין ההתלפגות המיוחסת ל- $\theta ^{(t)}$ לבין ההתפלגות המיוחסת ל- $\theta$ . המשוואה זו תקפה לכל ערך של θ, ובפרט אם ${\boldsymbol {\theta }}={\boldsymbol {\theta }}^{(t)}$ ,

\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})\,

ומתוך חיסור המשוואה האחרונה מהמשוואה הקודמת מתקבל

\log p(\mathbf {X} \mid {\boldsymbol {\theta }})-\log p(\mathbf {X} \mid {\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}\mid {\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}\mid {\boldsymbol {\theta }}^{(t)})\,

עם זאת, מאי-שוויון גיבס (אנ') נובע כי $H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})\geq H({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})$ .

מאפיינים

שלב התוחלת הוא קצת מטעה. בשלב הראשון מה שמחושב הם הפרמטרים הקבועים, פרמטרים תלויי נתונים של הפונקציה Q. לאחר שהפרמטרים של הפונקציה Q חושבו, הם נקבעים באופן סופי ומובאים לידי מקסימום בשלב השני של המיקסום.

למרות שפעולת האיטרציה באלגוריתם EM מגדילה את המידע הידוע על פונקציית הנראות, אין בכך ערובה שהתהליך יוביל בסופו של דבר לאומדן נראות מרבי. כלומר, אלגוריתם EM עשוי להתכנס למקסימום מקומי של פונקציית נראות שנצפתה, בהתאם לערכי ההתחלה. ישנן מגוון של גישות היוריסטיות ליציאה ממקסימום מקומי כגון אתחול אקראי או באמצעות שימוש בשיטות חישול מדומה.

אלגוריתם EM הוא שימושי במיוחד כאשר הנראות היא ממשפחת המעריכיים. צעד התוחלת הופך לסכום של תוחלות של סטטיסטים מספיקים וצעד המיקסום ממקסם את הפונקציה הליניארית. במקרה כזה, בדרך כלל ניתן לגזור עדכוני צורה סגורה לכל שלב, תוך שימוש בנוסחת סונדברג.

יישומים

מסנן קלמן משמש בדרך כלל עבור מדיניות הערכה online, ומינימום שונות חלקות עשויים להיות במדיניות הערכה off-line או הערכת מצב באצווה. פתרונות שונים דורשים הערכות של הפרמטרים מודל מרחב מצבים. סינון ושיפור אלגוריתמי תוחלת-מקסום עשויה להתרחש על ידי חזרה על התהליך בן שני השלבים הבאים:

שלב התוחלת להפעיל מסנן קלמן או מחליק עם שונות מינימלית, המעוצב עם הערכות הפרמטר הנוכחיות, כדי לקבל הערכות מצב מעודכנות.

שלב המיקסום השתמש בהערכות המצב המסוננות או המוחלקות בחישוב הנראות המקסימלית, כדי לקבל אומדני פרמטר מעודכנים. נניח שמסנן קלמן או מינימום שונות חלקה יותר פועל על מדידות רועשות של מערכת יחיד קלט יחיד פלט. ניתן לקבל אומדן שונות רעש מדידה מעודכן מחישוב הנראות המקסימלית.

${\hat {\sigma }}_{v}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{(z_{k}-{\hat {x}}_{k})}^{2}$

כאשר ${\hat {x}}_{k}$ הם אומדני תפוקת סקלר מחושבים על ידי מסנן או חלק ממדידות סקלר N ${z_{k}}$ . לתהליך אוטומטי רגרסיבית מסדר ראשון, אומדן שונות רעש תהליך מעודכן יכול להיות מחושב על ידי ${\hat {\sigma }}_{w}^{2}={\frac {1}{N}}\sum _{k=1}^{N}{({\hat {x}}_{k+1}-{\hat {F}}{\hat {x}}_{k})}^{2}$ .

כאשר ${\hat {x}}_{k}$ ו- ${\hat {x}}_{k+1}$ אומדני מדינת סקלר מחושבים על ידי מסנן או חלק יותר. ההערכה מקדם מודל המעודכן מתקבלת באמצעות: ${\hat {F}}={\frac {\sum _{k=1}^{N}({\hat {x}}_{k+1}-{\hat {F}}{\hat {x}}_{k})}{\sum _{k=1}^{N}{\hat {x}}_{k}^{2}}}$ .

גרסאות

מספר שיטות הוצעו על מנת להאיץ את ההתכנסות האיטית של אלגוריתם EM, כדוגמת אלו המשתמשות בשיפוע צמוד ומותאמות לטכניקות ניוטון-רפסון. בנוסף ניתן להשתמש ב-EM לטכניקות הערכה מאולצות. מיקסום מותנה תוחלת מחליף כל צעד של מיקסום עם רצף של שלבי מיקסום מותנים שבהם כל פרמטר θi מוגדל באופן יחיד והתנאים על הפרמטרים האחרים נותרים כפי שהם. רעיון זה, להאריך את האלגוריתם עוד יותר במיקסום תוחלת כללי ושבו רק פרמטר אחד גורם לעלייה בפונקציית המטרה F, לאחר ביצוע שני הצעדים של האלגוריתם (תוחלת ומיקסום), מהווה גרסה שימושית נוספת של אלגוריתם זה. ניתן גם לתאר את אלגוריתם EM כסדרה של אלגוריתמי מיקסום-מיקסום, ואפשר לעשות שימוש בכל התכונות שפותחו גם במקרה הכללי יותר.

אלגוריתם EM-α

הפונקציה Q המשמשת באלגוריתם EM מבוססת על לוגריתם הנראות. לכן, הוא נחשב לאלגוריתם לוג-תוחלת-מקסום. ניתן להכליל לשימוש בלוג הנראות של יחס סיכוי α-לוג. לאחר מכן, יחס הנראות של לוג-α של הנתונים שנצפו יכול לבוא לידי ביטוי בדיוק כשוויון באמצעות הפונקציה Q של יחס סיכוי α-log ו-α-הסטייה. קבלת פונקציה Q זו היא צעד תוחלת כללי. המקסום שלה הוא צעד מקסום כללי. זוג זה נקרא אלגוריתם EM-α אשר מכיל את אלגוריתם לוג-תוחלת-מקסום. לכן, אלגוריתם EM-α הוא הכללה של אלגוריתם לוג-תוחלת-מקסום מדויקת. אין צורך בחישוב מטריצת שיפוע או הסיאן. ניתן לראות באלגוריתם EM-α התכנסות מהירה יותר מאשר אלגוריתם לוג-תוחלת-מקסום על ידי בחירת α מתאים. אלגוריתם EM-α מוביל לגרסה מהירה יותר של אלגוריתם אמידת מודל מרקוב חבוי α-HMM.

הקשר לשיטות בייס השונות

תוחלת-מקסום הוא באופן חלקי שיטת נראות השונה מהשיטה הבייסיאנית. התוצאה הסופית שלה נותנת התפלגות הסתברות על המשתנים החבויים (בסגנון בייס) יחד עם אומד נקודתי ל-θ. גרסה בייסיאנית מלאה לאלגוריתם צריכה לייחס התפלגות הסתברות על θ, כמו גם למשתנים החבויים. למעשה, ניתן לראות שבגישה הבייסיאנית θ היא עוד משתנה סמוי, וההבחנה בין צעדי התוחלת והמקסום נעלמת. אם משתמשים בגרסה המלאה לקירוב Q כפי שתוארה לעיל (הווריאציה של בייס), ניתן לעבור על כל המשתנים הסמויים ולשפר אותם אחד-אחד. כעת יש k צעדים לכל איטרציה, כאשר k הוא מספר המשתנים הסמויים. למודלים גרפיים קל לעשות תלויי Q לכל משתנים, רק בשמיכת מרקוב שלה, כך שהעברת מידע מקומית יכולה לשמש למסקנה יעילה.^{[דרושה הבהרה]}

דוגמא

תערובת גאוסית

תון מדגם $\mathbf {x} =(\mathbf {x} _{1},\mathbf {x} _{2},\ldots ,\mathbf {x} _{n})$ של $n$ תצפיות בלתי תלויות מתערובת של שתי התפלגויות רב-נורמליות ממימד $d$ , ונניח שקיימים משתנים מקריים סמויים $\mathbf {z} =(z_{1},z_{2},\ldots ,z_{n})$ אשר קובעים מאיזה מרכיב נלקחה כל תצפית. ^[3]

$X_{i}\mid (Z_{i}=1)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{1},\Sigma _{1})$ ו-

$X_{i}\mid (Z_{i}=2)\sim {\mathcal {N}}_{d}({\boldsymbol {\mu }}_{2},\Sigma _{2})$ ,

כאשר

$\operatorname {P} (Z_{i}=1)=\tau _{1}\,$ ו-

$\operatorname {P} (Z_{i}=2)=\tau _{2}=1-\tau _{1}$ .

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

$\theta ={\big (}{\boldsymbol {\tau }},{\boldsymbol {\mu }}_{1},{\boldsymbol {\mu }}_{2},\Sigma _{1},\Sigma _{2}{\big )}$ ,

כאשר פונקציית הנראות בנוכחות הנתונים החסרים היא:

$L(\theta ;\mathbf {x} )=\prod _{i=1}^{n}\sum _{j=1}^{2}\tau _{j}\ f(\mathbf {x} _{i};{\boldsymbol {\mu }}_{j},\Sigma _{j})$ ,

ופונקציית הנראות בנוכחות נתונים שלמים היא:

$L(\theta ;\mathbf {x} ,\mathbf {z} )=p(\mathbf {x} ,\mathbf {z} \mid \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)}$ ,

(כאשר $\mathbb {I}$ היא פונקציה מציינת ו- $f$ היא פונקציית הצפיפות של של ההתפלגות הרב-נורמלית) או באופן שקול:

$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\}$ .

בשוויון האחרון, עבור כל $i$ , $\mathbb {I} (z_{i}=j)$ שווה לאפס עבור ערך מסויים של $j$ , ושווה לאחד עבור הערך האחר. הסכום הפנימי מצטמצם אפוא למחובר אחד.

שלב התוחלת

בהתחשב בהערכה הנוכחית שלנו של θ הפרמטרים (t), ההתפלגות המותנה של Z_i נקבעה על ידי משפט בייס להיות הגובה היחסי של הצפיפות הנורמלית משוקללת לפי τ $T_{j,i}^{(t)}:=\operatorname {P} (Z_{i}=j\mid 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)})}}$ .

אלה נקראים הסתברויות החברות ואלו בדרך כלל נחשבים לפלט, צעד E זה תואם את הפונקציה עבור Q הבא: ${\begin{aligned}Q(\theta \mid \theta ^{(t)})&=\operatorname {E} [\log L(\theta ;\mathbf {x} ,\mathbf {Z} )]\\&=\operatorname {E} [\log \prod _{i=1}^{n}L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})]\\&=\operatorname {E} [\sum _{i=1}^{n}\log L(\theta ;\mathbf {x} _{i},\mathbf {z} _{i})]\\&=\sum _{i=1}^{n}\operatorname {E} [\log L(\theta ;\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}}$

אין צורך לחשב את ערכו של הביטוי, כי בשלב M אנו דורשים רק את המונחים בהתאם τ כאשר אנו נמקסם את τ, או רק את המונחים בהתאם μ אם אנחנו נמקסם עבור μ.

שלב המקסום

הוא ביטוי ריבועי ב- Q(θ|θ^(t) משמעות הדבר היא כי קביעת הערכים עבור מקסום של θ היא פשוטה יחסית. שימו לב כי ניתן להגדיל כל אחד מבין (τ, (μ₁, Σ₁) ו-(μ₂, Σ₂), באופן בלתי תלוי, שכן כל שהם מופיעים בתנאים ליניארי נפרדים. כדי להתחיל, לשקול τ, שבה יש מגבלת τ₁, τ₂ = 1

${\begin{aligned}{\boldsymbol {\tau }}^{(t+1)}&={\underset {\boldsymbol {\tau }}{\operatorname {arg\,max} }}\ Q(\theta \mid \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}}$

שיש לה הצורה של אומד נראות מקסימלית להתפלגות הבינומית, ולכן

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

עבור האומדנים הבאים של (μ₁, σ₁)

${\begin{aligned}({\boldsymbol {\mu }}_{1}^{(t+1)},\sigma _{1}^{(t+1)})&={\underset {{\boldsymbol {\mu }}_{1},\sigma _{1}}{\operatorname {arg\,max} }}\ Q(\theta \mid \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}}$

זו יש לה הצורה כאומד נראות מקסימלית משוקלל להתפלגות נורמלית, ולכן

${\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)}}}$ וגם $\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)}}}$

ומסימטריה:

${\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)}}}$ וגם $\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_{Z\mid \theta ^{(t)},\mathbf {x} }[\log L(\theta ^{(t)};\mathbf {x} ,\mathbf {Z} )]\leq E_{Z\mid \theta ^{(t-1)},\mathbf {x} }[\log L(\theta ^{(t-1)};\mathbf {x} ,\mathbf {Z} )]+\varepsilon$

ל- $\varepsilon$ מתחת לסף מוגדר מראש.

הכללה

ניתן להכליל את האלגוריתם המודגם לעיל עבור תערובות של יותר משתי התפלגויות רב-נורמליות.

הערות שוליים

^ A. P. Dempster, N. M. Laird, D. B. Rubin, Maximum Likelihood from Incomplete Data Via the EM Algorithm, Journal of the Royal Statistical Society: Series B (Methodological) 39, 1977-09, עמ' 1–22 doi: 10.1111/j.2517-6161.1977.tb01600.x
^ C. F. Jeff Wu, On the Convergence Properties of the EM Algorithm, The Annals of Statistics 11, 1983-03, עמ' 95–103 doi: 10.1214/aos/1176346060
^ Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2001). "8.5 The EM algorithm". The Elements of Statistical Learning. New York: Springer. pp. 236–243. ISBN 978-0-387-95284-0.

[1] A. P. Dempster, N. M. Laird, D. B. Rubin, Maximum Likelihood from Incomplete Data Via the EM Algorithm, Journal of the Royal Statistical Society: Series B (Methodological) 39, 1977-09, עמ' 1–22 doi: 10.1111/j.2517-6161.1977.tb01600.x

[2] C. F. Jeff Wu, On the Convergence Properties of the EM Algorithm, The Annals of Statistics 11, 1983-03, עמ' 95–103 doi: 10.1214/aos/1176346060

[hastie2001-3] Hastie, Trevor; Tibshirani, Robert; Friedman, Jerome (2001). "8.5 The EM algorithm". The Elements of Statistical Learning. New York: Springer. pp. 236–243. ISBN 978-0-387-95284-0.

[1]

[2]

[3]

@@ שורה 109: / שורה 109: @@
 תוחלת-מקסום הוא באופן חלקי שיטת נראות השונה מ[[סטטיסטיקה בייסיאנית|השיטה הבייסיאנית]]. התוצאה הסופית שלה נותנת [[התפלגות]] [[הסתברות]] על המשתנים החבויים (בסגנון בייס) יחד עם אומד נקודתי ל-θ. גרסה בייסיאנית מלאה לאלגוריתם צריכה לייחס התפלגות הסתברות על θ, כמו גם למשתנים החבויים. למעשה, ניתן לראות שבגישה הבייסיאנית θ היא עוד משתנה סמוי, וההבחנה בין צעדי התוחלת והמקסום נעלמת. אם משתמשים בגרסה המלאה לקירוב Q כפי שתוארה לעיל (הווריאציה של בייס), ניתן לעבור על כל המשתנים הסמויים ולשפר אותם אחד-אחד. כעת יש k צעדים לכל איטרציה, כאשר k הוא מספר המשתנים הסמויים. למודלים גרפיים קל לעשות תלויי Q לכל משתנים, רק בשמיכת מרקוב שלה, כך שהעברת מידע מקומית יכולה לשמש למסקנה יעילה.{{הבהרה|לא ברור מה היה כתוב במקור}}
-==דוגמאות==
+==דוגמא==
-===שלב התוחלת===
+=== תערובת גאוסית ===
+[[קובץ:ClusterAnalysis_Mouse.svg|ממוזער|400x400 פיקסלים|השוואה של [[אלגוריתם k-מרכזים|k-means]] ו-EM על נתונים מלאכותיים המוצגים עם [[סביבה לפיתוח יישומי KDD נתמכים על ידי אינדקס-Structures|ELKI]] . באמצעות השוניות, אלגוריתם EM יכול לתאר את ההתפלגויות הנורמליות במדויק, בעוד k-means מפצל את הנתונים בתאי [[דיאגרמת וורונוי|Voronoi]] . מרכז האשכול מסומן על ידי הסמל הבהיר והגדול יותר.]]
+[[קובץ:Em_old_faithful.gif|ממוזער|240x240 פיקסלים|אנימציה המדגימה את אלגוריתם ה-EM המתאים [[מודל תערובת|מודל של תערובת]] גאוסית בשני מרכיבים למערך הנתונים [[אולד פיית'פול|של Old Faithful]] . מוצגים צעדי האלגוריתם מאתחול אקראי להתכנסות.]]
+תון מדגם <math>\mathbf{x} = (\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_n)</math>  של <math>n</math> תצפיות בלתי תלויות [[התפלגות תערובת|מתערובת]] של שתי [[התפלגות רב-נורמלית|התפלגויות רב-נורמליות]] ממימד <math>d</math>, ונניח שקיימים משתנים מקריים סמויים <math>\mathbf{z} = (z_1,z_2,\ldots,z_n)</math> אשר קובעים מאיזה מרכיב נלקחה כל תצפית. <ref name="hastie2001">{{Cite book|last=Hastie|first=Trevor|url=https://archive.org/details/elementsstatisti00thas_842|title=The Elements of Statistical Learning|last2=Tibshirani|first2=Robert|last3=Friedman|first3=Jerome|publisher=Springer|year=2001|isbn=978-0-387-95284-0|location=New York|pages=[https://archive.org/details/elementsstatisti00thas_842/page/n237 236]–243|chapter=8.5 The EM algorithm|author-link=Trevor Hastie|author-link2=Robert Tibshirani|url-access=limited}}</ref>
+<math>X_i \mid(Z_i = 1) \sim \mathcal{N}_d(\boldsymbol{\mu}_1,\Sigma_1)</math> ו-
+<math>X_i \mid(Z_i = 2) \sim \mathcal{N}_d(\boldsymbol{\mu}_2,\Sigma_2)</math>,
+כאשר
+<math>\operatorname{P} (Z_i = 1 ) = \tau_1 \, </math> ו-
+<math>\operatorname{P} (Z_i=2) = \tau_2 = 1-\tau_1</math>.
+המטרה היא להעריך את המשקלים של הצירוף הקמור בין הגאוסים ואת התוחלות והשונויות של כל אחד מהם:
+<math>\theta = \big( \boldsymbol{\tau},\boldsymbol{\mu}_1,\boldsymbol{\mu}_2,\Sigma_1,\Sigma_2 \big)</math>,
+כאשר פונקציית הנראות בנוכחות הנתונים החסרים היא:
+<math>L(\theta;\mathbf{x}) = \prod_{i=1}^n \sum_{j=1}^2 \tau_j \ f(\mathbf{x}_i;\boldsymbol{\mu}_j,\Sigma_j)</math>,
+ופונקציית הנראות  בנוכחות נתונים שלמים היא:
+<math>L(\theta;\mathbf{x},\mathbf{z}) = p(\mathbf{x},\mathbf{z} \mid \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)}</math>,
+(כאשר <math>\mathbb{I}</math> היא [[פונקציה מציינת]] ו- <math>f</math> היא [[פונקציית צפיפות|פונקציית הצפיפות]] של של ההתפלגות הרב-נורמלית) או באופן שקול:
+<math>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\}</math>.
+בשוויון האחרון, עבור כל <math>i</math>,  <math>\mathbb{I}(z_i=j)</math> שווה לאפס עבור ערך מסויים של <math>j</math> , ושווה לאחד עבור הערך האחר. הסכום הפנימי מצטמצם אפוא למחובר אחד.
+====== שלב התוחלת ======
 בהתחשב בהערכה הנוכחית שלנו של θ הפרמטרים (t), ההתפלגות המותנה של Z<sub>i</sub> נקבעה על ידי משפט בייס להיות הגובה היחסי של הצפיפות הנורמלית משוקללת לפי τ
 <math>T_{j,i}^{(t)} := \operatorname{P}(Z_i=j \mid 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)})} </math>.
@@ שורה 125: / שורה 161: @@
 אין צורך לחשב את ערכו של הביטוי, כי בשלב M אנו דורשים רק את המונחים בהתאם τ כאשר אנו נמקסם את τ, או רק את המונחים בהתאם μ אם אנחנו נמקסם עבור μ.
-===M step===
+====== שלב המקסום ======
 הוא [[ביטוי ריבועי]] ב- ''Q''(''θ''|''θ''<sup>(''t'')</sup> משמעות הדבר היא כי קביעת הערכים עבור מקסום של θ היא פשוטה יחסית. שימו לב כי ניתן להגדיל כל אחד מבין (τ, (μ<sub>1</sub>, Σ<sub>1</sub>) ו-(μ<sub>2</sub>, Σ<sub>2</sub>), באופן בלתי תלוי, שכן כל שהם מופיעים בתנאים ליניארי נפרדים.
 כדי להתחיל, לשקול τ, שבה יש מגבלת τ<sub>1</sub>, τ<sub>2</sub> = 1
@@ שורה 152: / שורה 188: @@
 <math>\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)}} </math> {{רווח קשיח|3}} וגם {{רווח קשיח|3}} <math>\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)}} </math>.
+====== סיום ======
+נסיים את התהליך האיטרטיבי כאשר <math> E_{Z\mid\theta^{(t)},\mathbf{x}}[\log L(\theta^{(t)};\mathbf{x},\mathbf{Z})] \leq E_{Z\mid\theta^{(t-1)},\mathbf{x}}[\log L(\theta^{(t-1)};\mathbf{x},\mathbf{Z})] + \varepsilon</math>
+ל- <math> \varepsilon </math> מתחת לסף מוגדר מראש.
+====== הכללה ======
+ניתן להכליל את האלגוריתם המודגם לעיל עבור תערובות של יותר משתי [[התפלגות רב-נורמלית|התפלגויות רב-נורמליות]].
 ==הערות שוליים==

	יש לערוך ערך זה. ייתכן שהערך סובל מבעיות ניסוח, סגנון טעון שיפור או צורך בהגהה, או שיש לעצב אותו, או מפגמים טכניים כגון מיעוט קישורים פנימיים.
	אתם מוזמנים לסייע ולערוך את הערך. אם לדעתכם אין צורך בעריכת הערך, ניתן להסיר את התבנית. ייתכן שתמצאו פירוט בדף השיחה.	עריכה

יש לערוך ערך זה. ייתכן שהערך סובל מבעיות ניסוח, סגנון טעון שיפור או צורך בהגהה, או שיש לעצב אותו, או מפגמים טכניים כגון מיעוט קישורים פנימיים.
אתם מוזמנים לסייע ולערוך את הערך. אם לדעתכם אין צורך בעריכת הערך, ניתן להסיר את התבנית. ייתכן שתמצאו פירוט בדף השיחה.