מה זה AdaGrad, ולמה נוצר: "קצב-למידה אחד לכולם" לא מספיק
ירידת-גרדיאנט הבסיסית וגרסתה הסטוכסטית (SGD) משתמשות בקצב-למידה יחיד וקבוע לכל הפרמטרים ברשת גם יחד — אותו η בדיוק לכל משקל, בלי קשר למידת-התדירות שבה כל פרמטר מתעדכן בפועל. AdaGrad, שהציגו ג'ון דוצ'י, אלעד חזן ויורם זינגר ב-2011, היה הראשון לשבור את ההנחה הזו: הוא מתאים לכל פרמטר בנפרד קצב-למידה משלו, לפי היסטוריית-הגרדיאנטים שהצטברה עבורו. המחברים תיארו את הרעיון כמציאת "מחטים בערמות-שחת בדמות תכונות חזויות-מאוד אך נדירות" — פרמטרים שמתעדכנים לעיתים רחוקות אך כשהם כן מתעדכנים זה משמעותי, ולכן ראוי שיקבלו קצב-למידה גבוה יותר מפרמטרים שמתעדכנים תדיר.
הנוסחה: מטריצה אלכסונית שצוברת ריבועי-גרדיאנטים
מבחינה טכנית, AdaGrad שומר לכל פרמטר סכום מצטבר של ריבועי-הגרדיאנטים שהתקבלו עבורו מתחילת האימון — במאמר המקורי זו האלכסון של מטריצה Gt, שמייצגת את סכום ריבועי-הגרדיאנטים ההיסטוריים לכל פרמטר בנפרד. עדכון-המשקל מחלק את קצב-הלמידה הבסיסי בשורש-הריבועי של הסכום הזה, פלוס איבר-החלקה זעיר שמונע חלוקה באפס. התוצאה: פרמטר שצבר גרדיאנטים גדולים בעבר מקבל קצב-למידה נמוך יותר קדימה, ופרמטר שכמעט לא התעדכן מקבל קצב-למידה גבוה יותר. אחד היתרונות המרכזיים של הגישה: היא כמעט מבטלת את הצורך לכוונן ידנית את קצב-הלמידה — רוב המימושים מסתפקים בערך ברירת-מחדל קבוע של 0.01.
מי כתב את AdaGrad, ומתי — מ-COLT 2010 ל-JMLR 2011
האלגוריתם פורסם במלואו במאמר "Adaptive Subgradient Methods for Online Learning and Stochastic Optimization", מאת ג'ון דוצ'י מאוניברסיטת קליפורניה בברקלי, אלעד חזן מהטכניון (כיום פרופסור בפרינסטון), ויורם זינגר מגוגל, בכתב-העת Journal of Machine Learning Research, כרך 12, עמודים 2121–2159, שהתקבל לפרסום ביולי 2011. גרסה מוקדמת יותר של אותה עבודה הוצגה כבר בכנס COLT 2010. חזן, שממשיך לחקור אופטימיזציה עד היום, נחשב לאחד השמות המוכרים בתחום המחקר הישראלי בתורת-האופטימיזציה המקוונת.
שימושים מוקדמים: זיהוי חתולים ביוטיוב ו-GloVe
עוד לפני עידן הלמידה-העמוקה הנוכחי, AdaGrad כבר הוכיח את עצמו בשני שימושים מוכרים: צוות-מחקר של גוגל בראשות ג'ף דין השתמש בו לאימון רשתות-נוירונים בקנה-מידה גדול — כולל הניסוי המפורסם שבו רשת למדה לזהות חתולים בסרטוני יוטיוב בלי פיקוח אנושי — ומצא שהוא משפר משמעותית את היציבות של SGD הרגילה. בנפרד, ג'פרי פנינגטון ושותפיו השתמשו ב-AdaGrad לאימון הטמעות-המילים (word embeddings) של GloVe, בדיוק מהסיבה שהאלגוריתם נועד לה: מילים נדירות זקוקות לעדכונים גדולים בהרבה ממילים נפוצות, וזה בדיוק מה ש-AdaGrad מספק באופן טבעי.
המגבלה שהובילה ל-RMSProp: קצב-הלמידה דועך לאפס
החולשה המרכזית של AdaGrad נובעת ישירות מהמנגנון שמייחד אותו: מכיוון שכל איבר שנוסף לסכום המצטבר הוא חיובי, הסכום רק גדל לאורך כל האימון ואף פעם לא קטן. באימונים ממושכים, במיוחד אימוני-למידה-עמוקה שאורכים מיליוני צעדים, הסכום הזה הופך גדול מאוד, קצב-הלמידה האפקטיבי מתכווץ בהתאם, ובשלב מסוים הוא הופך זעיר מכדי שהאלגוריתם ימשיך ללמוד דבר. בדיוק את הפגם הזה באו לתקן RMSProp ו-Adadelta — ששניהם פותחו במקביל וללא-תלות זה בזה סביב 2012, ומחליפים את הצבירה הבלתי-מוגבלת בממוצע-נע דועך שמאפשר לגרדיאנטים ישנים "להישכח" בהדרגה.
AdaGrad כמרכיב-היסוד ב-Adam, ושימושו היום
הרעיון המרכזי של AdaGrad — קצב-למידה נפרד לכל פרמטר לפי היסטוריית-הגרדיאנטים שלו — הוא נקודת-המוצא לכל שרשרת האלגוריתמים האדפטיביים שבאה אחריו: RMSProp שיפר אותו ב-2012, וב-2014 קינגמה ובא שילבו את הגרסה המתוקנת הזו יחד עם מומנטום כדי ליצור את Adam, אלגוריתם-האופטימיזציה הנפוץ ביותר כיום. AdaGrad עצמו עדיין בשימוש במקומות שבהם הבעיה המקורית שלו — תכונות דלילות (sparse) שמתעדכנות לעיתים רחוקות — עדיין קיימת, כמו הטמעות-מילים או מודלי-המלצה עם מיליוני תכונות נדירות, אך ברוב אימוני-הלמידה-העמוקה הכלליים הוא הוחלף מזמן ב-RMSProp, ב-Adam או ב-AdamW.