BackPropagation

19
Mar
2020

צעד קטן לאדם צעד גדול להתכנסות

מיועד ל- מטיבי לכת (כתבה מאוד טכנית)

נכתב על ידי Ayelet Sapirshtein

“המסע הארוך ביותר נפתח בצעד הלא נכון”. (צ’ארלס כריסטופר מארק)

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

מהי אופטימיזציה למזעור פונקציית ההפסד (loss function) ?

פונקציית המחיר משמעותה עד כמה המודל שלנו צודק. ככל שהערך של פונקציית ההפסד (loss) נמוכה יותר, כך המודל “צודק” יותר. מודל “צודק” משמעו מודל שהפרדיקציה במוצאו קרובה ל Ground Truth, התוצאה שאמורה להיות בהתאם לתיוגים. למשל במודל סיווג בינארי לדואר (דואר זבל=1 דואר רגיל=0) עד כמה הציון שהמודל נותן קרוב ל1 בהינתן דואר זבל ו0 בהינתן מייל רגיל.

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

Gradient Descent

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

לדוגמה לחישוב Gradient descent עבור מודל רגרסיה לינארית n מימדית:

עבור קלט וקטור x, וקטור y שהינו ה Ground Truth (התחזית הרצויה) ו θ

וקטור הפרמטרים של מודל הרגרסייה.

ההיפותזה של התחזית עבור קלט x נראית כך:

h_0(x)=\sum_{j=0}^n\theta_jx_j

h_0 מייצגת את התחזית עבור דוגמא x

בהינתן m דגימות פונקצית ההפסד תראה כך:

J_{train}(\theta )=\frac{1}{2m}\sum _{i=1}^m\left ( h_{\theta}\left ( x^{(i)}\right )-y^{(i)} \right )^2

הגרדיאנט: 

\frac{1}{m}\sum _{i=1}^m\left ( h_{\theta}\left ( x^{(i)}\right )-y^{(i)} \right )x_j^{(i)}

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

עבור learning rate נקבל שצעד העדכון הייה:

\theta_j-\alpha\frac{1}{m}\sum _{i=1}^m\left ( h_{\theta}\left ( x^{(i)}\right )-y^{(i)} \right )x_j^{(i)}

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

בפועל חישוב הגרדיאנט לפי כל סט האימון (גודל batch ענקי) לוקחת זמן רב ולא ישים מבחינה חישובית. לעומת זאת SGD=Stochastic Gradient Descent, היא שיטה לפיה עוברים בלולאה מספר פעמים (כמספר ה-epochs) על סט האימון, ובכל איטרציה במקום לחשב את הגרדיאנט לפי כל סט האימון, מחשבים את הגרדיאנט לפי הדוגמא הנוכחית. (זהו למעשה batch בגודל אחד)

כדי לגרום לגרדיאנטים להיות פחות תנודתיים, במקום לחשב גרדיאנט לפי קלט יחיד, מחשבים לפי קבוצה קטנה של קלטים, שיטה זו נקראת Mini Batch Gradient Descent.

מקור 

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

ללא קשר לגודל ה Batch לשיטת ה-SGD יש לא מעט בעיות:

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

  1. התכנסות למינימום מקומי ולנקודות אוכף. כאשר SGD מגיע למינימום מקומי, או נקודת אוכף הגרדיאנט שווה ל0 וSGD יעצר. במימד גבוה זו סיטואציה שכיחה, למעשה הרבה יותר ממינימום מקומי. מסיבה זו הבעיה העיקרית היא עם נקודות אוכף ופחות עם מינימום מקומי. בעיה זו נוצרת גם בסביבת נקודת האוכף, שבה גרדיאנט מאוד קטן, וזו בעיה גדולה.מקור
  2. כיוון הגרדיאנט עלול לסבול מרעשים בעקבות העבודה עם mini batch, לדגימות חריגות (outliers) ב-Batch יכולה להיות השפעה חזקה.למרבה המזל יש אסטרטגייה פשוטה שעובדת טוב ברוב המקרים כדי להתמודד עם בעיית תנודתיות הגרדיאנטים והעצירה בנקודות אוכף.

    הוספת מומנטום ל-SGD

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

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

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

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

 

מקור

לרוב בוחרים את rho להיות 0.9 או 0.99.

שיטת אופטימיזציה שנועדה כדי להתמודד עם הזיגזוג שנוצר כתוצאה מהמקרה בו גרדיאנט משתנה בעוצמה שונה בכיוונים שונים היא AdaGrad.

AdaGrad

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

מה יקרה כתוצאה מהחילוק בהנחה שיש לנו קואורדינטה אחת שהנגזרת הכיוונית שלה תמיד קטנה קואורדינטה אחרת שהנגזרת הכיוונית שלה תמיד גדולה?

מקור

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

מה קורה לAdaGrad לאורך תהליך האימון כאשר סכום הריבועים הולך וגדל?

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

יש וריאציה קלה לAdaGrad שמתמודדת עם הבעיה הזו הנקראת RMSProp

RMSProp

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

מקור

הקורא הדקדקן שישווה בין Ada-Grad לבין RMSProp יבחין שאם נחליף במשוואות של RMSProp את הממוצע המשוכלל לפי פרמטרdecay_rate לסכום, כלומר להחליף את decay_rate ב-1 ואת 1-decay_rate ב-1 נקבל בדיוק את AdaGrad.

RMSProp שומר על המאפיין הנחמד של Ada-Grad להאיץ מהירות לאורך כיוון אחד ולהאט אותה בכיוון אחר, מבלי הבעיה של תמיד להאט.

ניתן לראות ש RMSProp לא עושה overshoot והוא נע בכיוון יחסית שווה לאורך כל המימדים.

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

למה לא גם וגם ? ? ?

Adam

משלב את השיטות הקדמות Momentum+ AdaGrad

מקור

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

מקור

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

פרמטרים מומלצים לAdam: bata1=0.9, bata2=0.999 ,learning_rate=1e-3

מה החסרונות של Adam וכיצד מתמודדים איתם?

למרות שAdam הוא אחד משיטות האופטימיזציה השימושיות ביותר כיום, הוא סובל מ 2 בעיות עיקריות:

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

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

במקום שנגדיר בעצמנו את הפרמטרים עבור ה-warm-up ניתן להשתמש ב-RAdam .RAdam הוא אלגוריתם חדש שמחליף את ה-warm-up ב-Adam ולא מצריך הגדרת פרמטרים עבור תקופת החימום. חוקרים שפתחו את RAdam מצאו כי בעית ההתיצבות הראשונית נגרמת כתוצאה משונות לקויה ב-learning rate האדפטיבי כתוצאה מכמות הנתונים המוגבלת בתחילת האימון. הדרך בה (Rectified Adam)-RAdam פותר את הבעיה היא על ידי תיקון (Rectified) השונות של ה-learning rate האדפטיבי על סמך הגרדיאנטים.

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

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

איך בוחרים learning rate?

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

מקור 

לא חייבים לדבוק באותו learning rate לאורך כל האימון. מומלץ לרוב להקטין את ה-learning rate לאורך האימון ובכך לשלב בין היתרונות של קצב לימוד מהיר ואיטי. הקטנת ה -learning rate מקובלת לרוב בשימוש ב-SGD ופחות באלגוריתמים אדפטיבים שבהם שינוי ה-learning rate כבר נמצא באלגוריתם. בנוסף learning rate נמוך בתחילת האימון, warm-up, יכול להועיל, כפי שציינו קודם.

LookAhead

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

מתוך מאמר LookAhead

 

במה משתמשים בפועל?

נכון להיום השיטות הנפוצות ביותר הם Adam שמתכנס מהר ו-SGD עם מומנטום ו-learning rate decay משמש בדרך כלל עבור SOTA אבל דורש fine tuning. בין השיטות החדישות היום שנותנות תוצאות טובות ניתן למצוא את Ranger אופטימיזר שמשלב את RAdam עם LookAhead. כל אחד מהם מטפל בהיבטים שונים של אופטימיזציה. RAdam מייצב אימונים ההתחלתיים, ו-LookAhead מייצב את האימונים הבאים, מבצע אקספלורציה מזרז את תהליך ההתכנסות.

ספרו לנו בתגובות באילו שיטות אופטימיזציה אתם משתמשים, ומה עבד לכם טוב?

שאלות אפשריות לראיונות עבודה:

איך עובד backpropagation?

אילו שיטות אופטימיזציה לאימון רשתות אתה מכיר? ‍

כיצד משתמשים ב-SGD לאימוני רשת עצבית? ‍

מה היתרונות בשימוש במיני באצ’ים ב-gradient descent?

איך עובד Adam? מה ההבדל העיקרי בינו לבין SGD? ‍

למה לעיתים קרובות ל-Adam יש לוס נמוך יותר אבל SGD נותן תוצאות יותר טובות על ה-test ?
 ‍מה זה learning rate?

מה קורה כשה-learning rate גדול מדי? קטן מדי?

מה עדיף learning rate קבוע או משתנה לאורך האימון?

איך מחליטים מתי להפסיק לאמן רשת עצבית? 

מה זה model checkpointing?

חומר נוסף:

Gradient Descent Intuition Andrew Ng

Stochastic Gradient Descent  Andrew Ng 

cs231n Stanford Lecture 7

Ranger

Posted by Ayelet Sapirshtein in deep
09
Mar
2020

5 שאלות על פונקציות אקטיבציה שעלולות להופיע בראיון העבודה הבא שלך

מיועד ל- מתחילים (כתבה קצת טכנית)

נכתב על ידי Ayelet Sapirshtein

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

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

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

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

z^{[1]}=W^{[1]}x+b^{[1]}

נשתמש בפונקציית הזהות בתור פונקציית אקטיבציה:

a^{[1]}=id\left ( z^{[1]} \right )=W^{[1]}x+b^{[1]}

נחשב את האקטיבציה של השכבה הבאה: 

z^{[2]}=W^{[2]}a^{[1]}+b^{[2]}

\inline a^{[2]}&=id\left ( \right z^{[2]})=W^{[2]}a^{[1]}+b^{[2]} =W^{[2]}\left ( W^{[1]}x+b^{[1]}\right )+b^{[2]} =\left (W^{[2]}W^{[1]}\right )x+\left ( W^{[2]}b^{[1]}+b^{[2]} \right )=\acute{W}x+\acute{b}

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

פונקציית האקטיבציה הראשונה שהייתה בשימוש ברשתות הייתה סיגמואיד 

סיגמואיד:

 

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

Saturation (רוויה)- הרוויה הורגת את הגרדיאנט. כאשר השיפוע מתיישר הגרדיאנט שואף ל-0 ולכן פעפוע לאחור לא יוכל לעדכן את המשקלים.

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

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

חישוב האקספוננט לוקח זמן רב 

כדי לפתור את הבעייה שנוצרה מכך שסיגמואיד לא ממורכז סביב ה-0 עברו להשתמש בפונקציית tanh.

(טנגנס היפרבולי) tanh

 tanh מתנהגת כמו סיגמואיד שעבר הזזה והכפלה בקבוע. גרסה אחרת של tanh נראית כך: tanh(x)=2\sigma(x)-1. tanh ממורכזת סביב ה-0 מכווץ את המספרים לטווח של [1,1-].

Saturation (רוויה)-  בדומה לסיגמואיד tanh סובל מבעייה של דעיכת גרדיאנטים (vanishing gradient) בגלל רוויה.

חישוב tanh לוקח זמן רב 

כיום tanh שימושי בעיקר עבור רשתות rnn.

ReLU

AlexNet הייתה הרשת הראשונה שהחליפה את פונקציית האקטיבציה ל-ReLU, וגרמה לרשת להתכנס פי 6 יותר מהר.

ReLU מהיר לחישוב ביחס לסיגמואיד ו-tanh.

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

 

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

Leaky ReLU

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

Maxout

לא נכנסת לסטורציה אבל מכפילה את מספר המשקלים ברשת, במקום w יש לנו עכשיו w1 וw2. מסיבה זו היא לא פרקטית

ELU

 

חישוב אקספוננט לוקח זמן רב.

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

מה אפשר לעשות כדי למנוע מנוירונים ברשת למות ?

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

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

עם זאת בחירת learning rate נמוך מדי יאט את קצב ההתכנסות.
דרכים נוספות כדי למנוע מנוירונים למות הן pruning או dropout, ו-batch normalization.

מתכוננים לראיונות עבודה? ענו על השאלות הבאות בנושא:

  1. מדוע אנחנו זקוקים לפונקציות אקטיבציה?
  2. כתוב את פונקציית סיגמואיד ושרטט אותה?
  3. מה הנגזרת של פונקציית סיגמואיד?
  4. מה הבעיות בשימוש בפונקציית סיגמואיד בתור פונקציית אקטיבציה?
  5. מה גורם לתופעת ה vanishing gradient ברשתות, ובאילו דרכים אפשר להתמודד איתה?

כתבו את תשובותיכם בתגובות וקבלו מאיתנו פידבק. תפגיזו בראיונות!

מקורות:

046003, Spring 2019 טכניון
cs231n_2019  7 מצגת

Activation Functions (C1W3L06)

Why Non-linear Activation Functions (C1W3L07)

Lecture 0204 Gradient descent in practice II: Learning rate

 

 

Posted by Ayelet Sapirshtein in deep
02
Jul
2019

התקפות על למידת מכונה (Adversarial Attacks)

מיועד ל- מטיבי לכת (כתבה מאוד טכנית)

נכתב על ידי Oz Wilson

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

חלוקה לסוגי תקיפות

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

נהוג להבדיל בין שני סוגי התקפות דיגיטליות²:

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

ב) קופסה שחורה – לתוקף אין שום ידע או שיש לו ידע מוגבל על המודל. אם יש לתוקף גישה לתת למודל קלט ולחלץ פלט אז הוא מרוויח עוד מידע.

במאמר זה אספר על שלושה אפיקי התקפה שונים שמטרתם להכשיל Deep Neural Networks שמאומנות על ידי מאגרי תמונות מוכרות כגון MNIST, CIFAR ו-ImageNet: התקפות מבוססות גרדיאנט, התקפות מבוססות על אוגמנטציה מרחבית והתקפות גבול.

1) התקפות מבוססות גרדיאנט

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

שיטת Projected Gradient Descent- PGD

בשיטה זו מאמנים יצירת קלט זדוני x (כזה שיכשיל את המודל המותקף) באופן איטרטיבי. תהליך האימון מבוסס על כך שלוקחים גרדיאנט של פונקציית ההפסד J_{\Theta }^{adv}(x)  (תוסבר בהמשך) וכל איטרציה מכפילים בפרמטר α הגדול מ-0 שהוא ה – learning rate כמו ב BackPropogation-

כדי לייעל את התהליך לא מחפשים בכל מרחב הקלט, אלא רק בסביבה של הנקודות x במרחק 𝛆 מ-x_{0} (מרחק הגדול מ-0). סביבה זו מיוצגת על ידי ההיטל –\prod ל-N_{\varepsilon }(x_{0}) . מעדכנים את הקלט הזדוני x, כאשר הקלט מאותחל להפרעה רנדומלית בתוך הסביבה הזו³-

פונקציית ההפסד של שיטת PGD

פונקציית ההפסד מטרתה למדוד עד כמה הקלט הזדוני מביא לידי תגובה רצויה למודל המותקף. הפונקציה מוגדרת כ³-

הביטוי max_{j\not\equiv y_{0}}m_{\Theta }(x)_{j} הינו ערך פונקציית הלוגיט המקסימלי כאשר ϴ הם פרמטרי המודל – m ו- j אינה המחלקה התואמת ל-label ה- y_{0} של הקלט הזדוני x. 

פונקציה ההפסד J_{\Theta }^{adv}(x) רוצה להקטין את ההפרש בין ערך פונקציית הלוגיט המקסימלי לבין ערך פונקציית הלוגיט של ה-Label של הקלט הזדוני x – m_{\Theta }(x)_{y_{0}}.

בנוסף,  𝛆 תוחם את נורמה ה – ∞L_{∞} של ההפרש בין כל נקודה של הקלט הזדוני לקלט המקורי (ראו כתבה קצרה המסבירה על הנורמות השונות⁴).

לדוגמה –

במצב בינארי, נניח כי קיימת תמונה של חתול y_{0}. המחלקה של חתול מקבלת ערך לפי פונקציית הלוגיט I^{1}=1 . המחלקה של כלב (j) מקבלת ערך I^{2}=2. כלומר, לפי ערכי פונקציית הלוגיט, התמונה בעלת סיכוי יותר גבוה להיות תמונה של כלב. במצב הנתון קיים רק ערך (j) אחד שמייצג מחלקה שאינה חתול ולכן הוא יהיה מקסימלי לפי –max_{j\neq y_{0}}m_{\Theta }(x)_{j}. הפונקציה תמיד תיתן תוצאה שלילית כאשר קיים ניבוי מחלקה שגוי, כפי שניתן לראות גם בדוגמה I^{1}-I^{2}=-1 . כך, על ידי הפחתת פונקציית ההפסד עוד ועוד, נלמד כיצד למצוא הפרעה זדונית שתביא לניבוי מחלקה שגוי בהסתברות הולכת וגדלה.

איור 1 – בדוגמה עם 2 מחלקות, נראה מה קורה שהפרעה דוחפת קלט שהיה מסווג נכון מעבר לגבול ההחלטה של המודל לסיווג שגוי¹, נלקח מ – http://www.cleverhans.io/

ישנם עוד שיטות דומות ל-PGD, כמו BIM – Basic Iterative Method  וכמו Fast gradient sign method – FGSM. ההבדל היחיד² בין PGD ל – BIM הוא תנאי ההתחלה. לעומת זאת FGSM דומה לשתי השיטות האלו אך אינה איטרטיבית ומקבלת תוצאות סבירות בצעד אחד גדול².

במצבים בהם לא ניתן לקחת גרדיאנטים או שהם אינם עוזרים להתקפה ניתן לקרב אותם בעזרת שיטות סטוכסטיות. ניתן לעשות זאת בעזרת שיטה מוצלחת הנקראת SPSA – Simultaneous Perturbation Stochastic Approximation:

איור 2 – הפסאודו קוד³ נלקח מ – https://arxiv.org/pdf/1802.05666.pdf. למי שרוצה להבין לעמוק אז מצורף המאמר המקורי שעליו הפסאודו קוד מבוסס -https://www.jhuapl.edu/spsa/pdf-spsa/spall_tac92.pdf

הדבר החשוב לזכור: השוואה בין SPSA לבין PGD מראה כי אין הבדל משמעותי בתוצאות, ובמקרים מסוימים SPSA יכולה להתכנס לנקודת מינימום יותר טובה³.

2) התקפות מבוססות על אוגמנטציה מרחבית

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

איור 3 – סיבוב או הזזה דוחפים קלט שהיה מסווג בצורה נכונה לסיווג שגוי⁵-https://arxiv.org/pdf/1712.02779.pdf

3) התקפות גבול

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

איור 4 -הפסאודו קוד⁶ נלקח מ – https://arxiv.org/pdf/1712.04248.pdf

סיכום

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

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

קישורים:

¹ http://www.cleverhans.io/ – Cleverhans blog

² https://arxiv.org/pdf/1804.00097.pdf – Adversarial Attacks and Defences Competition

https://arxiv.org/pdf/1802.05666.pdf – Adversarial Risk and the Dangers of Evaluating Against Weak Attacks ³

medium.com/@montjoile/l0-norm-l1-norm-l2-norm-l-infinity-norm-7a7d18a4f40c ⁴

https://arxiv.org/pdf/1712.02779.pdf – A Rotation and a Translation Suffice: Fooling CNNs with Simple Transformations⁵

https://arxiv.org/pdf/1712.04248.pdf – Decision-Based Adversarial Attacks: Reliable Attacks Against Black-Box Machine Learning Models ⁶

⁷ https://github.com/google/unrestricted-adversarial-examples

Posted by Oz Wilson in deep
16
Dec
2018

Transfer Learning – הכללת ידע

מיועד ל- כל אחד (כתבה לא טכנית)

נכתב על ידי tomer peled

מוטיבציה

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

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

הגדרה

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

Transfer Learning

בשני מאמרים פורצי דרך [5], [4] הוכח שרשת שלמדה לפתור בעייה מסוימת – למשל סיווג תמונות מ 1000 קטגוריות המצויות ב ImageNet, יכולה בתהליך פשוט של Fine Tuning לעבור התאמה  לפתרון בעיה אחרת כגון סיווג אנשים (שלא מופיעים כקטגוריה ב ImageNet), מוצרים מחנות מכוונת או סיווג סצינות.

למעשה רוב העבודה שנעשית היום בלמידה עמוקה מבוססת על Tranfer-Learning ומאפשרת לחסוך לימוד על חומרה מרובת GPU במשך שבועות כמו שנעשה על ImageNet.

למה זה עובד ?

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

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

אז איך עושים את זה ?

תהליך ה Transfer Learning כולל לימוד מחדש של שכבת ההחלטה (סיווג או רגרסיה), תוך הקפאת (Trainable= 0, Freeze)  הלימוד בשאר השכבות. ולעיתים לאחר מכן גם לימוד של השכבות העליונות בקצב לימוד (Learning Rate) נמוך.

  • הדרך הפשוטה ביותר – ולעיתים זה כל מה שנידרש היא להשתמש ברשת מאומנת מראש על בעיה אחרת כגון ImageNet כ feature-extractor (מחלץ תכונות) ולאמן מסווג למשל Linear-SVM או SoftMax התכונות שחולצו מהתמונות שלנו.
  • הרחבה אפשרית לשיפור ביצועים נקראת כוונון עדין fine-tuning. כלומר התאמה קטנה של המשקלות בשאר הרשת.
    • מקובל להקפיא את הלימוד בשכבות הנמוכות של הרשת. מאחר שההכללה בלימוד על בסיס נתונים גדול כ Image-Net טובה מההכללה שתתקבל על סט תמונות קטן ומגוון פחות וכן ה features בשכבות אלו מבטאים אבסטרקציה כגילוי שפות וכתמים המשותפים לכלל הבעיות.
    • את השכבות העליונות ברשת מאמנים בקצב לימוד (Learning-rate) נמוך על מנת לשמור על השפעה קטנה.
    • לעיתים מאמנים בו זמנית את השכבות העליונות ברשת בקצב נמוך ואת המסווג בקצב גבוה יותר.

מקורות

Posted by tomer peled in deep
28
Nov
2018

מיני-פרויקט בלמידה חיזוקית (Reinforcement Learning)

מיועד ל- מתחילים (כתבה קצת טכנית)

נכתב על ידי תמיר נווה

אז אחרי שבניתי את הרובוט הזה (ראו את התמונה בעמוד הראשי של כל הכתבות) אני רוצה להכניס לו קצת בינה ודעת…

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

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

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

קצת טרמינולוגית RL

תודה ל https://becominghuman.ai/the-very-basics-of-reinforcement-learning-154f28a79071

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

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

Episode = אפיזודה\משחק שלם. ז”א שרשרת של מעברים ממצב ראשוני כלשהוא למצב סופי כלשהוא. במקרה של המשחק המתואר זה שרשרת המצבים מתחילת המשחק עד שהכדור מוחזק ע”י הסוכן והסוכן מגיע למשבצות האדומות.

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

π=Policy = מדיניות לפיה מחליט הסוכן איזו פעולה לבחור בכל מצב. למעשה פונקציה המקבלת מצב ומחזירה פעולה. בקוד תוכלו לראות שתי גישות אותן ניסיתי (ε-Greedy או Softmax Action Selection).

Return=G = סכום התגמולים שנתקבלו החל מצמד (פעולה, מצב) ועד לסיומה של האפיזודה

Quality=Q = טבלת הערך לכל צמד (פעולה, מצב). מחושב למשל כממוצע של כל ה-G שנתקבלו עבור על צמד (פעולה, מצב). המשמעות הינה כמה מוצלחת הפעולה הזו בהינתן המצב הזה?

Value=V = טבלת הערך לכל מצב. (לעיתים משתמשים ב V ולעיתים ב Q) המשמעות הינה עד כמה כדאי להימצא במצב הזה ? (מבחינת אפשרויות לנצחון)

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

אילו יש בידינו (בידי הסוכן) את הערכים האופטימליים לכל מצב\פעולה אז ישנן מדינויות  (Policies) לפעול כמו ε-greedy או softmax action selection. הרחבה על נושא זה תמצאו בכתבה הזו.

בכתבה זו נעסוק במספר שיטות לעידכון פונקציות הערך Q או V.

שיטת מונטה קרלו

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

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

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

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

שיטת Q-Learning

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

הערך Q עבור בחירת פעולה מסויימת At במצב מסויים St (בזמן\תור t) הינו הערך שהיה ועוד קומבינציה לינארית בין התגמול שנתקבל מפעולה זו לבין הערך הגבוה ביותר שניתן לקבל בעבור המצב הבא. (ע”י השוואה בין כל הפעולות האפשריות מהמצב החדש)

ראו כתבה קודמת ממוקדת על שיטה זו.

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

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

שיטת Deep Q-Learning

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

גם כאן ניתן לפעול לפי מדיניות כלשהיא, למשל ε-Greedy או Softmax Action Selection או כל מדיניות אחרת שמשתמשת ב Q שהרשת מספקת לכל מצב. ואת הלימוד (back propagate) של הרשת מבצעים באופן דומה ל Q Learning, תוך כדי המשחק. התהליך כולו (עליו חוזרים לאורך אפיסודות\משחקים רבים) נראה כך:

  • מזינים את המצב הנוכחי לרשת ומקבלים וקטור q1 (ערך לכל פעולה אפשרית). הפעלת זו של הרשת הינה רק קדימה ז”א ללא אימון BackPropagation.
  • בוחרים פעולה ומשחקים אותה (או בעלת הערך הגבוה ממה שיצא ברשת או אקראי תלוי במדיניות)
  • מזינים את המצב הנוכחי (שהוא החדש) לרשת ומקבלים וקטור q2 (זו שוב הפעלת הרשת קדימה ז”א ללא אימון עדיין)
  • בונים וקטור פרדיקציה (שישמש לשלב האימון) באופן הבא:

לוקחים את הווקטור q1 כאשר מחליפים בו את האלמנט של הפעולה בה בחרנו ושמים שם ערך חדש לפי נוסחת ה- Q-Learning:

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

האינטואיציה לכך: מצב ייחשב מוצלח אם ניתן להגיע ממנו למצב מוצלח אחר. (כמו במשחק השחמט: אומרים “שח” כי זה מצב ממנו ניתן לנצח בתור הבא)

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

כשאימנתי לפי שיטה זו היו דרושים יותר משחקי אימון (מאשר בשיטת Q-Learning) כדי להגיע להצלחה, אני מניח שזה מכיוון שזה קצת overkill לבעיה. היתרון הגדול בשימוש ב CNN לבעיות כאלו הם כשהמצב (state) הינו תמונה (כמו במשחקי אטארי) ולא וקטור או מטריצה (תמציתית) המתארת את המצב הנוכחי במשחק. במקרים שהמצב הוא תמונה, לתחזק טבלת ערכים לכל מצב אינו ריאלי.

טיפים לניפוי הקוד

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

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

  • חישוב והצגה של גרף של כמות האיטרציות כפונקציה של מספר האפיזודות (המשחקים) אליהן אומן הסוכן אמור להיות גרף יורד. מדד זה סיפק לי מידע אם אני בכיוון הנכון בכל הרצה. במילים אחרות: ככל שהסוכן מתאמן יותר, הוא אמור לנצח יותר מהר במשחק.
  • להשוות ביצועים של סוכן שמתנהג בצורה אקראית לגמרי (כמה תורות בממוצע ינצח במשחק ?) לעומת מודל מאומן.
  • לייצר ויזואליזציה של המשחק (זה מומלץ בכל domain), לאפשר לי משחק אינטראקטיבי (ז”א שאוכל לשחק כנגדו) שיגרום לי להבין מה בכל זאת למד המודל. למשל למד אסטרטגיות כאלו שמביאות אותו לפעולות מחזוריות ולכן לתקיעות. בכל צעד שהמודל “משחק” להציג את השיקולים שלו (ז”א את ערכי ה Q  לאותו המצב)
  • להתחיל במקרה פשוט ולאט לאט לסבך אותו (זה גם מומלץ בכל domain). במקרה זה התחלתי בלוח פשוט ביותר של 2×2 כאשר מצב הפתיחה קבוע. ואז מצב פתיחה אקראי, ואז הגדלת גודל לוח המשחק, וכו’

הסבר על הקוד

את הקוד תמצאו ב GitHub שלי !

Solve_game.py זהו הקוד הראשי שפותר את המשחק לפי כל אחת מהשיטות (זה הקוד שיש להריץ).

Game.py המחלקה המממשת את המשחק עצמו, מאפשרת לאתחל משחק לפי פרמטרים שונים, להקליט משחק, לשחק (לא משנה אם אדם או אלגוריתם), להציג לוח משחק ועוד… שימו לב למטודה state_as_tensor שמחזירה את מצב המשחק כטנזור בגודל nxnx2. כאשר n הוא גודל לוח המשבצות וערוץ אחד עבור מיקום הסוכן והערוץ השני עבור מיקום הכדור ומצבו (מוחזק או לא מוחזק ע”י הסוכן)

interactive_play.py מאפשר למשתמש (אנושי) לשחק במשחק

policies.py מאפשר מדיניות משחק: אפסילון החמדן (Greedy Epsilon) או Softmax Selection. בפרט שליטה על דעיכת הפרמטר אפסילון (ε).

Deep_Q_learning.py מימוש שיטת Deep-Q Learning כמוסבר מעלה.

tabular_learning.py מימוש שיטות מונטה קרלו או Q-Learning כמוסבר מעלה.

לסיכום

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

ראו סרטון שמדגים את תהליך הלמידה: (בהתחלה משחק אקראי וככל שמתקדם האימון משחק יותר ויותר בהגיון):


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

אשמח לשאלות ופידבקים!

Posted by תמיר נווה in deep
25
Apr
2018

המפתח לאימון רשתות נוירונים – BackPropogation

מיועד ל- מתחילים (כתבה קצת טכנית)

נכתב על ידי תמיר נווה

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

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

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

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

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

כי הרי באמת שם כביכול טמון הקסם…

התשובה הינה BackPropagation (חלחול לאחור) שהינה שיטה שהייתה ידועה בכל מיני גרסאות שונות עוד משנות השישים

(ובשנות השמונים הייתה בשימוש בעולם הרשתות נוירונים).

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

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

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

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

לרב עושים זאת תהליך (אופטימיזציה) זה באמצעות Gradient Descent שמתואר ע”י המשוואה הבאה:

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

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

זהו סוד הקסם (לפחות ברמת האינטואיציה…)

Posted by תמיר נווה in deep