טכני כבד

Oct

2022

בחירה נכונה של מודל שפה

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

נכתב על ידי yuval schreiber

בכתבה זו סיכמתי את המאמר: “ Domain-Specific Language Model Pretraining for Biomedical Natural Language Processing” שפורסם ב 16.09.21 ב arxiv. זהו מאמר מומלץ למתעניינים במודלי שפה עבור דומיינים שונים, בעיקר למתמקדים בדומיין הרפואי. המאמר כתוב בצורה ברורה ודורש היכרות בסיסית עם מודלי שפה ו-BERT. למי שרוצה להכיר יותר את המושגים הבסיסים שמוזכרים מוזמן לקרוא עוד בקישורים למטה.

מבוא

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

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

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

BERT

אוצר מילים– כדי להימנע מהבעיה בה מילים לא מופיעות באוצר המילים, ביצירת אוצר המילים לטוקנזיציה משתמשים ביחידות תתי מילים. במאמר משתמשים באלגוריתם WordPiece שהוא וריאציה של Byte-Pair Encoding (BPE) (אלגוריתם שמנסה בצורה חמדנית למצוא תתי מילים שיכולות ליצור את כל המילים, ומגדיל את אוצר המילים ע״י שרשור תתי המילים עד להגעה למספר מילים שהוגדר מראש), רק שבבחירת תתי המילים לשרשר מתבסס על מודל unigram ולא על תדירות.

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

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

פיקוח עצמי (self-supervision)– החידוש ב-BERT הוא השימוש במודל שפה ממוסך, שמחליף תת קבוצה של טוקנים באופן אקראי בטוקן [mask] ומבקש ממודל השפה לחזות אותם, לעומת מודלים מסורתיים שמנבאים את הטוקן הבא על סמך הקודמים. פונקציית המטרה היא CE בין הטוקנים הנחזים למקוריים. ב-BERT ו-RoBERTa נבחרים 15% מהטוקנים, מתוכם 80% ממוסכים 10% לא משתנים ו-10% מוחלפים בטוקן אקראי מאוצר המילים. (גישה נוספת היא להגדיל את שיעור המיסוך בהדרגה לאורך האפוקים מ-5% ל-25% מה שהופך את האימון ליציב יותר).
ב-BERT המקורי קל לחזות את הטוקנים הממוסכים מכיוון שלרוב טוקן מייצג תתי מילה וידיעת שאר המילה מקלה, במאמר משתמשים במיסוך של מילים שלמות אשר מאלץ את המודל ללכוד יותר תלויות הקשריות. בנוסף ב-BERT משתמשים גם במשימת חיזוי האם משפט אחד עוקב לשני בהינתן זוג משפטים (התועלת של משימה זו מוטלת בספק).

מודל שפה ביו-רפואי מאומן מראש (ביו-רפואה משמש כדוגמה לדומיין מסוים)

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

אימון מראש מעורבב דומיינים– הגישה הסטנדרטית לאימון מראש של BERT ביו-רפואי אשר נקראת אימון מתמשך (כמו ב-BioBERT) אשר מבצעת אימון מראש עם דומיין כללי (BERT המקורי – לכן נוח), וממשיכה את האימון על שתי המשימות (פיקוח עצמי) עם שימוש בטקסט ביו-רפואי (במקרה של BioBERT על תקצירי PubMed וכתבות מלאות של PubMed, ובמקרה של BlueBERT על PubMed והערות קליניות לא מזוהות מ-MIMIC-III).
מודל נוסף הוא SciBERT אשר מתאמן מאפס על טקסט ביו-רפואי וטקסט מדעי המחשב (שהוא מחוץ לדומיין).

אימון מראש מאפס לדומיין מסוים– הגישה המעורבת הגיונית אם לדומיין המסוים יש מעט טקסט, אך זה לא המקרה בביו-רפואה, ב-PubMed יש יותר מ-30 מיליון תקצירים ומתווספים יותר ממיליון כל שנה.
יתרון של אימון מראש לדומיין מסוים הוא שאוצר המילים בתוך הדומיין, כשהטוקנזיציה מבוססת על אוצר מילים כללי כמו ב-BERT הרבה מילים מהדומיין המסוים עשויות להתפצל באופן לא רלוונטי, למשל המחלה lymphoma תפוצל לטוקנים l-ym-ph-oma. יתרון נוסף הוא שהמודל לא מוותר על אופטימיזציה של דאטה מהדומיין על חשבון אופטימיזציות אחרות.

BLURB

בעבודות קודמות על אימון מראש ביו-רפואי השתמשו במשימות ודאטה סטים שונים כדי להעריך ביצועים, מה שהקשה להשוות ולהעריך את ההשפעה של מודלי שפה מאומנים מראש. לכן יצרו את BLURB שמתמקד ביישומי NLP ביו-רפואיים מבוססי PubMed, תוך תיעדוף בחירה של דאטה סטים ששימשו בעבודות קודמות על אימון מראש ביו-רפואי כדי שתהיה היכולת להשוות. ציון מסכם של מודל על BLURB יהיה ממוצע הציונים על סוגי המשימות הבאות: זיהוי ישות שם (NER), חילוץ מידע רפואי מבוסס ראיות (PICO), חילוץ קשרים, דמיון משפטים, סיווג מסמכים, מענה על שאלות (QA).

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

כוונון עדין ספציפי משימה

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

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

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

כדי להקל על ההשוואה במאמר מבצעים את אותו כוונון עדין לכל BERT וכל משימה, משתמשים ב-Loss CE למשימות סיווג וב-MSE למשימות לרגרסיה, מבצעים חיפוש הייפרפרמטרים ע”י שימוש בסט ה-dev עם מטריקות מתאימות למשימה, ובדומה לעבודות קודמות עושים כוונון עדין גם לראש וגם למודל הבסיסי.

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

הגדרות ניסוייות

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

תוצאות

אימון לדומיין ספציפי מראש מול אימון מעורבב דומיינים מראש–

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

השפעה של שיטות אימון מראש שונות–

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

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

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

1) מאמרים מלאים מכילים יותר רעש מתקצירים, ומכיוון שרוב המשימות מבוססות על תקצירים טקסטים מלאים עשויים להיות מעט מחוץ לדומיין.

2) גם אם הטקסטים המלאים עשויים להיות מועילים הכללתם דורשת יותר מחזורי אימון.

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

ניתן לראות שעבור משימות זיהוי ישות שם וחילוץ יחסים שכבה לינארית מספיק טובה (מכיוון ששימוש ב-BERT כבר לוכד תלויות לא לינאריות לאורך הטקסט) ושימוש ב-Bi-LSTM לא מוביל לשיפור.

השפעת סכמת התיוג במשימת NER:

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

השפעת דמיפיקציה של ישויות וקידוד קשרים:

לסימון ישויות 3 אפשרויות-

1) דמפיקציה של ישויות- החלפת הישויות שבקשר בתוויות ישויות השם שלהן

2) טקסט מקורי

3) סימוני ישויות- הוספת טוקן התחלה וסוף לפני ואחרי כל ישות בקשר

לאופן קידוד היחסים 3 אפשרויות-

1) הייצוג ההקשרי של טוקן CLS בתחילת הטקסט

2) שרשור הייצוגים של הישויות בקשר

3) במקרה של הוספת טוקני התחלה וסוף- שרשור ייצוגי טוקני ההתחלה של הישויות

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

סיכום

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

קישורים

העמקה ב-BERT ו-transformer-ים

העמקה ב-WordPiece ו-Byte Pair Encoding

העמקה ב-LSTM

העמקה ב-CRF

Sep

2022

מה זה Attention Mechanism ואיך זה עובד?

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

נכתב על ידי bar madar

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

על מנת להבין טוב יותר מהו Attention, בכתבה זאת נענה על השאלות הבאות:

מהו Attention בעולם הביולוגי, ואיך הוא מיושם בעולם ה AI?
כיצד מוגדר מנגנון Attention כללי ומהם מרכיביו?
דוגמא פרקטית לAttention במכונת תרגום
מנגנון הScaled Dot-Product Attention ב Transformers

בואו נתחיל!

Attention בעולם הביולוגי

Attention, או בעברית – “קשב”, הוא תחום רחב מאוד, שבעולם הביולוגי נחקר לעיתים קרובות בשילוב עם “עוררות”, “עירנות” ו”מעורבות סביבתית”.

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

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

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

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

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

(עכשיו אחריי שהסתכלתם על התמונה וזיהיתם את הפרי, תוכלו בלי להסתכל שוב, להגיד כמה אנשים יש בחוף? 🙂

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

Attention בעולם ה AI

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

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

מאיפה זה התחיל?

מנגנון ה Attention בלמידת מכונה,הוצג לראשונה במאמר של Bahdanau et al.(2014) בו הכותבים מנסים לפתור את בעיית צוואר הבקבוק במודלים של seq2seq מבוססים Encoder-Decoder. במודלים אלו, המידע מכל סדרת הקלט, נאסף לווקטור בעל מימד קבוע במוצא ה Encoder(hidden vector). ככל שהסדרה יותר ארוכה או מורכבת, ככה היכולת של אותו ווקטור “לתפוס” את המידע הרלוונטי מכל הקלט פוחתת. כתוצאה מכך, כאשר הקלט הוא ארוך ומורכב, הביצועים של מודלים אלו פוחתים, מכיוון שמידע רלוונטי “נשכח” ולא מתבטא ב hidden vector שהופך להיות צוואר הבקבוק של המודל.

במאמר, הכותבים הציגו את מנגנון ה Attention עבור מודל Encoder-Decoder, אשר מומש ע”י ארכיטקטורת RNN לכל אחד מהצדדים.

כאן בכתבה, נציג תחילה את האלגוריתם הכללי למימוש מנגנון ה Attention, ולאחר מכן נראה כיצד הוא בא לידי ביטוי במודלי ה Transformers הנפוצים היום בעולם ה NLP וה VISION.

אז איך זה עובד?

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

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

Q – queries
K – keys
V – values

לכל איבר i בסדרה (word embedding – במקרה שלנו), יחושבו 3 ייצוגים וקטוריים נלמדים (Qi, Ki, Vi). ייצוג הקלט (נניח של מילים) כווקטור מספרים זו בעיה מורכבת, ולכן נותנים לרשת כמה אפשריות בלתי תלויות ללמוד אותם.

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

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

$ q_i=W^q \cdot x_i $

עבור קלט של T מילים {w_t}, מנגנון ה Attention מורכב מהשלבים הבאים:

עבור כל מילה, מחשבים scores אל מול שאר המילים. ה scores מחושבים ע”י מכפלה סקלרית בין ווקטור q של המילה עם ווקטורי k של שאר המילים (כולל זה ששייך לאותה מילה).

לדוגמא ה score של מילה i אל מול מילה j

$ e_{i,j}=q_i \cdot k_j $ חשוב לשים לב $ e_{i,j} \neq e_{j,i} $

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

לדוגמא זהו ווקטור המשקלים של מילה i:

$ α_i = softmax({e_{i,t}})_{t=1..T} $

3. עבור כל מילה, ה attention מחושב ע”י סכום משוקלל של כל ווקטורי ה value בדאטה v_t=1..T יחד עם המשקלים היחסיים שחישבנו בשלב הקודם

לדוגמא:

$attention(w_i)=\sum_{t=1}^{T} \alpha_{i,t}v_t $

ווקטור ה attention שמייצג את מילה w_i

כאשר v_t הוא הווקטור התואם ל k_t , שעל בסיסו חישבנו את המשקל α_t.

דוגמא פרקטית – מכונת תרגום (Machine Translation)

נניח שיש לנו מודל מתרגם מבוסס Encoder-Decoder – הקלט ל Encoder זה טקסט בצרפתית, ומוצא ה Decoder – הטקסט באנגלית.

כל מילה בטקסט הנקלט מיוצגת ע”י 3 ווקטורים שנשמרים בזיכרון המודל (q_i, k_i, v_i) ,אשר מחושבים ע”י מכפלה של ווקטור המוצא ב Encoder(x_i) עם 3 המטריצות המשותפות לדאטה שנלמדות תוך כדיי האימון (W^q, W^k, W^v).

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

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

ווקטור ה attention שחישבנו ייכנס ל decoder ובמוצא תיפלט לנו המילה המתורגמת.

עבור המילה הבאה בתור (x_t+1), נבצע את אותו תהליך, כאשר הפעם נשתמש רק בווקטור ה query שלה (q_t+1), והמשקלים יחושבו בעזרת צמדי ווקטורי key, value של כל המילים שהמודל ראה עד נקודת הזמן הנוכחית – {v_t , k_t ; t=1..i+1}

*חשוב לציין – בשונה מהדוגמא הקלאסית, בהרבה מקרים ומודלים, מנגנון ה Attention ממומש באופן Bi-directional, כלומר ה attention של כל איבר ברצף (מילה לדוגמא) מחושב לפי המילים שהיו לפניה ואחריה במשפט. לצורת ה Bi-directional יש יתרון עצום בהבנת קונטקסט הרצף בצורה טובה יותר.

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

דוגמא למודל Bi-directional נפוץ שעושה שימוש ב Attention–BERT.

מנגנון ה Scaled Dot-Product Attention ב Transformers

ככל הנראה, רובכם נחשפתם לראשונה למנגנון ה Attention בהקשר של מודלי ה Transformers שפרצו את תקרת הזכוכית בעולם ה NLP ולאחרונה נהיו גם שם חם בעולם ה VISION.

ה Transformer, הוצג לראשונה במאמר Attention is all you need (2017),ובבסיסו, הוא מודל seq2seq, מבוסס ארכיטקטורות של encoder-decoder שהחידוש העיקרי בו, זה השימוש הייחודי במנגנון ה Attention, לטובת מיקוד ה”קשב” בין כל איבר בסדרה לשאר האיברים.

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

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

המרכיבים העיקריים של מנגנון ה Attention ב Transformers הם:

q, k – ווקטורים בגודל d_k, מכילים את ה query,key לכל איבר ברצף.
v – ווקטור בגודל d_v , מכיל את ה value לכל איבר ברצף.
Q, K, V – מטריצות שמאחדות סט של ווקטוריqueries, keys, values בהתאמה.
W^q, W^k, W^v – מטריצות הטלהממרחב הדאטה הנקלט (word embedding למשל) אל תתי המרחבים של ה queries, keys, values
W^o – מטריצת הטלה למוצא ה Multi-Head (נפרט בהמשך)

במאמר, הכותבים מציגים גרסה שונה מעט ממנגנון ה Attention הכללי, וקוראים לה Scaled Dot-Product Attention, ועליה בונים את קונספט ה Multi-head Attention.

כפי שתיארנו במנגנון ה Attention הכללי, גם כאן ווקטורי ה q, k, v (הטלות שונות של האיברים ברצף) הם האינפוטים למנגנון ה Scaled Dot-Product Attention.

כשמו הוא, מנגנון ה Scaled Dot-Product Attention, מחשב תחילה מכפלה סקלרית לכל ווקטור q עם כל ווקטורי הk, לאחר מכן ה scale על התוצאה מתבטא בחילוק של המכפלה ב

$ \sqrt{d_k} $

לקבלת הscore.

בהמשך, כמו במנגנון הAttention הכללי, הscores עוברים בפונקציית Softmax לקבלת המשקלים שמשמשים למשקול ווקטורי ה values.

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

לפיכך, החילוק ב scaling factor שבמקרה שלנו הוא

$ \sqrt{d_k} $

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

ובהמשך המשקלים שיוצאים מה softmax

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

לכן, נגדיר את Q, K, V להיות המטריצות שמהוות את הקלט למנגנון (נבצע חישוב מקדים של ווקטורי הq, k, v לכל איבר ברצף ע”י מטריצות ה (W^q,W^k,W^v), ולאחר מכן נשרשר אותם לקבלת מטריצות Q, K, V).

ונקבל את נוסחת ה Scaled Dot-Product Attention:

$ Attention(Q,K,V)=softmax( \dfrac{QK^t}{\sqrt{d_k}}) $

כעת, נציג את תהליך חישוב ה Scaled Dot-Product Attention, שלב אחריי שלב:

m – כמות האיברים ברצף שנרצה לחשב עבורם את ייצוג הScaled Dot-Product Attention
n – כמות האיברים ברצף שנרצה להתחשב בהם כקונטקסט שעל בסיסו נחשב לכל ווקטור את ייצוג הScaled Dot-Product Attention

חישוב ה scores, ע”י מכפלה סקלרית של סט ווקטורי הquery (שורות של מטריצה Q), עם סט ווקטורי ה keys (שורות של מטריצה K).

אם מטריצה Q בגודל nxd_k, ומטריצה K בגודל mxd_k, תוצאת המכפלה תיהיה בגודל mxn

$ QK^T=\begin{pmatrix} e_{11} e_{12} … e_{1n} \\ e_{21} e_{22} … e_{2n} \\ … … … … \\ e_{m1} e_{m2} … e_{mn} \\ \end{pmatrix} $

2. נבצע scaling לכל score ע”י חילוק בפקטור

$ \sqrt{d_k} $

$ \dfrac{QK^t}{\sqrt{d_k}}=\begin{pmatrix} \dfrac{e_{11}}{\sqrt{d_k}} \dfrac{e_{12}}{\sqrt{d_k}} … \dfrac{e_{1n}}{\sqrt{d_k}} \\ \dfrac{e_{21}}{\sqrt{d_k}} \dfrac{e_{22}}{\sqrt{d_k}} … \dfrac{e_{2n}}{\sqrt{d_k}} \\ … … … … \\ \dfrac{e_{m1}}{\sqrt{d_k}} \dfrac{e_{m2}}{\sqrt{d_k}} … \dfrac{e_{mn}}{\sqrt{d_k}} \\ \end{pmatrix} $

3. הפעלת Softmax על מנת לקבל סט משקלים עבור כל איבר

$ softmax(\dfrac{QK^t}{\sqrt{d_k}})=\begin{pmatrix} softmax(\dfrac{e_{11}}{\sqrt{d_k}}) softmax(\dfrac{e_{12}}{\sqrt{d_k}}) … softmax( \dfrac{e_{1n}}{\sqrt{d_k})} \\ softmax(\dfrac{e_{21}}{\sqrt{d_k}}) softmax(\dfrac{e_{22}}{\sqrt{d_k}}) … softmax(\dfrac{e_{2n}}{\sqrt{d_k}}) \\ … … … … \\ softmax(\dfrac{e_{m1}}{\sqrt{d_k}}) softmax(\dfrac{e_{m2}}{\sqrt{d_k}}) … softmax(\dfrac{e_{mn}}{\sqrt{d_k}}) \\ \end{pmatrix} $

4. חישוב סכום משוקלל של סט ווקטורי ה value (שורות של מטריצה V), לקבלת ייצוג ה Scaled Dot-Product Attention

מטריצת V בגודל nxd_v, ולכן התוצאה תהיה מטריצה בגודל mxd_v כשכל שורה היא ווקטור ייצוג ה Scaled Dot-Product Attention עבור האיבר התואם במטריצת Qd_v ובגודל של

$ softmax(\dfrac{QK^t}{\sqrt{d_k}}) \cdot V=\begin{pmatrix} softmax(\dfrac{e_{11}}{\sqrt{d_k}}) softmax(\dfrac{e_{12}}{\sqrt{d_k}}) … softmax( \dfrac{e_{1n}}{\sqrt{d_k})} \\ softmax(\dfrac{e_{21}}{\sqrt{d_k}}) softmax(\dfrac{e_{22}}{\sqrt{d_k}}) … softmax(\dfrac{e_{2n}}{\sqrt{d_k}}) \\ … … … … \\ softmax(\dfrac{e_{m1}}{\sqrt{d_k}}) softmax(\dfrac{e_{m2}}{\sqrt{d_k}}) … softmax(\dfrac{e_{mn}}{\sqrt{d_k}}) \\ \end{pmatrix} \cdot \begin{pmatrix} v_{11} v_{12} … v_{1d_v} \\ v_{21} v_{22} … v_{2d_v} \\ … … … … \\ v_{n1} v_{n2} … v_{nd_v} \end{pmatrix}= \begin{pmatrix} \widetilde{x_1} \\ … \\ \widetilde{x_m} \end{pmatrix} $

Multi Head Attention

על בסיס המנגנון שהראינו, כותבי המאמר הציגו תוספת של Multi Head לתהליך.

ההבדל במימוש הוא שבמקום ליצור סט אחד של ווקטורי queries, keys, values לכל איבר ברצף ע”י סט יחיד ומשותף של מטריצות {W_k,W_q,W_V}, מנגנון ה Multi Head Attention

מייצר h סטים כאלה ע”י h סטים משותפים של מטריצות.

$ \{W^q_i,W^k_i,W^v_i \}_{i=1}^h $

לאחר מכן, מנגנון ה Scaled Dot-Product Attention מופעל במקביל על כל אחת מ h ההטלות(ללא תלות אחת בשנייה) ומקבלים במוצא h ווקטורי attention לכל אחד מ m האיברים ברצף.

לאחר מכן, מבצעים שרשור בין כל h הווקטורים ששייכים לכל איבר, לקבלת ווקטור בודד בגודל 1 xhd_v . הווקטור המשורשר מוטל ע”י מטריצה W^o לקבלת ווקטור הייצוג הסופי.

הרעיון שעומד מאחורי ה Multi Head Attention הוא שכעת פונקציית ה attention יכולה לחלץ מידע מהאיברים ברצף שהם מיוצגים במספר תתי מרחב שונים וכך היכולת לחלץ מידע שתומך במשימה ולהדגיש אותו גדלה משמעותית.

פונקצייתה Multi Head Attention יכולה להיות מתוארת בצורה הבאה:

$ multihead(X)=concat(head_1,head_2,…head_h) \cdot W^o \\ s.t: head_i=attention(X \cdot W^i_q, X \cdot W^i_k, X \cdot W^i_v) $

לסיכום

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

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

מאמר המציג את השימושים ב attention בעולם ה Computer Vision:

Attention Mechanisms in Computer Vision: A Survey(2021)

אם לאחר קריאת הכתבה צצות לכם שאלות או שתרצו הרחבה נוספת בנושאים קשורים, מוזמנים לכתוב לי למייל או ליצור קשר ב LinkedIn ואשמח לנסות לעזור 🙂

Barmadar13@gmail.com

https://www.linkedin.com/in/bar-madar-838b15160/

Mar

2021

מהו Variational AutoEncoders?

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

נכתב על ידי avraham raviv

כדי להבין היטב את אופן הפעולה של Variational Autoencoders (VAE), נדבר מעט על הורדת מימדים, לאחר מכן נסביר מהו Autoencoders, כיצד הוא עובד ומה החסרונות שלו, ומשם נעבור ל-VAE.

Dimensionality Reduction

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

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

תהליך האימון הוא דו שלבי: דאטה $x\in R^{n}$ עובר דרך encoder, ולאחריו מתקבל $e(x)\in R^{m}$ , כאשר $m<n$ לאחר מכן התוצאה מוכנסת ל-decoder בכדי להחזיר אותה למימד המקורי, ולבסוף מתקבל $d(e(x)) \in R^{^{n}}$ אם לאחר התהליך מתקיים $x=d(e(x))$ אז למעשה לא נאבד שום מידע בתהליך, אך אם לעומת זאת $x\neq d(e(x))$ אז מידע מסוים אבד עקב הורדת המימד ולא היה ניתן לשחזר אותו במלואו בפענוח. באופן אינטואיטיבי, אם אנו מצליחים לשחזר את הקלט המקורי מהייצוג של במימד נמוך בדיוק טוב מספיק, כנראה שהייצוג במימד נמוך הצליח להפיק את הפיצ’רים המשמעותיים של הדאטה המקורי.

איור 1. ארכיטקטורת encoder ו-decoder.

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

$(e^{*},d^{*})=\underset{(e,d)\in ExD}{argmin}\epsilon (x,d(e(x)))$

כאשר $\epsilon (x,d(e(x)))$ הוא שגיאת השחזור שבין הדאטה המקורי לבין הדאטה המשוחזר.

אחת השיטות השימושיות להורדת מימד שאפשר להסתכל עליה בצורה הזו היא Principal Components Analysis (PCA). בשיטה זו מטילים (בצורה לינארית) דאטה ממימד n למימד m על ידי מציאת בסיס אורתוגונלי במרחב ה-m מימדי בו המרחק האוקלידי בין הדאטה המקורי לדאטה המשוחזר מהייצוג החדש הוא מינימלי.

איור 2. דוגמא להורדת מימד בשיטת PCA.

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

Autoencoders (AE)

ניתן לקחת את המבנה של ה- encoder-decoder המתואר בפרק הקודם ולהשתמש ברשת נוירונים עבור בניית הייצוג החדש ועבור השחזור. מבנה זה נקרא Autoencoder:

איור 3. Autoencoder – שימוש ברשתות נוירונים עבור הורדת המימד והשחזור.

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

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

איור 4. דוגמא לשימוש ב-Autoencoder.

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

Variational AutoEncoders (VAE)

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

כדי להתמודד עם בעיה זו, ניתן להשתמש ב-Variational AutoEncoders (VAE). בשונה מ-AE שלוקח דאטה ובונה לו ייצוג ממימד נמוך, VAE קובע התפלגות פריורית למרחב הלטנטי z – למשל התפלגות נורמלית עם תוחלת 0 ומטריצת II covariance. בהינתן התפלגות זו, ה-encoder מאמן רשת המקבלת דאטה x ומוציאה פרמטרים של התפלגות פוסטריורית z|x , מתוך מטרה למזער כמה שניתן את ההפרש בין ההתפלגויות z ו- z|x . לאחר מכן דוגמים וקטורים מההתפלגות הפוסטריורית z|x (הנתונה על ידי הפרמטרים המחושבים ב-encoder), ומעבירים אותם דרך ה-decoder כדי לייצר פרמטרים של ההתפלגות z|x . חשוב להבהיר שאם הדאטה המקורי הוא תמונה המורכבת מאוסף של פיקסלים, אזי במוצא יתקבל x|z לכל פיקסל בנפרד ומההתפלגות הזו דוגמים נקודה והיא תהיה ערך הפיקסל בתמונה המשוחזרת. באופן הזה, הלמידה דואגת לא רק להורדת המימד, אלא גם להתפלגות המושרית על המרחב הלטנטי. כאשר ההתפלגות המותנית במוצא x|z טובה, קרי קרובה להתפלגות המקורית של x, ניתן בעזרתה גם ליצור דוגמאות חדשות, ובעצם מתקבל מודל גנרטיבי. כאמור, ה-encoder מנסה לייצג את הדאטה המקורי באמצעות התפלגות במימד נמוך יותר, למשל התפלגות נורמלית עם תוחלת ומטריצת covariance: $z\sim p(z|x)=N(\mu _{z},\sigma _{x})$

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

איור 5. ארכיטקטורה של VAE.

לאחר שהוצג המבנה הכללי של VAE, ניתן לתאר את תהליך הלמידה, ולשם כך נפריד בשלב זה בין שני החלקים של ה-VAE. ה-encoder מאמן רשת שמקבלת דוגמאות מסט האימון, ומנסה להפיק מהן פרמטרים של התפלגות הקרובים כמה שניתן להתפלגות פריורית , שכאמור נקבעה מראש. מההתפלגות הנלמדת הזו דוגמים וקטורים חדשים ומעבירים ל-decoder. ה- decoderמבצע את הפעולה ההפוכה – לוקח וקטור שנדגם מהמרחב הלטנטי , ומייצר באמצעותו דוגמא חדשה הדומה לדאטה המקורי. תהליך האימון יהיה כזה שימזער את השגיאה של שני חלקי ה-VAE – גם שבמוצא יהיה כמה שיותר קרוב ל- המקורי, וגם ההתפלגות תהיה כמה שיותר קרובה להתפלגות הפריורית z. נתאר באופן פורמלי את בעיית האופטימיזציה ש-VAE מנסה לפתור. נסמן את הווקטורים של המרחב הלטנטי ב-z, את הפרמטרים של ה-decoder ב- $\theta$ , ואת הפרמטרים של ה-encoder ב- $\lambda$ . כדי למצוא את הפרמטרים האופטימליים של שתי הרשתות, נרצה להביא למקסימום את $p(\widehat{x}=x;\theta)$ , כלומר למקסם את הנראות המרבית של סט האימון תחת $\theta$ . כיוון שפונקציית log מונוטונית, נוכל לקחת את לוג ההסתברות:

$L(\theta)=log(p(x;\theta ))$

אם נביא למקסימום את הביטוי הזה, נקבל את ה- $\theta$ האופטימלי. כיוון שלא ניתן לחשב במפורש את $p(x;\theta )$ , יש להשתמש בקירוב. נניח וה -encoder הוא בעל התפלגות מסוימת $q(z;\lambda )$ (מה ההסתברות לקבל את z בהינתן x בכניסה). כעת ניתן לחלק ולהכפיל את $L(\theta )$ ב – $q(z;\lambda )$ :

$log[p(x;\theta )]=log \underset{z}{\Sigma}p(x,z;\theta )=log\underset{z}{\Sigma}q(z;\lambda )\frac{p(x,z;\theta)}{q(z;\lambda)}\geqslant \underset{z}{\Sigma}q(z;\lambda)log\frac{p(x,z_{i};\theta)}{q(z;\lambda)}$

כאשר אי השוויון האחרון נובע מאי-שוויון ינסן, והביטוי שמימין לאי השיוויון נקרא Evidence Lower BOund $ELBO(\theta,\lambda)$ . ניתן להוכיח שההפרש בין ה-ELBO לבין הערך שלפני הקירוב הוא המרחק בין שתי ההתפלגויות $p(z|x),q(z)$ , והוא נקרא Kullback–Leibler divergence ומסומן ב- $D_{KL}$ :

$log[p(x;\theta)]=ELBO(\theta,\lambda)+D_{KL}(q(z;\lambda)||p(z|x;\theta))$

אם שתי ההתפלגויות זהות, אזי מרחק $D_{KL}$ ביניהן הוא 0 ומתקבל שוויון: $log[p(x;\theta)]=ELBO(\theta,\lambda)$ . כזכור, אנחנו מחפשים למקסם את פונקציית המחיר $log[p(x;\theta)]$ , וכעת בעזרת הקירוב ניתן לרשום:

$L(\theta)=log[p(x;\theta)]\geqslant ELBO(\theta,\lambda)$

$\rightarrow \theta_{ML}=arg\underset{\theta}{max}L(\theta)=arg\underset{\theta}{max}\underset{\lambda}{max}ELBO(\theta,\lambda)$

כעת ניתן בעזרת שיטת GD למצוא את האופטימום של הביטוי, וממנו להפיק את הפרמטרים האופטימליים של ה-encoder ושל ה-decoder. נפתח יותר את ה- $ELBO(\theta,\lambda)$ עבור VAE, ביחס לשתי התפלגויות: $p(x|z;\theta)$ – ההסתברות ש-decoder עם סט פרמטרים $\theta$ יוציא x בהינתן z. $q(z|x;\lambda)$ – ההסתברות ש-encoder עם סט פרמטרים $\lambda$ יוציא את $z_{i}$ בהינתן x בכניסה לפי הגדרה:

$ELBO(\theta, \lambda)=\underset{z}{\Sigma}q(z|x;\lambda)log[p(x,z;\theta)]-\underset{z}{\Sigma}q(z|x;\lambda)log[q(z|x;\lambda)$

את הביטוי $log[p(x,z;\theta)]$ ניתן לפתוח לפי בייס:

$p(x,z)=p(x|z)\cdot p(z)$

$={\underset{z }{\sum}}q(z|x;\lambda)(log[p(x|z;\theta)]+log[p(z;\theta))])-{\underset{z }{\sum}}q(z|x;\lambda)log[q(z|x;\lambda)]$

$={\underset{z }{\sum}}q(z|x;\lambda)(log[p(x|z;\theta)]-{\underset{z }{\sum}}q(z|x;\lambda)(log[q(z|x;\lambda)]-log[p(z;\theta)])$

$={\underset{z }{\sum}}q(z|x;\lambda)(log[p(x|z;\theta)]-{\underset{z }{\sum}}q(z|x;\lambda)\frac{log[q(z|x;\lambda]}{log[p(z;\theta]}])$

הביטוי השני לפי הגדרה שווה ל- $D_{KL}(q(z|x;\lambda)||p(z;\theta))$ , לכן מתקבל:

$=\underset{z}{\sum}q(z|x;\lambda)log[p(x|z;\theta)]-D_{KL}(q(z|x;\lambda)||p(z))$

הביטוי הראשון הוא בדיוק התוחלת של $log[p(x|z;\theta)]$ . תחת ההנחה ש-z מתפלג נורמלית, ניתן לרשום:

$=E_{q(z|x;\lambda)}logN(x;\mu_{\theta}(z),\sigma_{\theta}(z))-D_{kl}(N(\mu_{\lambda}(x),\sigma_{\lambda}(x))||N(0,I)))$

כדי לחשב את התוחלת ניתן פשוט לדגום דוגמאות מההתפלגות $z|x\sim N(\mu_{\theta}(x),\sigma_{\theta}(x)))$ ולקבל:

$E_{q(z|x;\lambda)}logN(x;\mu_{\theta}(z),\sigma_\theta(z))\approx logN(x;\mu_{\theta}(z),\sigma_{\theta}(z))$

ועבור הביטוי השני יש נוסחה סגורה:

$D_{KL}(N(\mu,\sigma^{2})||N(0,I))=\frac{1}{2}(\mu^2+\sigma^2-log \sigma^2)$

כעת משיש בידינו נוסחה לחישוב פונקציית המחיר, נוכל לבצע את תהליך הלמידה. יש לשים לב שפונקציית המחיר המקורית הייתה תלויה רק ב- $\theta$ , , אך באופן שפיתחנו אותה היא למעשה דואגת גם למזעור ההפרש בין הכניסה למוצא, וגם למזעור ההפרש בין ההתפלגות הפריורית z לבין ההתפלגות z|x שבמוצא ה-encoder.

איור 6. תהליך הלמידה של VAE.

כאשר נתון סט דוגמאות , ניתן להעביר כל דוגמא $x_{t}$ ב-encoder ולקבל עבורה את $\mu _{\lambda },\sigma _{\lambda }$ . לאחר מכן דוגמים וקטור לטנטי z מההתפלגות עם פרמטרים, מעבירים אותו ב-decoder ומקבלים את $\inline \mu _{\theta},\sigma _{\theta}$ . לאחר התהליך ניתן להציב את הפרמטרים המתקבלים ב-ELBO ולחשב את ה-Loss. ניתן לשים לב שה-ELBO מורכב משני איברים – האיבר הראשון מחשב את היחס בין הדוגמא שבכניסה לבין ההתפלגות שמתקבלת במוצא, והאיבר השני מבצע רגולריזציה להתפלגות הפריורית במרחב הלטנטי. הרגולריזציה גורמת לכך שההתפלגות במרחב הלטנטי z|x תהיה קרובה עד כמה שניתן להתפלגות הפריורית z. אם ההתפלגות במרחב הלטנטי קרובה להתפלגות הפריורית, אז ניתן בעזרת ה-decoder ליצור דוגמאות חדשות, ובמובן הזה ה-VAE הוא מודל גנרטיבי.

הדגימה של z מההתפלגות במרחב הלטנטי יוצרת קושי בחישוב הגרדיאנט של ה-ELBO, לכן בדרך כלל מבצעים Reparameterization trick – דוגמים $z_{0}$ מהתפלגות נורמלית סטנדרטית, ואז כדי לקבל את z משתמשים בפרמטרים של ה-encoder:

$z=z_{0}\sigma _{\lambda}(x)+\mu _{\lambda }(x)$

.forward-backwardבגישה הזו כל התהליך נהיה דטרמיניסטי – מגרילים מראש $z_{0}$ ואז רק נשאר לחשב באופן סכמתי את ה

Reference:

https://towardsdatascience.com/understanding-variational-autoencoders-vaes-f70510919f73

Sep

2020

אלגוריתם Reinforce – Vanilla Policy Gradients

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

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

כשמתפרסם מאמר ב Science בתחום שלי (Machine Leaning) זה משהו מיוחד כי זה לא קורה כל יום.

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

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

לא הצלחתי למצוא תירגום טוב למונח: גראדיאנטים של מדיניות (אשמח לעזרה…)

אבל Policy Gradient הינה גישה אלגוריתמית לפתירת בעיות Reinforcement Learning שנגזרו ממנה אלגוריתמים רבים כגון: Actor Critic, A2C, A3C, TRPO, PPO, SAC ועוד ועוד…

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

רקע קצר על למידה באמצעות חיזוקים (Reinforcement Learning)

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

השפה המתמטית לתיאור בעיה זו היא תהליך החלטות מרקובי MDP=Markov Decision Process:

מקור: https://he.wikipedia.org/wiki/%D7%AA%D7%94%D7%9C%D7%99%D7%9A_%D7%94%D7%97%D7%9C%D7%98%D7%94_%D7%9E%D7%A8%D7%A7%D7%95%D7%91%D7%99

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

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

כעת חלק הכיפי,

פורמליזם מתמטי לתיאור הבעיה

בכל נקודת זמן t יש לנו מצב, פעולה ותגמול:

ומאחורי הקלעים קיימת פונקציית הסתברות המעברים בין המצבים:

שמשמעותה: מה ההסתברות שאם התחלנו במצב St והסוכן בחר לבצע פעולה At הסביבה עברה למצב St+1.

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

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

מסלול (Trajectory) סופי הינו וקטור של השלשות הבאות:

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

כל אחד מהאלמנטים במסלול 𝜏 הינו וקטור אקראי, וההסתברות לקבל מסלול שלם הינה:

ההסתברות לקבל מסלול 𝜏 היא מכפלת ההסתברות להיות במצב הראשון S1 כפול

ההסתברות לבחור פעולה A1 כפול ההסתברות לעבור למצב S2 כפול ההסתברות לבחור פעולה A2 וכו’…

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

פונקציית המטרה שלנו J שאותה נאפטם (ז”א נשאף למצוא לה מקסימום) הינה התוחלת של סכום התגמולים:

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

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

נשים לב ש כולל בתוכו למעשה גם את על אף שהסימון אינו מייצג זאת.

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

התחום Reinforcement Learning אומנם יושב תחת המטריה הרחבה של עולם ה Machine Learning אבל הוא אינו Supervised Learning וגם אינו Unsupervised Learning כי זה לא שיש לנו Ground Truth של אילו החלטות היה הסוכן אמור לבחור בכל צעד שלו, אבל מצד שני גם לא יהיה נכון לומר שלא קיים ברשותינו מידע לגבי מה נכון ומה לא כי יש לנו את התגמולים. ולכן זה מן תחום כלאיים בין Supervised לבין Unsupervised.

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

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

כידוע בלמידה עמוקה משתמשים ב Gradient Descent (או בשיכלולים שלו) כדי לאמן את המודל:

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

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

אז מה עושים בכל זאת ?

מכיוון שלכל f(x) מתקיים:

נוכל להשתמש בזה לטובתינו:

ולקבל:

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

נשים לב שההסתברות לקבלת מסלול תלויה ב θ אבל סך התגמולים אינו תלוי ב θ עבור מסלול מסויים 𝜏.

הטריק הזה שהוסיף לנו log עזר לנו להמנע מנגזרת של מכפלות.

נזכור שההסתברות לקבל מסלול היא מכפלת ההסתברויות של המעברים בתוך המסלול:

וכשמפעילים על מכפלות אלו לוג זה הופך לסכומי הסתברויות:

ואז הגרדיאנט שלנו לפי θ נהיה פשוט יותר כי כל מה שלא תלוי בו מתאפס:

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

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

כאשר i רץ על פני כל ה trajectories שהקלטנו ו t הוא האינדקס בכל trajectory.

פירוש לתוצאה:

המרכיב השמאלי בביטוי הוא ה Maximum Likelihood של ההסתברות ז”א הוא מבטא איך לעדכן את המשקולות כדי שבסבירות גבוהה יותר הסוכן יעבור את המסלולים שאגרנו.

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

צעד אחרון לפני מימוש

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

אז עידכון המשקולות נהיה בפועל:

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

לשם הפשטות נתעלם ממטריצת הקוואריאנס ומהחצי המופיע בביטוי. (נניח שמטריצת הקוואריאנס הינה מטריצת היחידה וממילא החצי נבלע ב Learning Rate):

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

וכעת כשמסתכלים על מימושים הכל נראה ברור יותר… לא כך ?

מקורות

May

2020

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

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

נכתב על ידי Elinor Rahamim

מהי אופטימיזציה ולמה היא משמשת?

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

סוג האלגוריתם השכיח ביותר באופטימיזציה ובמיוחד בתחום ML, הוא Gradient Descent (להלן: “GD”) . זהו אלגוריתם איטרטיבי המאפשר מינימיזציה של פונקציית ה-loss שאנחנו מגדירים. פונקציית ה-loss הלוא היא פונקציית המטרה שבעזרתה אנו מדריכים את המודל ומסבירים לו אילו פעולות הוא עושה טוב ואילו לא. GD מאפשר לשנות כל פרמטר לחוד בצורה כזו שתקדם את מטרת האופטימיזציה.

אופטימיזציה בעזרת GD היא השכיחה ביותר בתחום ה- Deep Learning בעיקר עקב הדרישה לעדכון מס’ עצום של פרמטרים במהלך ה-Backpropagation.

מה הרעיון הכללי ב-GD?

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

להלן האלגוריתמים הנפוצים והשמישים ביותר מתוך: Gradient Descent Optimizers Algorithms

1. Classic GD – זהו האלגוריתם הקלאסי ממשפחת GD, אלגוריתם זה מייצג את המבנה הבסיסי לכל אלו הבאים אחריו. בעזרת גזירת פונקציית Loss, אותה הגדרנו במודל, לפי כל אחד ממקדמי המשתנים (מסומנים כ θ) המסבירים בדאטה, ניתן למצוא את משקל הפרמטרים האופטימלי במודל. GD מתקדם בכל איטרציה בכיוון ה-Gradient כפול עד שהוא מצליח להגיע לנקודה האופטימלית ביותר בהינתן הנתונים ושיעור הלמידה שהכתבנו מראש.

Classic GD Algorithm:

2. Momentum – ל-SGD יש קושי לנווט בסביבת מינימום מקומי עקב המהירות אליה הוא מגיע, הוא תנודתי מאוד ופחות מכוון. שימוש בשיטת המומנטום עוזר ל-SGD להאיץ בכיוון הנכון ומקטין את התנודתיות באמצעות הוספת פרמטר חיכוך, . בכל איטרציה הוא מחשב ה-Gradient צועד לפיו ואז מתקן באמצעות . בפועל Momentum דואג לעדכן ולתת משקל גדול יותר למשתנים בעלי אותו כיוון כמו כיוון הכללי ולהקטין את משקלם של אלו הנמצאים בכיוון ההפוך. על הפרמטר להיות קטן מ-1, ובדרך כלל נהוג לקבוע 0.9 = , אך אין זה מחייב כלל.

Momentum Algorithm:

3. Nesterov Accelerated Gradient – אלגוריתם זה דומה ברעיון ל-Momentum, אך עם שיפור נוסף. במקום השימוש בוויסות האלגוריתם רק באמצעות חיכוך, בעזרת NAG האלגוריתם מקבל מושג מה הוא הכיוון שלו מלכתחילה ואיך הוא צריך להתכוונן. NAG מסתמך על כך שהכיוון שאליו הלך בעדכון הקודם הוא אותו כיוון גם בפעם הזו. לכן הוא קודם צועד לפי ה-Gradient שחישב קודם, ומבצע תיקון בעזרת מקדם החיכוך , אחר כך הוא מחשב את ה-Gradient הנוכחי, צועד לפיו ומתקן בעזרת .

NAG Algorithm:

4. Adagrad – זהו אלגוריתם GD עם Learning Rate מותאם, . Adagrad מתאים שיעור הלמידה אחר לכל אחד מהמשתנים המסבירים. במילים אחרות ופשוטות לכל משתנה מסביר בדאטה יש את הקצב שלו והרעיון הוא לא להשאיר אף מאחור מדי או קדימה מדי. עבור כל אחד מהמשתנים הוא מווסת את גודל הצעד ושואף ליישר קו בין כולם. שיטה זו עוזרת לשמור על יציבות המודל במהלך האימון. על אף יתרונותיו של Adagrad, חולשתו הגדולה מתבטאת בכך שהערך של V גדל חיובי בכל איטרציה, V מתעדכן בעזרת ה-Gradient בריבוע, , ומהר מאוד ערכו הופך להיות גדול מדי. שיעור הלמידה מתכווץ מהר לערך קטן מדי, וגורם לכך שתהליך האימון הופך איטי מאוד ופחות יעיל. בסופו של דבר שיעור הלמידה מתכנס לערך השואף ל-0 והמשקולות של הפרמטרים מפסיקות להתעדכן בשלב מוקדם מדי באימון ותהליך האופטימיזציה נפסק.

Adagrad Algorithm:

5. Adadelta – אלגוריתם זה הוא מעין הרחבה ל-Adagrad אשר בא לפתור את בעיית ההתכנסות המהירה של שיעור הלמידה כלפי מטה. אמנם הרעיון של Adagrad היה להתאים לכל משתנה מסביר שיעור למידה אחר, אך בגלל שפרמטר a שמראש נקבע, האלגוריתם הוגבל וכשל במצבים מסוימים. ב-Adadelta מתגברים על בעיה זו באמצעות הגבלתו של ה-Gradient המצטבר. במקום להשתמש בסכום כל הגראדינטים בריבוע שחושבו עד זמן t, עורכים ממוצע משוקלל המעניק משקל גדול יותר ל-Gradient האחרון שחושב, ז”א 0.5 > . ב-Adadelta אין צורך לקבוע פרמטר מראש משום שבמקומו ניצב ערך המשתנה בהתאם ל-, זהו יתרון מאוד גדול משום שזה מקטין את טווח הטעות, במיוחד בבניית מודלים Deep Learning המכילים שכבות שונות עם התפלגויות משתנות והמון פרמטרים.

Adadelta Algorithm:

RMSProp .6 – כמו Adadelta גם אלגוריתם זה פותח במטרה לפתור את בעיית Adagrad. פיתוחו נעשה במקביל ל-Adadelta בצורה בלתי תלויה, וזאת ככל הנראה בשל אותו צורך בפתרון. שיטה זו מתגברת על בעיית ההתכנסות המהירה באמצעות חישוב ממוצע משוקלל של ה-Gradient בריבוע, והענקת משקל גדול יותר ל-Gradient האחרון שחושב, ז”א 0.5 > .

RMSProp Algorithm:

Adam .7 – אלגוריתם משולב, קומבינציה של Mometum ו-RMSProp, אשר גם מתאים שיעור למידה שונה לכל משתנה ומעדכן אותו לפי הקצב שלו. Adam גם מצליח להתגבר על בעיית ההתכנסות המהירה וגם מאפשר טיפול נכון בתנודתיות המתרחשת באזור המינימום המקומי בעזרת השימוש ב-Momentum. בנוסף, בשלב השני לפני עדכון המשקולת, Adam מבצע Bias-correction עקב הטיה בסביבת 0 המתקבלת בזמן האיטרציות הראשונות עקב קבלת ממוצע נע התחלתי באזור ה-0. התיקון הוא עבור שלב האיטרציות הראשונות עד שהפרמטרים מתכנסים ל-0 ואין צורך עוד בתיקון. בזכות התיקון שמבוצע כאן, Adam מצליח ברוב המקרים לתת תוצאות טובות יותר מ- Adam .RNSProp הוא אחד מהאלגוריתמים החזקים והשימושיים ביותר בתחום בניית רשתות, עקב היכולת שלו להתאים את עצמו לדאטה ושמור על יציבות במהלך האימון.

Adam Algorithm:

Nadam .8 – אלגוריתם המשלב בין Adam לבין NAG. אלגוריתם זה מיושם במקרים בהם יש Gradient רועש או עקמומי. זהו שילוב של שתי שיטות מוצלחות בתחום, המסוגל לתת תוצאות טובות במקרים מסוימים.

Nadam Algorithm:

באיזה Optimizer משתמשים ומתי?

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

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

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

התכנסות למינימום מקומי ולנקודות אוכף. כאשר SGD מגיע למינימום מקומי, או נקודת אוכף הגרדיאנט שווה ל0 וSGD יעצר. במימד גבוה זו סיטואציה שכיחה, למעשה הרבה יותר ממינימום מקומי. מסיבה זו הבעיה העיקרית היא עם נקודות אוכף ופחות עם מינימום מקומי. בעיה זו נוצרת גם בסביבת נקודת האוכף, שבה גרדיאנט מאוד קטן, וזו בעיה גדולה.מקור
כיוון הגרדיאנט עלול לסבול מרעשים בעקבות העבודה עם 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 בעיות עיקריות:

האימון הראשוני של Adam לא יציב, בגלל שבתחילת האימון יש מעט נקודות לחישוב הממוצע עבור המומנט השני. צעדים גדולים מבוססים על מידע מועט ורועש יכולים לגרום להשתקעות בנקודת מינימום מקומית או אוכף. בעיה המשותפת לרוב אלגוריתמי אופטימיזציה.
המודל המתקבל לא מכליל בצורה טובה (נוטה ל 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

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

Apr

2019

למידה עמוקה על גרפים

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

נכתב על ידי Ori Cohen

מהם גרפים והיכן הם מופיעים

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

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

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

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

למידה עקיפה

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

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

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

למידה מתוך מבנה הגרף

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

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

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

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

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

קונבולוציות על גרפים Graph Convolutional Network

בשנת 2017 הוציאו שניים מהמוחות המבריקים ביותר בתחום למידת המכונה על גרפים, תומס קיפף ומקס וולינג, את אחד מהמאמרים בעלי ההשפעה הרחבה ביותר בתחום, Semi-Supervised Classification with Graph Convolutional Networks. במאמר זה הציגו לראשונה השניים את מה שהם כינו “רשתות קונבולוציה על גרפים”, רשתות שיכולות ללמוד תבניות בין קודקודים שונים באופן דומה לקונבולוציות על תמונות. השניים הציעו את המבנה הבא לשכבה אחת ברשת שלהם:

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

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

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

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

תוצאות

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

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

לקוח מ https://arxiv.org/pdf/1609.02907.pdf

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

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

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

קישורים

Nov

2018

ניתוח מתמטי לאלגוריתם PCA

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

נכתב על ידי Ori Cohen

הקדמה

“בתוך ערימות הנתונים האלה מוסתר ידע שיכול לשנות את חייו של מטופל, או שיכול לשנות את העולם”.

(Atul Butte, Stanford School of Medicine)

כתבה זו מתארת את העבודה שעשיתי עם נח גורני כעבודה אקדמאית.

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

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

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

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

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

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

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

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

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

מהו PCA

תהליך ה-PCA הוא מהתהליכים הפופולריים ביותר להורדת ממדים בנתונים.

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

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

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

למה זה מעניין אותנו?

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

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

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

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

ניתן לראות בבירור כי הן הדיוק והן הזמן שלוקח למודל להגיע לכל רמת דיוק משתפר משמעותית בעקבות תהליך ה-PCA.

מדוע PCA משפר ?

השאלה שבאמת מעניינת אותנו עכשיו היא למה זה קורה?

על מנת לענות על שאלה זו עלינו לחשוב על בעיית למידת מכונה כבעיית חיפוש.

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

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

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

ניסוח פורמלי של השיטה

הגדרה: משתנה מקרי הוא התאמה של ערך מספרי לאירועים אפשריים במרחב ההסתברות. פורמלית, משתנה מקרי $X$ מעל מרחב הסתברות $\Omega$ הוא פונקציה $X:\Omega \rightarrow \Re$ .

הגדרה: וקטור מקרי $X$ הוא וקטור $p$ -ממדי המקיים כי לכל $1\leq i\leq p$ : $X_i$ הוא משתנה מקרי.

הגדרה: מטריצת שונויות היא מטריצה $V$ מגודל $pxp$ בה:

$V_ij=cov(X_i,X_j )=E[X_i X_j ]-E[X_i ]E[X_j ]$

הגדרה: גורם עיקרי של וקטור מקרי $X$ הוא משתנה מקרי $({\alpha \in }\Re ^{p})z=\alpha \cdot x$ כך ש- $Var(z)$ מקסימלי תחת האילוץ $\left \| \alpha \right \|=1$ .

הערה: למרות שבדר”כ ניקח את הנורמה האוקלידית (כלומר, נדרוש כי $\alpha \cdot \alpha =1$ ), ניתן להחליף זאת בנורמות אחרות (נורמת מקסימום, נורמת סכום וכו’).

מסקנה: המקדמים $\alpha _k$ של הגורמים העיקריים $z_k$ ( $1\leq k\leq p$ ) הם הווקטורים העצמיים של מטריצת השונויות $V$ , המתאימים לערכים העצמיים $\lambda _k$ .

הגדרה: התפלגות D עם פרמטרים $(a_1,a_2,...)$ היא משפחת פונקציות המתאימות לכל מאורע מהצורה $X<c$

(X משתנה מקרי, c קבוע) סיכוי כלשהו לפי תבנית התלויה בפרמטרים הרלוונטיים, כלומר פונקציית ההתפלגות היא מהצורה:

$P(X<c|a_1,a_2...)$

סימון: אם המשתנה המקרי $X$ מתפלג לפי ההתפלגות עם הפרמטרים $(a_1,a_2,...)$ נסמן:

$X\sim D(a_1,a_2,...)$

הגדרה: סדרת התפלגויות $D$ עם הפרשים $(\triangle a_1,\triangle a_2,...)$ הינה אוסף של התפלגויות

$D_i=D_i(a_{1}^{i},a_{2}^{i},...), 1\leq i\leq N$

כך שמתקיים:

$a_{j}^{i}=a_{j}^{0}+(i-1)\Delta a_j$

כלומר, בכל שלב מוסיפים לכל פרמטר את ההפרש המתאים.

הגדרה: רכיב עיקרי יקרא מסדר $k$ אם הע”ע המתאים לו הינו ה- $k$ בגודלו.

סימון: את אוסף הרכיבים מסדר $k$ של סדרת ההתפלגויות $D=D(\Delta a_1,\Delta a_2,...)$ נסמן ע”י:

$PC_k(D)$

כעת, באופן פורמלי השיטה שלנו מורכבת מהשלבים הבאים:

נקבע את התפלגות בסיסית $D_0(a_1,a_2,...)$ . במקרה שלנו ההתפלגות הבסיסית הינה ההתפלגות הנורמלית הסטנדרטית $N(0,1)$
נקבע את ההפרשים $(\bigtriangleup a_1,\bigtriangleup a_2,...)$ . במקרה שלנו נרצה לשנות את סטיית התקן של ההתפלגות.
נייצר סדרת התפלגויות $\left \{ D_i \right \}_{i=1}^{N}$ כאשר מספר גדול מספיק. למעשה אנו משנים את ענן הנקודות אותם אנו דוגמים על מנת לראות את ההשפעה של הפרמטרים על התוצאות לאחר הפעלת תהליך ה-PCA.
עבור כל התפלגות $D_i$ נחשב את הגורמים העיקריים
נשרטט בדיאגרמת פיזור (scatter plot) את האוסף $\left \{ PC(D_i)) \right \}_{i=1}^{N}$ עבור הגורמים העיקריים הראשונים. אם נזכר בדוגמה של למידת המכונה, נשים לב כי הפיזורים הללו הם למעשה מרחב הקלטים האפשריים של מודל הלמידה שלנו.

תוצאות

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

כעת נבצע 100 חזרות של השלבים הבאים:

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

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

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

לדוגמה, כל נקודה בגרף הראשון מייצגת את אחד מהגורמים העיקריים הראשונים (כלומר, כל אחד מהם מתאים לערך העצמי הגדול ביותר שנובע מהתהליך ה-PCA עבור ההתפלגות ממנה הוא נוצר) ואנו יכולים לראות שבעוד השינוי שחוללנו בהתפלגות הווקטור המקרי שינתה את הערכים שמופיעים בקואורדינטות $y,z$ בטווח רחב ( $[-10,10]$ ) הערך בציר ה- $x$ כמעט ולא משתנה.

נשים לב לכמה דברים:

בשני הממדים הראשונים אנו יכולים לראות כי השינויים בתוצאות התהליך נמצאים אך ורק על מישורים, כלומר במונחים של בעיות חיפוש, חסכנו לעצמנו חיפוש במרחב תלת ממדי וכעת אנו צריכים לחפש אך ורק על מרחב דו-ממדי.
שני הממדים הראשונים מייצגים את רוב המידע שנמצא בנתונים, כאשר אנו מגיעים לרכיב השלישי הערכים שלו הם כבר בסדרי גודל של $10^{-2}$ , כלומר חסרי מידע מועיל על הנתונים המקוריים.

סיכום ומסקנות

אז מה אנו יכולים להסיק מכל זה?

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

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

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

https://www.intechopen.com/books/principal-component-analysis-engineering-applications

https://www.intechopen.com/books/principal-component-analysis-multidisciplinary-applications

Oct

2018

רשתות קונבולוציה על יריעות

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

נכתב על ידי Uri.itai

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

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

אבל מה קורה בבעיות בהן מרחב הנתונים אינו אוקלידי ?

מה לא אוקלידי ?

למשל בעולם המסחר אלקטרוני (e-commerce) ישנם נתוני רכישות, כל רכישה מכילה שדות שונים, כגון סכום הרכישה, מועד הרכישה, זהות הרוכש וכו’

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

מקרה נוסף הינו דגימות שנדגמו ממקור ידוע, למשל מכדור או ממשטח גיאומטרי עקום אחר:

תודה ל AugPi

ישנן עוד מגוון דוגמאות מעולמות תוכן נוספים כגון רשתות חברתיות, דגימות מסנסורי IOT וכו’

קצת מתמטיקה

כדי להתקדם נצטרך לדבר על שני מונחים מתמטיים:

המונח הראשון הוא יריעה גאומטרית.

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

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

המונח השני הוא עיקרון הדואליות של הקונבולוציה.

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

אז איך עושים קונבולוציה על יריעה ?

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

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

ז”א האם מתוך שמיעת התיפוף ניתן לשערך את צורתו הגיאומטרית ?

או אותו דבר לגבי פילים:

Can you hear the shape of an elephant?

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

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

לסיכום

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

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

1) לרשתות על יריעה לא אוקלידית:

Geometric deep learning: going beyond euclidean data

MM Bronstein, J Bruna, Y LeCun… – IEEE Signal …, 2017 – ieeexplore.ieee.org

2) לפלסיאן של גרף:

Godsil, C.; Royle, G. (2001). Algebraic Graph Theory, Graduate Texts in Mathematics. Springer-Verlag.

3) לפלס בלטרמי

Flanders, Harley (1989), Differential forms with applications to the physical sciences, Dover, ISBN 978-0-486-66169-8

Jun

2018

העמקה לרשת הקפסולות Dynamic Routing Between Capsules – תיאוריה

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

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

בכתבה זו מטרתי להסביר את התיאוריה שבמאמר “Dynamic Routing between Capsules”. למי שלא מכיר את ההקשר ממליץ לקרוא קודם את הרקע בכתבה הזו: “הרעיון מאחורי רשת הקפסולות” שמסבירה את המאמר המוקדם יותר של הינטון: “Transforming Auto-“encoders. (אם כי אפשר להבין גם הכול מכתבה זו בלבד)

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

תיאוריה

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

capsules demo

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

אז מהן בדיוק קפסולות ?

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

כל קפסולה מחזירה:

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

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

המשמעות של וקטורי הפרדיקציה הינם: מה לדעת קפסולה i יהיה המוצא של קפסולה j. אם נניח קפסולה i מומחית בזיהוי עיגולים ומזהה בהסתברות גבוהה עיגול בקורדינאטה (x3,y3) בתמונה, אז תנבא שקפסולה משכבה גבוהה ממנה שאחראית על זיהוי פנים תוציא כפלט פנים במיקום (x1,y1) .

כל קפסולה מקבלת:

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

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

מהו אלגוריתם Dynamic Routing

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

תיאור האלגוריתם בין שכבת קפסולות l לבין השכבה הבאה l+1 בעבור r איטרציות ניתוב (routing):

קלט: וקטורי הפרדיקציה של כל אחת מקפסולות i מהשכבה l לכל אחת מהקפסולות j בשכבה l+1: $\widehat{u}_{j|i}$

פלט: וקטור המוצא של כל קפסולה j משכבה l+1 : $v_{j}$

האלגוריתם:

בהתחלה אפס את כל מקדמי הצימוד $b_{i,j}$

בצע r איטרציות את שתי הפעולות הבאות: (שיקלול וקטור מוצא + עידכון משקלים)

1. $v_{j}=squash(\Sigma_{i}c_{ij}\widehat{u}_{j|i})$

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

$c_{i}=softmax(b_{i})=\frac{e^{b_{i}}}{\sum_{k}e^{^{b_{k}}}}$

2. עדכן את מקדמי הצימוד לפי מידת ההסכמה (המכפלה הסקלרית) בין וקטורי הפרדיקציה לוקטור התוצאה:

$b_{ij}=b_{ij}+\widehat{u}_{_j|i}\cdot v_{j}$

סוף!

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

“העמקה לרשת הקפסולות Dynamic Routing Between Capsules – פרקטיקה“

Jun

2018

העמקה לרשת הקפסולות Dynamic Routing Between Capsules – פרקטיקה

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

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

בכתבה זו מטרתי להסביר באופן מפורש ומספיק מפורט עד כדי שהקורא החרוץ יידע לממש בעצמו את המאמר “Dynamic Routing between Capsules”. למי שלא מכיר את ההקשר ממליץ לקרוא קודם את הרקע בכתבה הזו: “הרעיון מאחורי רשת הקפסולות” שמסבירה את המאמר המוקדם יותר של הינטון: “Transforming Auto-encoders. ואז את הכתבה הזו: “העמקה לרשת הקפסולות Dynamic Routing Between Capsules – תיאוריה” שמסבירה על התיאוריה שבמאמר.

פרקטיקה

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

נשים לב כי באופן כללי אלגוריתם Routing פועל בין כל שתי שכבות קפסולות סמוכות אך במימוש המוצע הוא פועל רק פעם אחת כי יש סה”כ 2 שכבות של קפסולות.

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

תודה ל Dynamic Routing between Capsules

הסבר על כל בלוק:

בלוק הכי שמאלי: הרשת מקבלת תמונה (של ספרה) בגודל 28×28
בלוק ReLU Conv1: שכבת קונבולוציה שהינה 256 פילטרים בגודל 9×9 ב stride=1 עם אקטיבציית Relu. לכן הטנזור במוצא בגודל 20x20x256.
בלוק PrimaryCaps: שכבת קונבולוציה שהינה 256 פילטרים בגודל 9×9 ב stride=2 עם אקטיבציית Squash (*). לכן הטנזור במוצא בגודל 6x6x256. אותו טנזור בגודל 6*6*256 אלמנטים מסודר כ 32 טנזורים בגודל 6x6x8. כל אחד מבין ה 32x6x6 וקטורים בגודל 8 כל אחד יסומן $u_{i}$
בלוק DigitCaps: שכבת Fully Connected שממומשת ע”י מטריצה W שהופכת כל אחד מה 6x6x32=1152 וקטורי $u_{i}$ לעשרה וקטורי (פרדיקציה) $\widehat{u}_{j|i}$ בגודל 16.

(*) – אקטיבציית squash הינה פעולה לא לינארית שהופכת וקטור Sj להפוך לוקטור Vj בגודל שבין 0 ל 1:

squash function

אם כך זו רשת CNN רגילה… איפה פה הקפסולות ?

“חבויות” פה שתי שכבות קפסולות:

האחת נקראת Primary Caps ומכילה 6*6*32=1152 קפסולות שכל אחת מחזירה וקטור $u_{i}$ ממימד 8 ובנוסף מחזירה 10 וקטורי פרדיקציה $\widehat{u}_{j|i}$ שהינם המוצא של בלוק DigitCaps. j=1..10, i=1..1152)).

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

השניה נקראת DigitCaps מכילה 10 קפסולות שכל אחת מחזירה וקטור $v_{j}$ ממימד 16 (מחושבים באמצעות אלגוריתם Routing). קפסולות אלו לא מחזירות וקטורי פרדיקציה כי אין שכבה שלישית במימוש זה. (התרשים לא מראה את ה dynamic routing על אף שהינו חלק מהרשת)

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

כל אחד מהוקטורים $v_{j}$ יש לסמן כ $v_{j}^{r}$ (עם מציין לאינדקס האיטרציה) כי למעשה וקטורי r+1 מחושבים על בסיס וקטורי r.

אז מה בדיוק מאמנים פה ? מהי פונקציית ה Loss ?

פונקציית ה Loss מורכבת ממרכיב ה Margin Loss ומרכיב ה Reconstruction Loss.

מרכיב ה Margin Loss מבוסס על עשרת וקטורי המוצא $v_{j}$ של שכבת הקפסולות השניה (DigitCaps) .

ה- Margin Loss הינו סכום עבור k=0..9 של:

capsule loss function

כאשר Tk=1 אם ורק אם התמונה שהוזנה מכילה ספרה k, והפרמטרים +-m הינם ספים 0.1\0.9 בהתאמה, ו λ=0.5. (ערכים מומלצים לפי המאמר).

משמעות Loss זה בפשטות הינו תתגמל אם Vk מצביעה על הספרה של התמונה שהוזנה ותעניש אם לא.

כמו כן ישנו את מרכיב ה Reconstrucion Loss לו נותנים משקל נמוך והוא למעשה הפרש הריבועים בין התמונה המקורית לבין תמונה משוחזרת.

התמונה המשוחזרת נבנית באמצעות Decoder המורכב משלושה שכבות Fully Connceted שמקבלות את מוצא ה DigitCaps.

מרכיב ה- Reconstruction Loss אינו חובה וכשהוסיפו אותו אכן שיפר תוצאות.

קצת על הקוד

בקישור זה למשל תוכלו למצוא מימוש מלא ב TensorFlow:

https://github.com/naturomics/CapsNet-Tensorflow

הדבר הייחודי ששווה להזכיר שב Dynamic Routing יש לולאה בה כל המשתנים הם חלק מהאימון (ז”א ה Back-Propogation מעדכן אותם) הוא די מבלבל ולא סטנדרטי.

כך למשל ניתן לממש לולאה של טנזורים: (בקישור המימוש קצת שונה)

def condition(input, counter):
return tf.less(counter, 100)

def loop_body(input, counter):
output = tf.add(input, tf.square(counter))
return output, tf.add(counter, 1)

with tf.name_scope(“compute_sum_of_squares”):
counter = tf.constant(1)
sum_of_squares = tf.constant(0)
result = tf.while_loop(condition, loop_body, [sum_of_squares, counter])

with tf.Session() as sess:
print(sess.run(result))

זהו להפעם… אשמח לשאלות ודיונים בנושא!

Jun

2018

רשת הInception הקיצונית: Xception

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

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

רקע

רשתות Inception v4 ו Xception הינן מהרשתות הטובות ביותר כיום בזיהוי מה רואים בתמונה.

ב 2014 גוגל ניצחה בתחרות ILSVRC עם רשת GoogLeNet שהראתה לקהילה ארכיטקטורה חדשנית בשם Inception לפיה שכבות לאו דווקא חייבות להיות בטור אלא במקביל ואת תוצאותיהן משרשרים. השיטה הזו חסכה בזיכרון והביאה לביצועים הטובים ביותר דאז. מאז יצאו גירסאות נוספות שנקראות inception v2, v3, v4 או Inception-Resnet שמשלבת את הרעיון הזה של גוגל עם רעיון המעקפים של מיקרוסופט של רשת Resnet.

כל רשתות CNN=Convolution Neural Network מכילות פעולות קונבולוציה. ב 2016 יצאה רשת Xception שחידשה את פעולת הקונבולוציה ע”י כך שהיקצינה את מודל ה Inception.

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

הרשת Xception (extreme inception) מקצינה את הרעיון הזה באמצעות פעולה שנקראת depthwise separable convolution.

כותב המאמר Xception הינו François Chollet שגם ידוע כיוצר של Keras!

טכני

בקונבולוציה רגילה, בעבור טנזור בגודל 6x6x3 נצטרך kernel בגודל nxnx3. נניח n=2 אז קובית ה kernel בגודל 2x2x3 נעה בכיוון x,y בלבד על פני הקוביה הגדולה של ה 6x6x3 ובכל מעבר סוכמים את המכפלות. מימדי העומק של הטנזור ושל הגרעין שניהם שווים (לשלוש בדוגמא זו) ולכן הקוביה הקטנה לא נעה בכיוון z.

בקונבולוציה רגילה מימד העומק של הטנזור והגרעין זהים

בפעולת ה depthwise separable convolution לעומת זאת, יש שני שלבים, באחת הקוביה הקטנה נעה בכיוונים x,y ובשניה קוביה קטנה (אחרת) נעה בכיוון z.

ישנן גירסאות מימוש שונות, לפי המימוש המקובל (למשל ב Tensorflow) קודם מבצעים קונבולוציות מרחביות לכל ערוץ בנפרד (ז”א ה-kernel בגודל nxnx1) ואז מבצעים קונבולוציה למימד הערוץ ז”א מימד עומק (ה-kernel בגודל 1x1xc)

למשל, שורות הקוד הבאות מדגימות טנזור בגודל 6x6x3 שעובר separable conv עם פילטר מרחבי בגודל 3×3 ומכפיל את הערוצים פי 2 ועם פילטר “עומקי” שמגדיל 6 ערוצים ל 12 ערוצים:

x = tf.placeholder(tf.float32, [None, 6, 6, 3])
depthwise_filter = tf.get_variable(‘depthwise_filter’, shape=[3, 3, 3, 2])
pointwise_filter = tf.get_variable(‘pointwise_filter’, shape=[1, 1, 6, 12])
y = tf.nn.separable_conv2d(x,depthwise_filter, pointwise_filter, strides=[1, 1, 1, 1], padding=‘SAME’)

והתוצאה הינה טנזור בגודל:

?x6x6x12

(? מייצג את גודל ה batch)

ארכיטקטורת Xception כפי במוצגת במאמר כוללת שלושה מרכיבים: middle, entry, exit הכוללים בעיקר פעולות Seperable Conv, ReLu, MaxPooling:

תודה ל Xception

תוצאות

באותו מאמר הם מציגים ביצועים על מאגר ImageNet (מאגר של עשרות מיליוני תמונות עם אלף מחלקות).

תודה ל xception

ותוצאות על FastEval14K (מאגר של 14,000 תמונות עם 6,000 מחלקות) כאשר הרשת אומנה על JFT (מאגר פנימי של גוגל של 350 מיליון תמונות עם 17,000 מחלקות):

תודה ל xception

כמו כן הרשת MobileNet (רשת קלה וקומפקטית שרצה על מובייל) מבוססת על Xception.

קישורים

מימוש Xception ב Tensorflow:

https://github.com/kwotsin/TensorFlow-Xception

מימוש Xception ב Keras:

https://github.com/keras-team/keras/blob/master/keras/applications/xception.py

Attention בעולם הביולוגי

Attention בעולם ה AI

אז איך זה עובד?

דוגמא פרקטית – מכונת תרגום (Machine Translation)

מנגנון ה Scaled Dot-Product Attention ב Transformers

Dimensionality Reduction

Autoencoders (AE)

Variational AutoEncoders (VAE)

רקע קצר על למידה באמצעות חיזוקים (Reinforcement Learning)

פורמליזם מתמטי לתיאור הבעיה

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

אז מה עושים בכל זאת ?

פירוש לתוצאה:

צעד אחרון לפני מימוש

מקורות

מהי אופטימיזציה ולמה היא משמשת?

מה הרעיון הכללי ב-GD?

להלן האלגוריתמים הנפוצים והשמישים ביותר מתוך: Gradient Descent Optimizers Algorithms

באיזה Optimizer משתמשים ומתי?

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

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

Gradient Descent

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

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

AdaGrad

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

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

RMSProp

Adam

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

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

LookAhead

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

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

חומר נוסף:

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

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

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

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

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

סיכום

קישורים:

מהם גרפים והיכן הם מופיעים

למידה עקיפה

למידה מתוך מבנה הגרף

קונבולוציות על גרפים Graph Convolutional Network

תוצאות

קישורים

הקדמה

מהו PCA

למה זה מעניין אותנו?

מדוע PCA משפר ?

ניסוח פורמלי של השיטה

תוצאות

סיכום ומסקנות

מה לא אוקלידי ?

קצת מתמטיקה

אז איך עושים קונבולוציה על יריעה ?

לסיכום

תיאוריה

אז מהן בדיוק קפסולות ?

כל קפסולה מקבלת:

מהו אלגוריתם Dynamic Routing

פרקטיקה

הסבר על כל בלוק:

אם כך זו רשת CNN רגילה… איפה פה הקפסולות ?

אז מה בדיוק מאמנים פה ? מהי פונקציית ה Loss ?

קצת על הקוד

רקע

טכני

תוצאות

קישורים