Gradient descent

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

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

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

מבוא אינטואיטיבי

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

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

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

תיאור מתמטי

Gradient descent מבוססת על ההבחנה שאם פונקציה מרובת משתנים $F(\mathbf {x} )$ מוגדרת ודיפרנציאבילית בסמוך לנקודה $\mathbf {a}$, אז $F(\mathbf {x} )$ יורדת בצורה התלולה ביותר כשהולכים מ $\mathbf {a}$ בכיוון נגדי לגרדיאנט של $F$ ב-$\mathbf {a}$, $-\nabla F(\mathbf {a} )$. מכאן שאם

$\mathbf {a} _{n+1}=\mathbf {a} _{n}-\gamma \nabla F(\mathbf {a} _{n})$

עבור $\gamma$ קטן דיו, אז $F(\mathbf {a_{n}} )\geq F(\mathbf {a_{n+1}} )$. במילים אחרות, הביטוי $\gamma \nabla F(\mathbf {a} )$ מוחסר מ-$\mathbf {a}$ כיוון שרוצים לזוז נגד כיוון הגרדיאנט, מטה לכיוון המינימום. בהתבסס על הבחנה זו, ניתן לנחש נקודה ראשונית $\mathbf {x} _{0}$ כנקודת מינימום של $F$, ולקבל את הסדרה $\mathbf {x} _{0},\mathbf {x} _{1},\mathbf {x} _{2},\dots$ כך ש:

$\mathbf {x} _{n+1}=\mathbf {x} _{n}-\gamma _{n}\nabla F(\mathbf {x} _{n}),\ n\geq 0.$

שבהתבסס על ההבחנה:

$F(\mathbf {x} _{0})\geq F(\mathbf {x} _{1})\geq F(\mathbf {x} _{2})\geq \cdots ,$

הסדרה $(\mathbf {x} _{n})$ יכולה להתכנס לנקודת המינימום המבוקשת. גודל הצעד $\gamma$ יכול להשתנות בכל איטרציה. יחד עם הנחות מסוימות על הפונקציה $F$ (לדוגמה, $F$ קמורה ו $\nabla F$ ליפשיצית) ובחירות מתאימות של $\gamma$ (למשל באמצעות line search שמקיים את תנאי וולף או שיטת ברזילאי-בורווין להלן),

$\gamma _{n}={\frac {(\mathbf {x} _{n}-\mathbf {x} _{n-1})^{T}[\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})]}{||\nabla F(\mathbf {x} _{n})-\nabla F(\mathbf {x} _{n-1})||^{2}}}$

מתכנסת הסדרה למינימום מקומי. כאשר הפונקציה $F$ היא קמורה, ניתן להשתמש ב-gradient descent למציאת פתרון גלובלי.

ב-1964 הציג בוריס תאודורוביץ' פוליאק הרחבה לשיטה שנקראת שיטת המומנטום אשר משפרת את קצב ההתכנסות. ב-1983 הציג יורי נסטרוב את שיטת הגרדיאנט המואץ (Nesterov’s Accelerated Gradient ולעיתים בקיצור NAG), שיכולה להשיג קצב התכנסות טוב יותר. גרסה נוספת של Gradient descent מבוססת על הערכה סטוכסטית של הגרדיאנט וידועה כ-Stochastic gradient descent.

אלגוריתם

להלן קוד פייתון של האלגוריתם gradient descent:

# x0 - initial guess
# df - gradient of function
def gradient_descent(x0, df):
	cur_x = x0 # The algorithm starts at x0
	gamma = 0.01 # step size multiplier
	precision = 0.00001
	previous_step_size = cur_x
	while previous_step_size > precision:
 		prev_x = cur_x
 		cur_x += -gamma * df(prev_x)
 		previous_step_size = abs(cur_x - prev_x)
	return cur_x

קישורים חיצוניים

מדיה וקבצים בנושא Gradient descent בוויקישיתוף