Gradient descent
Gradient descent (בתרגום מילולי: מורד הגרדיאנט) היא שיטת אופטימיזציה איטרטיבית מסדר ראשון למציאת מינימום מקומי של פונקציה. בשיטה זו, נעשה צעד נגדי לגרדיאנט ביחס לנקודה הנוכחית. לעומת זאת, אם נעשה צעדים בכיוון של הגרדיאנט נמצא את המקסימום המקומי של הפונקציה (אלגוריתם זה נקרא Gradient ascent, בתרגום מילולי: מעלה הגרדיאנט).
מבוא אינטואיטיבי
השיטה עובדת על שדה סקלרי של נתונים. שדה סקלרי הוא מרחב בו כל נקודה מורכבת מכמה מספרים המייצגים נתונים שונים. מרחב זה יכול להיות בעל מספר רב של ממדים כך שכל מימד מייצג קטגוריה של ערכים. דוגמה לשדה סקלרי בעל שלושה ממדים הוא מפה טופוגרפית בה יש אורך, רוחב וגובה. לפי השיטה משתמשים בגרדיאנט, שהוא כלי מתמטי וקטורי, כלומר בעל כיוון, המאפשר למצוא את הכיוון אליו הנגזרת מקסימלית דהיינו הכיוון בו נמצא השינוי הדרסטי ביותר בין הנתונים סביב נקודה מסוימת. במפה הטופוגרפית יהווה הגרדיאנט את הכיוון בו זווית המדרון מקסימלית, והאלגוריתם מוצא את הדרך האופטימלית להגיע למינימום בשדה הסקלרי, שהוא בהקבלה הנקודה הנמוכה ביותר במפה.
השיטה עובדת כך שבכל שלב של ההפעלה היא מתקדמת לכיוון הפוך לגרדיאנט (כיוון שהגרדיאנט מראה את השיפוע כלפי מעלה) כך שבכל שלב יש התקדמות נגד השיפוע המקסימלי עד שמגיעים לנקודה מספיק נמוכה המוגדרת בתנאי העצירה. דבר זה דומה לאדם העומד בנקודה על המפה הטופוגרפית אך ישנו ערפל סמיך אשר עוצר בעדו. לכן באפשרותו לבדוק רק בסביבה הקרובה לו היכן הזווית הכי תלולה של המדרון ודרכה הוא יורד.
תיאור מתמטי
Gradient descent מבוססת על ההבחנה שאם פונקציה מרובת משתנים מוגדרת ודיפרנציאבילית בסמוך לנקודה , אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\mathbf{x})} יורדת בצורה התלולה ביותר כשהולכים מ הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}} בכיוון נגדי לגרדיאנט של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} ב-הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}} , הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle -\nabla F(\mathbf{a})} . מכאן שאם
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{a}_{n+1} = \mathbf{a}_n-\gamma\nabla F(\mathbf{a}_n)}
עבור הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} קטן דיו, אז הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\mathbf{a_n})\geq F(\mathbf{a_{n+1}})} . במילים אחרות, הביטוי הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma\nabla F(\mathbf{a})} מוחסר מ- כיוון שרוצים לזוז נגד כיוון הגרדיאנט, מטה לכיוון המינימום. בהתבסס על הבחנה זו, ניתן לנחש נקודה ראשונית הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{x}_0} כנקודת מינימום של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} , ולקבל את הסדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{x}_0, \mathbf{x}_1, \mathbf{x}_2, \dots} כך ש:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbf{x}_{n+1}=\mathbf{x}_n-\gamma_n \nabla F(\mathbf{x}_n),\ n \ge 0.}
שבהתבסס על ההבחנה:
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F(\mathbf{x}_0)\ge F(\mathbf{x}_1)\ge F(\mathbf{x}_2)\ge \cdots,}
הסדרה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle (\mathbf{x}_n)} יכולה להתכנס לנקודת המינימום המבוקשת. גודל הצעד הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} יכול להשתנות בכל איטרציה. יחד עם הנחות מסוימות על הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} (לדוגמה, הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} קמורה ו ליפשיצית) ובחירות מתאימות של הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \gamma} (למשל באמצעות line search שמקיים את תנאי וולף או שיטת ברזילאי-בורווין להלן),
- הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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} }
מתכנסת הסדרה למינימום מקומי. כאשר הפונקציה הפענוח נכשל (SVG (אפשר להפעיל MathML בעזרת הרחבת דפדפן): תשובה בלתי־תקינה ("Math extension cannot connect to Restbase.") מהשרת "https://wikimedia.org/api/rest_v1/":): {\displaystyle F} היא קמורה, ניתן להשתמש ב-gradient descent למציאת פתרון גלובלי.
ב-1964 הציג בוריס תאודורוביץ' פוליאק הרחבה לשיטה שנקראת שיטת המומנטום אשר משפרת את קצב ההתכנסות.[1] ב-1983 הציג יורי נסטרוב את שיטת הגרדיאנט המואץ (Nesterov’s Accelerated Gradient ולעיתים בקיצור NAG), שיכולה להשיג קצב התכנסות טוב יותר.[2] גרסה נוספת של 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
קישורים חיצוניים
הערות שוליים
- ^ B. T. Polyak, “Some methods of speeding up the convergence of iteration methods”, Zh. Vychisl. Mat. Mat. Fiz., 4:5 (1964), 791–803; U.S.S.R. Comput. Math. Math. Phys., 4:5 (1964), 1–17, www.mathnet.ru
- ^ YU. E. NESTEROV, A method of solving a convex programming problem with convergence rate O(1/k^2), Soviet Mathematics Doklady, 27, 1983 (הקישור אינו פעיל, 2020-11-12) (אורכב 12.11.2020 בארכיון Wayback Machine)
31888328Gradient descent