הבנת שיפוע ממוצע סטוכסטי

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

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

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

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

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

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

ירידה בשיפוע רגיל

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

משוואת עדכון המשקל נראית כך:

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

ירידה בשיפוע סטוכסטי (SGD)

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

שיפוע ממוצע סטוכסטי

גישת ה-Stochastic Average Gradient (SAG) הוצגה כאמצעי ביניים בין GD ל-SGD. הוא בוחר נקודת נתונים אקראית ומעדכן את ערכה בהתבסס על השיפוע באותה נקודה וממוצע משוקלל של מעברי העבר המאוחסנים עבור אותה נקודת נתונים מסוימת.

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

קצב התכנסות

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

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

שינויים נוספים

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

• שקלול מחדש באיטרציות מוקדמות: התכנסות SAG נשארת איטית במהלך האיטרציות הראשונות מכיוון שהאלגוריתם מנרמל את הכיוון עם n (מספר כולל של נקודות נתונים). זה מספק אומדן לא מדויק מכיוון שהאלגוריתם עדיין לא ראה נקודות נתונים רבות. השינוי מציע לנרמל על ידי m במקום n, כאשר m הוא מספר נקודות הנתונים שנראו לפחות פעם אחת עד לאיטרציה המסוימת הזו.
• מיני אצוות: גישת ה-Stochastic Gradient משתמשת במיני-אצות לעיבוד נקודות נתונים מרובות בו-זמנית. ניתן ליישם את אותה גישה על SAG. זה מאפשר וקטוריזציה והקבילה לשיפור יעילות המחשב. זה גם מפחית את עומס הזיכרון, אתגר בולט עבור אלגוריתם SAG.
• ניסוי שלב-גודל: גודל הצעד שהוזכר קודם לכן (116L) מספק תוצאות מדהימות, אך המחברים ערכו ניסויים נוספים באמצעות גודל הצעד של 1L. האחרון סיפק התכנסות טובה עוד יותר. עם זאת, המחברים לא הצליחו להציג ניתוח רשמי של התוצאות המשופרות. הם מסיקים שיש להתנסות בגודל הצעד כדי למצוא את האופטימלי עבור הבעיה הספציפית.

מחשבות אחרונות

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

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

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