קורס למידת מכונה - שבוע 1: מה זה, סוגי למידה ורגרסיה ליניארית

למידת מכונה – Machine Learning

סדרת הכתבות הבאה היא למעשה סיכום בעברית של הקורס המומלץ (והחינמי) “Machine Learning” של Andrew Ng מאתר קורסרה.

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

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

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

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

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

שבוע 1

מה זה למידת מכונה?

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

ארתור סמואל, שחקר את התחום בשנות ה60', כתב שזה "מחקר בנושא האפשרות של מחשב ללמוד דבר, בלי להיות מתוכנת לכך באופן ספציפי."

טום מיצ'ל מאוניברסיטת קרנגי מלון, עשה זאת בצורה יותר פורמלית – תוכנת מחשב תיקרא "לומדת" מניסיון E ביחס למטלה כלשהי T ומדד ביצועים P – אם כשהיא מבוצעת על T, היא משתפרת לפי P עם הניסיון E.

סוגי אלגוריתמים ללמידת מכונה:

למידה מודרכת Supervised Learning
למידה לא מודרכת Unsupervised Learning

קיים גם סוג שנקרא למידה דרך חיזוק (Reinforcement Learning), ומערכת המלצות (Recommendation System), אך אלו לרוב פחות נפוצים מהשניים הנ"ל.

למידה מודרכת

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

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

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

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

למידה לא מודרכת

בלמידה לא מודרכת, מצד שני, אנו מקבלים מידע שאינו מתויג (משמע – אין לנו את ה"תשובות הנכונות"), ואנו מבקשים מהמחשב לנסות ללמוד את המבנה שלו, ולמצוא קבוצות דומות או מאפיינים דומים, וכן הלאה.

אם נסתכל לדוגמה על כל אפליקציית חדשות שאוספת כתבות מאתרים שונים – נוכל לשים לב שהן מקבצות הרבה כתבות בכל יום לנושאים. אלגוריתמים כאלו, שמקבלים מידע רב שאינו מתויג ומנסים לקבץ אותו לאשכולות\מקבצים (clusters), נקראים אלגוריתמי קיבוץ (Clustering algorithms).

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

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

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

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

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

רגרסיה ליניארית

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

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

לפני שממשיכים, כדאי לשים לב – לאורך הקורס נשתמש בכמה סימנים מוסכמים לתיאור של משתנים:

$m$ – מספר הדוגמות בסט האימון. אם יש לנו 145 פרטים על בתים ומחיריהם, m שווה 145.

$x$ – מספר ערכי ה"קלט" או המאפיינים שלנו. אם בסט האימון שלנו על הבתים יש שורה גם לגודל הבית וגם למספר החדרים, יהיו לנו 2 קלטים.

$y$ – ובהתאם, מספר ערכי ה"פלט" שלנו, או "מטרות". בדוגמה שלנו, זה מחיר הבית שאנו מנסים לחזות.

ולפי זה, נסמן כל שורה בהתאם עם הסימון הכללי $(x,y)$, או $ (x^{(i)},y^{(i)})$ לשורה ספציפית (כש-i מתייחס למספר השורה, כמובן).

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

רגרסיה ליניארית עם משתנה אחד

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

בדומה בפונקציה ליניארית של קו ישר, ההיפותזה שלנו תיראה כך:

$$ h(x) = \theta_0+\theta_1·x $$

כששני התטות הן הפרמטרים שלנו שעלינו לחזות, למעשה.

פונקציית עלות (Cost function)

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

בצורה פורמלית (כי מה יותר יפה מהצורה הזאת??) נגדיר זאת כך בקורס שלנו:

$$J(\theta_0,\theta_1) = \frac{1}{2m}\sum_{i=1}^m (\hat{y_i} −y_i)^2 = \frac{1}{2m}\sum_{i=1}^m (h_\theta(x_i) −y_i)^2 $$

הבפנים של מה שיש בתוך הסיגמא הוא למעשה משוואה מאוד פשוטה – התוצאה שקיבלנו ($\hat{y}$), פחות התוצאה האמיתית $y$. בדיוק ההפרש שדיברנו עליו. החילוק ב$m$ נותן את ממוצע ההפרשים. נוסחה כזו נקראת MSE – Mean Squared Error = שגיאה ממוצעת בריבוע.

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

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

שיטת מורד השיפוע (Gradient descent)

כנראה פעם אחרונה שאני מתרגם משהו באופן כזה, נשמע מזעזע.

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

הרעיון הוא פשוט ודיי מובן מאליו – לנו יש פונקציה $J(\theta_0,\theta_1 … \theta_N)$ , ואנחנו רוצים למצוא את המינימום שלה:

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

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

המשך עד להתכנסות:

$\theta_j := \theta_j − \alpha\frac{d}{d\theta_j}J(\theta_0,\theta_1)$ – כשj הוא האינדקס של כל אחת מהתכונות שלנו, $\alpha$ הוא ערך חיובי שמסמל את קצב הלמידה שלנו (ולכן – אם $\alpha$ יהיה גדול, הצעדים שנעשה בכל פעם יהיו גדולים יותר, וכן להפך).

אם תפתחו את הנגזרת, תקבלו את המשוואות הבאות (ל$\theta_0$ ו$\theta_1$ בהתאמה):

$$\theta_0 := \theta_0 − \alpha \frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)}) – y^{(i)})$$

$$\theta_1 := \theta_1 − \alpha \frac{1}{m}\sum_{i=1}^m(h_\theta(x^{(i)}) – y^{(i)}) \cdot x_1^{(i)}$$

הסיבה להבדל בכפל בסוף ב$x_1$ הוא בגלל הנגזרת. זכרו שהגדרנו שונה את $\theta_0$ ו$\theta_1$.

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

שימו לב שצריך לעדכן את כל המשתנים בו זמנית – אם תעדכנו את $\theta_0$ ורק אז את $\theta_1$ , התוצאה תהיה שונה כי $\theta_0$ כבר השתנה. שימו לב לנקודה הזו כשאתם מממשים את האלגוריתם.

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

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

סיימנו את השבוע הראשון. להמשך לשבוע השני, לחצו כאן!

הרגישו חופשי לשאול \ להעיר \ לצעוק בתגובות