אלגוריתם ציפייה - מקסום

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

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

היסטוריה[עריכת קוד מקור | עריכה]

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

מבוא[עריכת קוד מקור | עריכה]

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

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

תיאור מתמטי[עריכת קוד מקור | עריכה]

בהתחשב מודל סטטיסטי המורכב מסדרה של 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) אלגוריתם ציפייה- מקסום מבקש למצוא את הערכת הנראות המרבית של הנראות השולית על ידי יישום איטרטיבי של שני הצעדים הבאים:

שלב ציפייה: לחשב ערך צפוי של פונקציית לוג הנראות, ביחס להתפלגות מותנה של 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] \,

שלב מקסום: מצא את הפרמטר שמגדיל כמות זו: ::\boldsymbol\theta^{(t+1)} = \underset{\boldsymbol\theta}{\operatorname{arg\,max}} \ Q(\boldsymbol\theta|\boldsymbol\theta^{(t)}) \,

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

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

עם זאת, ניתן להחיל את אלגוריתם ציפייה- מקסום על כל מיני מודלים.

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

במקרה שבו הן Z והן θ לא ידוע:

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

הוכחה של תקינות[עריכת קוד מקור | עריכה]

אלגוריתם ציפייה-מקסום פועל לשיפור 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{align}
\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{align}

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)}) \ge H(\boldsymbol\theta^{(t)}|\boldsymbol\theta^{(t)}).

מאפיינים[עריכת קוד מקור | עריכה]

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

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

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

יישומים[עריכת קוד מקור | עריכה]

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

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

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

\hat{\sigma}^{2}_v = \frac{1}{N} \sum_{k=1}^N {(z_k-\hat{x}_{k})}^{2}

איפה \hat{x}_k הם אומדני תפוקת סקלר מחושבים על ידי מסנן או חלק ממדידות סקלר N {z_k}. לתהליך אוטומטי רגרסיבית מסדר ראשון, אומדן שונות רעש תהליך מעודכן יכול להיות מחושב על ידי \hat{\sigma}^{2}_w =   \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 לטכניקות הערכה מאולצות. מקסום מותנה ציפייה מחליף כל צעד של מקסום עם רצף של שלבי מקסום מותנים שבכל פרמטר θi מוגדל באופן אישי, בין התנאים על הפרמטרים האחרים שנותרו קבועים. רעיון זה, להאריך את האלגוריתם עוד יותר במקסום ציפייה כללי, שבו רק אחד מבקש עלייה בפונקציית המטרה F עבור שני הצעדים ציפייה ומקסום תחת התיאור החלופי. ניתן גם לשקול את אלגוריתם ציפייה- מקסום כסדרה של אלגוריתם מקסום-מקסום, ולכן ניתן שימוש בכל המכונות שפותחו במקרה הכללי יותר.

אלגוריתם ציפייה- מקסום - α[עריכת קוד מקור | עריכה]

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

הקשר לשיטות בייס השונות[עריכת קוד מקור | עריכה]

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

דוגמאות[עריכת קוד מקור | עריכה]

E step[עריכת קוד מקור | עריכה]

בהתחשב בהערכה הנוכחית שלנו של θ הפרמטרים (t), ההתפלגות המותנה של ZI נקבעה על ידי משפט בייס להיות הגובה היחסי של הצפיפות הנורמלית משוקללת לפי τ 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{align}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{align}

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

M step[עריכת קוד מקור | עריכה]

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

\begin{align}\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{align}

זו יש לה הצורה כMLE להתפלגות הבינומית, ולכן

\tau^{(t+1)}_j = \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)}

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

\begin{align}(\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{align}

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

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