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

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

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

היסטוריה

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

מבוא

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

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

תיאור מתמטי

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

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

$Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})=\operatorname {E} _{\mathbf {Z} |\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 }}|{\boldsymbol {\theta }}^{(t)})\,$

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

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

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

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

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

הוכחת נכונות

אלגוריתם EM פועל לשיפור $Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})$ במקום ישירות לשיפור $\log p(\mathbf {X} |{\boldsymbol {\theta }})$. כאן אנו מראים כי שיפורים לראשון רומזים לשיפורים לאחרון. עבור כל Z בהסתברות שאינה אפס $p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }})$ אנחנו יכולים לכתוב: $\log p(\mathbf {X} |{\boldsymbol {\theta }})=\log p(\mathbf {X} ,\mathbf {Z} |{\boldsymbol {\theta }})-\log p(\mathbf {Z} |\mathbf {X} ,{\boldsymbol {\theta }})\,$

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

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

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

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

וחיסור המשוואה האחרונה, זו מהמשוואה הקודמת נותן

$\log p(\mathbf {X} |{\boldsymbol {\theta }})-\log p(\mathbf {X} |{\boldsymbol {\theta }}^{(t)})=Q({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})-Q({\boldsymbol {\theta }}^{(t)}|{\boldsymbol {\theta }}^{(t)})+H({\boldsymbol {\theta }}|{\boldsymbol {\theta }}^{(t)})-H({\boldsymbol {\theta }}^{(t)}|{\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 לכל משתנים, רק בשמיכת מרקוב שלה, כך שהעברת מידע מקומית יכולה לשמש למסקנה יעילה.

דוגמאות

שלב התוחלת

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

M step

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

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

28410532אלגוריתם מיקסום התוחלת