שבוע 8 ב'
הפוסט הזה הוא החלק השני של השבוע השמיני. אם פספסתם או סתם לא זוכרים, לחצו כאן כדי לעבור לשבוע 8א' .
הערה – אם אתם גולשים מהנייד, חלק מהנוסחאות עלולות "להימרח" לצדדים. סובבו את המכשיר לרוחב אם זה קורה.
החומר של השבוע חולק לשני חלקים כדי שיהיה נוח יותר לקרוא.
הפחתת מימדים Dimenioality Reduction
נושא נוסף בלמידה לא מודרכת הוא הפחתת מימדים. כשאנחנו מפחיתים מימדים, אנחנו למעשה "מועכים" את כל הנקודות למימד נמוך יותר חדש, ומשתמשים במאפיינים חדשים (שנסמנם מעכשיו כ$z^{(i)}$ למאפיין החדש הi) של המימד החדש כדי לייצג כל תצפית. שימו לב שזה לא סתם "מחיקת מימדים" (=מחיקת מאפיינים), אלא למעשה ניסיון לשמור את המידע בשימוש מופחת במאפיינים. המטרה אחת היא בפשטות לצמצם את מספר המאפיינים (כל מאפיין הרי מייצג מימד) כדי לאפשר לאלגוריתם שלנו לרוץ יותר מהר (ולהוריד את קיבולת הזכרון הדרוש על הדרך). אלגוריתם שרץ על מספר מימדים נמוך יותר יכול להביא ביצועי זמן ריצה יותר טובים.
סיבה נוספת לשימוש בהפעלת מימדים היא כדי לטובת הדמיה של הנתונים שלנו. הדמיה של המידע שאנחנו מתעסקים איתו הרבה פעמים עוזרת לנו להבין איזה כיוונים לקחת ואיך לפתח אלגוריתם למידה יעיל. נניח שיש לנו נתונים על מדינות העולם כשהמאפיינים הם 50 נתוני כלכלה כמו תמ"ג, תמ"ג לנפש ועוד. אם נרצה לנסות להדפיס גרף בעולם של 50 מימדים כנראה שלא יילך כל כך טוב, לכן הצלחה של הפחתת מימדים לבעיה הזו (נניח ל3 או 2) יכולה לקדם אותנו הרבה מבחינת הבנה של איך המדינות מתפלגות כלכלית.
"טוב אחי, הבנתי שזה חשוב מאוד ועוזר. אבל איך עושים את זה?", אז בשביל זה יש לנו אלגוריתם שנקרא
ניתוח רכיבים עיקריים Principal Component Analysis (PCA)
אפשר לתרגם את זה באיזה 20 דרכים, הלכתי על מה שהאקדמיה אומרת (שדיי דומה למה שחשבתי לתרגם). זהו אחד האלגוריתמים הכי נפוצים או הנפוץ ביותר לבעיה של הפחתת מימדים. כדי להתחיל לדבר עליו, נפשט קודם למונחים יותר פורמליים את מה שאנחנו מנסים להשיג:
נחשוב לרגע על מספר נקודות במרחב דו-מימדי שאנחנו רוצים להפוך לחד מימדי, נניח ששני המאפיינים שלנו הם מידות בס"מ ובאינץ', ככה שבסה"כ אפשר לדמיין איזה קו ליניארי דמיוני אבל התצפיות קצת נוטות ממנו כי עיגלנו את המספרים שהמרנו לאינץ' (אינץ' זה בערך 2.54 סנטימטר). הדרך בה "נפסיד" הכי פחות מידע, היא אם נמצא איזשהו וקטור, שאם נמתח ממנו קו לכל התצפיות המרחקים המצטברים שלהם יהיו מינימליים – כך נבטיח שגם אם הורדנו מימד נשארנו עם אומדן יחסית טוב לאיפה כל תצפית עומדת.
במילים אחרות, מטרתנו היא להביא למינימום את ההיטל (projection error) של התצפיות על הוקטור. למי שלא חזק באלגברה ליניארית, מטרתנו היא פשוט למצוא משטח מופחת מימדים כלשהו להציג עליו את הנתונים שלנו, על ידי הבאה למינימום של המרחק של כל תצפית מקורית מהתצפית המופחת מימדים לפי הכיוונים החדשים שמצאנו. נגיד שיש לנו תצפיות בתלת-מימד, אנחנו נמצא שני כיוונים\חיצים חדשים שיוצרים "פלטה" שעליה נדפיס את התצפיות שלנו – כל התלת מימד הופחת לתוך הפלטה הזו.לסיכום, אפשר להסתכל על האלגוריתם כעל "אלגוריתם דחיסה" מהרבה מימדים לפחות מימדים.
אם יש אנשים ביניכם שאומרים לעצמם עכשיו שזה נשמע דומה לרגרסיה ליניארית, חשוב להדגיש שזה לא – ברגרסיה ליניארית, מטרתנו היא למצוא היפתוזה כלשהי שהמרחק בינה לבין התצפיות שלנו הוא מינימלי – מבחינה מתמטית זה אומר שאנחנו מותחים קו ישר מהתצפית למעלה\למטה לכיוון התצפית ומודדים את ההפרש. בPCA, קודם כל אין לנו y-ים, ויותר חשוב מכך, המטרה היא לצמצם את ההיטל, דהיינו למתוח קו מאונך לכיוון הווקטור שלנו ולחשב את ההפרש.
שלבי האלגוריתם
לפני כל הפעלה של PCA, יש שלב של עיבוד נתונים שחייבים לעשות בו עושים נרמול על פי ממוצע, ואולי גם התאמת מאפיינים אבל זה תלוי אם יש צורך לפי המאפיינים שלכם. אחרי שעשינו את זה, יש שני שלבים לאלגוריתם:
קודם, עלינו לחשב ממוצע לכל תצפית של מטריצה שנקראת מטריצת השונות המשותפת (covariance matrix):
$$\Sigma = \frac{1}{m}\sum_{i=1}^n (x^{(i)})(x^{(i)})^T$$
למי שלא בקיא באלגברה (או לא זוכר), הסתכלו שבתוך הסכימה (בצד ימין) אנחנו מכפילים כל תצפית בעצמה. הפלט של ההכפלה הזאת היא מטריצה בגודל nxn של הכפלות של מאפיין במאפיין, כשהערכים הם השונות המשותפת (זה מין מדד לתיאור הקשר או התלות בין שני ערכים). כתוצאה נחלק ב$m$ ונקבל את הממוצע. (וכן שמתי לב שיש סיגמא גם בצד שמאל, ככה מסמנים את המטריצה הזו.)
השלב השני הוא לחשב את הווקטורים העצמיים (eigenvectors) של המטריצה $\Sigma$. בעיקרון פשוט תמצאו ספריה שמחשבת את זה בשפה שבה אתה משתמשים. באוקטב אפשר לעשות את זה ככה:
[U, S, V] = svd(A)
כשמה שאנחנו צריכים זו המטריצה המתקבלת U. בצורה הכי ברורה שאני מצליח לחשוב עליה באמצע הלילה, "וקטור עצמי" של מה שאנחנו מחפשים זה וקטור כזה, שאם תכפילו אותו במטריצה שלנו תהיה לזה אותה תוצאה כמו להכפיל אותו במספר (ליותר מידע כרגע ולמה זה מעניין או מחשוב, תצטרכו כרגע לפתוח ספר אלגברה).
אחרי שני השלבים האלו, נגלה שמה שבעצם התקבל מהבלאגן האלגברי הזה זו מטריצה $U$ שבה כל עמודה מייצגת את אחד מהווקטורים שחיפשנו. אם נרצה להפחית מימדים מ$n$ ל$k$ מסוים, פשוט ניקח את $k$ העמודות הראשונות של המטריצה. נקרא למטריצה שלנו $U_{reduce}$.
כעת, נהפוך את המטריצה שלנו, ונכפיל אותה בכל תצפית כדי לקבל את התצפיות החדשות בK המימדים המופחתים שלנו. בצורה פורמלית, לכל תצפית נחשב
$$z^{(i)} = U_{reduce}^T \cdot x^{(i)}$$
וסיימנו. במשפט – המטריצה $U_{reduce}$ היא בגודל $n \times k$, כשהפכנו אותה היא $k \times n$. כעת נכפיל אותה בתצפית $x$ שהוא וקטור $n \times 1$, וסה"כ נקבל וקטור $z$ חדש בגודל $k \times 1$ שהוא מייצג את התצפית ב$k$ מימדים.
אם נרצה להחזיר את התצפיות שלנו למימדים המקוריים שלהם, נוכל לעשות זאת על ידי
$$x_{approx}^{(i)} = U_{reduce} \cdot z^{(i)}$$
כשהתצפיות שיתקבלו יהיו שערוך של תצפיות המקוריות (כי "דרסנו" חלק מהקשרים בין המאפיינים כשבחרנו רק $k$ מימדים). שערוך דיי טוב, אבל שערוך. לפעולה הזו נקרא שחזור מימדים, או שחזור מהצגה דחוסה.
בחירת מספר המימדים
נוסיף בקרוב 🙂
עד כאן שבוע 8 ! עברנו שליש