Gradient descent

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

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

הערות שוליים

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

31888328Gradient descent