שבוע 8 א'
הפוסט הזה הוא החלק הראשון של השבוע השמיני. אם פספסתם או סתם לא זוכרים, לחצו כאן כדי לעבור לשבוע 7א' או כאן כדי לעבור לשבוע 7ב' (חסר כרגע).
הערה – אם אתם גולשים מהנייד, חלק מהנוסחאות עלולות "להימרח" לצדדים. סובבו את המכשיר לרוחב אם זה קורה.
החומר של השבוע חולק לשני חלקים כדי שיהיה נוח יותר לקרוא.
למידה לא מודרכת Unsupervised Learning
השבוע נתחיל לדבר על תחום נוסף בלמידת מכונה: למידה לא מודרכת. בניגוד ללמידה מודרכת, בבעיות אלו הדבר היחידי שיש לנו זה תצפיות לא מתוייגות (זאת אומרת בלי איזשהו ערך $y$), ואנחנו מבקשים מהאלגוריתמים שלנו ללמוד מהם מבנה מסוים. קיימים מספר משפחות של אלגוריתמים בתחום הזה, אך אנחנו נתחיל בלדבר על משפחה שנקראת אלגוריתמי קיבוץ (Clustering algorithms), שמטרתם היא לקבל סט תצפיות לא מתוייגות ולחלק אותם למקבצים או קבוצות נפרדות.
דוגמות לשימוש באלגוריתמי קיבוץ ניתן לראות בכמה מקומות: פילוח שוק ללקוחות של חברה מסוימת, ניתוח קשרים של אנשים ברשתות חברתיות לקבוצות, ניהול של חדרי שרתים למחשבים שיעבדו זה עם זה או ניסיון להבנה של מידע אסטרונומי על כוכבים וגלקסיות. המשותף לכל הנושאים האלו הוא שאנחנו לא יודעים לתת לתצפיות שלנו קבוצה מראש, אלא מנסים להבין ביניהם קשרים על ידי האלגוריתם ובכך ללמוד תובנות חדשות על התצפיות שלנו.
אלגוריתם k מרכזים K-Means Algorithm
נתחיל מאחד מאלגוריתמי הקיבוץ הכי נפוצים – אלגוריתם k המרכזים, או k-means באנגלית. הרעיון הולך ככה: בהתחלה, אנו בוחרים את $k$, שהוא מספר המקבצים שנרצה לחילוק התצפיות. האלגוריתם יגריל $k$ נקודות רנדומליות שכל אחת מסמלת את נקודת המרכז (centroid) של מקבץ מסוים, ויתחיל לרוץ: בכל שלב, הוא יכניס כל נקודה למקבץ לפי המרכז שהכי קרוב אליה. לאחר שהוא סיים, הוא ייקח את כל הנקודות הנוכחיות בכל מקבץ, ייחשב את הממוצע שלהן וייקבע אותו בתור המרכז החדש. את התהליך הזה נמשיך שוב ושוב עד שאין כבר תצפיות שקופצות למקבצים שונים. בסיום נקבל מערך שבו לכל תצפית יש את המקבץ שאליו היא שייכת. כל מקבץ מוגדר בעצם לפי אותה נקודת מרכז שלו, ה-centroid, ואליו שייכות כל התצפיות שהכי קרובות אליו משאר המרכזים של המקבצים האחרים.
בצורה האהובה עליכם (=פורמלית. רק מזכיר לכם מה אתם אוהבים), נגיד ככה:
האלגוריתם מקבל שני קלטים: $K$ – מספר המרכזים, ו$X = {x_1,x_2,…x_m}$ סט אימון.
אתחל רנדומלית K מרכזים לכל מקבץ – ${\mu_1,\mu_2…,\mu_K}$, והמשך עד להתכנסות:
- לכל תצפית$x_i$, חשב את:
- $c^{(i)}$ := האינדקס (מ1 עד K) של המקבץ שנקודת המרכז שלו היא הכי קרובה לתצפית.
זה נעשה לרוב על ידי חישוב של המרחק האוקלידי בין נקודת התצפית שלנו לכל אחד מהמרכזים: $\min_k ||x^{(i)} – \mu_k||$.
- כעת, לכל מרכז $k=1 to K$:
- $\mu_k$ := הממוצע של כל התצפיות שתחת המקבץ $k$.
האלגוריתם נעצר (נקודת ההתכנסות) כאשר אחרי איטרציה שלמה אף אחד מהמרכזים לא השתנה וכעת כל המקבצים קבועים (מה שאומר שכל התצפיות נשארו באותו מקבץ שכבר היו בו).
במקרים בהם יוצא לכם באמצע מקבץ ללא אף נקודה, בדרך כלל נוהגים פשוט למחוק אותו. אם מאוד קריטי לכם להישאר עם K מקבצים, תוכלו פשוט לאתחל אותו מחדש.
טיוב (אופטימיזציה) של k מרכזים
למעשה, באלגוריתם זה ננסה להביא למינימום את פונקציית העלות (לפעמים נקראת גם פונקציית העיוות distortion function) הבאה:
$$J(c^{(1)}… c^{(m)},\mu_1…\mu_K) = \frac {1}{m} \sum_{i=1}^m \lVert x^{(i)} – \mu_{c^{(i)}}\rVert ^2$$
כאשר $\mu_{c^{(i)}}$ זה המרכז של התצפית $x^({i)}$. בעברית, מה שיש לנו בתוך הסיגמא זה את המרחק של כל דוגמה מהמרכז הנוכחי שלה, ואנחנו מחלקים ב$m$ כדי לקבל את המרחק הממוצע. פונקציה שתביא את זה הנוסחה הזו למינימום למעשה מביאה בממוצע כל תצפית ל"מרכז" שהכי נכון לה, ושקרוב יחסית לדוגמות אחרות.
הדרך שבה האלגוריתם מוצא את המינימום היא בחילוק לשני השלבים מלמעלה: קודם, אנחנו מקבעים את ערכי המרכזים $\mu_k$ שלנו, ואז רצים על כל התצפיות כדי למצוא לכל אחת את המרחק המינימלי ולשייך אותה למרכז מסוים $c^{(i)}$. אחר כך, אנחנו הופכים ומקבעים את ערכי המרכזים שקיבלנו $c^{(i)}$, ואז רצים על כל $\mu_k$ ומחשבים אותו מחדש, בנתינת ערך שהכי מינימלי בממוצע לנקודות שנמצאות אצלו כרגע.
החשיבות בהבנה של מטרת פונקציית העלות היא גם כמו תמיד שנדע לבדוק את המימוש שלנו ולבחון אם משהו לא עובד טוב (למשל, שימו לב שבגלל שבכל שלב $J$ אמור לרדת, לא הגיוני שבריצה שלנו הוא יקפוץ או יעלה פתאום), אבל בנוסף גם כי בשונה מאחרים שלמדנו, האלגוריתם הזה יכול להיתקע במינימום מקומי, וכדאי שנדע לזהות את זה ולערוך בו שינויים.
אתחול רנדומלי (Random Intialization)
הדרך המומלצת לאתחול ההתחלתי של המרכזים היא לא להגריל סתם נקודות, אלא להגריל K תצפיות ולקבוע את המרכזים להיות בדיוק הם. בצורה זו יש סיכוי יותר טוב לקבל J יחסית מינימלי. השיטה הזו עדיין לא מבטיחה לנו שלא ניתקע במינימום מקומי, לכן, לרוב מה שעושים זה להריץ את האלגוריתם מספר פעמים (אנדרו אומר שבדרך כלל בין 50 ל1000), ובסוף לקחת את המודל שעבורו ה$J$ היה מינימלי. למרות זאת, השיטה הזו עוזרת לרוב רק כשK שלנו יחסית קטן, לדוגמה 2-10, אבל עבור K גדול ממש, כנראה שכבר ההרצה הראשונה שלכם תהיה סבבה.
האמת, לבחירת מספר המקבצים המומלץ אין איזה שיטה אוטומטית או טריק, ובדרך כלל בוחרים אותם ידנית. הסיבה הפשוטה היא, שכשאין לנו תיוג של התצפיות, להחליט לכמה קבוצות לחלק אותן זה דיי מעורפל והרבה פעמים סובייקטיבי ולא חד משמעי. תסתכלו על התמונה הזו ותבינו:
יש כאן 2 מקבצים או 4? אולי 3? (זא, אם הצלחתם לראות 3 תעדכנו אותי איך)
בחירת מספר המרכזים
עדיין, יש כמה שיטות קיימות לבחירה של K. אחת מוכרת נקראת "שיטת המרפק" (Elbow method). הרעיון הוא פשוט להתחיל ב$K=1$, להתקדם הלאה ובכל פעם להדפיס את ה$J$ שקיבלנו כפלט של מספר המרכזים. ברגע שנראה נקודה שממנה הירידה הבאה כבר לא כל כך גבוהה, נבחר את המספר שלה וזה יהיה מספר המרכזים. השיטה נקראית כך כי היא בונה על גרף שנראה כמו מרפק (כן רציני) – זאת אומרת ירידה חדה כמו מהכתף למרפק, ואז מתונה יותר כמו בין המרפק ליד.
הבעיה בשיטה הזאת, היא שהם לא חשבו על אפשרות שהשיטה תהפוך ל"שיטת התמנון" (הם אשכרה קראו לה מרפק) – לפעמים הגרף פשוט לא נראה ככה, והוא מתכנס בצורה יותר איטית משני קווים גסים. במצב כזה קצת יותר קשה להחליט לפי העין מתי לעצור כי ההבדלים ב$J$ בין המקבצים לא גדולים מידי. לכן לסיכום זו שיטה שאפשר להשתמש בה אבל לא תמיד לסמוך עליה הרבה.
נקודה אחרונה שחשוב לציין היא שבעיקרון הפונקציה שואפת ל0 כשמעלים את K (נסו לחשוב למה), אבל לא בהכרח שתמיד תראו את זה בגרף, והסיבה היא שיכול להיות שהרצה ספציפית נתקעה במינימום מקומי. אם קורה לכם דבר כזה (נניח שהפלט לשני מרכזים נמוך יותר מהפלט ל3), נסו לאתחל מחדש את ההרצה הבעייתית.
דרך נוספת להסתכל על בחירת מספר המרכזים היא לחשוב במונחים של המטרה שלנו – לדוגמה, אם אני מנסה להחליט כמה מידות חולצה שונות להדפיס לקונים שלי, מספר המרכזים שלי יהיה תלוי במטרה שלי שהיא מכירת החולצות. אם אתחיל מ3 ואראה שקונים לא מרוצים \ לא הכל נמכר, יכול להיות שהתובנה תהיה שכדאי להריץ את האלגוריתם שוב עם יותר מרכזים כדי לקבל מידות חולצה רבות יותר. במשפט אחד – פשוט לשאול את עצמכם למה אתם מריצים את האלגוריתם ומה אתם מנסים להשיג.
עד כאן שבוע 8 א' לבנתיים! עברו כאן לשבוע 8ב'
ספרו לנו בתגובות מה דעתכם